지난 학습 요약
4/20 20차 세션에서 구현/시뮬레이션 범위를 복습하며 18차 약점이던 y 차원 경계 체크(0 <= ny < n)를 힌트 없이 재현하여 정착을 확인했다. 반면 2차원 90도 회전 공식 rotated[i][j]=arr[n-1-j][i] 은 재노출 공백으로 잠시 날아갔고, 경계 순회 문제에선 arr[x][y] not in result 같은 값 기반 중복 체크가 중복 값 반례에서 깨져 좌표 기반 visited = {(0,0)} 방식으로 교정했다. 세션 말미에 스스로 "루프 전 초기 값 세팅을 자주 깜빡한다", "인덱스+값을 병렬로 다루는 감각이 아직 약하다" 두 약점을 정확히 진단했고, 오늘은 그 연장선에서 가볍게 워밍업한다.
오늘 수업 계획
20차 자기 진단에서 나온 두 약점(초기값 세팅 누락 / 인덱스+값 병렬 처리 미숙)을 겨냥해 enumerate → zip → 튜플 정렬 순서로 빈칸 세 문제만 가볍게 푼다. 이 세 도구는 겉보기엔 다르지만 "두 종류의 데이터를 같은 시점에 묶어 다룬다"는 같은 범주에 속한다. 풀이 중 학습자가 제기한 "부호 뒤집기 트릭의 경계 조건" 질문에서 stable sort 기반 2단계 정렬 트릭까지 확장하고, 마지막에 그리디 알고리즘 개념을 이미 푼 프린터 우선순위 문제를 매개로 정립한다.
학습 내용 정리
0) 세션 시작 전 질문: 알고리즘 용어 점검
수업 중 질문: "최근에 1급 딴 다른 사람 후기 봤는데 DFS BFS DP 그리디 이런
알고리즘 용어가 나오더라고? 잘 몰랐는데 이미 내가 푼 적도 있는거야?"현 커리큘럼 기준으로 정리하면 다음과 같다.
| 용어 | 뜻 | 학습 상태 |
|---|---|---|
| DFS (깊이 우선 탐색) | 한 갈래 끝까지 가보고 막히면 돌아와서 다른 갈래 | 미학습, 4월 말 진입 예정 |
| BFS (너비 우선 탐색) | 가까운 곳부터 한 겹씩 퍼져나가며 탐색 | 미학습, 4월 말 진입 예정 |
| DP (동적 프로그래밍) | 작은 문제 답을 저장해두고 큰 문제에 재활용 | 커리큘럼 제외 (합격 전략상 불필요) |
| 그리디 | 매 순간 가장 좋아 보이는 선택을 하는 전략 | 이미 푼 적 있음 (용어만 몰랐을 뿐) |
특히 그리디의 경우 이미 17차/19차에서 푼 프린터 우선순위 문제가 정통 그리디 유형이었다는 점을 확인하고, 오늘 세션 마지막에 개념을 명시적으로 정립하기로 했다.
1) enumerate — 인덱스와 값을 같이 순회
문제: 숫자 리스트에서 가장 큰 값이 있는 위치(인덱스)를 반환하는 함수를 작성하라. max(), index() 사용 금지.
def find_max_index(arr):
max_idx = 0
max_val = arr[0]
for i, v in enumerate(arr):
if v > max_val:
max_val = v
max_idx = i
return max_idx핵심:
enumerate(arr)은(인덱스, 값)튜플을 하나씩 내어주는 반복자. 이걸for i, v in ...로 언패킹하면 한 번의 순회로 두 정보를 동시에 쓸 수 있다.>부등호(등호 없음) 때문에 동점이면 먼저 나온 인덱스가 유지된다.[5, 5, 5]입력에서0이 나오는 이유.
수업 중 질문 (풀이 직후): "초기값 세팅은 내가 한 거 아니야."정확한 지적이었다. 이 문제에서 max_idx = 0 / max_val = arr[0] 두 줄은 빈칸 바깥에 제시된 코드라 학습자가 직접 쓴 부분은 아니었다. 초기값 세팅 약점 개선은 다음 문제에서 진짜로 확인하기로 했다.
2) zip — 두 리스트를 값끼리 병렬 순회
문제: 학생 이름 리스트와 점수 리스트가 있을 때, 가장 높은 점수를 받은 학생의 이름을 반환하라.
def top_student(names, scores):
top_score = scores[0]
top_name = names[0]
for name, score in zip(names, scores):
if score > top_score:
top_score = score
top_name = name
return top_name핵심:
zip(names, scores)는 같은 위치의 두 원소를 튜플로 묶어 내어주는 반복자. 길이가 다르면 짧은 쪽에 맞춰 멈춘다 (그래서 짧은 리스트의 길이까지만 순회됨).enumerate가 "(인덱스, 값)" 을 묶었다면zip은 "(값, 값)" 을 묶는다. 묶는 대상이 다를 뿐 "두 데이터를 병렬로 쓴다" 는 목적은 같다.
이번 문제에서는 top_score = scores[0], top_name = names[0] 초기값 세팅 두 줄을 힌트 없이 직접 썼다. 20차 때 스스로 진단했던 "루프 전 초기값을 자주 깜빡한다" 약점이 이번엔 작동하지 않았다 — 한 번의 실전 노출로 개선 신호를 확인한 셈.
enumerate ↔ zip 비교표:
| 상황 | 도구 | 언패킹 예 |
|---|---|---|
| 한 리스트의 인덱스와 값이 같이 필요 | enumerate(arr) | for i, v in ... |
| 두 리스트를 같은 위치끼리 비교 | zip(a, b) | for x, y in ... |
| 세 리스트 이상 | zip(a, b, c) | for x, y, z in ... |
| 인덱스도 있고 두 리스트도 같이 | enumerate(zip(a, b)) | for i, (x, y) in ... |
3) 튜플 정렬 — 다중 key + 부호 뒤집기 트릭
문제: [(이름, 점수), ...] 리스트를 점수 내림차순, 동점이면 이름 가나다순으로 정렬하라.
def sort_students(students):
return sorted(students, key=lambda x: (-x[1], x[0]))핵심 아이디어:
sorted()의 key 함수가 튜플을 반환하면 Python은 튜플을 앞에서부터 순서대로 비교한다. 1차 기준이 같을 때만 2차 기준을 본다.- 문제의 함정: 점수는 내림차, 이름은 오름차 — 방향이 섞였다.
reverse=True는 튜플 전체를 뒤집기 때문에 둘 다 내림차가 되어 버린다. - 해법: 한 쪽만 부호를 뒤집는다. 점수
-x[1]로 넣으면 정렬은 오름차로 하면서 실제 결과는 점수 내림차가 된다.
Java와 비교:
| 언어 | 점수 내림 + 이름 오름 정렬 |
|---|---|
| Java | list.sort(Comparator.comparingInt(Student::score).reversed().thenComparing(Student::name)) |
| Python | sorted(list, key=lambda x: (-x[1], x[0])) |
Java의 .reversed().thenComparing() 체이닝과 Python의 부호 뒤집기 트릭은 목표는 같지만 표현이 다르다. Python 쪽이 짧은 대신 "숫자에만 먹힌다"는 제약이 있다.
4) 부호 뒤집기 트릭의 경계: 문자열에 적용하려면?
수업 중 질문: "지금은 내림차순 정렬하는 값이 숫자라서 가능한 거지?
만약 이름을 내림차순(사전 반대방향)으로 정렬한다고 하면
어쩔 수 없이 reverse=True 사용해야되겠지?"매우 정확한 경계 질문이다. 답을 정리하면:
>>> -"abc"
TypeError: bad operand type for unary -: 'str'부호 뒤집기는 숫자에만 먹힌다. 그렇다고 reverse=True 만이 유일한 답은 아니다. Python의 sorted() 가 stable(안정 정렬) 이라는 성질을 이용하면 문자열에도 "방향이 섞인 다중 정렬"이 가능하다.
Stable sort 의 정의: 같은 key 값을 가진 원소들의 상대 순서가 정렬 전후에 유지된다.
활용법 — 2단계 정렬: "덜 중요한 기준을 먼저, 더 중요한 기준을 나중에" 두 번 정렬한다.
# 예: 점수 오름차 + 이름 내림차 (사전 반대 방향)
students = [("철수", 80), ("영희", 80), ("민수", 70)]
# 1단계: 덜 중요한 기준 먼저 — 이름 내림차
temp = sorted(students, key=lambda x: x[0], reverse=True)
# → [('철수', 80), ('영희', 80), ('민수', 70)]
# 2단계: 더 중요한 기준 나중 — 점수 오름차
result = sorted(temp, key=lambda x: x[1])
# → [('민수', 70), ('철수', 80), ('영희', 80)]
# 점수 오름차 ✓, 동점은 이름 내림차(철 > 영) ✓정리표:
| 상황 | 쓸 수 있는 방법 |
|---|---|
| 모든 기준이 같은 방향 | reverse=True 하나로 해결 |
| 숫자 기준 방향이 섞임 | -x 부호 뒤집기 (오늘 푼 문제) |
| 문자열 기준 방향이 섞임 | 2단계 정렬 (stable sort 활용) |
COS Pro 1급에서 문자열 내림차 + 다른 기준 조합은 빈도가 낮다. 실전 빈출은 점수 내림 + 이름 오름 쪽이라 오늘 푼 (-x[1], x[0]) 패턴이 훨씬 자주 나온다. 2단계 정렬은 "이런 카드도 있다" 정도로 알아두면 충분하다.
5) 그리디 (Greedy) 개념 정립
수업 중 질문: "끝내기 전에 이미 내가 한 적 있다던 그리디에 대해
정리하고 가자. 문제 풀 건 아니고 개념 → 예시 문제 → 바로 풀이법 설명까지.
내가 푼 적 있는 문제면 더 좋고."한 문장 정의:
"매 순간, 지금 당장 가장 좋아 보이는 선택을 한다."
- 전체 경로를 미리 고민하지 않고 지역 최적(local optimal) 을 고른다.
- 이 선택들을 쌓은 결과가 전체 최적(global optimal) 과 일치하는 문제에서만 그리디로 풀 수 있다.
이미 푼 예시: 프린터 우선순위
문제 요약: 대기열에 있는 문서들에 각자 우선순위가 있다. 큐 맨 앞 문서를 꺼냈을 때, 뒤에 더 높은 우선순위가 남아있으면 그 문서를 맨 뒤로 보낸다. 없으면 인쇄한다.
입력 예: priorities = [2, 1, 3, 2], 내 문서 위치 = 2 → 출력: 1
왜 이게 그리디냐:
"현재 대기열에서 우선순위가 가장 높은 문서부터 먼저 인쇄한다."
지금 남아있는 것 중 제일 큰 것을 처리하면 된다 — 이게 곧 탐욕 규칙.
from collections import deque
def solution(priorities, location):
queue = deque((i, p) for i, p in enumerate(priorities))
count = 0
while queue:
idx, pri = queue.popleft()
if queue and max(p for _, p in queue) > pri:
queue.append((idx, pri)) # 더 큰 거 있으니 뒤로
else:
count += 1
if idx == location:
return countmax(...) > pri 로 "지금 가장 높은 게 뭐냐" 를 묻는 부분이 그리디의 핵심이다.
그리디가 항상 맞는 건 아니다 (중요)
반례: 동전 [1원, 4원, 5원] 으로 8원 만들기
| 전략 | 선택 | 동전 개수 |
|---|---|---|
| 그리디 (큰 거부터) | 5 + 1 + 1 + 1 | 4개 |
| 최적 | 4 + 4 | 2개 |
그래서 그리디를 선택하기 전에 "이 전략이 정말 전체 최적과 일치하는가?" 를 한 번 점검해야 한다. 애매하면 DP 영역으로 넘어가야 한다.
다행히 COS Pro 1급 수준의 그리디는 대부분 "정렬 후 순서대로 집어먹기" 패턴으로 해결되어 복잡한 증명 없이 접근 가능하다. 그래서 그리디 문제에는 거의 항상 sorted() 가 등장한다.
대표 유형 (이름만 기억)
| 유형 | 한 줄 설명 |
|---|---|
| 거스름돈 문제 | 큰 동전부터 최대한 사용 |
| 회의실 배정 | 끝나는 시간 빠른 것부터 선택 |
| 구명보트 문제 | 가장 무거운 사람 + 가장 가벼운 사람 짝짓기 |
이미 가진 그리디 감각
- 17차·19차 프린터 우선순위 — 19차에선
(인덱스, 우선순위)튜플을 힌트 없이 스스로 설계 - 20차 점수 순 정렬 — "가장 좋은 것부터" 사고방식은 그리디와 결이 같음
용어만 몰랐을 뿐 감각은 이미 있다. 앞으로 문제에서 "가장 ~한 것부터" 라는 키워드가 보이면 "그리디 + 정렬" 을 먼저 떠올리면 된다.
오늘의 결과
- 푼 문제 3문제 (enumerate / zip / 튜플 정렬 빈칸 채우기), 1차 정답률 100%
- 20차 자기 진단 약점 "초기값 세팅 깜빡" — 문제 2에서 힌트 없이 직접 세팅하여 개선 확인
- 다음 학습: 이진 탐색 + 수학(소수/GCD/LCM) 진입
