2회차 미션: 내 약점 파악과 목표 설정
이번 갭체크 진단 결과에서 나에게 부족한 개념은 Backtracking, 즉 완전탐색 II로 확인되었다.
정말 오래간만에 코드트리에 다시 접속하여 갭체크를 진행했다. 이전에는 나의 점수와 상대적인 나의 위치를 같이 그래프로 보여줬던 것 같은데, 사라져서 조금 아쉽다.
핵심 요약에서 “주어진 문제의 조건을 만족하는 모든 가능한 해를 탐색하기 위해 분기별 선택을 시도하고, 필요 시 이전 상태로 되돌아가는 백트래킹 알고리즘에 대한 이해가 필요하다”고 설명하고 있다.
완전탐색과 백트래킹은 DFS, BFS, DP 같은 더 고급 알고리즘으로 넘어가기 전에 반드시 익숙해져야 하는 기반 개념이라고 느꼈다.
이번 글에서는 내가 어떤 개념을 보완해야 하는지 먼저 정리하고, 앞으로 어떤 순서로 학습할지 목표를 세워보고자 한다.
1. 2차원 리스트를 만드는 방법
코딩테스트 문제에서는 격자판, 지도, 좌표, 행렬 형태의 입력이 자주 등장한다.
이때 가장 기본이 되는 자료구조가 2차원 리스트다.
예를 들어 N x N 크기의 빈 격자판을 만들고 싶다면 다음과 같이 작성할 수 있다.
N = int(input())
grid = [[0] * N for _ in range(N)]예를 들어 N = 3이면 다음과 같은 구조가 만들어진다.
[
[0, 0, 0],
[0, 0, 0],
[0, 0, 0]
]입력으로 주어진 격자 값을 저장할 때는 다음과 같이 작성한다.
N = int(input())
grid = [list(map(int, input().split())) for _ in range(N)]예를 들어 입력이 다음과 같다면:
3
7 10 9
2 8 7
11 9 0grid에는 다음 값이 저장된다.
[
[7, 10, 9],
[2, 8, 7],
[11, 9, 0]
]문자 격자판이 필요한 경우에는 다음처럼 만들 수 있다.
N = int(input())
grid = [['.'] * N for _ in range(N)]2차원 리스트는 완전탐색, DFS, BFS, 시뮬레이션 문제의 기본이 되므로 먼저 익숙해질 필요가 있다.
2. 방향 배열과 dx, dy 개념
격자 이동 문제에서는 방향 배열을 자주 사용한다.
예를 들어 동, 남, 서, 북 순서라면 다음과 같이 작성할 수 있다.
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]| 방향 | dx | dy |
|---|---|---|
| E | 0 | 1 |
| S | 1 | 0 |
| W | 0 | -1 |
| N | -1 | 0 |
만약 위와 같이 문자 N, S, E, W에 따라 이동해야 한다면 딕셔너리를 사용하는 것이 더 직관적이다.
move = {
'N': (-1, 0),
'S': (1, 0),
'E': (0, 1),
'W': (0, -1)
}
direction = input()
dx, dy = move[direction]3. 완전탐색과 백트래킹 개념 부족
이번 진단 결과에서 가장 핵심적으로 부족하다고 나온 개념은 Backtracking이다.
백트래킹은 완전탐색의 한 종류다.
가능한 모든 경우를 탐색하되, 조건에 맞지 않는 경우는 더 이상 탐색하지 않고 되돌아간다.
즉, 백트래킹의 핵심은 다음 세 가지다.
- 선택한다.
- 다음 단계로 이동한다.
- 조건에 맞지 않으면 되돌아간다.
내가 제출하지 못했던 문제를 AI와 함께 다시 풀어보자. 1번부터 2N번까지의 용액 중 N개를 골라서 만들 수 있는 음료수 개수를 최대화하는 문제 이다.
이 문제는 다음과 같이 이해할 수 있다.
전체 용액은
2N개 있다.
그중 정확히N개만 고를 수 있다.
각 음료수는 두 용액(A_i, B_i)가 모두 있어야 만들 수 있다.
어떤 용액 N개를 골라야 가장 많은 음료수를 만들 수 있는가?
예제에서는 N = 3이므로 총 용액은 1 ~ 6까지 6개다.
이 중 3개를 골라야 한다.
예를 들어 {1, 2, 4}를 고르면 다음 음료수를 만들 수 있다.
1번 음료수: 1 + 1 → 가능
2번 음료수: 1 + 2 → 가능
5번 음료수: 2 + 4 → 가능총 3개를 만들 수 있다.
처음에 문제가 잘 이해가 안갔고, 단순 반복문으로 접근하려 했으나 실패했다.
왜냐하면 “2N개 중 N개를 고르는 모든 조합”을 확인해야 하기 때문이다.
이때 필요한 개념이 바로 조합 탐색이고, 이를 직접 구현하는 방식 중 하나가 백트래킹이다.
4. 백트래킹의 기본 코드 구조
백트래킹은 보통 다음과 같은 형태를 가진다.
def backtrack(start):
if len(selected) == N:
# 선택이 완료된 상태에서 정답 계산
return
for i in range(start, 2 * N + 1):
selected.append(i)
backtrack(i + 1)
selected.pop()여기서 중요한 부분은 selected.pop()이다.
append()로 선택한 값을 넣고, 재귀 호출이 끝나면 다시 pop()으로 제거한다.
이 과정을 통해 이전 상태로 되돌아갈 수 있다.
즉, 백트래킹은 단순히 재귀를 쓰는 것이 아니라,
선택 → 탐색 → 선택 취소
의 흐름을 명확히 구현하는 것이다.
조합을 만드는 기본 예시는 다음과 같다.
N = 5
M = 3
selected = []
def backtrack(start):
if len(selected) == M:
print(selected)
return
for i in range(start, N + 1):
selected.append(i)
backtrack(i + 1)
selected.pop()
backtrack(1)이 코드는 1부터 5까지의 수 중에서 3개를 고르는 모든 경우를 출력한다.
예상 출력은 다음과 같다.
[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 3, 4]
[1, 3, 5]
[1, 4, 5]
[2, 3, 4]
[2, 3, 5]
[2, 4, 5]
[3, 4, 5]여기서 핵심은 start다.
start를 사용하면 이미 선택한 숫자보다 작은 숫자를 다시 고르지 않게 만들 수 있다.
즉, 중복 조합을 방지할 수 있다.
5. 완전탐색과 백트래킹의 차이
완전탐색은 가능한 모든 경우를 하나씩 확인하는 방식이다.
예를 들어 리스트에서 두 수를 고르는 문제라면 다음처럼 작성할 수 있다.
arr = [1, 2, 3, 4]
for i in range(len(arr)):
for j in range(i + 1, len(arr)):
print(arr[i], arr[j])이 코드는 모든 두 수의 조합을 확인한다.
하지만 선택해야 하는 개수가 많아지거나, 선택 과정 중 조건 판단이 필요한 경우에는 반복문이 복잡해진다.
예를 들어 N개 중 M개를 고르는 문제에서 M이 고정되어 있지 않거나, 문제마다 달라진다면 중첩 반복문만으로는 대응하기 어렵다.
이때 백트래킹을 사용하면 선택 개수와 조건을 유연하게 처리할 수 있다.
| 구분 | 설명 |
|---|---|
| 완전탐색 | 가능한 모든 경우를 확인 |
| 백트래킹 | 모든 경우를 탐색하되, 선택과 취소를 반복하며 조건에 맞는 경우를 찾음 |
| 가지치기 | 더 볼 필요 없는 경우를 중간에 중단 |
백트래킹은 완전탐색을 기반으로 하지만, 재귀와 상태 복구를 활용한다는 점에서 한 단계 더 어렵다.
6. 음료수 문제를 백트래킹 관점으로 이해하기
앞에서 본 음료수 문제는 백트래킹 연습에 적합한 문제다.
문제를 다시 정리하면 다음과 같다.
전체 용액: 1번부터 2N번까지
구매 가능 개수: 정확히 N개
음료수 개수: K개
각 음료수: 두 용액 Ai, Bi가 모두 있어야 만들 수 있음
목표: 만들 수 있는 음료수 개수의 최댓값예제 입력은 다음과 같다.
3
6
1 1
1 2
2 3
4 5
2 4
5 6여기서 N = 3이므로 용액은 총 6개다.
1, 2, 3, 4, 5, 6이 중 정확히 3개를 골라야 한다.
가능한 선택 중 하나는 다음과 같다.
1, 2, 4이때 만들 수 있는 음료수는 다음과 같다.
1번 음료수: 1 1 → 가능
2번 음료수: 1 2 → 가능
3번 음료수: 2 3 → 불가능
4번 음료수: 4 5 → 불가능
5번 음료수: 2 4 → 가능
6번 음료수: 5 6 → 불가능총 3개를 만들 수 있다.
이 문제를 풀기 위해서는 다음 과정을 생각할 수 있다.
1. 1번부터 2N번까지의 용액 중 N개를 고른다.
2. 선택한 용액 집합으로 만들 수 있는 음료수 개수를 센다.
3. 그중 최댓값을 저장한다.이를 백트래킹 코드로 표현하면 대략 다음과 같다.
N = int(input())
K = int(input())
drinks = [tuple(map(int, input().split())) for _ in range(K)]
selected = []
answer = 0
def count_drinks():
selected_set = set(selected)
count = 0
for a, b in drinks:
if a in selected_set and b in selected_set:
count += 1
return count
def backtrack(start):
global answer
if len(selected) == N:
answer = max(answer, count_drinks())
return
for i in range(start, 2 * N + 1):
selected.append(i)
backtrack(i + 1)
selected.pop()
backtrack(1)
print(answer)이 코드는 다음 흐름으로 동작한다.
1. 용액 하나를 선택한다.
2. 다음 용액을 선택하러 재귀 호출한다.
3. N개를 모두 선택하면 만들 수 있는 음료수 개수를 계산한다.
4. 계산이 끝나면 마지막 선택을 취소한다.
5. 다른 선택지를 다시 탐색한다.이 구조를 이해하면 “N개 중 M개 고르기”, “조건을 만족하는 조합 찾기”, “선택한 조합의 점수 최댓값 구하기” 같은 문제를 풀 수 있다.
7. 앞으로 학습해야 할 개념
이번 진단 결과와 문제 풀이 과정을 기준으로 보면, 우선순위는 다음과 같다.
첫 번째: 2차원 리스트 생성과 입력 처리
코딩테스트에서는 입력을 올바르게 저장하는 것이 문제 풀이의 시작이다.
특히 격자판 문제에서는 2차원 리스트를 자연스럽게 만들 수 있어야 한다.
학습할 내용은 다음과 같다.
| 개념 | 학습 목표 |
|---|---|
| 빈 2차원 리스트 생성 | [[0] * N for _ in range(N)] 형태 익히기 |
| 입력 기반 2차원 리스트 생성 | [list(map(int, input().split())) for _ in range(N)] 형태 익히기 |
| 잘못된 생성 방식 이해 | [[0] * N] * N의 참조 공유 문제 이해하기 |
| 문자 격자 생성 | [['.'] * N for _ in range(N)] 형태 익히기 |
| 리스트 접근 | grid[i][j] 방식에 익숙해지기 |
두 번째: 방향 배열과 격자 이동
DFS, BFS, 시뮬레이션 문제에서는 특정 위치에서 상하좌우로 이동하는 경우가 많다.
이때 dx, dy 배열을 사용하면 반복문으로 이동을 처리할 수 있다.
학습할 내용은 다음과 같다.
| 개념 | 학습 목표 |
|---|---|
| 방향 배열 | dx, dy를 이용해 상하좌우 이동 구현 |
| 문자 방향 처리 | N, S, E, W를 딕셔너리로 매핑 |
| 다음 위치 계산 | nx = x + dx, ny = y + dy 구조 익히기 |
| 범위 체크 | 격자 밖으로 나가지 않는 조건 작성하기 |
세 번째: 백트래킹
백트래킹은 완전탐색보다 한 단계 더 어렵다.
모든 경우를 탐색하지만, 재귀와 상태 복구가 들어가기 때문이다.
학습할 핵심은 다음이다.
| 개념 | 설명 |
|---|---|
| 재귀 함수 | 자기 자신을 호출하는 함수 |
| 종료 조건 | 더 이상 탐색하지 않고 멈추는 조건 |
| 선택 | 현재 단계에서 하나를 고르는 것 |
| 상태 복구 | 선택했던 것을 되돌리는 것 |
| 가지치기 | 불가능한 경우를 더 탐색하지 않는 것 |
가장 먼저 연습할 문제 유형은 다음과 같다.
1. N개 중 M개 고르기
2. 순열 만들기
3. 조합 만들기
4. 조건을 만족하는 조합 개수 세기
5. 선택한 조합으로 점수 최대화하기8. 마무리, 차주 청약 목표
이번 갭체크 결과를 통해 내가 부족한 부분은 Backtracking, 즉 완전탐색 II 영역이라는 점을 확인했다.
백트래킹은 문제에서 가능한 선택지를 나누고, 각각의 경우를 탐색하며, 조건에 맞는 최적의 답을 찾는 사고방식에 가깝다.
따라서 차주 청약 과정에서는 다음 부분을 집중적으로 개선하고자 한다.
- 2차원 리스트 입력과 생성에 익숙해지기
- 방향 배열을 활용한 격자 이동 문제 연습하기
- 완전탐색 문제에서 모든 경우를 빠짐없이 확인하기
- 백트래킹 문제에서 선택과 복구 흐름을 익히기
- 조합 탐색 문제를 직접 구현할 수 있도록 연습하기이번 과정에서는 단순히 문제를 많이 푸는 것보다, 문제를 풀고 난 뒤 다음 내용을 반드시 정리하는 방식으로 학습하려고 한다.
1. 이 문제는 어떤 유형인가?
2. 어떤 선택지가 존재하는가?
3. 모든 경우를 어떻게 탐색할 수 있는가?
4. 반복문으로 가능한가, 재귀가 필요한가?
5. 백트래킹을 쓴다면 종료 조건은 무엇인가?
6. 선택 후 어떤 상태를 복구해야 하는가?구체적으로는 다음과 같은 코드를 막힘없이 작성할 수 있는 것을 목표로 한다.
def backtrack(start):
if len(selected) == M:
print(selected)
return
for i in range(start, N + 1):
selected.append(i)
backtrack(i + 1)
selected.pop()이 구조를 정확히 이해하면 조합 문제뿐 아니라, 조건을 만족하는 선택 문제, 최대값/최소값 탐색 문제, DFS 기반 탐색 문제로 확장할 수 있다.
커리큘럼 중 IL (알고리즘 입문) 백트래킹을 시작으로 IL을 학습하는것이 이번 코드트리 청약 이벤트의 1차 목표가 될 것 같다.
해당 게시글을 읽고 무료로 코드트리 청약 이벤트에 합류하고 싶다면 해당 코드트리 링크를 클릭하면 된다.
