조세프 문제
01배열
- 죽은 병사 음수
- 음수 카운트 X
- 남은 병사수 2명이면 인덱스 값 확인
02리스트
- 노드 생성, 데이터 저장
- 저장 후 3만큼 이동
삽입 정렬
연결리스트일때 삽입정렬이 효율적
- S : 정렬된 앞부분의 원소들
- U: 정렬되지 않은 나머지 원소들
- U의 원소를 하나씩 S에 삽입정렬
- 시간 복잡도 O(n^2)
arr = [69, 10, 30, 2, 16, 8, 31, 22]
N = len(arr)
for i in range(1, N):
tmp = arr[i]
print(arr[:i], arr[i:])
j = i - 1
while j >= 0 and arr[j] > tmp:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = tmp
print(arr)병합 정렬
여러개의 정렬된 자료 병합하여 정렬
연결 리스트시 유리
- 분할 정복 알고리즘 활용
- 최소 단위 문제까지 나눈 후 차례대로 정렬
- top-doen
- 분할 - 정복 - 병합(합병)
- O(n log n)
우선순위 큐
트리로 구현하자^^ 더 이득