이 문제에서는 정수 N이 주어졌을 때, 수열 1, 2, 2, 4, 4, 4, 4, 8, 8, 8, 8, 8, 8, 8, 8…에서 N번째 항을 구하는 프로그램을 작성하는 것이 목표입니다.
이 수열은 2의 거듭제곱(1, 2, 4, 8, …)으로 이루어져 있으며, 각 값이 자기 자신만큼 반복되는 규칙을 가집니다. 즉, 1은 1번, 2는 2번, 4는 4번, 8은 8번 나타납니다.
예제로 문제 이해하기
입력
N = 7
출력
4
설명: 수열의 7번째 항은 4입니다.
방법 1: 반복문을 이용한 단순 접근
가장 직관적인 방법은 반복문을 사용해 N번째 위치에 도달할 때까지 항을 차례대로 세어가는 것입니다. 매 반복마다 현재 항 값을 두 배로 늘리고, 그 값을 카운터에 더해 진행 상황을 추적합니다.
솔루션의 동작을 보여주는 예제 코드:
코드
#include <iostream>
using namespace std;
int calcNthTerm(int N) {
int termCounter = 0, termValue = 1;
while (termCounter < N) {
termCounter += termValue;
termValue *= 2;
}
return termValue / 2;
}
int main() {
int N = 10;
cout << N << "번째 항의 값은 " << calcNthTerm(N);
return 0;
}출력
10번째 항의 값은 8
방법 2: 일반항을 이용한 효율적 접근
더 효율적인 방법은 수열의 일반항을 찾아 한 번의 계산으로 답을 구하는 것입니다.
각 항과 그 항이 마지막으로 등장하는 인덱스: 1 -> 마지막 인덱스 = 1 2 -> 마지막 인덱스 = 3 4 -> 마지막 인덱스 = 7 8 -> 마지막 인덱스 = 15 . . T(N) -> 마지막 인덱스 = 2*(T(N)) - 1 또한 T(N)은 항상 2의 거듭제곱입니다. 즉, T(N) = 2m 2m은 인덱스 2m+1-1까지 수열에 존재합니다.
따라서 N을 이용해 m의 값을 계산하면 해당 항을 바로 구할 수 있습니다. 조건은 다음과 같습니다.
2m - 1 < N 따라서, m < log2(N + 1)
즉, m = ⌊log₂(N + 1)⌋이고, N번째 항은 2m입니다.
솔루션의 동작을 보여주는 예제 코드:
코드
#include <iostream>
#include <math.h>
using namespace std;
int calcNthTerm(int N) {
return ( pow(2, (floor)(log(N + 1) / log(2))) );
}
int main() {
int N = 10;
cout << N << "번째 항의 값은 " << calcNthTerm(N);
return 0;
}출력
10번째 항의 값은 8
두 방법의 비교
반복문을 사용하는 단순 접근법의 시간 복잡도는 O(N)입니다. 반면 로그를 활용한 효율적 접근법은 O(log N)으로 실행 속도가 훨씬 빠르므로, N이 커질수록 후자의 방법이 훨씬 유리합니다.