[코드트리 챌린지] 2주차_실력진단(잔꾀쓰다가 망함)[백트래킹_K개 중 하나를 N번 선택하기]

되도 않는 변명을 하자면 좀 많이 바빴다. ...네

실력진단 점수 그래프

 

사실 실력 진단 테스트가 문제 유형이 어느정도 정해져 있어서 내가 전에 못풀었던 순열, 조합 관련 결과값을 출력해야하는 문제만 풀면 점수가 오르지 않을까? 하는 되도 않는 잔머리를 부려봤다. 사실 아이디어 자체는 유효한거 같은데 문제는 내가 수박 겉핥기로 배우고 넘어가다보니 적용을 못하겠다. 결국 점수는 그대로인걸로

 

수열, 조합 문제 중 내가 공부했던 문제를 톺아보자면 다음과 같다.

https://www.codetree.ai/cote/13/problems/n-permutations-of-k-with-repetition?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

순열 조합 문제

 

이 문제를 나름대로 이해했다고 생각했는데 매우 유사하게 나왔음에도 못풀었다...

코드트리에서 제공하는 개념은 재귀함수를 통해 분할정복으로 문제를 해결하는 방식이다.

이 개념은 몹시 중요해서 대학교 전공에서도 계속 배우고 있지만 나는 아직 많이 부족한 듯하다.

코드트리 개념설명1

스스로를 재귀적으로 호출하면서 좀더 작은 문제로 쪼개서 해결한 후 점차 합치면서 해결한다. 

 

재귀 함수라는 개념을 활용해 위의 문제를 나 나름대로 풀어보았다

문제 풀이

깊이 n까지 들어가는 재귀를 k번 반복한다.

1부터 n까지 for문을 통해 하나씩 증가하는 순서로 진행이 되는데,

k가 3일 경우 1 -> 1 -> 1을 push 한다음 최대 깊이이므로 1 1 1을 출력,

이후 마지막 1을 pop한다. 다음 for문에서 2를 맨 뒤에 넣고 반복하면서 1 1 2가 출력되는 구조이다.

개념적으로는 이해했는데, 이게 문제가 조금만 조건이 변해도 뇌가 정지해버려서 익숙해질때까지 연습이 필요할 듯 하다.