728x90

https://www.acmicpc.net/problem/15649

😢 오랜만에 보는 순열과 조합

😊 DFS(Depth First Search)를 이용해 풀어낼 수 있다.

* Base case

cnt === M일 때, 출력하고 return해준다(입력 받은 길이만큼)

* Recursion

for loop을 열고 재귀를 진행해준다.
방문을 했다면 true, output에 해당 값(i+1) push 그리고 그 다음 숫자를 진행하기 위헤 dfs(cnt+1)를 진행해준다.
depth의 끝까지 진행하기 위해 마지막 값을 pop()하고 해당 방문은 false로 변경해준다.

3. print() function을 이용해 원하는 값의 길이만큼 값을 구할 때마다 출력해준다.

위와 같은 재귀를 이용해 위 문제를 해결할 수 있다. 조금 세세하게 이해하기 위해서는 debugging 추천한다.

📢 지금까지는 대회를 생각하고 C++를 이용해 알고리즘을 푼 것이 아니기 때문에 시간에 그렇게 신경을 쓰지 않았다.
정확한 로직을 이용해 효율적으로 문제를 해결할 수 있으면 된다고 생각했기 때문이다.
하지만 우연히 console.log() 방법을 바꿔보았더니 시간 단축이 엄청나졌다. 앞으로는 console.log를 최소화 해야겠다.
시간 단축에 엄청난 도움이 된다. 성능을 위해서 사소한 하나까지 신경쓰자.

결론은 Solution 2를 추천한다. 출력 방법만 조금 바꿨을 뿐이다.

이해에 도움이 됐던 post 👉 https://yabmoons.tistory.com/115

+ Recent posts