본문 바로가기

Algorithm

[C] 우선순위 큐와 힙 (priority queue / heap), 힙 정렬 (Heapsort) 우선수위 큐(priority queue) 우선순위 큐는 평범한 큐나 스택과 비슷한 축약 자료형이다 단, 가장 먼저 혹은 나중에 입력된 자료가 가장 먼저 꺼내지는 것이 아니라, 우선순위가 가장 높은 자료가 가장 먼저 꺼내진다 이를 균형 잡힌 이진 검색 트리를 사용하면, (우선순위가) 최대인 원소를 찾아 삭제하는 일과 새 원소를 삽입하는 일 모두 O(logN) 시간에 할 수 있다 하지만 이보다 훨씬 단순한 구조로 구현할 수 있는데, 그 중 대표적인 것이 힙(heap)이라는 트리이다 힙(heap) 힙은 다음 규칙이 만족하도록 구성된 이진 트리이다 (이진 힙; binary heap) - 마지막 레벨(리프 노드)을 제외한 모든 레벡에 노드가 꽉 차 있어야 한다 - 마지막 레벨에 노드가 있을 때는 항상 가장 왼쪽부.. 더보기
[C] 트리 회전 회전하게 되는 경우에 대해서 먼저 정의를 해보자. 총 4가지 타입으로 나눌 수 있다. 새로 삽임된 노드 N으로부터 가장 가까우면서 균형 인수가 +-2가 된 조상 노드를 A라고 하자. LL 타입 : N이 A의 왼쪽 서브 트리의 왼쪽 서브 트리에 삽입된다. (Left Left) LR 타입 : N이 A의 왼쪽 서브 트리의 오른쪽 서브 트리에 삽입된다. (Left Right) RR 타입 : N이 A의 오른쪽 서브 트리의 오른쪽 서브 트리에 삽입된다. (Right Right) RL 타입 : N이 A의 오른쪽 서브 트리의 왼쪽 서브 트리에 삽입된다. (Right Left) LL과 RR은 대칭이고 역시 LR과 RL도 대칭이다. 이제 각 타입별로 알맞게 트리의 균형을 맞추자. 다음은 각각의 경우 대하여 균형 트리로 다.. 더보기
온라인 알고리즘 / 오프라인 알고리즘 모든 입력 값을 메모리에 저장하기에 부담스러운 경우가 많을 것이다 이럴 경우에는 모든 값을 메모리에 생성해 올려놓지 않고, 이 중 일부만을 사용하는 온라인 알고리즘(online algorithm)을 작성하면 된다 다시 말해, 입력을 차례로 받아들이면서 처리하는 알고리즘이다 예를 들어 삽입 정렬은 새 원소를 이전의 정렬된 목록에 끼워넣는 방식으로 동작하므로 온라인 알고리즘이라고 할 수 있다 (삽입 정렬 - snupi.tistory.com/15 ) 이와 반대로, 입력 전체를 가지고 시작해야만 동작하는 알고리즘을 오프라인 알고리즘이라고 한다 예를 들어 분할 정복을 이용하는 합병 정렬이나 퀵 정렬 등이 있겠다 (합병 정렬 - snupi.tistory.com/18 ) 더보기
[백준 11051번][C] 이항 계수 (동적계획법 ; DP) 이항 계수 설명에 앞서, 동적 계획법에 대한 설명은 다음 게시글을 참고하자 snupi.tistory.com/37 [C code] 동적 계획법 (DP ; Dynamic Programming) 동적 계획법이란 복잡한 문제를 부분적인 문제(subproblem)로 나누어 푸는 방법을 말한다 예를 들어, 1번 줄에서부터 10번 줄까지의 어떤 조건에 따라 계산을 하는데 2번 줄에서의 계산 방식과 7번 snupi.tistory.com 이항 계수 이항 계수란, n개의 물건에서 중복을 허락하지 않고 k개를 꺼내는 조합의 수를 말한다 원래의 방법대로라면, 로, factorial(int n)의 함수를 구현하여, 계산할 수 있다 하지만 n, k값이 조금만 커지더라도 이 값을 구하기 매우 어렵다 따라서 다음과 같은 성질을 이용.. 더보기
[Python] 유클리드 알고리즘 유클리드 알고리즘은 두 수의 최대공약수를 구하는 방법으로, 기록이 남아 있는 가장 오래된 알고리즘이다 이는 gcd(a, b) == gcd(a-b, b) 임을 이용한다 ( ∵ a, b의 공약수 g가 있다고 하자 a = a'g, b = b'g 이다 a-b = (a'-b')g 이므로 g는 a'-b', a-b, b의 공약수이다 ) 코드는 다음과 같다 def gcd(a, b): if(a < b): a, b = b, a if(q == 0): return p return gcd(a-b, b) 하지만 더 최적화할 수 있다 a의 값이 충분히 클 때, 이 알고리즘은 적어도 a/b 번의 재귀 호출을 거칠 것이다 이를 a-b 대신, a%b로 취한다면, 보다 더 깔끔하게 동작할 것이다 코드는 다음과 같다 def gcd(x, y.. 더보기

티스토리툴바