본문 바로가기

Theory/Algorithms

(35)

다이나믹 프로그래밍 (Dynamic Programming) 다이나믹 프로그래밍 (Dynamic Programming) 은 리차드 벨만 (Richard Bellman) 이 1953년에 고안한 알고리즘입니다. 우리 말로 "동적 계획법" 이지만 동적이라 함은 보통 프로그래밍에서 프로그램이 실행되는 도중에 필요한 메모리를 그때마다 할당하는 기법을 뜻하고 다이나믹 프로그래밍에서는 딱히 큰 의미는 없습니다. 다이나믹 프로그래밍은 문제를 각각의 작은 문제로 나누어 해결한 결과를 저장해두었다가 나중의 큰 문제의 결과와 합하여 풀이하는 방식입니다. 그럼 어느 경우에 다이나믹 프로그래밍을 주로 사용할까요? 문제가 최적 부분 구조 (Optimal Substructure) 를 가지고, 동일한 작은 문제를 반복적으로 해결해야 하는 경우 (중복되는 부분 문제) 에 적합합니다. 문제가 최..

이진 탐색 (binary search) 이진 탐색 (혹은 검색, binary search) 는 이미 정렬된 배열에서 타겟을 찾는 검색 알고리즘으로 시간 복잡도가 $O(log n)$이 소요되는 대표적인 로그 시간 알고리즘입니다. 술자리에서 0부터 100까지의 임의의 숫자를 생각해 놓고 업다운을 통해 숫자를 맞추는 게임이 있습니다. 이때, 하나씩 높여가는 것이 아니라 50 -> 25,75 -> 12,37,87 등 숫자 범위의 절반을 줄여가면서 탐색 범위를 점점 좁히게 되죠. 합병정렬처럼 매번 절반으로 쪼개니 $O(\log n)$의 시간 복잡도가 소요됩니다. 절반으로 탐색 범위를 좁혀 계산 횟수가 $\log$ 만큼 줄게 만드는 것은 시간 복잡도 측면에서 굉장히 강력한 성능을 띠게 됩니다. 100까지의 숫자는 7번, 1억까지의 숫자도 27번의 비교로..

그래프 (2) - 너비우선탐색 (BFS, Breadth First Search) 이번 포스트에서는 너비우선탐색 (BFS, Breadth First Search) 를 살펴보겠습니다. 스택이나 재귀로 구현하는 깊이우선탐색과 달리 너비우선탐색은 First-In First-Out (FIFO) 의 큐 자료구조를 사용해 구현하며, 다익스트라 알고리즘과 같은 최단 경로를 구하는 데 사용됩니다. 코드를 어떻게 구현하게 될까요? 선입선출의 큐를 이용하니 파이썬의 list나 collections 모듈의 deque를 이용할 수 있을 것 같습니다. 깊이우선탐색에서의 스택과 달리 큐는 배열의 첫 번째 원소가 추출되는 구조이니 해당 정점의 인접점들을 모두 방문하고 다음 레벨의 정점을 방문하게 됩니다. 깊이우선탐색과 같은 그래프 예로 코드를 한 번 살펴보겠습니다. graph = {1: [2,3,4], 2: [..

그래프 (1) - 깊이우선탐색 (DFS, Depth First Search) 정점 (vertex) 와 엣지 (edge) 로 구성된 그래프에서 그래프의 각 정점을 방문하는 그래프 순회에는 깊이우선탐색 (DFS, Depth First Search) 와 너비우선탐색 (BFS, Breadth First Search) 가 있습니다. 이번 포스트에서 살펴볼 그래프 순회 방법은 깊이우선탐색으로 19세기 프랑스의 수학자 찰스 피에르 트레모 (Charles Pierre Tremaux) 가 미로 찾기 문제를 풀다가 고안한 것으로 알려져 있습니다. 깊이우선탐색은 보통 1. 스택, 2. 재귀 로 구현할 수 있으며 코딩 테스트때 그래프 관련 단골 문제로 출제되는 만큼 굉장히 중요한 문제입니다. 먼저 다음 그림과 같은 그래프를 구성해 보겠습니다. 위 그래프에 대해서 각 정점 별 이웃을 담은 인접 리스트를..

안정 정렬 vs 불안정 정렬 KTX 역에서 도착역과 출발 시간으로 이루어진 다음과 같은 데이터가 있다고 가정해 봅시다. [(대구, 1400), (순천, 1500), (대구, 1430), (부산, 1300), (목포, 1400), (대구, 1500)] 지역명으로 오름차순으로 정렬한다고 했을 때, 다음과 같이 우리는 '대구->목포->부산->순천' 순으로 정렬하면서 대구의 중복된 데이터 3개는 시간 순서대로 그대로 유지되게 하고 싶겠죠. [(대구, 1400), (대구, 1430), (대구, 1500), (목포, 1400), (부산, 1300), (순천, 1500)] 하지만 정렬 방법마다 이렇게 중복된 원소가 본래 순서대로 정렬될 수도 있고 정렬되지 않고 섞일 수도 있습니다. 이번 포스트에서 살펴볼 내용은 안정정렬과 불안정정렬입니다. 안정..

병합 정렬 / 합병 정렬 (Merge Sort) "분할하여 정복한다" 흔히 "Divide and Conquer"라 알려져 있는 격언은 실제 정치에서 뿐만 아니라 알고리즘에서도 자주 사용하는 norm 입니다. 전체를 한 번에 다 아우르지 않고 다룰 수 있는 작은 부분으로 쪼개면 일이 훨씬 수월해지는 것은 당연한 이치입니다. 이번 포스트에서 다룰 병합 정렬은 퀵 정렬과 더불어 정렬 알고리즘 중 대표적인 "분할 정복" 알고리즘입니다. 역사상 최고의 천재 중 손꼽히는 존 폰 노이만 (John Von Neumann) 이 무려 1945년에 고안한 알고리즘으로 최선/최악의 경우 일정하게 $O(n\log n)$의 시간 복잡도를 보장하는 알고리즘입니다. 한 번 예를 들어 살펴볼까요? EXAMPLE 병합정렬은 크게 2 가지 스텝으로 이루어져 있습니다. 1. 분할 (Di..

계수 정렬 (Counting Sort) 계수 정렬은 이름 그대로 배열의 원소를 각각 셈으로써 정렬하는 방식입니다. 데이터의 크기가 제한되어 있고 중복된 데이터가 많을 때 효과적인데요. 배열 [2,4,0,6,1,2,8,4,9] 예를 들어 한 번 살펴보겠습니다. EXAMPLE 계수정렬은 먼저 배열의 가장 작은 값과 큰 값이 모두 담길 수 있는 리스트를 생성합니다. 0 1 2 3 4 5 6 7 8 9 0 0 0 0 0 0 0 0 0 0 생성한 리스트에 데이터의 값과 동일한 인덱스의 값을 증가시킵니다. 0 1 2 3 4 5 6 7 8 9 1 1 2 0 2 0 1 0 1 1 그 다음에는 리스트의 첫 번째 데이터부터 하나씩 출력합니다. 파이썬 코드 def counting_sort(array): count = [0] * (max(array) - min(a..

퀵 정렬 (Quick Sort) 퀵 정렬은 토니 호어 (Tony Hoare) 가 1959년에 고안한 알고리즘으로 피벗 (pivot) 을 기준으로 좌우를 나누는 특징으로 인해 파티션 교환 정렬 (Partition-Exchange Sort)라고도 불립니다. 퀵정렬은 피벗을 기준으로 작은 값들은 왼쪽, 큰 값들은 오른쪽으로 계속 나누어 분할해가며 정렬하는데요, 빠르고 효율적으로 최선의 경우 $O(n\log n)$의 시간 복잡도를 가집니다. 그렇다면 맨 처음 단계에서 피벗을 어떻게 설정해야 할까요? 여러 인덱스가 피벗이 될 수 있지만 일반적으로 맨 왼쪽 혹은 맨 오른쪽 인덱스를 피벗으로 설정하게 됩니다. 배열 [2,8,7,1,3,5,6,4]에 대해 왼쪽, 오른쪽 피벗을 살펴보도록 하죠. 왼쪽 피벗 왼쪽 피벗의 경우 left 포인트, right..

이전 1 2 3 4 5 다음

티스토리툴바