해설 보기
정답sum(x - 1) — 인자를 1 줄여 재귀 호출해야 x + sum(x-1)이라는 올바른 점화식이 완성됩니다.
핵심 개념
재귀 함수의 점화식 구성 — 1부터 x까지의 합
재귀 함수는 '종료 조건(base case)'과 '자기 자신을 더 작은 입력으로 호출하는 부분(recursive case)'의 두 축으로 이루어집니다. 이 문제의 sum(x)는 1부터 x까지의 합을 구하는 함수이므로 점화식은 sum(x) = x + sum(x-1)이고, 종료 조건은 x가 1 이하일 때 1을 반환하는 것입니다. 따라서 빈칸 (가)에는 현재 값 x를 제외한 나머지 구간, 즉 1부터 x-1까지의 합을 구하는 재귀 호출이 들어가야 합니다. 재귀 호출의 인자는 반드시 종료 조건 쪽으로 '작아지는' 방향이어야 하며, 인자가 커지거나 그대로면 무한 재귀에 빠져 스택 오버플로가 발생한다는 점이 핵심 판별 기준입니다.
선지별 해설
①x + (x + 1)이 되어 재귀 호출 자체가 없어지고 단순히 2x+1을 반환합니다. 예를 들어 sum(3)은 7이 되어 정답 6과 다르므로 틀렸습니다.
②x + (x - 1)이 되어 역시 재귀 호출이 없습니다. sum(3)이 5가 되어 1+2+3=6과 맞지 않으므로 틀렸습니다.
③인자가 x+1로 오히려 커져 종료 조건 x<=1에 영원히 도달하지 못합니다. 무한 재귀로 스택 오버플로가 발생하므로 틀렸습니다.
④return x + sum(x-1)이 되어 sum(x)=x+sum(x-1) 점화식이 완성됩니다. sum(3)=3+sum(2)=3+2+sum(1)=3+2+1=6으로 정확하며, 인자가 줄어들어 종료 조건에도 반드시 도달합니다.
해설 보기
정답보이어-무어(Boyer-Moore) 알고리즘 — bad character와 good suffix 두 이동표를 사용하는 대표적 문자열 매칭 알고리즘입니다.
핵심 개념
문자열 매칭 알고리즘 — 보이어-무어의 두 가지 이동 규칙
보이어-무어(Boyer-Moore) 알고리즘은 패턴을 오른쪽 끝에서 왼쪽으로 비교하면서, 불일치가 발생하면 패턴을 한 칸씩이 아니라 여러 칸씩 건너뛰는 문자열 매칭 알고리즘입니다. 건너뛸 칸 수는 두 개의 전처리 표로 결정하는데, 하나는 텍스트에서 만난 불일치 문자가 패턴 어디에 있는지를 이용하는 '불일치 문자(bad character)' 이동표이고, 다른 하나는 이미 일치한 접미부가 패턴 내 다른 곳에 다시 나타나는지를 이용하는 '일치 접미부(good suffix)' 이동표입니다. 두 표가 제시하는 이동량 중 큰 값을 택해 이동하므로 실제 텍스트에서 매우 빠르게 동작합니다. 지문에 bad character와 good suffix 두 표가 모두 언급된 것이 결정적 단서입니다.