DP피보나치 수열로 재귀, DP 모두 비교해보기!1. 재귀함수자기 자신을 호출하는 함수로 반복적으로 호출을 함으로써 원하는 결과를 도출피보나치는 O(2^N) 시간복잡도 걸림public static int fibonacci_recur(int n) { //O(2^N) if (n 2. DP1) DP의 핵심최적 부분 구조'큰 문제의 최적해'가 '작은 문제의 최적해'를 포함하는 성질중복 부분 문제'동일한 작은 문제를 반복적으로 해결'해야 하는 성질💡 이 순서대로 해보자!1. DP 방식을 적용할 수 있는지 확인하기: 최적 부분 구조, 중복 부분 문제인지 따져보기2. 점화식 세우기 : 일반화 할 수 있는 수식 생각하기 2) DP의 종류💡 메모이제이션(Memoization)이란?‘중복 계산'을 피하기..

0. 그래프0.1 그래프정점(node 혹은 vertex)과 간선(edge)로 이루어지 자료구조정점: 데이터를 저장하는 위치간선: 정점을 연결하는 선인접 정점: 간선에 의해 직접 연결된 정점 (ex. 1과 2는 인접 정점)차수: 무방향 그래프에서 하나의 정점에 인접한 정점의 수ex. 1의 차수: 2와 50.2 그래프 구현 방법0.2.1 인접 행렬 (Adjacency Matrix)2차원 배열 이용matrix[ i ][ j ] == true 라면 i -> j로의 간선이 있음의미int 행렬의 경우 1 = true, 0 = false배열 구성 → 간선 정보 조회빠름 O(1)간선의 개수 무관하게 항상 n^2의 메모리 공간 차지인접한 노드를 찾기 위해 모든 노드 전부 순회해야함0.2.2 인접 리스트(Adjacency..

정렬 알고리즘 시간 복잡도Bubble Sort (버블 정렬)O(n^2)Selection Sort (선택 정렬)O(n^2)Insertion Sort (삽입 정렬)O(n^2)Quick Sort (퀵 정렬)평균 : O(nlogn) / 최악 : O(n^2)Merge Sort (병합 정렬)O(nlogn)Radix Sort (기수 정렬)O(kn) / k : 최대 데이터의 자릿수Arrays.sort()평균 : O(nlogn) / 최악 : O(n^2)Collections.sort()O(nlogn)1. 버블정렬1.1 개념순서대로 보면서 두 수를 비교해서 오른쪽 수가 왼쪽수보다 더 작으면 교화한번 작업 시 → 맨 마지막 자리에 가장 큰수가 가게 되는 원리즉, 마지막을 제외하고 n-1번 작업을 하면 정렬완료시간 복잡도 O(..

요즘 코프링에 관심이 좀 생겼는데 마침 모바일프로그래밍 수업도 듣게되었담 ^!^그래서 이참에 코틀린 문법을 쬠 정리 해보려구 한다 :)계속 추가해서 적을 예정임 1. 변수 선언Var읽기, 쓰기 가능Val읽기만 가능 (== 변경이 불가능!하다)Val(Var) 변수명: 타입아래는 코드예시이다Var i: Int = 10 Val j: Int = 10i = 20j = 20 //(x)에러 *Tip: 혹여나 나중에 변수를 바꾸면 안될 경우에는 Val 로 미리 선언하여 오류를 통해 방지할 수 이따! 2. ? null 기본적으로 코틀린은 Null을 허용하지않는다! (자바를 주언어로 하는 나에겐... 신세계....!!! ㄱ- 맨날 NPE땜에 스트레쓰받는... ㅋㅅㅋ)만약 Null을 허용하고싶다면 타입 옆에 ?를 붙이자!V..

알고리즘 문제를 풀다가 ArrayList로 풀어야 하다가도 리턴은 Array여서 바꿔야할 경우가 많았구, 특히 ArrayList는 Integer 이고, Array는 int 인 경우가 많아 이부분에 대해서 공부가 필요했다!1. ArrayList 두가지 방법1)ArrayList list = new ArrayList(Arrays.asList("aa","bb","cc")); 2)ArrayList list = new ArrayList();list.add("bb");list.add("aa");list.add("cc"); +) ArrayList 출력은 그냥 값을 넣으면 된다! 참고로 그냥 배열(Array)은 Arrays.toString(list)로해야한다는 사실! 2.ArrayList -> String[] 으로 ..