N과 M 문제들 다시 풀어보기

N과 M(1)

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

중복되는 수열을 여러 번 출력하면 안되며 -> boolean 배열을 사용해서 방문 체크

 

N과 M(2)

• 고른 수열은 오름차순이어야 한다.

위 조건으로 인해서 idx라는 파라미터가 추가되서 백트래킹을 돌리게 된다. 이전 문제에서 헷갈렸던 부분, i+1로 돌리느냐 idx + 1로 돌리느냐의 차이는 idx + 1로 돌리면, 현재 인덱스를 기준으로 다음 인덱스를 호출하기 때문에 항상 오름차순이지 않다.

 

하지만, i+1은 현재 요소를 기준으로 다음 요소를 선택하기 때문에 [1,2,3,4] -> 1을 다 순회했다면 다시 1을 사용하지 않아서 모두 오름차순이 된다.

dfs(i + 1, depth + 1);

 

N과 M(3)

• 같은 수를 여러 번 골라도 된다.

말그대로, 모든 경우의 수를 출력하는 것이기 때문에 idx라는 파라미터가 필요가 없고 방문체크 또한 할 필요 없다. 

 

N과 M(4)

• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.

dfs(i, depth + 1);

 

3번 문제와 달라진 부분은 오름차순으로 출력해야 한다. 아까 2번에서는 중복을 허용하지 않고 오름차순으로 정렬해야 했었다. 백트래킹을 돌릴 때 (i, depth + 1)로 돌리게 되면 다음 원소는 현재 원소까지 포함해서 고를 수 있게 된다.

 

N과 M(5)

지금까지 문제와는 다르게 입력값을 배열 형태로 저장하고, 또 다른 배열인 tmp를 선언해서 tmp[depth] = arr[i] 형태로 저장하는 문제였다. 특이 사항으로는 StringBuilder를 쓰지 않고 그냥 출력하면 시간 초과가 발생한다.

 

그리고 arr의 크기를 n이 아닌 10으로 설정하고 sort 했을 때 아무것도 출력이 되지 않아 당황했는데, [0,0,0...4,5,2] 이런 형태가 되니까 그런거였다.

 

N과 M(6)

• 고른 수열은 오름차순이어야 한다.

2번 문제와 동일하다. 파라미터 idx를 추가해주고 

dfs(idx + 1, depth + 1);

을 돌리면 모든 오름차순인 수열을 출력한다.

 

N과 M(7)

• 같은 수를 여러 번 골라도 된다.

3번과 같은 문제. 모든 경우의 수를 출력하는 문제이므로 그대로 풀면 된다.

 

N과 M(8)

• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.

dfs(i, depth + 1);

을 사용하면, 여러번 고르면서 오름 차순인 결과값을 뽑아낼 수 있다.

 

N과 M(9)

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

 

이전 문제들과는 살짝 느낌이 다르다. 

예제)

4 2
9 7 9 1

 

결과값)

1 7
1 9
7 1
7 9
9 1
9 7
9 9

 

먼저 sort를 해준다면 [1, 7, 9, 9] 가 되고 조합으로 만들 수 있는 모든 순서쌍을 출력하는 문제였다. (단, 중복 제외!) 

dfs(i, depth + 1);

로 백트래킹을 돌리면, 모든 조합을 만들 수 있다. 하지만 중복이 발생한다. ex) (1,9), (1,9)

 

이를 방지하기 위해서 순서가 보장된 LinkedHashSet을 만들어서 담아주고, 출력했다. 

 

20일전에 문제를 풀었을 때는 Prev라는 변수를 만들어서 이전값과 동일하지 않은 경우에만 백트래킹을 하도록 구현했지만 완벽하게 이해를 하지 못했다. 개인적으로 Set을 이용한 방법이 나에게 더 직관적으로 와닿는다.

 

N과 M(10)

• 고른 수열은 비내림차순이어야 한다.

1 7
1 9
7 9
9 9

dfs(i + 1, depth + 1);

단순히 i + 1로 돌리면 오름차순인 경우만 출력한다.

 

N과 M(11)

• 같은 수를 여러 번 골라도 된다. -> visited 배열 x, 모든 순서쌍 출력

파블로프의 개처럼 바로 나와야된다.

N과 M (12) 

• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.

1 1
1 7
1 9
7 7
7 9
9 9

 

이런식으로 결과가 출력되니, 다음 요소는 현재 요소와 동일해도 상관없지만 1을 전부 사용하고 난 뒤엔 쓸 수 없다.

 

그래서 (7,1)과 같은 결과가 존재할 수 없다.

dfs(i, depth + 1);

이렇게 i 그대로 돌린다면 1을 전부 사용하고 나서는, 7부터 순회하게 된다.

 

 

다시 1~12번을 복습해봤는데 많은 도움이 된 것 같다.