글 작성 제목과 내용을 간결하게 정리해 주세요. 제목 내용 <h2>버블(Bubble)</h2><p>옆에 있는 값과 비교하여 더 작은 값을 반복적으로 앞으로 보내는 알고리즘</p><p>(앞에서 부터 큰 값을 뒤로 보내는 것과 같음)</p><p>구현이 가장 쉽지만 가장 비효율적인 알고리즘 : 매번 스왑을 해야하기 때문</p><p><strong>시간 복잡도</strong> : O(N^2)</p><p>코드</p><pre><code class="language-python"># 스왑 메소드 def swap(a, b): temp = a a = b b = temp return (a, b) # 정렬할 리스트 입력 list = list(map(int, input("버블 정렬할 숫자를 띄어쓰기로 구분하여 입력 : ").split(' '))) n = len(list) # 버블 정렬 for i in range(0, n): for j in range(1, n-i): if list[j-1] > list[j]: list[j - 1], list[j] = swap(list[j-1], list[j]) # 정렬된 리스트 출력 for i in list: print(i, end=' ') </code></pre><h2>선택 (Selection)</h2><p>가장 작은 것을 선택해서 제일 앞으로 보내는 알고리즘</p><p>가장 윈시적이고 기초적인 방법이며 비효율적임</p><p><strong>시간 복잡도</strong> : O(N^2)</p><p>코드</p><pre><code class="language-python"># 스왑 메소드 def swap(a, b): temp = a a = b b = temp return (a, b) # 정렬할 리스트 입력 list = list(map(int, input("선택 정렬할 숫자를 띄어쓰기로 구분하여 입력 : ").split(' '))) n = len(list) # 선택 정렬 index = 0 for i in range(0, n): min = 9999 for j in range(i, n): if min > list[j]: min = list[j] index = j list[i], list[index] = swap(list[i], list[index]) # 정렬된 리스트 출력 for i in list: print(i, end=' ') </code></pre><h2>삽입 (Insert)</h2><p>각 숫자를 적절한 위치에 삽입하는 알고리즘</p><p>(뒤로 가면서 앞의 숫자 크기를 보고 그 사이에 적절히 삽입)</p><p>선택, 버블 정렬에 비해 필요한 경우에만 위치를 바꿔 좀 더 효율적임</p><p>미리 어느정도 정렬이 되어 있다면 아주 빠르게 끝낼 수 있음</p><p><strong>시간 복잡도</strong> : O(N^2) (최악의 경우)</p><p>코드</p><pre><code class="language-python"># 스왑 메소드 def swap(a, b): temp = a a = b b = temp return (a, b) # 정렬할 리스트 입력 list = list(map(int, input("삽입 정렬할 숫자를 띄어쓰기로 구분하여 입력 : ").split(' '))) n = len(list) # 삽입 정렬 # while 문 for i in range(1, n): key = list[i] # key : 정렬할 원소 j = i - 1 while j >= 0 and list[j] > key: list[j+1] = list[j] j = j - 1 list[j+1] = key # for 문 '''for i in range(0, n-1): #for j in range(0, i+1): # print(list[j], end=' ') for j in range(0, i+1): if list[i-j] > list[i-j + 1]: list[i-j], list[i-j + 1] = swap(list[i-j], list[i-j + 1]) #print("")''' # 정렬된 리스트 출력 for i in list: print(i, end=' ') </code></pre><h2>퀵 (Quick)</h2><p>대표적인 '분할 정복' 알고리즘(Divide and conquer algorithm)으로, 특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나누는 것을 반복 하는 알고리즘.</p><h3>[방법]</h3><p>기준 값인 피벗(Pivot)이 필요 (보통 첫 번째 원소를 피벗으로 사용함)</p><p>기준 값보다 큰 값을 배열의 왼쪽부터, 작은 값을 오른쪽부터 찾음.</p><p>작은 값의 인덱스가 큰 값의 인덱스보다 크면, 작은 값과 큰 값을 교환.</p><p>작은 값의 인덱스가 큰 값의 인덱스보다 작으면, 피벗 값과 작은 값을 교환.</p><p>위 과정을 기준 값의 좌우측에 반복</p><p>시간 복잡도:</p><p>O(N * logN) (평균)</p><p>O(N^2) (최악)</p><p>-> 피벗값에 따라 최악의 경우가 생길 수 있음 [ex) 이미 정렬된 배열]</p><p>코드</p><pre><code class="language-python"># 스왑 메소드 def swap(a, b): temp = a a = b b = temp return (a, b) # 재귀를 이용하여 퀵 정렬 수행 def quickSort(start, end): if start>=end: # 원소가 1개인 경우 그대로 둠 return pivot = start # 피벗은 첫번째 원소 i = start + 1 j = end while i <= j: # 엇갈릴 때까지 반복 while(i <= end and list[i] <= list[pivot]): #끝에 도달하거나 피벗보다 큰 값을 찾을 때까지 반복 i = i + 1 while(j > start and list[j] >= list[pivot]): #피벗에 도달하거나 피벗보다 작은 값을 찾을 때까지 반복 j = j - 1 if(i > j): # 엇갈린 상태(작은 값의 인덱스가 큰 값의 인덱스보다 작으면, 피벗 값과 작은 값을 교환) list[pivot], list[j] = swap(list[pivot], list[j]) else: # 엇갈리지 않은 상태 (작은 값의 인덱스가 큰 값의 인덱스보다 크면, 작은 값과 큰 값을 교환) list[i], list[j] = swap(list[i], list[j]) quickSort(start, j - 1); # 피벗보다 작은 값들에 대해서도 새로운 피벗을 설정하여 퀵정렬 실행 quickSort(j + 1, end); # 피벗보다 큰 값들에 대해서도 새로운 피벗을 설정하여 퀵정렬 실행 # 정렬할 리스트 입력 list = list(map(int, input("퀵 정렬할 숫자를 띄어쓰기로 구분하여 입력 : ").split(' '))) n = len(list) # 퀵 정렬 quickSort(0, n-1) # 정렬된 리스트 출력 for i in list: print(i, end=' ') </code></pre><h2>병합 (Merge)</h2><p>퀵 정렬과 같은 분할 정복 알고리즘을 사용하는 정렬 알고리즘. 일단 반으로 나누고 나중에 정렬하는 방식</p><ul><li>퀵 정렬과 다르게 피벗 값에 상관없이 정확히 반을 나누어 정렬하므로 최악의 경우에도 O(N * logN)의 시간 복잡도를 보장.</li></ul><h3>[방법]</h3><p>다 쪼개진 원소들을 합치면서 정렬을 수행</p><p>합쳐진 배열은 정렬이 됨</p><p>최종적으로 합쳐지면 정렬이된 전체 배열을 얻음</p><p>시간 복잡도 : O(N * logN)</p><p>코드</p><pre><code class="language-python"># 스왑 메소드 def swap(a, b): temp = a a = b b = temp return (a, b) # 재귀를 이용하여 퀵 정렬 수행 def mergeSort(start, end): if end == start: return start else: half = (end - start) // 2 l = mergeSort(start, half) r = mergeSort(half+1, end) # 정렬할 리스트 입력 list = list(map(int, input("병합 정렬할 숫자를 띄어쓰기로 구분하여 입력 : ").split(' '))) n = len(list) # 병합 정렬 print() mergeSort(list) # 정렬된 리스트 출력 for i in list: print(i, end=' ') </code></pre><h2>힙 (Heap)</h2><ul><li>힙 : 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조</li></ul><h2>셸</h2><p>삽입정렬을 보완한 알고리즘</p><p> </p> 글 종류 이론 정리 알고리즘 이론에 대한 정리글입니다. 문제 풀이 알고리즘 문제 풀이입니다. 알고리즘 분류 수정 취소