[알고리즘] 병합 정렬 (Merge Sort)
병합 정렬이란 배열을 앞부분과 뒷부분 두 그룹으로 나누어 각각 정렬한 후, 다시 병합하는 작업을 반복하는 알고리즘입니다. 분할 정복(divide and conquer) 방법을 사용하여 문제를 해결합니다. 병합 정렬 예 [5, 3, 2, 1, 6, 8, 7, 4] #정렬하려는 배열 1. divide 1단계: [5] [3]을 병합하면 [3, 5] [2] [1]을 병합하면 [1, 2] [6] [8]을 병합하면 [6, 8] [7] [4]을 병합하면 [4, 7] 2단계: [3, 5] 과 [1, 2]을 병합하면 [1, 2, 3, 5] [6, 8] 와 [4, 7]을 병합하면 [4, 6, 7, 8] A : [1, 2, 3, 5] #정렬된 배열 B : [4, 6, 7, 8] #정렬된 배열 C : [] #정렬할 원소를 저..
2022. 5. 2.
[알고리즘] 삽입 정렬 (Insertion Sort)
삽입 정렬이란? 삽입 정렬은 전체에서 하나씩 올바른 위치에 "삽입" 하는 방식입니다. 필요할 때만 위치를 변경하므로 선택 정렬보다 더 효율적인 방식입니다. 키 순으로 정렬된 사람들이 일렬로 서 있는데, 다음 원소가 정렬된 사람들 사이를 비집고 들어가는 방식입니다. 선택 정렬 예 예) [4, 6, 2, 9, 1] 1단계 : [4, 6, 2, 9, 1] #4 2 이므로 위치 변경, 4 > 2 이므로 위치 변경을 합니다. [2, 4, 6, 9, 1] 3단계 : [2, 4, 6, 9, 1] #6 < 9 이므로 위치 변경을 하지 않습니다. [2, 4, 6, 9, 1] 4단계 : [2, 4, 6,..
2022. 4. 28.
[알고리즘] 선택 정렬(Selection Sort)
선택 정렬이란 선택해서 정렬하는 방식입니다. 예를 들면, 키 차이가 나는 사람들이 무작위 정렬해 있을 때 한번 쓱 훑어보고 키가 가장 작은 사람을 찾아 맨 앞으로 보냅니다. 그 다음 쓱 훑어봐서 두 번째로 작은 사람을 찾아 두번째에 배치합니다. 이 방법을 계속 반복하여 오름차순으로 정렬합니다. 선택 정렬 예 예) [4, 6, 2, 9, 1] 1단계 : [4, 6, 2, 9, 1] #제일 작은 수 1을 찾아 4와 교체 [1, 6, 2, 9, 4] 2단계 : [1, 6, 2, 9, 4] #1을 제외한 제일 작은 수 2를 찾아 6과 교체 [1, 2, 6, 9, 4] 3단계 : [1, 2, 6, 9, 4] #2를 제외한 제일 작은 수 4를 찾아 6과 교체 [1, 2, 4, 9, 6] 4단계 : [1, 2, 4,..
2022. 4. 27.
[알고리즘] 버블 정렬 (Bubble Sort)
버블 정렬이란 1번째와 2번째 값을 비교, 2번째와 3번째 값을 비교, ... , n-1번째와 n번째 값을 비교하여 자료를 정렬하는 방식, 제일 큰 값을 맨 뒤로 보내며 정렬한다. n-1번째 값 n번째 값 이면 둘의 위치를 변경합니다. 버블 정렬 예 예) [4, 6, 2, 9, 1] 1단계 : [4, 6, 2, 9, 1] #4와 6을 비교, 4 2 이므로 위치를 변경 [4, 2, 6, 9, 1] 3단계 : [4, 2, 6, 9, 1] #6과 9를 비교, 6 1 이므로 ..
2022. 4. 26.
[알고리즘] 공간 복잡도 (Space Complexity)
공간 복잡도란? 알고리즘이 문제를 완전히 해결하는데 필요한 메모리 크기입니다. 입력값이 2배로 커졌을 때 문제를 해결하는 데 메모리가 몇 배나 커지는지 확인해야 하며 메모리를 적게 사용하는 알고리즘이 좋은 알고리즘입니다. 최빈값 찾기 알고리즘의 공간 복잡도 판단해보기 1. alphabet_array의 길이 = 26 max_occurrence, max_alphabet, occurrence 변수 = 3 29만큼의 공간을 사용 # a~z까지, 26개의 공간을 사용 alphabet_array = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "x", "y", "..
2022. 4. 24.
