Kim Seon Deok

힙 정렬 힙의 특성을 이용하여 정렬하는 알고리즘 힙에서 최댓값은 루트에 위치한다. 선택 정렬을 응용한 알고리즘 최댓값인 원소를 선택하는 시간 복잡도는 O(n), 힙 정렬에서 다시 힙으로 만드는 작업의 시간 복잡도는 O(logn) 힙 부모의 값이 자식의 값보다 항상 크거나 작다는 조건을 만족하는 완전 이진 트리 두 값의 대소 관계가 일정하면 된다. 부모와 자식관계는 일정하지만 형제 사이의 대소관계는 일정하지 않다. 루트를 삭제한 힙의 재구성 힙에서 루트를 꺼냄 루트 위치의 힙의 마지막 원소(가장 하단의 오른쪽에 위치한 원소)를 비어있는 루트자리로 이동 다음 단계에 있는 자식의 크기를 비교하여 부모의 값이 자식의 값보다 항상 커야 한다는 힙의 조건을 만족시키기 위해 더 큰 자식과 위치를 바꾸고 아래로 내려감..

퀵 정렬 일반적으로 사용되는 아주 빠른 정렬 알고리즘 피벗을 선택하여 나누기를 반복하며 모든 그룹이 1명씩 남으면 정렬이 완료된다. 피벗 : 그룹을 나누는 기준 피벗을 어떤 값으로 선택하느냐에 따라 배열을 나누는 것과 정렬하는 성능에 영향을 미친다. # 퀵 정렬 알고리즘 구현하기 from typing import MutableSequence def qsort(a: MutableSequence, left : int, right: int) -> None: """a[left] ~ a[right]를 퀵 정렬""" pl = left # 왼쪽 커서 pr = right # 오른쪽 커서 x = a[(left + right) // 2] # 피벗 (가운데 원소) while pl x : pr -= 1 if pl None: ..

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 1.조합함수를 사용하기 위한 itertools 모듈 생성 2.짝수의 수 N과 N회 반복하여 길이가 N인 리스트를 리스트 e에 저장해 2차원 리스트 생성 3. 1~N까지 수를 possible_team리스트에 저장 4.start_team = possible_team의 절반(0번째 인덱스~ 절반 인덱스) link_team = possible_team의 절반(절반 인덱스~ 마지막 인덱스) 5. start_team 과 link..

https://www.acmicpc.net/problem/20436 20436번: ZOAC 3 첫 번째 줄에는 두 알파벳 소문자 sL, sR이 주어진다. sL, sR은 각각 왼손 검지손가락, 오른손 검지손가락의 처음 위치이다. 그 다음 줄에는 알파벳 소문자로 구성된 문자열이 주어진다. 문자열의 www.acmicpc.net sl,sr = list(input().split()) s =list(map(str,input())) left = [['q','w','e','r','t'], ['a','s','d','f','g'], ['z','x','c','v','']] right = [['','','','','','y','u','i','o','p'], ['','','','','','h','j','k','l'], ['',..

1.단순 선택 정렬 가장 작은 원소부터 선택해 알맞은 위치로 옮기는 작업을 반복하며 정렬하는 알고리즘 교환 과정은 다음과 같다. 아직 정렬하지 않은 부분에서 값이 가장 작은 원소 a[min]을 선택한다. a[min]과 아직 정렬하지 않은 부분에서 맨 앞에 있는 원소를 교환한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 # 단순 선택 정렬 알고리즘 구현하기 from re import I from typing import MutableSequence def selection_sort(a: MutableSequence) -> None: """단순 선택 정렬""" n = len(a) for i in range(n-1): min = i # 정렬할 부분에서 가장 작은 원소의 인덱스 fo..