완전 탐색
모든 경우의 수를 탐색하여 찾는 방법
- 장점 : 답이 존재한다면 반드시 답을 찾을 수 있음
- 단점 : 경우의 수가 너무 많은 문제의 경우 적합하지 않음
- 주로 DFS/BFS 활용
순열
- 서로 다른 n개의 원소에서 중복을 허용하지 않고 r개를 순서 대로 선택하는 것
nPr = n!/(n-r)! - 시간 복잡도 : O(N^r)
순열에서 이전에 뽑은 index 보다 큰 index 뽑으면 조합
조합
- 서로 다른 n개의 원소에서 중복을 허용하지 않고 r개를 순서 없이 선택하는 것
nCr = n!/r!(n-r)!
부분 집합
- 주어진 집합에서 일부 원소들로 구성된 집합을 만드는 것
- 집합 X의 원소가 n개 일 때. 공집합을 포함한 부분집합의 개수는 2^n개
- 데이터가 많은 경우 시간 복잡도 복잡
1) 선택 O
2) 선택 X
☑ 재귀로 구현 시
1) 종료 조건
2) 재귀 확장
꼭 기억할것
상 : [y-1][x], 하 : [y+1][x], 좌 : [y][x-1], 우 : [y][x+1]
좌상 : [y-1][x-1] , 좌하 : [y+1][x-1], 우상 : [y-1][x+1], 우하 : [y+1][x+1]
4방 탐색
target의 상,하,좌,우 값을 탐색 하는 것
int dy[] = { -1, 1, 0, 0 };
int dx[] = { 0, 0, -1, 1 };
또는
int delta[][] = {{-1,0}, {1,0}, {0,-1},{0,1}};8방 탐색
target의 상,하,좌,우,좌상,좌하,우상,우하
즉 상,하,좌,우, 모든 대각선 방향 값을 탐색 하는 것
❗dy[]와 dx[]배열을 처리 할때,
위의 좌표 이미지에서 12시를 기준으로 시계방향으로 돌아가며 값을 초기화해주면 된다.
int dy[] = { -1, -1, 0, 1, 1, 1, 0, -1};
int dx[] = { 0, 1, 1, 1, 0, -1, -1, -1};
또는
int delta[][] = {{-1,0}, {-1,1}, {0,1}, {1,1}, {1,0}, {1,-1},{-1,-1}};❗ delta 탐색 시 해당 배열의 범위를 벗어나지 않도록 예외처리를 해주는 것을 주의하자!
int now_y = y + dy[d];
int now_x = x + dx[d];
또는
int now_y = y + delta[i][0];
int now_x = x + delta[i][1];
...
//범위를 벗어나는 값 예외처리
if(now_y<0 || now_x<0 || now_y>=N || now_x>=N) continue;
또는
if(now_y>=0 || now_x>=0 || now_y<N || now_x<N ) continue; 
Just Do IT ------- 🏃♀️