앳코더 ABC 458 후기
tkd0711 · 2026. 5. 16.
AtCoder Beginner Contest 458
https://atcoder.jp/contests/abc458
- 날짜: 2026-05-16 (Sat)
- 결과: A~D AC, 1000점
- A: 1:25
- B: 5:42
- C: 13:25
- D: 33:07
- E: 미해결
1. 전체 느낌
이번 대회는 월요일 면접을 앞두고 참가했다.
사실 컨디션이나 일정상 너무 오래 붙잡고 있을 수는 없었고,
목표도 “끝까지 갈아 넣기”보다는 평소 루틴을 유지하는 쪽에 가까웠다.
결과는 A~D까지 해결해서 1000점.
시간도 D까지 33분 정도라 꽤 깔끔했다.
E는 끝까지 답이 떠오르지 않았지만,
면접 전날 무리해서 더 붙잡기보다는 적당히 끊는 게 맞다고 판단했다.
이번 대회는 전체적으로
A~D를 안정적으로 처리하고, E는 무리하지 않고 접은 대회였다.
2. A, B – 무난한 시작
A와 B는 크게 문제 없이 해결했다.
A는 1분대, B는 5분대에 처리했고,
초반 흐름은 괜찮았다.
최근 들어 A, B는 꽤 안정적으로 풀고 있고,
이번에도 큰 실수 없이 C로 넘어갈 수 있었다.
3. C – C Stands for Center: C를 가운데로 두고 세기
문제 요약
문자열 S가 주어지고,
다음 조건을 만족하는 부분문자열의 개수를 구하는 문제였다.
- 길이가 홀수
- 가운데 문자가
C
같은 문자열이라도 뽑힌 위치가 다르면 따로 센다.
접근
이 문제는 비교적 바로 보였다.
어떤 위치 i의 문자가 C라면,
그 문자를 가운데로 하는 홀수 길이 부분문자열을 세면 된다.
가운데가 C로 고정되어 있으므로
왼쪽과 오른쪽으로 같은 길이만큼 뻗을 수 있다.
즉,
- 왼쪽에 있는 문자 수:
i - 오른쪽에 있는 문자 수:
len - i - 1 - 가능한 개수:
min(왼쪽 개수, 오른쪽 개수) + 1
이다.
여기서 +1은 C 하나만 뽑는 경우다.
자료형
문자열 길이가 최대 50만이므로,
답이 커질 수 있다고 보고 long으로 처리했다.
요즘 계속 자료형에서 맞은 적이 있어서,
이번에는 처음부터 답 변수를 long으로 둔 점이 괜찮았다.
느낀 점
C는 조건을 직접 복잡하게 보지 않고,
“각 C를 가운데로 잡는다”로 바꿔서 보면 쉬운 문제였다.
이런 식으로 중심이 정해지는 문제는
각 위치를 기준으로 몇 개 만들 수 있는지를 세는 방향으로 보는 게 좋다는 걸 다시 확인했다.
4. D – Chalkboard Median: 예전에 푼 중앙값 문제가 도움이 됐다
문제 요약
처음 칠판에 정수 X가 하나 적혀 있고,
각 쿼리마다 정수 두 개를 추가한다.
그때마다 지금까지 칠판에 적힌 수들의 중앙값을 출력하는 문제였다.
항상 원소 개수는 홀수이므로 중앙값이 하나로 정해진다.
접근
이 문제는 예전에 백준에서 “중앙값 구하기” 유형을 풀어본 경험이 바로 떠올랐다.
매번 모든 수를 정렬하면 너무 느리다.
대신 우선순위 큐 두 개를 사용하면 된다.
- 작은 절반을 담는 큐
- 큰 절반을 담는 큐
작은 절반 쪽은 가장 큰 값이 위로 오게 하고,
큰 절반 쪽은 가장 작은 값이 위로 오게 한다.
그리고 작은 절반의 크기를 항상 큰 절반보다 하나 크게 유지하면,
작은 절반의 맨 위 값이 중앙값이 된다.
구현
내 코드에서는 이름이 조금 헷갈리긴 했지만, 역할은 다음과 같았다.
minpq: 작은 값들을 담는 쪽, 내림차순maxpq: 큰 값들을 담는 쪽, 오름차순
새 값이 들어올 때마다
현재 중앙값과 비교해서 알맞은 큐에 넣고,
두 큐의 크기를 다시 맞췄다.
그 뒤 minpq.peek()을 출력했다.
느낀 점
D는 이번 대회에서 가장 기분 좋게 풀린 문제였다.
처음 보는 유형이었다면 조금 헤맸을 수도 있는데,
전에 풀어본 중앙값 유지 문제가 바로 떠올라서 빠르게 접근할 수 있었다.
역시 예전에 풀어본 문제가 실전에서 바로 연결될 때가 있다.
이번 D는
이전에 풀었던 문제 경험이 실전에서 제대로 도움이 된 문제였다.
5. E – Count 123: 재귀로는 안 되는 문제였다
문제 요약
1, 2, 3으로 이루어진 수열을 만든다.
- 1은
X1개 - 2는
X2개 - 3은
X3개
정확히 사용해야 하고,
인접한 두 원소의 차이가 1 이하가 되어야 한다.
즉 1과 3은 바로 붙을 수 없다.
그런 수열의 개수를 구하는 문제였다.
처음 생각
처음에는 재귀로 생각했다.
현재까지 놓은 마지막 숫자를 보고,
다음에 1, 2, 3 중 가능한 것을 선택하는 방식이다.
하지만 X1, X2, X3가 최대 100만이므로,
이런 식의 재귀나 단순 메모이제이션으로는 절대 안 된다.
핵심 관찰까지는 갔다
그래도 문제를 보면서 하나는 보였다.
1과 3은 서로 바로 붙을 수 없고,
2가 둘 사이를 이어주는 역할을 한다.
즉 2가 완충 역할을 한다는 점이다.
하지만 여기서 더 나아가
정확한 조합식이나 세는 구조까지는 만들지 못했다.
왜 접었는가
월요일 면접을 앞두고 있었고,
이미 A~D를 33분 정도에 해결한 상태였다.
E를 더 붙잡으면 한참 더 고민해야 할 것 같았고,
그게 오늘의 목적과는 조금 다르다고 생각했다.
그래서 E는
“재귀로는 안 되고, 1과 3 사이에 2를 어떻게 배치할지를 세는 문제였을 것이다”
정도까지만 정리하고 멈췄다.
느낀 점
E는 못 풀었지만,
완전히 손도 못 댄 문제는 아니었다.
적어도
- 재귀는 안 된다
- 1과 3이 바로 붙을 수 없다는 게 핵심이다
- 2의 배치가 중요하다
까지는 봤다.
다만 아직 이런 조합 세기 문제는
정확한 식으로 정리하는 힘이 부족하다고 느꼈다.
6. 이번 대회에서 좋았던 점
1) A~D를 빠르게 정리했다
D까지 33분 정도에 해결했다.
면접 전 컨디션을 생각하면 꽤 괜찮은 결과였다.
2) C에서 long을 자연스럽게 사용했다
최근 자료형 실수로 많이 맞았는데,
이번 C에서는 답이 커질 수 있다는 걸 보고 바로 long으로 처리했다.
3) D에서 예전 경험을 잘 활용했다
중앙값 유지 문제를 풀어본 경험이 바로 떠올랐고,
두 개의 우선순위 큐로 안정적으로 해결했다.
4) 무리하지 않고 끊었다
E가 안 보였지만,
면접을 앞두고 무리하게 뇌를 갈아 넣지 않고 적당히 멈췄다.
이번에는 이것도 중요한 판단이었다.
7. 아쉬웠던 점
1) E의 조합 구조를 끝까지 못 만들었다
1과 3이 붙을 수 없고 2가 중요하다는 관찰은 했지만,
그걸 식으로 정리하지는 못했다.
2) D 코드를 더 깔끔하게 만들 수는 있었다
우선순위 큐 두 개를 사용하는 구조는 맞았지만,
큐 이름이나 균형을 맞추는 부분은 조금 더 정리할 수 있었을 것 같다.
대회 중에는 맞추는 게 우선이었으니 큰 문제는 아니지만,
나중에 다시 보면 더 깔끔하게 쓸 수 있을 것 같다.
8. 다음 목표
- 조합 세기 문제에서 작은 관찰을 식으로 바꾸는 연습하기
- “붙으면 안 되는 쌍”이 있는 문제를 배치 문제로 바꿔 보는 연습하기
- 우선순위 큐 두 개로 중앙값 유지하는 코드는 더 깔끔한 형태로 익혀두기
- 면접이나 다른 일정이 있을 때는 무리하지 않고 적당히 끊는 것도 실력으로 보기
한 줄 정리
ABC 458은 면접을 앞두고도 A~D를 33분에 정리했고,
E는 못 풀었지만 무리하지 않고 멈춘 대회였다.