하루 한 줄 요약
구멍이 숭숭 뚫린 내 지식.
오늘 공부한 내용
- 시간 복잡도 & 공간 복잡도
- 정렬 2회독(안정성,Do it 자료구조 내용 추가)
- 하노이 탑 알고리즘(재귀)
새로 배우게 된 내용
시간 복잡도 & 공간 복잡도
⏳ 시간 복잡도
코딩 테스트 문제를 풀 때 시간 복잡도가 중요한 힌트가 될 수 있다.
보통 채점용 PC는 1초에 약 1억 번의 연산을 수행한다고 가정할 때,
입력값 N에 따라 사용할 수 있는 알고리즘의 시간 복잡도를 예측할 수 있다.
- N ≤ 500 ⇒ 시간복잡도가 O(N^3) 이하
- N ≤ 2000 ⇒ 시간복잡도가 O(N^2) 이하
- N ≤ 100,000 ⇒ 시간 복잡도가 O(N log N) 이하
- N ≤ 10,000,000 ⇒ 시간복잡도가 O(N) 이하
- N ≤ 10,000,000,000 ⇒ 시간 복잡도가 O(log N)예를 들어, 백준 2751번 문제의 경우 N = 1,000,000이므로
O(N^2) 시간 복잡도를 갖는 선택 정렬이나 버블 정렬을 사용하면 시간 초과가 발생한다.
📦 공간 복잡도
일반적으로 코딩 테스트에서는 128MB ~ 512MB 메모리 제한이 주어진다.
예를 들어, 백준 10989번 문제의 경우 메모리 제한이 8MB인데,
리스트를 추가로 생성하고 정렬하려다가 메모리 초과가 발생했다
len(arr) = 1,000 => 4KB
len(arr) = 1,000,000 => 4MB
len(arr) = 10,000,000 => 40MB이를 고려하여 계수 정렬(Counting Sort)의 특성을 활용해 원본 배열을 수정하는 방식으로 해결했다.
정렬 2회독
나름 2회독 인데... 팀 스터디 하면서 내가 이부분을 맡아서 발표 했는데,
갑자기 리스트 칠판에 그려서 직접 보여달라고 하시는데 당황해서 제대로 못했다
🔹 버블 정렬
PASS 개념을 잘 설명하지 못했는데, 팀원의 설명에 따르면
for문 루프를 한 번 도는 것이 PASS 1회라고 한다.
또한 안정성(stability) 개념을 배우면서 동일한 원소의 상대적 순서 유지 여부에 따라 정렬이 나뉜다는 것을 알게 되었다.
🔹 셸 정렬
셸 정렬은 삽입 정렬의 단점을 보완하기 위해 고안된 알고리즘으로,
간격(gap)을 두고 원소들을 비교하며 정렬한다.
예를 들어,
arr = [9, 8, 3, 7, 5, 6, 4]에서 gap = 3일 경우,
(0,3,6), (1,4), (2,5)와 같이 해당 간격만큼 떨어진 원소들끼리 삽입 정렬을 수행한다.
팀 스터디 시간에 2개씩 묶어서 진행하는 것으로 오해하고 설명해서 혼란을 드렸는데
간격을 기준으로 그룹을 형성한다고 수정해서 다시 말씀 드렸다.
🔹 퀵 정렬
퀵 정렬은 피벗을 기준으로 양 끝에서 이동하며 값 교환 후,
피벗을 중심으로 재귀적으로 정렬하는 방식이다.
설명 중 Pl과 Pr이 교차한 후 피벗과 Pr을 교환하는 과정을 빠뜨려서
분할 기준을 명확히 설명하지 못했다.
[6, 8, 3, 7, 2, 5, 4]에서 Pl과 Pr이 교차할 때 배열 상태는
[4, 2, 3, 7, 8, 5, 6]이고, Pr(3)과 피벗(5)을 교환하면
[4, 2, 3, 5, 8, 7, 6]위와 같게 되고, 피벗을 기준으로 작은값은 앞으로, 피벗을 기준으로 큰값은 뒤로 가서
[4,2,3] 과 [8,7,6]을 재귀적으로 정렬하게 된다.
하노이탑 알고리즘
하노이탑 알고리즘을 공부할때 키워드를 잘 정리해놓은 글이 있어서 공유한다
재귀를 이해하기 좋은 알고리즘으로,
핵심 개념은 출발지 → 경유지 → 목적지로의 이동을 일반화하는 것이다.
N = int(input())
moving_count = 2 ** N - 1
def move(start, end):
print(start, end)
# start : 1, end :3 sub : 2
def hanoi(N, start, end, sub):
if N == 1:
move(start, end)
else:
hanoi(N - 1, start, sub, end)
move(start, end)
hanoi(N - 1, sub, end, start)
if N <= 20:
print(moving_count)
hanoi(N, 1, 3, 2)
else:
print(moving_count)🎯 핵심 개념 정리
1️⃣ 가장 큰 원판(3번 원판)을 C 기둥으로 이동하려면,
작은 원판(1,2번)은 B 기둥에 있어야 한다.
2️⃣ 이후, 작은 원판을 B 기둥에서 C 기둥으로 이동해야 한다.
이를 일반화하면, Hanoi(N) → Hanoi(N-1) 호출 2번의 구조를 갖게 된다.
따라서 Hanoi(3) 을 호출하게 되면 Hanoi(2)를 두번 재귀적으로 호출해야한다.
여기서 재귀라는 키워드를 얻는 것이다.
다만 이 두번의 Hanoi(2) 재귀적 호출이 원반을 움직이는 개수는 같지만, 각각
출발지와 목적지가 다르기때문에 우린 이걸 변수로 받아서 추적하는 것!
공부하면서 어려웠던 점
정렬의 방식이 양이 많아서 각각의 개념들이 헷갈리는 것 같다.
다시한번 명확히 정리하는 시간을 통해서 극복하겠다.
