[취업준비일지] - 146

면접 준비를 하면서 예전에 제출한 코드를 봤는데 멍청하게 전혀 문제와 상관없는 답을 제출한게 있었다.

 

문제에 대해서 말하기는 애매해서 예시를 하나 보자면

어떤 손가락을 접고 있는지를 물었는데

손가락간의 관계를 모두 분석하고 1을 출력하는 코드를 작성해버렸다.

 

처음 작성하는 파이썬에 대한 부담감을 가진 상태로

(기본) 단계의 문제임을 인식하지 못하고 

최소 공통부모와 dfs등을 통해 부모 노드 탐색 등을 떠올리며

그 코드를 파이썬으로 작성하다가 다시 또 제한 조건을 생각하며 코드를 꼬아버렸다.

 

제일 웃긴 부분은 dfs로 탐색을 하게 만들어버렸기 때문에 무조건 루트노드인 1이 출력되는데

테스트케이스의 정답이 모두 1이라 의심하지 않고 빠르게 다음 문제로 넘어갔다..

(시간제한이 며칠이었는데 시작하면 카운트다운이 되는 시험이라고 생각하고 4시간 전쯤 시작했다)

 

해당 문제를 js로는 1분이면 풀 수 있는 문제지만

파이썬으로 다시 작성하니 에러들을 만나 10여분 걸렸는데

이제 유사한 문제를 본다고 하더라도 2~3분 안에 풀 수 있을 것 같다.

 

 

 

 

 

(1).백준 10870번 피보나치 수 5는 간단하게 dp를 사용해 구현할 수 있다.
0번째 값에 0, 1번째 값에 1을 넣은 다음 n번까지 n-1, n-2를 더하면 되는데
사실 여러가지 값에 접근할 것이 아니라면 굳이 dp까지도 필요없다.

prev = 0, now = 1로 두 개의 값을 선언해준 다음
input의 입력에 따라 temp = now, now = prev + now, prev = temp로 
현재 값을 now = 1, prev = 1로 증가시킬 수 있으며
횟수가 증가할수록 (1,2), (2,3), (3,5)등 now값이 증가하는 것을 볼 수 있다.

어쨌든 테스트케이스가 많이 주어지는 문제라면 dp로 값을 저장해두는 편이 좋고
단 한번이라면 prev, now 형태도 괜찮을 것 같다.

const input = 10

const dp = [0,1]

for(let i = 2 ; i <= input ; i++){
    dp[i] = dp[i-1] + dp[i-2]
}

console.log(dp[input])