코테 문풀

paramad·2026년 2월 27일

코딩테스트

목록 보기

1/2

프롬프트-

해당 문제의 링크를 줄테니 문제를 읽고 다음과 같이 정리
- 문제를 한 줄로 요약
- 문제의 조건을 기재하고, 어떤 부분이 중요한지도 체크
- 문제의 유형이 뭐고, 이 문제를 풀 때 핵심이 되는 키워드
- 내 코드의 개선점, 향후 개선점 (정답 코드 및 지금까지 나눈 대화를 이력으로 작성해줘)

모든 답안은 짧고 간결하게 줄글과 들여쓰기 형식으로 기재.

1197번 최소 스패닝 트리

제곧내. 최소 스패닝 트리를 구현하는 문제.

최소값을 기준으로 정렬하고, 유니온 파인드를 이용해 '사이클 여부'를 판단한다.
다만 계속 get_parent 함수를 반복하다보면 재귀 제한이 걸릴 수도 있음.
- 이 경우 경로 압축 로직이 필요함.

# 일반적인 get_parent
def get_parent(x):
	if parent[x] != x:
    	parent[x] = get_parent(parent[x])
    return parent[x]

# 경로 압축
def get_parent(x):
    curr = x # x의 부모를 일단 먼저 구함
    while parent[curr] != curr:
        curr = parent[curr]
    
    # 여기가 핵심! 지나가는 길목을 쫙 다 부모(curr)로 깔아버림
    while parent[x] != curr:
        nxt = parent[x]
        parent[x] = curr
        x = nxt
        
    return curr

1238번 파티

$N$ 명의 학생이 각자의 집에서 목적지 $X$ 에 갔다가 다시 자기 집으로 돌아오는 경로 중, 가장 오래 걸리는 학생의 소요 시간을 구하는 문제.

유형: 그래프 이론, 최단 경로(Dijkstra) 알고리즘.
포인트: $A \to B$ 와 $B \to A$ 의 소요 시간이 다를 수 있음.

자기 집으로 돌아가는 거야 목적지 X에서 다익스트라를 돌리면 될 일이지만, N명이 학생이 각자 출발지에서 X로 가는 가장 빠른 '최단 거리'를 구하는 방식을 어떻게 구하는지 관건이다. 일반적인 다익스트라 문제인 줄 알았으나, 시간을 획기적으로 줄이는 '역방향 그래프'에 대한 단서가 숨겨져 있던 문제. 일반적인 거리 정보를 담은 리스트 roads와 이를 거꾸로 담은 rev_roads를 만들고, X에서 다익스트라를 출발하면 오히려 각자 출발해 X에 도착할 때 가장 빠른 경로가 저장된다는 충격적인 사실...

본래 방법은 $N$ 명의 학생이 있을 때 $N-1$ 번 다익스트라를 돌려야 했겠지만, 이 방식대로라면 단 2번만에 값을 구할 수 있다.

1463번 1로 만들기

주어진 정수 n에 세 가지 연산을 적절히 사용하여 1을 만드는 데 필요한 최소 연산 횟수를 구하는 문제

'내려가기' 풀고 벽 느껴서 DP 문제 차례차례 독파하기로 결정...
절대 BFS로 풀지마 (풀 수는 있지만) → 'DP적 사고' 스스로 계속 인지하기
- 처음에는 미리 배열을 만들어두고 deque로 채우는 방식을 했음
$dp[i/3], dp[i/2], dp[i-1]$ 로 깔끔하게 점화식을 채울 수 있다

1644번 소수의 연속합

자연수 $N$ 이 주어졌을 때, 하나 이상의 연속된 소수의 합으로 $N$ 을 나타낼 수 있는 경우의 수를 구하는 문제

N이 400만이라는 점을 잘 봐야 한다.
- 관건은 두 개, 소수를 빠르게 구해야 하고, 그 소수 내 리스트에서 연속합을 효율적으로 탐색할 수 있느냐.
- 후자는 투 포인터로 구현이 가능하지만, 전자는 '에라스토테네스의 체'를 필수적으로 사용해야 한다.
  - 슬라이싱 일괄 대입이 획기적 아이디어
  - 내 경우에는 그냥 sum(prime[start:end+1])로 합을 구했지만, 실제로는 굉장히 위험한 방식이다. 연속합을 만드는게 베스트.

# 슬라이싱 일괄 대입
for i in range(2, n+1):
    if is_prime[i]:
        prime.append(i)
        is_prime[i*i : n+1 : i] = [False] * len(range(i*i, n+1, i))
        
# 예시: 0부터 10까지 리스트에서 2의 배수 자리를 모두 False로 바꾸기
nums = [True] * 11
# 인덱스 4, 6, 8, 10 (2의 배수들) 선택
nums[4:11:2] = [False] * 4 
# 결과: [True, True, True, True, False, True, False, True, False, True, False]

1753번 최단 거리

방향 그래프가 주어졌을 때, 시작 노드에서 다른 모든 노드로 가는 최단 경로의 길이를 각각 구하는 문제
모든 간선의 가중치는 10 이하의 자연수 (음수 가중치가 없으므로 다익스트라 사용 가능)
서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수 있음에 유의해야 합니다. (최단으로 갱신해줘야 함)

그냥 다익스트라 문제였음. 제발 손으로 먼저 풀어!!
- 나는 당연히 BFS인줄 알고 또 한참을 헤맸다. 1916번에서 배운 점도 없었나...
- 큐를 쓰고, 방문 기록을 체크하는 BFS는 메모리 초과에 엄청 취약하다
매 단계마다 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택하기 위해 우선순위 큐(Priority Queue)를 사용

1916번 최소비용 구하기

N개의 도시와 M개의 버스 노선이 주어질 때, 특정 출발 도시에서 도착 도시까지 가는 최소 버스 비용을 계산하는 문제

가중치 양수 + 단일 출발점의 최단 거리 → 다익스트라 바로 갈겼어야 하는 문제
- 여기에 우선순위 큐까지 사용하면 시간을 더 단축할 수 있었다.
사실 조건만 봐도 다익스트라로 풀 수 밖에 없는 문제였다. 조건 보면서 하나씩 지워가보면 된다
- 애초에 N 크기가 1,000이 넘어가니 플로이드 워셜 (X)
- 최단 거리가 아닌 최소 비용인데다, visited()로 한 번 간 곳은 다시 안 가기 때문에 최소 비용 갱신이 불가능한 BFS (X)
- 그렇다고 모든 경로 다 도는 DFS (X)

# 코스트를 먼저 높은 수로 다 채워 놓고
cost = [1e9 for _ in range(n+1)]

# 시작점에서 출발 (0으로 잡고)
heapq.heappush(q, (0, start))
cost[start] = 0

# 이후 heapq 돌면서 하나씩 제끼면 된다
while q:
    c1, now = heapq.heappop(q)
    # 애초에 들어온 값이 아예 커버리면 계산도 패스
    if cost[now] < c1:
        continue

	# 지금 경로 + 앞으로 갈 경로가 더 작으면 갱신
    for c2, next in graph[now]:
        c = c1 + c2
        if c < cost[next]:
            cost[next] = c
            heapq.heappush(q, (c, next))

print(cost[end])

2096번 내려가기

N*3 격자 위에서 인접한 칸으로만 이동하며 내려갈 때, 얻을 수 있는 점수의 최댓값과 최솟값을 구하는 문제

슬라이딩 윈도우: N이 최대 10만이지만 메모리 제한이 4MB로 매우 적으므로, 모든 데이터를 저장하지 않고 이전 줄과 현재 줄의 결과값만 유지해야 함.
상태 전이 점화식: 현재 칸(j)으로 올 수 있는 이전 줄의 칸(j-1, j, j+1)들 중 최대/최소값을 선택하여 현재 칸의 점수와 더해나가는 방식의 DP 사용. (이건 걍 DP를 많이 풀어봐야 알 수 있는 감각적인 부분인듯)
이렇게 N이 겁나 많은 경우에는 무조건 sys.stdin.readline()을 때려박아야 한다. (10배나 줄어드는 상황)

2239번 스도쿠

빈칸을 백트래킹으로 쫓아가면서 하나씩 값을 넣어보고, 아니면 뒤로 돌아가는 문제.

백트래킹 구현도 구현이지만, 숫자를 놓을 때마다 행, 열, 박스를 매번 전체 탐색하면 시간이 너무 오래 걸린다는 걸 알아야 하는 문제.
방문 배열을 만들어 $O(1)$ 의 시간 복잡도로 유효성을 검사하는 것이 핵심이다 (일종의 인덱싱이랄까)

row_check = [[False] * 10 for _ in range(9)]
col_check = [[False] * 10 for _ in range(9)]
box_check = [[False] * 10 for _ in range(9)]

2467번 용액

정렬된 정수 배열에서 두 수를 더해 0에 가장 가까운 조합을 찾는 문제

양 끝에서 시작하여 합의 부호에 따라 포인터를 안쪽으로 이동시킨다.
- 중요한 점은, 높은 값을 무지성으로 1e9로 설정하면 큰일남! (이보다 더 클 수 있다)
- 앞으로는 float('inf')로 설정할 것.

2887번 행성 탈출

3차원 공간의 $N$ 개 행성을 최소 비용으로 모두 연결하는 문제

당연하게도 모든 행성을 전부 연결해 보고 최소 스패닝 트리를 구현하면 시간 초과 메모리 초과가 출력된다.
- 따라서, 문제에서 주어진 비용 계산식( $min(|xA-xB|, |yA-yB|, |zA-zB|)$ )을 잘 보고 연산 수를 줄였어야 함.
- 모든 행성 쌍( $N^2$ )을 검사하는 대신, 각 좌표축으로 정렬했을 때 바로 옆에 있는 행성들만 후보로 선정하는 방식
그래서 문제 유형에 최소 스패닝 트리 말고도 '정렬'이 있던 이유다

9202번 Boggle

$4 \times 4$ 보드판에서 인접한 8방향의 알파벳을 연결하여 주어진 단어 사전(최대 30만 개)에 존재하는 단어를 찾아 점수, 최장 단어, 찾은 단어 개수를 출력하는 문제.

조건이 매우 많다. (상하좌우 및 대각선을 포함한 8방향으로 이동하며 단어를 만들기 + 최장 단어를 출력할 때, 길이가 같은 단어가 여러 개라면 사전 순으로 앞서는 것을 선택 + 하나의 보드에서 같은 단어를 여러 번 찾을 수 있으나 점수는 한 번만 계산 등...)
우선 사전의 단어 수가 30만 개라는 점을 고려해 단순 문자열 비교가 아닌 트라이 자료구조를 사용해야 했던 문제.
- 트라이 문제는 대개 '적용' 선에서 그치는 것에 불과했는데, 이번 문제는 여러 알고리즘이 복합적으로 섞여 있다보니 구현 난이도가 꽤 상당했다.
처음에는 BFS로 풀었으나, 천천히 생각해보니 백트래킹으로 풀어야 했던 문제.
- 이유는 간단하다. 각 경로마다 방문한 칸이 다르기 때문에 큐에 지금까지 방문 기록 전체를 들고 다녀야 했기 때문. 최대 길이가 8이므로 재귀 단위가 매우 얇아 그냥 DFS(=백트래킹)로 풀었어도 무방했던 문제였다.
- 또한 단어를 찾았다고 해서 바로 return하는 게 아니라 계속 탐색해서 더 긴 단어를 놓치면 안됨.
- Gemini 친구는 여기서 보드판을 비트마스킹으로 방문 처리해 메모리와 속도를 비약적으로 개선하는 것을 권했지만... 이건 좀 어나더레벨 같은데...

11404번 플로이드

모든 도시 쌍( $n \times n$ ) 사이의 최단 거리를 구하는 전형적인 플로이드-워셜 알고리즘 문제

Python에서 min() 함수는 함수 호출 오버헤드가 있다. 차라리 이럴 때는 if 문을 사용하는 것이 실행 시간 단축에 도움이 된다.

(묘하게 빨라졌다)

13460번 구슬 탈출2

직사각형 보드 안에 빨간 구슬과 파란 구슬을 두고, 보드를 상하좌우로 기울여 빨간 구슬만 구멍(O)을 통해 빼내는 최소 횟수를 구하는 시뮬레이션 문제

핵심 키워드는 벽을 만날 때까지 이동 뿐만 아니라, 현재 칸이 구멍일 때까지 이동시키는 조건.
- while board[y + dy][x + dx] != '#' and board[y][x] != 'O':
- 나는 구멍 전까지 움직인 다음, 같은 방향으로 한 번 더 움직일 경우를 체크했는데, 이 경우 논리적 공백이 발생할 가능성이 있다고.
또한 빨간 구슬과 파란 구슬이 좌표가 겹칠 경우 '더 많이 이동한 구슬'을 하나 롤백시키는 로직 또한 매우 중요했다.