다락방

비트마스크(BitMask)집합의 요소들의 구성 여부를 표현할 때 유용한 테크닉이다.사용 이유DP나 순열 등, 배열 활용만으로 해결할 수 없는 문제를 해결하기 위해서.작은 메모리와 빠른 수행시간으로 해결이 가능하다.원소의 수가 많지 않아야 한다.집합을 배열의 인덱스로 표현할 수 있다.코드가 간결해진다.비트(Bit)란?컴퓨터에서 사용되는 데이터의 최소 단위비트 연산AND(&) : 대응하는 두 비트가 모두 1일 때, 1을 반환한다.OR(|) : 대응하는 두 비트 중 모두 1이거나 하나라도 1일 때, 1을 반환한다.XOR(^) : 대응하는 두 비트가 서로 다를 때, 1을 반환한다.NOT(~) : 비트 값을 반전하여 반환한다.SHIFT(>>,1. 삽입삽입의 경우 OR 연산을 활용한다.2. 삭제삭제의 경우 AND ..

이분 탐색(Binary Search)탐색 범위를 두 부분으로 분할하면서 찾는 방식과정우선 정렬을 해야한다.left와 right로 mid 값을 설정한다.mid와 내가 구하고자 하는 값과 비교한다구할 값이 mid보다 높으면 left = mid + 1, 구할 값이 mid보다 낮으면 right = mid - 1 로 설정한다left > right가 될 때까지 반복한다.

힙 정렬(Heap Sort)완전 이진 트리를 기본으로 하는 힙(Heap) 자료구조를 기반으로한 정렬 방식이다.불안정 정렬에 속한다.완전 이진 트리각 노드가 최대 2개의 자식 노드를 갖는 트리 형태의 자료구조이다.마지막 레벨을 제외한 모든 노드는 완전히 채워져 있어야 한다.과정최대 힙을 구성한다.현재 힙 루트는 가장 큰 값이 존재한다. 루트의 값을 마지막 요소와 바꾼 후, 힙의 사이즈 하나를 줄인다.힙의 사이즈가 1보다 크면 위 과정을 반복한다.유용한 경우가장 크거나 가장 작은 값을 구할 때최대 k만큼 떨어진 요소들을 정렬할

병합 정렬(Merge Sort)합병 정렬이라고도 부르며, 분할 정복 방법을 통해 구현된다.빠른 정렬로 분류되며, 퀵소트와 함께 많이 언급되는 정렬 방식이다.퀵소트와는 반대로 안정 정렬에 속한다.요소는 분리하고 다시 합병시키면서 정렬해나가는 방식으로, 분리하는 방식은 퀵정렬과 유사하다.Quick Sort : 피벗을 통해 정렬 → 분리Merge Sort : 분리되지 않을 때 까지 분리 → 정렬Merge Sort는 순차적인 비교로 정렬을 진행하므로, LinkedList의 정렬이 필요할 때 사용하면 효율적이다.시간복잡도O(nlogn)공간복잡도병합 정렬이 입력 배열에서 분할 및 정복 방식으로 작동하고 정렬된 후 하위 배열이 다시 병합되기 때문에 공간복잡도는 O(n)이다.장점병합 정렬은 동일한 값을 가진 요소의 상..

퀵 정렬(Quick Sort)분할 정복(divide and conquer) 방법을 통해 주어진 배열을 정렬한다.분할 정복문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.Quick Sort은 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. 또한 Merge Sort는 배열을 비균등하게 분할한다.과정배열 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗(pivot)이라고 한다.피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 배열을 둘로 나눈다. 이렇게 배열을 둘로 나누는 것을 분할(Divide) 이라고 한다. 분할을 마친 뒤에 피벗은 더 ..

삽입 정렬(Insertion Sort)손 안의 카드를 정렬하는 방법과 유사하다.Selection Sort와 유사하지만, 좀 더 효율적인 정렬 알고리즘이다.2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘이다.최선의 경우 O(N)이라는 엄청나게 빠른 효율성을 가지고 있어, 다른 정렬 알고리즘의 일부로 사용될 만큼 좋은 정렬 알고리즘이다.과정정렬은 2번째 위치(index)의 값을 temp에 저장한다.temp와 이전에 있는 원소들과 비교하며 삽입해나간다.‘1’번으로 돌아가 다음 위치(index)의 값을 temp에 저장하고, 반복한다.시간복잡도평균, 최악의 경우 O(n^2)최선의 경우 O(n)공간복잡도주어진 ..

선택 정렬(Selection Sort)해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘이다.배열에서 해당 자리를 선택하고 그 자리에 오는 값을 찾는 것이다.과정주어진 배열 중에 최소값을 찾는다.그 값을 맨 앞에 위치한 값과 교체한다.맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다.시간복잡도비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 배열을 정렬하는데 O(n^2) 만큼의 시간이 걸린다. 최선, 평균, 최악이 경우 시간복잡도는 O(n^2)으로 동일하다.공간복잡도주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n) 이다.장점알고리즘이 단순하다.정렬을 위한 비교 횟수는 많지만, Bubble Sort에 비해 실제로 교환하는 횟..

거품 정렬(Bubble Sort)서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘 이다.과정1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를,,, 이런 식으로 (마지막-1) 번째 원소와 마지막 원소를 비교하여 조건에 맞지 않는다면 서로 교환한다.1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 원소까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.시간복잡도O(n^2)정렬이 돼있던 안돼있던, 2개의 원소를 비교하기 때문에 최선, 평균, 최악의 경우 모두 시간 복잡도가 O(n^2)으로..

AVL Tree 자가균형 이진 탐색트리의 한 유형 각 노드의 서브트리 높이 차이가 최대 1을 유지하도록 스스로 균형을 유지하는 트리 이 서브트리의 높이 차이를 균형계수(BalanceFactor, BF)라 한다. 그렇기 때문에 삽입, 삭제 연산을 수행할 때마다 트리의 균형계수를 체크하고, 균형계수가 1보다 커질 때 회전(Rotation) 연산을 통해 균형을 유지한다. 검색, 삽입, 삭제 모두 O(logN) 하지만 삽입, 삭제시마다 회전연산을 수행하기에 연산속도가 느릴 수 있다. 회전연산의 종류 왼쪽 - 왼쪽 오른쪽 - 오른쪽 Single rotation 왼쪽 - 오른쪽 오른쪽 - 왼쪽 double rotation 특징 이진 검색 트리 모든 노드의 두 하위 트리의 높이는 최대 1까지 차이가 난다. 트리의 모..

최장 공통 부분수열(Longest Common Subsequence) 최장 공통 문자열Longest common substring 점화식 if i == 0 or j == 0: LCS[i][j] = 0 elif string_A[i] == string_B[j] LCS[i][j] = LCS[i-1][j-1] + 1 else: LCS[i][j] = 0 동작 문자열 A, 문자열 B의 한 글자씩 비교한다. 두 문자가 다르다면 LCS[i][j]에 0을 표시 두 문자가 같다면 LCS[i-1][j-1] 값을 찾아 + 1 위 과정을 반복한다. 이 과정이 성립하는 이유는 공통 문자열은 연속 되어야 하기 때문에 현재 두 문자가 같을 때 두 문자의 앞 글자 까지가 공통 문자열이라면 계속 공통 문자열이 이어질 것이고, 아니라면 ..