앳코더 ABC 454 후기
tkd0711 · 2026. 4. 18.
Keysight Technologies Programming Contest (AtCoder Beginner Contest 454)
https://atcoder.jp/contests/abc454
- 날짜: 2026-04-18 (Sat)
- 결과: A~D AC (1025점)
- A: 0:48
- B: 4:20
- C: 18:21, 1틀
- D: 56:07, 1트
- 레이팅: 821
- 드디어 그린 달성
1. 전체 느낌
이번 대회는 결과도 좋았고, 체감도 좋았다.
A, B를 빠르게 처리했고,
C는 한 번 삽질하긴 했지만 방향을 바로 고쳐서 해결했다.
그리고 D를 결국 원트로 끝냈다.
무엇보다 이번 대회의 가장 큰 의미는
레이팅 821로 그린에 진입했다는 점이다.
그동안 회고를 쓰면서
문제 독해 실수, 자료형 실수, D에서 끝까지 못 정리하던 문제들을 계속 복기해왔는데,
이번에는 그 흐름이 실제 결과로 이어진 느낌이었다.
2. A, B – 안정적인 시작
A와 B는 비교적 무난하게 풀었다.
최근 대회들처럼 초반 문제는 안정적으로 처리되고 있고,
이번에도 A/B에서 크게 말리지 않았다.
ABC에서 중요한 건 초반 문제를 빠르게 넘기고 C, D에 사고 시간을 확보하는 건데,
이번에는 그 부분이 잘 됐다.
3. C – Straw Millionaire: 최대값 문제가 아니라 도달 가능 문제였다
문제 요약
처음에는 아이템 1만 가지고 있다.
각 친구에게 특정 아이템 A_i를 주면 B_i를 받을 수 있다.
이 과정을 반복해서 얻을 수 있는 아이템 종류 수를 구하는 문제였다.
처음 접근
처음에는
“한 번에 얻을 수 있는 최대값”처럼 생각해서 DFS로 접근했다.
그런데 이건 최적화 문제가 아니라,
사실상 1번 아이템에서 출발해서 도달 가능한 정점 수를 세는 문제였다.
그래프처럼 보면:
- 아이템 = 정점
A_i -> B_i= 간선
이 되고,
1번에서 갈 수 있는 곳의 개수를 세면 끝이었다.
왜 처음 DFS가 별로였는가
첫 DFS 구현에서는 방문 배열을 재귀가 끝날 때 다시 false로 돌리는 식으로 짰다.
이렇게 하면
같은 정점을 여러 경로에서 계속 다시 방문하게 되고,
문제 구조상 필요 없는 탐색이 많아진다.
그래서 이 문제는 백트래킹 DFS가 아니라,
- 한 번 방문한 정점은 다시 안 보고
- BFS나 일반 DFS로 퍼지는 식
으로 가야 했다.
최종 풀이
최종적으로는 BFS로 바꿨다.
- 시작점 1을 큐에 넣고
- 한 번 방문한 아이템은 다시 넣지 않고
- 도달 가능한 모든 정점을 탐색
이 방식으로 해결했다.
교훈
이번 C의 핵심은 이거였다.
“최대 몇 개를 얻을 수 있느냐”가 아니라
“1번에서 어디까지 갈 수 있느냐” 문제였다.
즉 경로를 따지는 문제로 보기보다,
그래프 탐색 문제로 보는 게 맞았다.
4. D – (xx): 막막했지만 형태를 줄여서 비교하는 문제였다
문제 요약
문자열 A와 B가 주어진다.
가능한 연산은:
(xx) -> xxxx -> (xx)
이 두 가지다.
이 연산을 반복해서 A를 B로 만들 수 있는지 판별하는 문제였다.
처음 느낌
처음엔 꽤 막막했다.
- 괄호를 그냥 다 지우면 되나?
- 올바른 괄호쌍처럼 봐야 하나?
xx를 기준으로 양옆을 봐야 하나?
이런 식으로 생각이 여러 방향으로 퍼졌다.
핵심 관찰
결국 이 문제의 핵심은xx를 중심으로 감싸진 괄호들은 있어도 되고 없어도 된다는 점이었다.
즉 (xx)는 xx와 같게 만들 수 있고,
그 바깥 괄호도 같은 식으로 계속 없앨 수 있다.
그래서 각 문자열에서
xx를 찾고- 거기서 좌우로
(,)가 짝을 이루며 감싸는 부분을 전부 표시해서 제거한 뒤 - 마지막에 남는 문자열 모양이 같은지만 보면 된다.
내 풀이
구현에서는:
- 문자열 안에서
xx를 찾고 - 그
xx를 중심으로 좌우를 확장하면서 - 지울 수 있는 괄호를 표시한 다음
- 두 문자열에서 그런 괄호를 다 제거하고
- 남는 문자 배열을 비교했다.
왜 맞는가
결국 이 연산으로 바뀔 수 있는 건xx를 둘러싼 괄호층뿐이다.
그래서 두 문자열이 같은 형태로 줄어들면 Yes,
아니면 No가 된다.
느낀 점
처음엔 막막했는데,
중간에
“괄호를 다 없애고 남는 모양을 보면 되는 거 아님?”
이 방향으로 간 게 핵심이었다.
완전히 정석 풀이를 처음부터 본 건 아니었지만,
구조를 잘 줄여서 원트로 마무리한 게 좋았다.
5. 이번 대회에서 좋았던 점
1) A/B가 안정적이었다
초반 문제에서 크게 흔들리지 않았다.
2) C에서 방향 교정이 빨랐다
처음엔 DFS로 잘못 접근했지만,
도달 가능 문제라는 걸 보고 바로 BFS로 바꿨다.
3) D를 원트로 끝냈다
시간은 56분 정도 걸렸지만,
방향을 잡은 뒤에는 한 번에 맞췄다.
4) 드디어 그린 달성
이번 대회의 가장 큰 성과는 결국 이거다.
레이팅 821로 그린에 진입했고,
그동안 쌓아온 회고와 복기가 실제 결과로 이어졌다는 점이 가장 만족스럽다.
6. 아쉬웠던 점
아쉬운 점이 아예 없는 대회는 아니었다.
1) C에서 처음 문제를 잘못 봤다
최대값 문제처럼 생각해서 DFS로 간 건 불필요한 우회였다.
2) D에 시간이 꽤 들었다
원트이긴 했지만, 막막한 구간이 길었다.
좀 더 빨리 구조를 정리했으면 더 좋았을 것 같다.
7. 다음 목표
- 그래프 문제에서
“최대/최적화”처럼 보여도 도달 가능 문제인지 먼저 보기 - 문자열 문제에서
직접 시뮬레이션하려 들기보다 줄였을 때 남는 핵심 형태가 무엇인지 먼저 생각하기 - D를 맞추는 것에서 끝나지 않고,
D를 더 빨리 정리할 수 있는 단계로 가기 - 그린 진입에 만족하지 않고,
이제는 그린을 안정적으로 유지하기
한 줄 정리
ABC 454는 A~D를 모두 해결했고,
C에서 방향을 바로 고쳐 잡고 D를 원트로 끝내면서 결국 그린까지 달성한 대회였다.