hs-archive

자료구조 중 그래프에 대해 알아보자 얻어갈 지식 그래프 그래프 그래프란 노드와 노드를 연결하는 간선으로 표현되는 자료 구조이다. 종류는 크게 3가지이다. 무방향 그래프( undirected graphs ) 방향 그래프( directed graphs ) 가중치 그래프( weighted graphs ) 무방향 그래프( Undirected graphs ) 두 노드 사이의 간선은 방향을 나타내지 않고 양쪽 모두를 오갈 수 있다. 양방향 그래프( Directed graphs ) 두 노드 사이의 간선이 방향을 갖는다. 가중치 그래프 ( Weighted graphs ) 연결마다 가중치를 갖는다. 가중치의 의미는 시간, 거리, 크기 등이 될 수 있다. 일상생활에서 가장 흔히 볼 수 있는 가중치 그래프는 아래와 같은 ..

보호되어 있는 글입니다.

계수 정렬에 대해 알아보자. 얻어갈 지식 계수 정렬 이해 계수 정렬 계수 정렬은 배열의 인덱스에 숫자의 개수를 카운팅하는 방식으로 정렬한다. 예를 들어, a = [ 1, 1, 0 ]라는 배열이 있으면 배열 크기가 2이며 모든 요소가 0인 배열 b를 선언한 뒤 a의  첫 번째 요소가 1이므로 b[1] += 1 a의 두 번째 요소가 1이므로 다시 b[1] += 1 a의 마지막 요소가 0이므로 b[0] += 1 해당 과정이 끝나면 배열 b에 있는 0을 제외한 모든 요소를 순서대로 출력하면 된다. 정수(-, 0, +)와 문자가 들어있을 때 가능하며 실수가 들어있을 경우(3/2, 0.123 등) 계수 정렬이 어렵다. 코드로 작성 def count_sort(arr): count_arr = [0] * (max(..

퀵 정렬에 대해 알아보자. 얻어갈 지식 퀵 정렬 이해 퀵 정렬 병합 정렬과 마찬가지로 분할-정복 알고리즘이다. 대강의 순서는 아래와 같다. 값의 기준점이 될 기준 데이터(pivot)를 정한다. 기준 데이터(pivot)를 기준으로 작은 수는 왼쪽 큰 수는 오른쪽에 오도록 재배치한다. 그렇게 나뉜 두 개의 배열 속에서 또 기준점을 잡고 2번을 반복한다. 해당 과정을 더 이상 분할할 수 없을 때까지 반복한다. 조금 더 자세히 설명하면 피벗 값을 x, 왼쪽 끝 요소의 인덱스를 pl, 오른쪽 끝 요소의 인덱스를 pr이라고 할 때. pl은 인덱스 0부터 하나 씩 올라오며 x보다 큰 값을 찾고 반대로 pr은 오른쪽 끝 인덱스부터 x보다 작은 값을 찾는다. pl의 값이 pr보다 크지 않으면 서로의 값을 스왑하고 만약..

병합 정렬에 대해 알아보자 얻어갈 지식 병합 정렬 병합 정렬 퀵 정렬과 마찬가지로 분할-정복 알고리즘이다. 어레이 크기가 1이 될 때까지 반복적으로 분할하고 크기가 1이 되면 전체 어레이가 병합될 때 까지 병합한다. 스테이블한 정렬 알고리즘이며 버블 정렬, 선택 정렬, 삽입 정렬보다 빠르지만, O(N) 만큼의 추가 메모리 공간이 필요하다. 아래 사진과 영상을 보고 이해해보자. 병합 정렬 동영상 코드로 작성 def mergeSort(arr): if len(arr) > 1: mid = len(arr) // 2 L = arr[:mid] R = arr[mid:] mergeSort(L) mergeSort(R) i = j = k = 0 while i < len(L) and j < len(R): if L[i] < R..

삽입 정렬에 대해 알아보자. 얻어갈 지식 삽입 정렬 삽입 정렬 작은 데이터 셋에 효율적이다. 삽입 정렬은 간단한 정렬 알고리즘이다. 어레이는 정렬된 부분과 정렬되지 않은 부분으로 나뉜다. 정렬되지 않은 어레이의 값이 선택되고 정렬된 어레이의 올바른 위치에 배치된다. 삽입 정렬 예시 [ 12, 11, 13, 5, 6 ]이 있을 때 첫 번째 패스 0 번째 값과 1 번째 값 비교 12는 11보다 크므로 자리 바꿈 [ 11, 12, 13, 5, 6 ] 두 번째 패스 1 번째 값과 2 번째 값 비교 12는 13보다 작으므로 그대로 유지 [ 11, 12, 13, 5, 6 ] 세 번째 패스 2 번째 값과 3 번째 값 비교 13은 5보다 크므로 자리 스왑 12는 5보다 크므로 자리 스왑 11은 5보다 크므로 자리 스..

선택 정렬에 대해 알아보자 얻어갈 지식 선택 정렬 선택 정렬 정렬되지 않은 어레이에서 최소 수를 찾아 선두에 배치하여 정렬하는 방법이다. 버블 정렬이 인덱스 맨 뒤에서부터 정렬을 하는 것이라면 선택 정렬은 앞에서부터 정렬하는 방법이다. 선택 정렬 예시 [ 64, 25, 12, 22, 11 ]을 오름차순으로 정렬할 때 첫 번째 패스 min_idx 변수에 0을 넣는다. arr[min_idx]와 arr[1]를 비교하고 더 작은 수를 갖고있는 인덱스를 min_idx에 넣는다. arr[min_idx]와 arr[2]를 비교하고 더 작은 수를 갖고있는 인덱스를 min_idx에 넣는다. arr[min_idx]와 arr[3]를 비교하고 더 작은 수를 갖고있는 인덱스를 min_idx에 넣는다. arr[min_idx]와 ..

버블 정렬에 대해 알아보자. 얻어갈 지식 버블 정렬 버블 정렬 가장 간단한 정렬 알고리즘이다. 평균적으로 그리고 최악의 경우 시간 복잡성이 매우 높기 때문에 대규모 데이터 셋에는 적합하지 않다. 버블 정렬 예시 [ 5, 1, 4, 2, 8 ]로 되어있는 어레이가 있을 때 오름차순으로 정렬하면 아래와 같다. 첫 번째 패스 ( 가장 큰 수를 제일 마지막 자리로 옮기기 ) 5는 1보다 크므로 서로 자리를 바꾼다. [ 1, 5, 4, 2, 8 ] 5는 4보다 크므로 서로 자리를 바꾼다. [ 1, 4, 5, 2, 8 ] 5는 2보다 크므로 서로 자리를 바꾼다. [ 1, 4, 2, 5, 8 ] 5는 8보다 크지 않으므로 자리를 바꾸지 않는다. [ 1, 4, 2, 5, 8 ] 두 번째 패스 ( 두 번째로 큰 수를 뒤..