# 알고리즘 재활 3편 — 정답을 찾는 것보다, 왜 그 코드가 맞는지 설명하는 게 어려웠다

About this offer

지난 2편에서는 문제를 보면서 조금씩 알고리즘의 패턴을 떠올리기 시작했다고 썼다. 이번에는 그 패턴을 실제 코드로 옮기는 과정에서 다시 많이 막혔다. 9월 21일부터 30일까지 이분 탐색과 파라메트릭 서치, 순열을 이용한 완전 탐색, N으로 표현 의 DP를 공부했다. 그 사이에 딕셔너리 조회 방법을 다시 물었고, set 에 append() 를 쓰는지도 확인했다. lambda 가 어렵다고 했다가, 사실은 key 라는 단어부터 직관적으로 이해되지 않는다고 다시 질문하기도 했다. 가장 오래 붙잡았던 질문은 이것이었다. 실제 계산은 mid 로 하는데, 왜 마지막에는 lo 를 반환해도 되는가? 설명을 한 번 듣고 바로 납득하지 못했다. 같은 부분을 다시 물었고, 작은 예시로 범위를 움직여보는 설명도 다시 들었다. 이번 공부는 새로운 알고리즘을 많이 외운 기록보다는, 내가 어디까지 이해했고 어디부터 설명하지 못하는지를 확인한 기록에 가깝다. 1. 조건문부터 다시 확인했다 알고리즘을 공부하는 중에도 기본 문법에서 흐름이 자주 끊겼다. if 에 음수가 들어가면 실행되는지, None 이면 실행되지 않는지부터 다시 확인했다. if -1: print("실행됨") if 0: print("실행되지 않음") if None: print("실행되지 않음") 정수에서는 0만 거짓으로 취급하고, 음수도 0이 아니면 참이다. None 과 빈 문자열, 빈 리스트 같은 값도 조건문에서는 거짓으로 평가된다. 여기서 중요한 건 값의 참·거짓을 확인하는 것과, 값이나 키가 존재하는지 확인하는 것은 다르다 는 점이었다. d = {"a": 0} if d.get("a"): print("실행되지 않음") if "a" in d: print("실행됨") "a" 라는 키는 있지만 값이 0이어서 첫 번째 조건은 거짓이다. 저장된 값이 0일 수도 있는 상황에서는 get() 의 결과를 그대로 조건으로 쓰면 존재 여부를 제대로 판단하지 못한다. 컴프리헨션의 if 는 위치에 따라 역할이 달랐다 numbers = [-2, -1, 0, 1, 2] # 조건에 맞는 원소만 남긴다. positive = [x for x in numbers if x > 0] # [1, 2] # 모든 원소를 처리하되, 넣을 값을 조건에 따라 바꾼다. changed = [x if x > 0 else 0 for x in numbers] # [0, 0, 0, 1, 2] 첫 번째는 원소를 고르는 조건이고, 두 번째는 결과에 넣을 값을 결정하는 조건이다. 단순히 if 가 앞에 오는지 뒤에 오는지를 외우기보다, 이 원소를 넣을 것인지와 무엇을 넣을 것인지를 구분 해서 보려고 한다. do while 은 따로 없었다 최소 한 번 실행한 뒤 종료 여부를 판단하고 싶어서 Python의 do while 도 물었다. Python에서는 다음처럼 쓸 수 있다. x = 1 while True: print(x) x += 1 if x > 5: break 조건을 먼저 검사하는지, 작업을 한 뒤 검사하는지에 따라 반복문의 의미가 달라진다는 것도 같이 확인했다. 2. 딕셔너리의 메서드를 이름이 아니라 목적별로 구분했다 딕셔너리에서 무언가를 꺼내고 싶을 때 items() 를 써야 하는지, get() 을 써야 하는지 헷갈렸다. values() 를 설명받은 뒤에도 특정 값 하나가 궁금할 때는 무엇을 써야 하는지 다시 물었다. d = { "apple": 1000, "banana": 2000 } d["apple"] # 특정 키의 값: 1000 d.get("apple") # 특정 키의 값: 1000 d.keys() # 모든 키 d.values() # 모든 값 d.items() # 모든 (키, 값) 쌍 keys() , values() , items() 에는 인자를 넣지 않는다. 특정 키 하나를 지정하는 것은 d[key] 나 d.get(key) 다. 키가 확실히 존재한다면 d[key] 와 d.get(key) 로 얻는 값은 같다. 없는 키를 조회할 때는 차이가 있다. d["orange"] # KeyError d.get("orange") # None d.get("orange", 0) # 0 딕셔너리를 그냥 순회하면 키가 나온다는 것도 다시 확인했다. for key in d: print(key) 이것은 다음과 같은 의미다. for key in d.keys(): print(key) 키와 값을 같이 꺼내고 싶으면 items() 를 쓴다. for key, value in d.items(): print(key, value) 결국 기억할 기준은 단순했다. 키 하나로 값을 찾을 것인지, 전체 키를 볼 것인지, 전체 값을 볼 것인지, 둘을 함께 볼 것인지부터 정하면 된다. 3. 딕셔너리는 반대 방향 검색까지 자동으로 해주지 않았다 2000 이라는 값에 해당하는 키가 무엇인지, 순회하지 않고 바로 찾을 방법이 있는지도 물었다. d = { "apple": 1000, "banana": 2000 } 이 구조는 기본적으로 "banana" → 2000 을 빠르게 찾기 위한 구조다. 반대로 2000 → "banana" 를 바로 찾을 수 있는 별도의 인덱스가 있는 것은 아니다. key = next(k for k, v in d.items() if v == 2000) 이렇게 한 줄로 적어도 내부적으로는 결국 순회한다. 코드가 짧아진 것과 시간복잡도가 줄어든 것은 별개였다. 반대 방향 조회가 자주 필요하다면 처음부터 별도의 딕셔너리를 만들 수 있다. reverse_d = { 1000: "apple", 2000: "banana" } reverse_d[2000] # "banana" 즉 자료구조를 만들 때부터 어느 방향으로 조회할 일이 많은가 를 생각해야 한다. 4. set 은 만들기부터 연산까지 다시 정리했다 N으로 표현 을 풀면서 set 관련 질문을 연속으로 했다. 빈 집합은 어떻게 만드는지부터 다시 봤다. s = set() 주의할 점은 이것이다. s = {} 이것은 빈 set 이 아니라 빈 dict 다. 실제로 다음처럼 작성했다가 에러가 났다. dp = {set() for _ in range(9)} 내가 원한 것은 집합 아홉 개를 담는 리스트였는데, 바깥을 {} 로 써서 집합 안에 집합을 넣으려고 했다. dp = [set() for _ in range(9)] 이렇게 해야 했다. 추가와 제거도 리스트와 달랐다 리스트에서는: arr.append(1) 집합에서는: s.add(1) 을 쓴다. 여러 개를 추가하려면: s.update([1, 2, 3]) 삭제는: s.remove(1) 또는: s.discard(1) 을 쓴다. 차이는 없는 원소를 삭제하려고 할 때다. s.remove(100) # KeyError s.discard(100) # 에러 없음 합집합과 원소끼리의 연산은 다른 이야기였다 집합 자체를 합치려면: a = {1, 2} b = {2, 3} a | b # {1, 2, 3} 또는: a.union(b) 를 쓴다. 하지만 set 끼리 숫자처럼 곱하거나 나눌 수는 없다. a * b # 불가능 a / b # 불가능 N으로 표현 에서 필요한 것은 두 집합의 각 원소를 하나씩 꺼내 계산하는 것이었다. for x in a: for y in b: result.add(x * y) 즉 set끼리 연산하는 것이 아니라 set 안의 원소끼리 연산하는 것 이었다. 5. in 과 pop() 도 자료구조와 위치에 따라 달랐다 if x in ... 의 시간복잡도가 O(N) 인지 물었는데, 정확히는 자료구조에 따라 다르다. x in list → O(N) x in tuple → O(N) x in set → 평균 O(1) key in dict → 평균 O(1) 그래서 코딩테스트에서 어떤 값이 존재하는지 반복해서 검사한다면 list 보다 set 이 훨씬 유리할 수 있다. pop() 도 마찬가지였다. arr.pop() 맨 뒤를 제거하면 O(1) 이다. 하지만: arr.pop(0) 맨 앞을 제거하면 뒤의 원소들을 앞으로 당겨야 해서 O(N) 이다. list.pop() → O(1) list.pop(0) → O(N) 앞에서 계속 제거해야 한다면 deque.popleft() 를 고려할 수 있다. 문법 하나만 보고 시간복잡도를 외우기보다, 어떤 자료구조의 어느 위치를 건드리는가 를 같이 봐야 했다. 6. 완전 탐색과 순열 9월 26일에는 완전 탐색과 순열을 공부했다. 완전 탐색은 말 그대로 가능한 경우를 전부 확인하는 방식 이다. 예를 들어 [1, 2, 3] 의 모든 순서를 확인하고 싶다면: from itertools import permutations arr = [1, 2, 3] result = list(permutations(arr)) print(result) 결과는: [ (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1) ] 일부만 뽑으면서 순서까지 고려하고 싶으면: permutations(arr, 2) 를 사용할 수 있다. 이걸 프로그래머스의 피로도 문제에 적용했다. 처음에는 던전을 입력 순서대로 한 번만 돌았다. for i in range(size): if k >= dungeons[i][0]: ... 하지만 던전의 방문 순서에 따라 결과가 달라진다. 그래서 모든 방문 순서를 확인했다. from itertools import permutations ad = list(permutations(dungeons)) 그리고 각 순열마다 피로도를 처음 값으로 되돌렸다. origin = k while ad: count = 0 k = origin dun = ad.pop() for d in dun: if k >= d[0] and k - d[1] >= 0: k -= d[1] count += 1 이 풀이를 가장 정확하게 표현하면: 순열을 이용한 완전 탐색 이다. 던전이 N 개라면 순열은 N! 개이고, 각 순열에서 최대 N 개의 던전을 확인하므로 대략: O(N × N!) 의 시간복잡도를 가진다. 경우의 수가 매우 빠르게 증가하기 때문에 입력 크기가 작은 문제에서만 사용할 수 있다. 7. 이분 탐색을 배웠는데 무엇을 이분 탐색해야 하는지 몰랐다 처음 이분 탐색을 배울 때는 정렬된 배열에서 특정 값을 찾는 방식으로 이해했다. def binary_search(arr, target): left = 0 right = len(arr) - 1 while left <= right: mid = (left + right) // 2 if arr[mid] == target: return mid elif arr[mid] < target: left = mid + 1 else: right = mid - 1 범위를 절반씩 줄이기 때문에 시간복잡도는 O(log N) 이다. 그런데 입국심사 문제를 보니 혼란이 왔다. 내 코드의 주석에도 다음과 같은 고민이 남아 있었다. # 이분 탐색을 어디서 사용하지? # 뭘 정렬하지? # 심사관을 뽑을 때? 당시에는 이분 탐색을 하려면 입력 배열을 정렬해서 그 안에서 뭔가를 찾아야 한다 고 생각하고 있었다. 하지만 입국심사에서는 times 안의 값을 찾는 것이 아니었다. 찾아야 하는 것은: 모든 사람의 입국심사가 끝나는 최소 시간 이었다. 즉 배열이 아니라 정답 후보인 시간 자체를 이분 탐색해야 했다. 8. 입국심사 — 사람을 한 명씩 배치하려고 했다 처음 작성한 코드는 이런 식이었다. def solution(n, times): size = len(times) times.sort() loadings = times.copy() n -= size while n != 0: p = [] for i in range(size): p.append(loadings[i] + times[i]) m = min(p) p_i = p.index(m) loadings[p_i] = m n -= 1 return max(loadings) 생각은 단순했다. 첫 사람을 심사대에 넣음 다음 사람을 가장 빨리 끝나는 심사대에 넣음 다음 사람을 다시 배치 ... 샘플: n = 6 times = [7, 10] 에서는 실제로 28이 나왔다. 하지만 문제에서 n 은 최대 10억이다. 한 사람씩 처리하면 반복문을 최대 10억 번 돌아야 한다. 즉 문제의 크기부터 내 접근법과 맞지 않았다. 9. 파라메트릭 서치 — 사람 대신 시간을 하나 찍어봤다 관점을 바꿨다. 기존 질문은: 다음 사람을 어느 심사대에 넣을까? 였다. 바꾼 질문은: X분 동안 심사관들이 총 몇 명을 처리할 수 있을까? 였다. 예를 들어: times = [7, 10] 28분 동안 가능한 사람 수는: 28 // 7 = 4 28 // 10 = 2 총 6명 코드로 쓰면: people = 0 for time in times: people += mid // time 이렇게 된다. 시간이 충분한지를 판별할 수 있게 된 것이다. 예를 들어 n = 6 이라면: 25분 → 불가능 26분 → 불가능 27분 → 불가능 28분 → 가능 29분 → 가능 30분 → 가능 결국 다음 경계를 찾는 문제로 바뀐다. X X X X X | O O O O O ↑ 처음으로 가능한 시간이 어디인가? 이게 이 문제에서 파라메트릭 서치를 사용하는 이유였다. 10. 이분 탐색 구현에서 mid 를 범위에서 제거해야 했다 처음 작성한 코드에서는 이렇게 했다. if p > n: hi = mid else: lo = mid 문제는 mid 를 다시 탐색 범위에 남겨둔다는 것이다. 예를 들어: lo = 27 hi = 28 이면: mid = (27 + 28) // 2 # 27 여기서: lo = mid 를 하면: lo = 27 hi = 28 로 아무것도 변하지 않는다. 다음 반복에서도 mid = 27 . 결국 무한루프가 날 수 있다. 그래서 이미 검사한 mid 를 제외해야 한다. lo = mid + 1 또는: hi = mid - 1 11. p > n 과 p >= n 의 차이가 중요했다 또 하나 헷갈렸던 부분은 조건이었다. 처음에는: if p > n: 또는: if p <= n: 처럼 작성했다. 하지만 우리가 원하는 것은: n명 이상 을 처리할 수 있는 최소 시간 이다. 예를 들어: n = 6 28분 → 6명 29분 → 6명 30분 → 7명 28분도 이미 충분하다. 따라서: if p >= n: 으로 판단해야 한다. 그리고 최소 시간을 찾는 중이므로, 충분하다면 더 작은 시간을 확인한다. if p >= n: hi = mid - 1 else: lo = mid + 1 이렇게 된다. 12. 가장 이해하기 어려웠던 return lo 이 부분은 설명을 듣고도 바로 이해되지 않았다. 내 질문은 이것이었다. 실제로 사람 수를 계산하고 예측한 값은 mid 인데 왜 lo 를 반환하지? 처음에는 mid 가 답이라고 생각했다. 하지만 mid 는 정답을 저장하는 변수 가 아니었다. mid 는 매번 이렇게 질문하는 값이다. "이 시간이면 가능한가?" 그 질문의 결과를 이용해서 lo 와 hi 를 움직인다. 작은 예를 보면 더 명확했다. 시간 25 26 27 | 28 29 30 가능? X X X | O O O 27을 검사해서 불가능하다면: lo = mid + 1 이므로: lo = 28 이 된다. lo = 28 이 된 것은 28을 계산해서가 아니라, 27 이하가 모두 정답 후보에서 제거됐기 때문 이다. 반대로 28이 가능하면: hi = mid - 1 이 된다. 최종적으로는: 27 | 28 X | O ↑ ↑ hi lo 와 같은 경계가 만들어진다. 그래서 이 구현에서는 lo 가 최초로 가능한 값에 도착한다. 정리하면: mid = 지금 검사하는 값 lo = 검사 결과가 누적되면서 결국 최초의 가능한 값에 도달하는 경계 였다. 다만 이것도 모든 이분 탐색에서 무조건 lo 를 반환한다는 뜻은 아니다. 어떤 경계를 찾고 있고, lo 와 hi 를 어떤 규칙으로 움직이는지에 따라 달라진다. 13. N으로 표현 — 처음에는 최소공배수를 떠올렸다 9월 28일에는 프로그래머스의 N으로 표현 문제를 풀었다. 처음 생각은 최소공배수였다. import math lcm = N * number // math.gcd(N, number) N 으로 어떤 공통 값을 만든 뒤 number 를 만드는 방향으로 접근해보려고 했다. 하지만 이 문제는 그런 구조가 아니었다. 예를 들어: 12 = 55 / 5 + 5 / 5 12 = (55 + 5) / 5 처럼 숫자를 이어 붙이거나 다양한 사칙연산 조합이 가능하다. 여기서 필요한 것은 N을 몇 개 사용했는가 를 기준으로 가능한 결과들을 쌓는 것이었다. 14. DP의 기준을 잡았다 핵심 정의는: dp[k] = N을 정확히 k개 사용해서 만들 수 있는 모든 숫자 였다. 예를 들어 N = 5 라면: dp[1] = {5} N을 2개 사용하면: 55 5 + 5 = 10 5 - 5 = 0 5 * 5 = 25 5 // 5 = 1 이므로: dp[2] = { 55, 10, 0, 25, 1 } 여기서 set 을 사용한 이유는 같은 숫자가 여러 방식으로 나와도 중복 저장할 필요가 없기 때문이다. 15. 처음에는 잘못된 DP끼리 합치고 있었다 내 코드는 처음에 이런 식이었다. l1 = list(dp[k - 2]) l2 = list(dp[k - 1]) 문제는 k = 4 일 때다. dp[2] → N을 2개 사용 dp[3] → N을 3개 사용 이 둘을 조합하면 N을 5개 사용한다. 그런데 결과를 dp[4] 에 넣고 있었다. 즉 DP의 정의가 깨졌다. dp[4] 를 만들려면: dp[1] + dp[3] dp[2] + dp[2] dp[3] + dp[1] 처럼 두 인덱스의 합이 4가 되어야 한다. 그래서 일반적으로: for a in range(1, curr): b = curr - a 로 나눌 수 있다. for i in dp[a]: for j in dp[b]: ... 그리고 두 값을 사칙연산한다. 16. 뺄셈과 나눗셈에서는 순서도 중요했다 덧셈과 곱셈은: a + b = b + a a * b = b * a 이지만 뺄셈과 나눗셈은 다르다. a - b != b - a a // b != b // a 그래서 한쪽 조합만 계산하려면 양방향 연산을 직접 넣어야 했다. dp[curr].update([ i - j, j - i, i + j, i * j ]) if j: dp[curr].add(i // j) if i: dp[curr].add(j // i) 이렇게 하면: dp[1] + dp[4] dp[2] + dp[3] 까지만 보더라도 반대 방향 연산을 같이 확인할 수 있다. 17. DP 구현 중에도 기본 문법에서 여러 번 틀렸다 update 호출 문법 한 번은: dp[curr].update[i-j, j-i, i+j, i*j] 라고 작성했다. 하지만 update 는 함수이므로 괄호로 호출해야 한다. dp[curr].update([i-j, j-i, i+j, i*j]) 반복 변수를 계속 초기화했다 다음 코드도 작성했다. a = 1 while True: a = 1 b = curr - a ... a += 1 아래에서 a += 1 을 해도 다음 반복에서 다시 1이 된다. 결국 같은 조합만 계속 계산할 수 있다. 입국심사에서 lo = mid 로 범위가 줄지 않았던 것과 비슷했다. 반복문에서 변수를 변경했다는 사실보다 다음 반복에서도 그 변경이 유지되는지가 중요했다. / 와 // 처음에는: i / j 를 사용했다. 그러면: 5 / 2 # 2.5 가 된다. 문제에서는 나눗셈에서 나머지를 무시하므로 정수 나눗셈을 사용해야 한다. i // j 그리고 분모가 0일 때는 계산하면 안 된다. if j: dp[curr].add(i // j) 18. 0을 지우는 것도 다시 생각했다 한때: dp[k].discard(0) 으로 0을 제거했다. 하지만: 5 - 5 = 0 도 정상적인 계산 결과다. 0이라는 값 자체가 문제인 것이 아니라: 0으로 나누는 것 이 문제다. 따라서 0을 상태에서 없애버리는 것과, 분모가 0인 연산을 막는 것은 구분해야 한다. 19. 초기 상태도 정답인지 확인해야 했다 DP를 고친 뒤에는 다음처럼 3 부터 확인했다. for curr in range(3, 9): ... if number in dp[curr]: return curr 하지만: N = 5 number = 5 라면 답은 1이다. N = 5 number = 55 라면 답은 2다. 따라서 dp[1] , dp[2] 도 정답인지 확인해야 했다. 초기 상태를 만들어놓았다고 해서 자동으로 정답 검사가 된 것은 아니었다. 20. 리스트를 순회하면서 동시에 수정했다 9월 29일에는 다음 문제를 풀었다. # 정수 리스트