조합론

‘K번째 문자열 찾기’는 알고리즘 문제해결에서 ‘생성(Generation)’과 ‘계수(Counting)’의 차이를 극명하게 보여주는 대표적인 유형입니다. 본 리포트에서는 백준 1256번을 예시로, 문자열을 직접 생성하려는 시도가 왜 메모리 초과를 유발하는지, 그리고 List을 int로 치환하는 과정이 어떻게 문제의 본질을 ‘조합 탐색’으로 변화시키는지 분석합니다. 또한, 파스칼의 삼각형을 이용한 DP 전처리부터 분할 정복을 이용한 ‘Skip Logic’까지, 대규모 탐색 공간을 효율적으로 제어하는 정석 패턴을 상세히 다룹니다.