[D+76] 알고리즘문제 1 - 2번

 

D+76

-  알고리즘문제 1 - 2번 -

(Toy Problem 1 - 2)

 

---

 

 

이번에 알고리즘 문제가 새롭게 업그레이드가 된 관계로

1번부터 새로 시작하는 마음으로 시작하기로 했다.

(많이 어려워졌더라... ㄸㄹㄹ)

 

 

 

# 01

가위바위보 게임의 경우의 수만큼 나오는 배열을 리턴하는 문제였는데

기본적인 문제는 반복적인 for문을 통해서 문제를 풀었었지만 아쉽게도 advanced한 문제는 건드리지도 못했다.

 

rounds에 값을 넣으면서 재귀적으로 돌고돈다는 것은 파악했으나

안에 또다시 함수를 넣어 거의 이중급으로 재귀가 돈다는 것까지는 파악하지 못했다.

 

래퍼런스 코드를 봐도 이해가 거의 안되어서 손으로 직접 적어서 문제를 풀어보았고,

그제서야 어느정도는 이해할 수 있게 되었다.

(rounds를 2를 넣었기에 망정이지 수가 더 컸으면 실패했을지도....?)

 

rounds의 값이 작은 숫자라면 그냥 단순히 다중 for문을 사용하겠지만 큰 수가 들어가면

이렇게 사용하는 방향으로 해야겠다.

 

 

# 02

피보나치를 계산하는 문제였는데 기존에 나는 재귀적인 특성을 이용해 문제를 풀었는데

이럴 경우에는 시간복잡도가 O(2^n)이기 때문에 오래 걸린다는 것을 문제를 통해 알게되었다.

 

이유를 찾아보니 피보나치를 재귀적으로 문제를 해결하면 쪼개지면서

중복된 계산을 여러번 할 수 있다고 한다.

 

ex) f(10) = f(9) + f(8) = f(8) + f(7) + f(7) + f(6) = ...

=> 이런식으로 f(7)을 불필요하게 두번 풀어줘야 한다.

 

그래서 이런 중복적인 부담을 줄여주는 방법이 특정 인덱스에 값을 넣어주는데

이때 재귀적으로 돌다가 특정 인덱스에 값이 있을 경우엔 계산 해주지 않고 특정 인덱스의 값을 리턴하는 방법을 사용하면

훨씬 효율적이라고 한다.

 

그 이후엔 최종적인 값을 리턴하는데 엄청난 방식인 것 같다.