앳코더 ABC 451 후기
tkd0711 · 2026. 3. 28.
AtCoder Beginner Contest 451
https://atcoder.jp/contests/abc451
- 날짜: 2026-03-28 (Sat)
- 결과: A~D AC
- C: 우선순위 큐로 해결
- D: DFS 완전생성으로 해결
1. 전체 느낌
이번 대회는 전체적으로 A~D까지 해결했다.
특히 D는 처음에는 시간복잡도에 확신이 없어서 “이게 되나?” 싶은 상태로 제출했는데, 결과적으로는 통과했다.
이번 대회에서 인상적이었던 건 두 가지였다.
- C는 아이디어가 직관적이어서 비교적 빠르게 정리된 문제
- D는 브루트포스처럼 보이는 풀이를 실제로 밀어붙였는데, 생각보다 충분히 가능한 범위였던 문제
최근 회고들에서 자주 나왔던
문제 독해 실수, 자료형 실수, 구현 디테일 실수 같은 것보다는
이번엔 아이디어를 잡은 뒤 그걸 끝까지 밀어붙이는 감각이 조금 더 좋았던 대회였다.
2. A, B – 비교적 무난한 진행
A와 B는 큰 사고 없이 처리했다.
요즘은 A, B에서 시간을 많이 쓰는 경우는 많이 줄었고,
이번 대회도 초반 흐름 자체는 비교적 안정적이었다.
결국 ABC에서 중요한 건
A, B를 빠르게 넘기고 C, D에 사고 시간을 확보하는 건데,
이번에는 그 부분이 어느 정도 잘 됐다.
3. C – Understory: 우선순위 큐로 깔끔하게 처리
문제 요약
처음에는 정원에 나무가 하나도 없다.
쿼리는 두 종류:
1 h: 높이h인 나무 하나 추가2 h: 현재 정원에 있는 나무 중 높이가h이하인 나무를 전부 제거
그리고 매 쿼리 직후 정원에 남아 있는 나무 수를 출력하면 된다.
처음 생각
처음 문제를 읽고 나서 든 생각은 단순했다.
- 삽입이 있고
- 작은 값부터 한꺼번에 삭제해야 하니까
- 최소 힙(PriorityQueue)으로 관리하면 되지 않을까?
실제로도 그 방향이 맞았다.
풀이 아이디어
1 h가 들어오면 min-heap에h를 넣는다.2 h가 들어오면 heap의 top이h이하인 동안 계속 꺼낸다.- 매 쿼리마다 heap의 size를 출력한다.
핵심은
삭제 쿼리에서 while이 들어가니까 느리지 않을까 싶을 수 있는데,
각 나무는:
- 한 번 삽입되고
- 많아야 한 번 삭제된다.
즉 전체적으로 poll() 횟수 총합이 최대 Q번이다.
그래서 시간복잡도는 전체 기준으로
- 삽입:
O(Q log Q) - 삭제: 총합
O(Q log Q)
정도로 충분히 통과 가능하다.
느낀 점
이 문제는 자료구조 선택만 바로 하면 깔끔하게 풀리는 문제였다.
괜히 TreeSet이나 복잡한 구조를 생각하기보다,
“현재 가장 작은 값부터 필요할 때 제거한다”는 문제 구조를 보고
우선순위 큐를 떠올리면 되는 유형이었다.
이런 문제에서 자료구조를 과하게 잡지 않고
가장 단순한 해법으로 가는 것도 중요하다고 느꼈다.
4. D – Concat Power of 2: 완전생성이 실제로 되는 문제
문제 요약
다음 조건을 만족하는 양의 정수를 good integer라고 한다.
- 2의 거듭제곱들 (
1, 2, 4, 8, 16, 32, ...) 중 하나 이상을 - 중복 및 순서 자유롭게 골라
- 문자열로 이어붙인 뒤
- 그 결과를 정수로 본 것
이렇게 만들 수 있는 수들을 오름차순으로 나열했을 때,
N번째 수를 구하는 문제였다.
그리고 조건상 N번째 good integer는 10^9 이하임이 보장된다.
처음 생각
처음에는 이게 정렬/탐색/수학 중 어느 쪽 문제인지 잘 감이 안 왔다.
그런데 조건을 보면
정답 자체가 10^9 이하, 즉 최대 9자리라는 게 핵심이었다.
그래서 생각한 방식은:
- 사용할 수 있는 조각은 2의 거듭제곱 문자열들
- 길이 9를 넘기지 않는 범위에서
- 가능한 모든 연결 문자열을 DFS로 생성
- 정수로 바꿔 set에 넣고
- 정렬된 순서에서 N번째를 꺼내기
였다.
처음에는 솔직히 시간복잡도에 확신이 없었다.
“이거 너무 많이 나오는 거 아니야?” 싶었는데, 일단 밀어붙였다.
실제로 왜 되는가
겉으로 보면 DFS가:
- 매번 여러 개의 조각을 붙일 수 있고
- 길이 9까지 확장되니까
굉장히 큰 탐색처럼 보인다.
하지만 실제로는:
- 최종 수가 9자리 이하로 제한되고
- 각 조각 길이도 1자리, 2자리, 3자리... 식으로 다양해서
- 가능한 유효 문자열 수가 생각보다 그렇게 많지 않다.
즉 이 문제는
무식하게 보이는 완전생성이 실제로 가능한 범위 안에 들어오는 문제였다.
구현 방식
코드는 대략 이런 흐름이었다.
2^0 ~ 2^30정도까지 미리 만들어둔다.- DFS로 문자열을 이어붙인다.
- 길이가 9를 넘으면 종료한다.
- 길이가 1 이상이면 정수로 바꿔 TreeSet에 넣는다.
- 마지막에 set을 리스트로 옮겨서 N번째를 출력한다.
코드상 특징
내 구현에서는 TreeSet<Integer>를 써서
- 자동으로 정렬되고
- 중복이 제거되도록 처리했다.
이 문제에서는 동일한 문자열 결과가 여러 방식으로 나와도
결국 같은 정수는 한 번만 세면 되므로 TreeSet이 자연스럽게 맞았다.
느낀 점
이 문제는 에디토리얼 없이 대회 중에 풀었을 때
“정말 이게 되는 건가?” 싶은 불안이 남는 유형이었다.
하지만 결국 중요한 건:
- 문제의 출력 범위가 실제로 얼마나 작은지
- 완전생성 후보가 진짜 몇 개나 되는지
- 제한이 브루트포스를 허용하는지
를 보는 것이다.
이번 D는 그 감각이 어느 정도 맞아떨어진 문제였다.
즉, 단순히 “브루트포스처럼 보인다 → 안 된다”가 아니라,
제한을 보고 실제 탐색 공간을 계산해보는 태도가 중요하다는 걸 다시 느꼈다.
5. 이번 대회에서 좋았던 점
1) C를 깔끔하게 처리
자료구조 선택이 빠르게 끝났고,
복잡한 방향으로 새지 않았다.
2) D를 끝까지 밀어붙인 것
처음엔 확신이 없었지만,
제한을 믿고 완전생성 방향을 끝까지 구현해서 해결했다.
3) 최근 자주 나오던 실수는 상대적으로 적었음
- 문제를 완전히 잘못 읽는 실수
- long을 놓치는 실수
- 자료구조 선택을 완전히 잘못하는 실수
이런 종류의 사고는 이번엔 비교적 덜했다.
6. 아쉬웠던 점
아쉬운 점이 전혀 없는 대회는 아니었다.
특히 D는 맞추긴 했지만,
대회 중에는 시간복잡도에 대한 확신이 부족해서
약간 “될 것 같아서 찍은” 느낌이 있었다.
즉, 풀이를 맞추긴 했지만
왜 이게 되는지 수치적으로 설명할 수 있는 확신은 부족했다.
이건 나중에 비슷한 문제를 다시 만났을 때
정신적으로 흔들릴 수 있는 부분이라서,
풀이가 맞았더라도 한번쯤 복기해볼 필요가 있다.
7. 다음 목표
- 브루트포스/완전생성 문제를 볼 때
“무조건 안 된다”가 아니라
실제 후보 수가 얼마나 되는지 계산해보기 - 자료구조 문제에서
가장 단순한 자료구조(PQ 등)로 충분한지 먼저 생각하기 - 맞춘 문제도
“왜 통과되는지”를 시간복잡도 관점에서 다시 설명해보기