2022 02 11

알고리즘 문제풀이 - DFS, BFS 활용¶

순열과 조합
- 순열(nPr) : 서로 다른 n개 중에 r개를 순서와 "상관있이" 선택하는 경우의 수 => 어떤놈이 어떻게 줄세웠는지가 중요!
  - nPr = n! / (n-r)!
  - n개를 나열하는 경우의 수 / 그 중 (n-r)개를 나열했을 때의 경우를 다 제외해
- 조합(nCr) : 서로 다른 n개 중에 r개를 순서와 "상관없이" 선택하는 경우의 수 => 어떤놈이 뽑힌건지가 중요!
  - nCr = n! / (n-r)!r!
  - n개를 나열하는 경우의 수 / 그 중 (n-r)개를 나열했을 때의 경우 다 제외해 + r개의 순서 나열도 제외해!
- 미리 순열과 조합을 쟁여두는 방법
  - 우선 팩토리얼을 구하자 (0! ~ N! 까지의 수)
```
int[] factorial = new int[N + 1];
for (int i = 0; i <= N; i++) {
    if (i == 0) {
        factorial[0] = 1;
    } else {
        factorial[i] = factorial[i - 1] * i;
    }
}
```
  - 이후 조합을 한번 구해보자 *(n-1C0 ~ n-1Cn-1)
```
combination = new int[N];
for (int i = 0; i < N; i++) {
    combination[i] = getCombination(N-1 ,i);
}

private static int getCombination(int N, int target) {
    return factorial[N] / (factorial[N-target] * factorial[target]);
}
```

순열 구하기
- (3, 6) 이랑 (6, 3) 은 다르니까 둘 다 구해야겠지?
  - 한명은 반장, 한명은 부반장이라 생각하기
- 원소 for문 돌면서 LinkedHashSet에 중복 없으면 담자
  - 재귀로 들어간 for문이 또 LinkedHashSet에 중복 검사하면서 줍줍
  - 2개 다 뽑았으면 출력

조합 구하기
- (3, 6) 이랑 (6, 3) 은 같은거야 이번엔
  - 대표 두명 뽑는거라 생각하기
- 원소 for문 돌되, 시작하는 index 부터서 LinkedHashSet에 중복없으면 담자
  - 그다음 원소 for문 돌땐 index + 1 부터 돌도록 조치를 취하자!
  - 2개 다 뽑았으면 출력하자

배열 미로탐색
- 모든 경우의 수를 따져야하니 DFS로 풀자!
- 함정은 배열의 범위
  - if문으로 다음 격자가 1~7 범위안에 들어온 경우만 재귀를 돌리는 방법도 있고
  - 아니면 아예 바깥쪽을 -1로 초기화해서 상하좌우 보고 -1이면 가지 않는 방법도 있음
- 중요) 갔다 왔는지를 체크해야하는데 시작점을 우선 check 해줘야함!!

너무 너무 헷갈렸던 2차원 배열
- 그냥 int[][] board = new int[x][y]
- 여기에서 x는 위아래로 움직여주고, y는 양옆으로 움직여줌 (좌표 평면 아니야 까먹어 그냥)
- x랑 y가 반대로 주어져도 당황말고 하자
  - 그냥 int[x][y] 라고 잡고, [3][5]가 성립하는지 확인하고 뚝딱