Heap(히프) Heap 은 root 가 최대값인 max-heap, 최소값인 min-heap이 있는데 다른 언급이 없으면 max-heap 을 의미합니다. heap은 아래에서 위로 순서를 가지고 있는 이진 트리이므로 모든 leaf-root path 를 따라 가는 순회는 오름차순으로 key 를 방문합니다. 이것은 어떠한 key도 부모보다 크지 않다고 말하는 것과 같습니다. 히프화 알고리즘은 2 * log n 번 이상의 비교를 하지 않습니다. 히프화 알고리즘은 특정 노드를 root로 하는 서브트리에 대해 heap 특성이 만족됩니다. 가장 하위 내부 노드 부터 시작하여 root 에 이르기까지 각각의 x 에 대한 이 연산을 반복함에 의해 전체 트리를 히프화할 수 있습니다. 이러한 과정을 히프 구축(Heap Bui..
비트마스크란 정수의 이진수 표현을 자료구조로 사용하는 기법입니다. 부호없는 N비트 정수형 변수는 N자리의 이진수로 사용할 수 있습니다. 이때 각 비트가 표현하는 값은 2^0 부터 2^k-1 까지입니다. 2^k-1 에 해당하는 비트를 최상위 비트(most significant bit)라고 부르고, 2^0를 나타내는 비트를 최하위 비트(least significant bit) 라고합니다. 어떤 정수를 이진수로 표현했을 때 어떤 비트의 위치가 1이라면 해당비트가 "켜져있다"라고 말하고, 0이라면 꺼져있다고 말합니다. 비트 관련 연산 정의 비트별 AND 연산(&) 두 정수에 해당 비트가 모두 켜져있을때만 결과의 비트를 켭니다. (같의 위치에 있는 두 비트가 전부 1인 경우 결과가 1이고 그 이외에는 0입니다.)..
여러 가지 데이터 타입 및 자료구조가 있지만, 알고리즘에 집중하기 위해 정수(int) 배열을 오름차순으로 정렬하는 형식으로 진행하겠습니다. 각각의 정렬 알고리즘은 특정 환경에 에서 최적의 성능을 발휘합니다. 메모리 공간을 적게 쓴다든지, 배열의 길이가 얼마 이하이면 제일 빠르다든지, 이미 정렬된 경우 제일 빠르다든지.... 참고로 알고리즘의 성능은 비교 횟수와 교환횟수, 추가로 사용하는 저장 공간, 초기 정렬 상태 등 에 따라 결정됩니다. swap 함수 Bubble Sort(버블 정렬) 가장 단순한 정렬 알고리즘입니다. 비교하는 과정이 탄산음료를 담은 컵에 두개의 거품(크기가 서로 다른)이 수면 위로 상승하는 과정과 비슷합니다. 두 거품이 상승중에 충돌 하였을 때 큰 거품이 작은 거품보다 먼저 상승하게 ..
알고리즘 문제 해결 전략 책에서 앞부분 개인적으로 요약 정리해 보았습니다. 접근 방법 무식하게 풀 수 있는지 확인합니다. (문제를 일단 푸는게 우선이고, 나중에 회고를 통해서 더 좋은 알고리즘을 찾습니다.) 문제를 수식화가 가능한지 확인합니다. 문제를 부분 문제로 여러개 나누어 계산이 가능한지 확인합니다. (예 : 팩토리얼) 문제에서 주어진 순서에서 반대로 풀수 있는지 계산이 가능한 문제인지 확인합니다. (예 : 사다리타기) 실수 줄이기 1. 일관된 표현방식 사용 반 열린 구간 을 사용하여 실수를 예방습니다. (열린구간, 닫힌구간 등은 사용을 자제합니다.) low