[코딩테스트 준비] 백준 브론즈 3문제(10870 피보나치 수 5 / 1987 소수 찾기 / 2581 소수), 실버 1문제 (14888 연산자 끼워넣기)

10870 피보나치 수 5

피보나치 수열은 이전 두 항의 합으로 현재 항을 구하는 점화식을 가진다.
문제에서 n의 범위가 0 ≤ n ≤ 20으로 매우 작기 때문에 복잡한 최적화는 필요 없으며, 반복문을 이용한 단순 구현으로 충분하다.

기본 정의는 다음과 같다.

• F(0) = 0
• F(1) = 1
• F(n) = F(n−1) + F(n−2) (n ≥ 2)

풀이에서는 먼저 n이 0 또는 1인 경우를 예외 처리한다.
그 이후에는 두 개의 변수에 각각 F(n−2), F(n−1)을 저장해 두고, 반복문을 통해 다음 피보나치 수를 계산하면서 값을 갱신한다.

 

만약 n이 0이라면 0을 출력하고, a와 b를 각각 0,1로 초기화해놓고 c=a+b a=b, b=c로 놓고 풀면 된다. 

이 방식은 불필요한 재귀 호출을 피할 수 있어 구현이 간단하고 안정적이다.

시간 복잡도는 O(n), 공간 복잡도는 O(1)이며, 문제 조건 내에서 가장 효율적인 해결 방법이라고 생각한다.

 

1987 소수 찾기

소수는 1과 자기 자신만을 약수로 가지는 수로, 1은 소수가 아니다.
문제에서는 최대 100개의 수가 주어지고, 각 수의 최대값이 1000이기 때문에 각 수를 개별적으로 소수 판별해도 충분하다.

각 수에 대해 2부터 √n 까지만 나누어 떨어지는지 확인한다.
어떤 수 n이 합성수라면 √n 이하의 약수를 반드시 하나 이상 가지기 때문에, 그 이후까지 확인할 필요가 없다.

입력된 수가 2 미만인 경우는 소수가 아니므로 바로 제외하고, 나누어 떨어지는 경우가 한 번도 없을 때만 소수로 판단하여 개수를 증가시킨다.

이 방식의 시간 복잡도는 O(N√M)이며, 문제의 입력 범위 내에서는 효율적으로 동작한다.

 

2581 소수

주어진 구간 [M,N][M, N][M,N] 내의 모든 자연수에 대해 소수 여부를 판별한 뒤, 소수들의 합과 최솟값을 구하는 문제이다.
수의 최대 범위가 10,000이므로 각 수를 하나씩 검사하는 방식으로 충분히 해결할 수 있다.

소수 판별은 2부터 √n 까지만 나누어 보는 방법을 사용한다.
어떤 수가 합성수라면 반드시 √n 이하의 약수를 가지므로, 그 이상 확인할 필요가 없다.
1은 소수가 아니므로 예외 처리한다.

구간을 순회하면서 소수인 경우에만 합에 더하고, 처음 발견한 소수를 최솟값으로 저장한다.
반복이 끝난 뒤 소수가 한 개도 없었다면 문제 조건에 따라 -1을 출력한다.

이 방식의 시간 복잡도는 O((N−M)√N)이며, 문제의 입력 범위 내에서 충분히 효율적으로 동작한다.

 

14888 연산자 끼워넣기

이 문제는 숫자의 순서는 고정된 상태에서, 주어진 개수만큼의 연산자를 모든 가능한 순서로 배치해 보는 완전 탐색 문제이다.
연산자 우선순위는 무시하고 앞에서부터 계산해야 하므로, 중간 결과를 계속 누적하면서 다음 숫자를 처리한다.

백트래킹을 이용해 현재 숫자 위치와 누적 결과를 상태로 두고, 남아 있는 연산자 중 하나를 선택해 다음 단계로 진행한다.
연산자를 하나 사용하면 해당 연산자의 개수를 감소시키고, 재귀 호출이 끝난 뒤에는 다시 복구한다.

모든 숫자를 사용했을 때 최댓값과 최솟값을 갱신한다.
나눗셈은 문제 조건에 따라 음수일 경우 절댓값으로 나눈 뒤 부호를 다시 붙이는 방식으로 처리한다.

N의 최대값이 11이므로 모든 경우를 탐색해도 시간 제한 내에 충분히 해결할 수 있다.