Huilife

코테를 좀 풀다 보면 항상 ㅎㅇㅎㅇ 오늘도 또 왔슈 하고 나오는 조건들이 있다. 그 중 하나가 바로 int 범위 한정으로 숫자가 들어온다는 것이다. 가령, 문제에서 어떤 수 x가 들어온다고 하면서 x는 $-2^{31}$보다 크거나 같고 $2^{31}$보다 작다 라는 말이 붙을 때가 있는데, 이걸 말하는 것이다. 사실 그냥 이럴 경우 그래 input 받는 변수를 int로 해도 되겠구나 라고 int 타입 변수 선언하고 끝나면 된다. 그런데, 오늘은 max heap을 구현하다가 진짜로 INF를 숫자로 선언할 일이 있어서 약간 띠용했다. $-2^{31}$이나 $2^{31}$을 어떻게 선언해야 할까? 원시적인 방법부터 스마트해보이는 방법 순으로 살펴보자. 목차는 다음과 같다. 암기빵 먹기 조금 쌈빡한 암기빵 먹기..

알고리즘의 수행 시간을 분석하다 보면, 수 많은 점화식들이 쏟아지게 된다. 이를 풀기 위한 방법은 크게 3가지로 나눌 수 있다. 치환법 재귀 트리 방법 마스터 방법 이 포스트에서는 위의 세 가지를 가볍게 핵심만 훑고 지나가 보도록 하자. 추후 시간이 생긴다면 과연 언제 적절한 예시도 추가하도록 하겠다. 치환법 개념 점화식을 풀기 위한 치환법은 다음의 두 단계를 거친다. 해의 모양을 추측한다. 상수들의 값을 알아내기 위해 수학적 귀납법을 사용하고, 그 해가 제대로 동작함을 보인다. 단계 2에서 수학적 귀납법을 사용할 때, 더 작은 문제에 대하여 단계 1에서 추측한 해로 치환한다. 그렇기 때문에 이 방법의 이름이 치환법인 것이다. 재귀 트리 방법 개념 재귀 트리(recursion tree) 방법은 각 노드가..

Merge sort의 특징은 다음과 같다. 외부 정렬 방법이다. 분할 정복을 이용한다. Pseudo Code MERGE 결합 단계에서 정렬된 두 부분 수열을 병합하는 프로시저이다. MERGE(A, p, q, r) n1 = q - p + 1 n2 = r - q create L[1, ..., n1 + 1], R[1, ..., n2 + 1] for i = 1 to n1 L[i] = A[p + i - 1] for j = 1 to n2 R[j] = A[q + j] L[n1 + 1] = INF R[n2 + 1] = INF i = 1 j = 1 for k = p to r if L[i]

Priority Queue는 heap의 대중적인 응용 중 하나이다. Priority Queue에도 heap과 같이 max-priority-queue와 min-priority-queue 두 가지가 있다. 이 글에서는 max-heap을 기반으로 하여 max-priority-queue를 구현하는 프로시저에 대해 초점을 맞춘다. Priority Queue의 정의 Priority Queue는 key라는 값을 가진 원소들의 집합 S를 다루기 위한 자료구조이다. Priority Queue의 응용 Priority Queue는 다양하게 응용될 수 있다. max-priority-queue 공유 컴퓨터에서 작업 순서를 계획하는 것 min-priority-queue 사건 반응형 시뮬레이터 Priority Queue의 기본 프..

Quick Sort의 특징 내부 정렬을 이용한 방법이다. 분할 정복을 이용한다. 분할 배열 $A[p, ..., r]$ 을 두 개의 부분 배열 $A[p, ..., q-1]$ 과 $A[q+1, ..., r]$ 로 분할한다. 부분 배열 $A[p, ..., q-1]$ 에는 $A[q]$ 보다 작거나 같은 원소를, $A[q+1, ..., r]$ 에는 $A[q]$ 보다 크거나 같은 원소를 배치한다. 정복 quick sort를 재귀 호출해서 부분 배열 $A[p, ..., q-1]$ 과 $A[q+1, ..., r]$ 를 정렬한다. 결합 1, 2의 과정을 통해 부분 배열이 이미 정렬되어 있으므로 따로 합치는 작업이 필요하지 않다. quick sort는 기본적인 quick sort 방법과 랜덤화 기법을 사용하여 모든 입력에..

아마도 소프트웨어 혹은 컴과 전공생이라면 아직 찌들지 않은 푸릇한 1~2학년 시절 자료구조나 이산수학을 배우면서 행렬(배열)의 row-major, col-major를 눈 깜짝할 새 배우고 지나갔을 것이다. 그것이 어언 몇 년이 지나 지금이 되면.. 그게 뭔지는 대충 아는데 왜 배웠는지 기억이 나는 새럼 손 드세요. 손 드신 분들은 그대로 가슴에 손을 얹고 양심에게 여쭈어보시면 됩니다. 정녕 잘 기억이 나는가! 암튼 이번 포스트에서는 행렬(배열)의 row-major, col-major의 차이점과 중요성에 대해서 알아보도록 하자. row-major, column-major가 뭔데? 얘네들은 2차원 이상의 배열을 저장할 때 적용이 되는 것들이다. 어떤 배열을 2차원으로 한정하여 생각해 보자. 아무리 배열이 2..