Karatus::[문제집] baekjoon

이번에는 하나의 문제집에 대한 문제들을 전체적으로 다뤄보도록 하겠습니다.

만든 사람은 'baekjoon'님으로 BOJ 사이트 이름만 봐도 얼마나 대단하신 분인지 알 수 있죠. ㅎㅎ

시작하기에 앞서 'N과 M'이라는 이 문제집은 전체적으로 하나의 알고리즘을 기준으로 풀게 됩니다.

그 알고리즘이란 여러분들도 익히 들어보셨을 만한 DFS(Depth-First Search)입니다!

이 개념은 왜 나왔느냐 하면은 State-Space tree라는 것에서 이용하기 위해서 나온 것입니다.

[Reference: Maximizing Rewards in Wireless Networks with Energy and Timing Constraints for Periodic Data Streams - Scientific Figure on ResearchGate. Available from: https://www.researchgate.net/figure/The-complete-state-space-tree-by-pruning_fig3_220466160 [accessed 17 Jul, 2019] ]

N개의 수 중 M개를 골라 출력하는 것으로 수학

에서 배우는 "조합" 문제라고 생각하셔도 좋습니다.

즉, 우리는 문제의 조건에 맞게 조합 알고리즘을 구현하는 것입니다.

문제의 유형을 나눠보도록 하겠습니다.

< 입력받는 값 >

< $N$개 중 $M$개의 출력 형태 >

총 12개의 문제가 위 $3 \times 4 = 12$의 유형의 조합으로 이루어져 있습니다.

먼저 '입력받는 값'들에 대한 일반적인 시각을 가져보도록 하죠.

1번은 조건이 1부터 $N$으로 정해져있기 때문에 딱히 입력받는 값이 없습니다. for문으로 값들을 순차적으로 적용해주면 될 것입니다.

2번은 '서로 다른' $N$개의 정수라고 했으니 값들에 대한 중복 처리의 고민없이 값들을 저장한 후 정렬(!)하고 사용하면 됩니다. (정렬의 이유는 작은 값부터 접근하기 위함입니다.)

3번의 경우에는 조금 생각할 시간이 필요했습니다. 각 접근 단계마다 중복되는 숫자들의 검사가 필요했죠.

하지만 저는 중복에 대한 feasibility를 일일이 검사하다가는 시간도 많이 걸리고 비효율적일 것 같은 기분이 들어 다른 방법이 없나 물색했죠.

그 결과 숫자들에 대한 Unique성이 보장되어야 한다고 생각했습니다.

각 숫자들을 하나의 단일 숫자로서 취급하되, 몇 개가 존재하는지를 저장해주어 최대 사용 가능 횟수를 제한해주어 사용하는 것이 중복도 피하고 시간도 적게 걸리게 만들어주는 것입니다.

이렇게 만들어줄 좋은 STL이 없나 생각하던 찰나에 예전부터 이용해보고 싶었던 것이 떠올랐습니다.

[Reference: "27. STL 컨테이너(map, multimap)," 시작! 쿨프로그래밍, n.d. 수정, 2019년 7월 17일 접속, http://blog.daum.net/coolprogramming/83. ]

바로 map 템플릿이었죠. map에 대해 간단히 설명하자면 값들이 key와 value로 이루어져있고, key를 통해 value로 접근하는 것이 가능합니다. 그리고 이 key값들은 유일(Unique)하죠. 게다가 key들은 자동으로 sort됩니다!

이 특성을 이용해 입력받는 값들을 Unique하게 해주고 개수를 value에 저장해주었습니다.

이후 DFS의 State-Space Tree를 내려갈 때마다 value가 영향을 주게 설정하여 같은 depth에서는 중복을 피하게 만들었습니다.

(다른 분들이 한 것들을 보니 '중복을 피한다'라는 점과 'depth에 영향을 준다'라는 점에서는 동일했습니다. 뭐 이게 문제를 푸는 열쇠이긴 하지만요. ㅎㅎ)

두 번째로 '출력 형태'에 대해 살펴보도록 하겠습니다.

이번 유형은 의외로 간단합니다.

1번의 경우, 각각의 값들을 방문했는지 안 했는지를 알려줄 지표가 필요로 합니다.

그리고 방문했을 때를 가정하여 DFS를 돌고, 방문 이후에는 방문하지 않은 것으로 설정하고 다음 숫자로 넘어가도록 만듭니다.

2번의 경우, 1번과 마찬가지로 방문했는지 안 했는지를 알려줄 지표가 필요하고 덧붙여서 자신보다 큰 수를 호출할 필요가 있죠.

그래서 저는 DFS의 매개변수로 int start를 하나 추가해 start 이상의 수를 가진 수들만 다음 DFS에서 이용하도록 만들었습니다.

3번은 중복의 허용이었습니다. 이는 훨씬 간단합니다.

중복을 검사해줄 필요가 없다는 것은 즉 방문 여부를 검사할 필요없이 처음부터 출력하면 된다는 것입니다. 그래서 방문 여부 지표를 사용하지 않고 풀 수 있는 유형이라 할 수 있습니다.

4번은 '중복 허용 + 비 내림차순(==오름차순)'의 의미이므로 간단히 1번과 3번에서 언급했던 방법 모두를 사용하여 적절히 검사해주며 DFS를 돌면 됩니다.

입력받는 값들의 처리보다 훨씬 간단한 아이디어로 접근할 수 있었습니다.

사실 이 문제들은 DFS의 개념과 중복 처리 여부만을 적절히 사용하면 그다지 어려운 문제들이 아니었습니다.

~~(9번 빼고요...)~~

아무튼 여러분들도 'N과 M' 문제집을 정복해보도록 합시다!! Fighting!

[문제집] baekjoon - N과 M