본문 바로가기

Information Technology/Algorithms

 (13)
[알고리즘] 힙(heap)의 응용: 우선순위 큐(priority queue) 이 글은 개인의 학습을 목적으로 정리한 글입니다. 이점 참고하고 읽어주세요;) 우선순위 큐 역시 힙과 같이 최대 우선순위 큐(maximum priority queue)와 최소 우선순위 큐(mininum priority queue)로 나눌 수 있습니다. 최대 우선순위 큐는 큐에 저장된 데이터들은 모두 우선순위를 가지고 있고, 이 우선순위가 최대한 데이터들이 큐를 먼저 나갈 수 있습니다. 큐에 데이터를 저장하는 INSERT(x) 연산에 대해서는 아무 데이터나 상관없지만, 큐를 빠져나가는 EXTRACT_MAX(x) 연산에 대해서는 함수의 이름에서 알 수 있듯이 우선순위가 MAX인 데이터만 이 연산을 진행할 수 있습니다. 우선순위 큐의 종류에는 FIFO 큐라는 종류의 큐도 존재합니다. FIFO 큐란 First ..
[JAVA] 합병정렬(merge sort) 이 글은 개인의 학습을 목적으로 정리한 글입니다. 이점 참고하고 읽어주세요;) merge sort는 분할 정복법(divide and conquer)이라는 방법을 사용하는 알고리즘입니다. 분할 정복법이란 예전에 로마 제국이 주변 나라들을 정복할 때, 통째로 정복하기보다는 분할을 해서 각각을 정했다는 것에서 착안한 이름이라고 합니다. 즉, 1) 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할해서 2) 각각의 작은 문제를 순환적으로 해결하고 3) 작은 문제의 해를 합하여(merge) 원래 문제의 해를 구하는 방법입니다. 여기서 핵임은 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할한다는 것인데, 이를 통해 합병정렬이 기본적으로 재귀(recursive)의 아이디어를 사용한다는 걸 알 수 있습니..
[JAVA] 기본적인 정렬 알고리즘 이 글은 개인의 학습을 목적으로 정리한 글입니다. 이점 참고하고 읽어주세요;) 프로그래밍에 있어 정렬(sort)은 정말 중요합니다. 데이터를 찾거나, 분류하거나, 추가하거나, 등등 대부분의 작업에서 정렬은 거의 필수로 가져가는 기능입니다. 이번 포스팅에서는 기본적인 정렬 알고리즘에 대해 알아보겠습니다. 가장 큰 값을 맨 끝에 위치한 데이터와 교체하는 게 selection sort의 기본적인 아이디어입니다. 가장 큰 값은 맨 끝자리에 오게 되고, 가장 큰 값은 다음 비교에서 제외합니다. selection sort는 모든 비교연산에 대해 n^2의 시간 복잡도를 가지게 됩니다. Bubble sort는 가장 큰 값을 맨 뒤에 위치시킨다는 점에서 Selection sort와 동일하지만, 가장 큰 값을 맨 뒤로 이..
[JAVA] 멱집합 {a, b, c, d, e, f}의 모든 부분집합 = (1) a를 포함하지 않는 {b, c, d, e, f}의 부분집합 + (2) a를 포함하는 {b, c, d, e, f}의 부분집합 (1)과 (2)의 크기는 사실 같습니다. 결국 (1)에서 구한 {b, c, d, e, f}의 부분집합에 a를 더한 것들이 (2)이기 때문입니다. 만약 (1)의 크기가 2^5이라면, (2)의 크기 역시 2^5입니다. 때문에 (1) + (2)는 2^5* 2 = 2^6입니다. 여기서 recursion을 발견할 수 있습니다. {b, c, d, e, f}에 대해서도 위의 과정에서 했던 것처럼 b를 포함하지 않는 부분집합과 b를 포함하는 부분집합을 더해줍니다. recursion을 통해 부분 집합들을 계속 return하면 많은 양의 데..
[JAVA] Recursion의 응용: N-Queens 이 글은 개인의 학습을 목적으로 정리한 글입니다. 이점 참고하고 읽어주세요 ;) 이번 포스팅에서 다룰 것은 N-queens라는 문제입니다. N-queens 문제는 아래의 그림과 같이 N * N개로 나뉜 공간에서 N개의 점들이 단 한 점도 동일 선상 위에 놓이지 않게 배열하는 문제입니다. 마치 체스에서 직선과 대각선 모두 이동할 수 있는 퀸에게 잡히지 않게 말들을 배열하는 것에서 그 이름을 따왔을 것이라고 생각합니다. 이 포스팅에서는 N-queens 문제를 상태 공간 트리에서 Backtracking을 통해 해결하는 방법에 대해 알아볼 것입니다. 우선 상태 공간 트리란 가능한 모든 경우의 수들을 노드를 통해 연결한 개념적 그래프를 의미합니다. 가능한 모든 경우의 수를 다루고 있기 때문에 우리가 찾는 해 역시..
[JAVA] Recursion 응용: Counting Cells in a Blob 이 글은 개인의 학습을 목적으로 정리한 글입니다. 이점 참고하고 읽어주세요;) 흑백으로 구성된 Binary 이미지에서, 서로 연결된 image pixel의 집합을 blob이라고 합니다. 이번 포스팅의 제목인 Counting cells in a blob은, Binary 이미지에서 임의의 한 점으로부터 그 점이 포함된 Blob의 크기를 구하는 작업을 의미합니다. Blob의 count를 계산하는 방법 역시 Recursion을 이용합니다. 위의 그림과 같이 하나의 좌표가 주어졌을 때, 그 픽셀을 둘러싸는 8개의 픽셀들을 대상으로 blob을 COUNT 하는 함수를 재귀 호출하고, count 한 cell에 대해서는 색을 바꿔 이후에 중복으로 count 되는 걸 방지합니다. public class CountCell ..
[JAVA] Recursion 응용: 미로찾기 이번 포스팅에서는 미로가 주어졌을 때 재귀(Recursion)를 통해 경로를 찾는 방법에 대해 알아보겠습니다. 현재 위치에서 출구까지 가는 경로가 있으려면 1) 현재 위치가 출구이거나 혹은 2) 이웃한 셀들 중 하나에서 현재 위치를 지나지 않고 출구까지 가는 경로가 있거나 위의 1번과 2번을 모두 적용해서 답을 찾아야 합니다. 이동할 위치의 셀이 통로에 속한 셀이면서 2번을 적용할 수 있을 때 Recursion 실행합니다. KEY. 이 Recursion이 무한루프에 빠지지는 않는지 확인해야 합니다! 때문에 Base case가 반드시 필요합니다. 이 문제 같은 경우는 한 칸 이동을 한 다음에 다시 자신이 왔던 것으로 돌아가며 무한 루프에 빠질 위험이 존재합니다. public class Maze { priv..
[JAVA] Recursion 설계 이번 포스팅에서는 이전 포스팅에서 다룬 Recursion 알고리즘을 설계하는 방법에 대해 알아보겠습니다. 순환적 알고리즘을 설계하는 조건 중 가장 중요한 것은 바로 적어도 하나의 base case, 즉 순환되지 않고 종료되는 case가 있어야 한다는 것입니다. 그리고 모든 case가 결국 base case로 수렴하여 무한 반복을 탈출할 수 있어야 합니다. 1. 순차 탐색 Sequential search public int search(int[] data, int n, int target){ for(int i=0; iend) return -1; else if(target == data[begin]) return begin; else return search(data, begin+1, end, target)..

티스토리툴바