최종 프로젝트. (1)

신나는 알고리즘 풀이 시간. 

문제 설명

효진이는 멀리 뛰기를 연습하고 있습니다. 한 번에 1칸 또는 2칸씩 뛸 수 있는데, 총 nnn개의 칸이 주어졌을 때 효진이가 맨 끝 칸에 도달하는 방법은 몇 가지일까요?

예를 들어 n=4n=4n=4일 때, 효진이가 끝에 도달하는 방법은 다음과 같습니다:

1. (1칸, 1칸, 1칸, 1칸)
2. (1칸, 2칸, 1칸)
3. (1칸, 1칸, 2칸)
4. (2칸, 1칸, 1칸)
5. (2칸, 2칸)

즉, 경우의 수는 5가지입니다.

제한 조건

• nnn은 1 이상, 2000 이하의 정수입니다.
• 결과 값이 너무 커질 수 있으므로 1234567로 나눈 나머지를 반환해야 합니다.

문제를 보고 작성한 노트 

 

문제를 풀지 못 한 원인

f(n) = f(n-1) + f(n-2)에서 피보나치 수열을 연상해내지 못 했기 때문.

 

그걸 연상해냈더라면 풀 수 있었던 문제였는데, 다소 아쉽다. 

 

코드 구현

다음은 효율적인 풀이를 위한 코드다:

function solution(n) {
  let a = 1; // f(1)
  let b = 2; // f(2)

  for (let i = 3; i <= n; i++) {
    let temp = (a + b) % 1234567; // 점화식 적용 및 나머지 연산
    a = b; // f(n-1)로 갱신
    b = temp; // f(n)로 갱신
  }

  return n === 1 ? a : b; // n이 1이면 a(=1), 아니면 b 반환
}

 

풀이 과정

1. 점화식 f(n)=f(n−1)+f(n−2)f(n) = f(n-1) + f(n-2)f(n)=f(n−1)+f(n−2)를 코드로 구현.
2. 계산 중에 123456712345671234567로 나머지를 구해 숫자가 커지는 걸 방지.
3. 배열 대신 변수 두 개만 사용해 메모리를 절약.

테스트 결과

예제 n=4n=4n=4:

• f(4)=f(3)+f(2)=3+2=5f(4) = f(3) + f(2) = 3 + 2 = 5f(4)=f(3)+f(2)=3+2=5

예제 n=5n=5n=5:

• f(5)=f(4)+f(3)=5+3=8f(5) = f(4) + f(3) = 5 + 3 = 8f(5)=f(4)+f(3)=5+3=8

모든 계산에서 1234567로 나눈 나머지를 적용해 제한 조건을 만족

 

마무리

이 문제는 피보나치 수열의 특징을 활용해 동적 계획법(DP)으로 푸는 좋은 예다.
n값이 커질수록 효율적인 코드 구현이 중요했고, 나머지 연산을 통해 메모리와 시간 복잡도를 절약할 수 있었다.

이 문제를 풀면서 점화식과 동적 계획법에 대한 이해가 한층 더 깊어졌다.

 

최종 프로젝트 / 기획

오늘은 최종 프로젝트를 기획하기 위한 회의를 진행하였다. 

 

 

기획은 다 했지만, 해당 기획을 진행하는 것에 대한 타당성과 근거를 확보하기 위해서, 설문 조사를 진행하였다. 

https://docs.google.com/forms/d/e/1FAIpQLScxZA3z_Ups_xpO4tMDlLla3CDclGHX3FpQqNLZbBSttpMkfw/viewform