BOJ 풀이 노트: 그리디 수식 처리와 플로이드-워셜 점검
· tech
BOJ 1541, 1389 두 문제를 문제 핵심 요약, 접근 이유, 복잡도, 실수 포인트, 코드 핵심 라인과 함께 실전형으로 정리한 글.
오늘은 문자열 수식 그리디 1문제와 그래프 최단거리 1문제를 묶어서 풀었다.
- BOJ 1541 - 잃어버린 괄호
- BOJ 1389 - 케빈 베이컨의 6단계 법칙
둘 다 구현 자체는 길지 않지만, “왜 이 선택이 맞는지”를 분명히 잡아두면 재사용하기 좋다.
1) BOJ 1541 - 잃어버린 괄호
문제 핵심 요약
수식에 괄호를 적절히 쳐서 결과값을 최소로 만들어야 한다.
연산자는 +, -만 나오며 숫자는 자연수 형태다.
접근 아이디어(왜 이 방법인지)
핵심 관찰은 단 하나다.
첫 -가 나온 뒤의 모든 수는 최대한 빼는 게 이득이다.
예를 들어 55-50+40은 55-(50+40)로 묶을 때 최소가 된다.
즉,
- 수식을 숫자/연산자로 파싱하고
- 첫
-전까지는 더하고 - 첫
-이후는 전부 빼면 된다.
괄호를 실제로 만들 필요 없이, 상태 플래그(subtractMode)만으로 처리 가능하다.
시간/공간 복잡도
- 시간:
O(L)(L=수식 길이) - 공간:
O(L)(숫자/연산자 저장)
실수하기 쉬운 포인트
- 마지막 숫자를 루프 밖에서
push하지 않으면 누락된다. -를 한 번 만난 뒤 다시+가 나와도 계속 빼야 한다.- 자릿수 누적(
current = current * 10 + digit)을 빼먹으면 두 자리 이상 숫자에서 오답이 난다.
C++ 코드 설명(핵심 라인)
if (ops[i] == '-') subtractMode = true;
if (subtractMode) answer -= nums[i + 1];
else answer += nums[i + 1];- 첫
-이후를 통째로 “빼기 구간”으로 고정하는 핵심 로직이다.
if (isdigit(ch)) {
current = current * 10 + (ch - '0');
}- 문자열 기반 숫자 파싱의 기본. 자릿수 처리 정확도가 중요하다.
다른 풀이 가능성
- 기준으로 문자열을 먼저 split한 뒤, 각 덩어리 안의 + 합을 계산해
첫 덩어리는 더하고 나머지는 빼는 방식도 많이 쓴다.
개인적으로는 현재 풀이처럼 단일 스캔 + 상태 전환이 디버깅이 쉽다.
2) BOJ 1389 - 케빈 베이컨의 6단계 법칙
문제 핵심 요약
사람 간 친구 관계 그래프에서, 각 사람의 “다른 사람까지의 최단거리 합”을 계산한다. 그 합(케빈 베이컨 수)이 가장 작은 사람 번호를 출력하면 된다.
접근 아이디어(왜 이 방법인지)
노드 수(N)가 크지 않은 전형적인 케이스라, 모든 쌍 최단거리를 한 번에 구하는
플로이드-워셜이 구현/검증 측면에서 가장 안정적이다.
dist[i][j]를 무한대로 초기화- 자기 자신은 0, 친구 관계는 1
- 중간 노드
k를 거쳐 갱신
이후 각 i에 대해 sum(dist[i][j])를 구해 최소값을 고르면 된다.
동점이면 문제 조건상 작은 번호가 유리하므로, score < bestScore일 때만 갱신하면 된다.
시간/공간 복잡도
- 시간:
O(N^3) - 공간:
O(N^2)
실수하기 쉬운 포인트
INF를 너무 크게 잡고 덧셈할 때 오버플로를 유발하지 않도록 주의해야 한다.- 자기 자신 거리(
dist[i][i] = 0) 초기화를 빼먹으면 합산 결과가 깨진다. - 동점 처리에서
<=를 쓰면 뒤 번호로 덮어써질 수 있다.
C++ 코드 설명(핵심 라인)
for (int k = 1; k <= N; ++k) {
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= N; ++j) {
if (dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}- 플로이드-워셜의 표준 3중 루프.
k를 중간 노드로 허용하며 거리 갱신을 누적한다.
if (score < bestScore) {
bestScore = score;
bestPerson = i;
}- 동점 시 작은 번호 유지 조건을 자연스럽게 만족하는 비교다.
다른 풀이 가능성
모든 시작점에서 BFS를 N번 돌리는 방식(O(N*(N+M)))도 가능하다.
이번 문제 크기에서는 둘 다 충분히 통과 가능하며,
구현 취향에 따라 BFS 다중 실행이 더 직관적일 수도 있다.
오늘 정리 포인트:
- 1541은 **관찰(첫
-이후는 모두 빼기)**이 핵심인 그리디. - 1389는 모든 쌍 최단거리 + 합산 비교를 깔끔히 구현하는 문제.
기본기 유형이라도 이런 문제를 짧게라도 기록해두면, 이후 구현 속도가 꽤 빨라진다.