본문 바로가기
반응형

분류 전체보기

 (369)
그래프 (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..
삽입 정렬 (Insertion Sort) 삽입 정렬은 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 원소들과 비교하여 자신의 위치를 찾아가는 정렬방법입니다. for 문을 통해 배열의 원소를 순회하면서 해당 인덱스의 원소가 찾아갈 위치를 앞부분의 어디에 삽입할 것인가를 찾는 알고리즘인데요, 특이하게도 삽입 정렬은 배열의 두 번째 인덱스부터 루프를 시작합니다. 배열 [8,5,6,2,4] 예를 들어 살펴볼까요? Example 1. 첫 번째 스텝입니다. 두 번째 인덱스인 5부터 for 루프를 시작합니다. 두 번째 인덱스 기준에서는 앞선 인덱스가 첫 번째 인덱스밖에 없으니 첫 번째 원소인 8과 비교를 하고 8이 5보다 크니 둘의 위치를 바꿔줍니다. 2. 두 번째 스텝입니다. 세 번째 인덱스인 6을 기준으로 앞서 첫 번째 스텝에서 정렬되었던 배열에 ..
버블 정렬 (Bubble Sort) 버블 정렬은 정렬 알고리즘 중 가장 비효율적인 알고리즘입니다. 2008년 버락 오바마가 대통령 후보시 접견한 구글 CEO 에릭 슈미트가 "32비트 정수 100만 개를 정렬하는 가장 효율적인 방법은 무엇인가요?"라고 물었을 때, 변호사 출신인 오바마가 이런 대답을 했다고 합니다. "버블정렬은 잘못된 시작일 것 같습니다". 법학을 전공한 오바마조차 이런 말을 한 것은 다음 코드를 보면 매우 자명합니다. 파이썬 코드 from typing import List def bubble_sort(List: array) -> List: for i in range(1, len(array)): for j in range(0, len(array)-1): if array[j] > array[j+1]: array[j], arra..
반응형

티스토리툴바