알고리즘

애드혹 문제와 구현 문제 차이를 헷갈리는 경우가 많습니다. 이번 글에서는 구현, 시뮬레이션, 애드혹을 같은 수준의 예시로 비교하면서 코딩테스트에서 어디서부터 발상이 필요한지 단계적으로 정리합니다.

애드혹 문제란 무엇인가를 코딩테스트 관점에서 쉽게 정리합니다. 브루트포스, 구현형과의 차이, 문제에서 애드혹 냄새를 맡는 신호, 접근 순서까지 단계별로 설명합니다.

애드혹 문제 풀이법의 핵심은 공식을 빨리 떠올리는 일이 아니라 작은 입력 표 작성, 패턴 가설, 반례 검증, 손 시뮬레이션 순서를 지키는 것입니다. 문자열 그룹 관찰과 요세푸스 예시로 그 흐름을 정리합니다.

요세푸스 문제는 처음엔 시뮬레이션이 자연스럽지만, 입력이 커질수록 제거 뒤 남은 구조를 다시 보는 규칙 관찰이 더 중요해집니다. 작은 예시, 점화식, k=2 패턴까지 쉽게 정리합니다.