테케 안나오면 단계별로 다 찍어보면서 디버깅 해라. 찾아 진다. 겁먹지 말것
1. DFS
1. 가지치기 어디서 할 것인지 생각하자.
보통 depth에 대한 가지치기는 모든 조건 확인한 후 해준다.
(왜냐하면 맨 마지막꺼 고르고 돌아와서 조건문 확인하는 경우에는 n == depth가 된 상태임)
2. DFS 다녀와서 플래그 원복 해주는 경우는 "모든 경로를 탐색해야 할 때" 이다. 즉 방문했던 노드를 재방문해야 하는 경우이다.
플래그 원복해주지 않는 경우는 모든 노드를 방문해야 할 때 이다.
// 조합 배열로 구현
#include <cstdio>
int N, M;
int choice[8 + 2];
void DFS(int n, int s)
{
if (n == M) {
for (int i = 0; i < M; i++) printf("%d ", choice[i]);
printf("\n");
}
for (int i = s; i <= N; i++) {
choice[n] = i;
DFS(n + 1, i + 1);
}
}
int main()
{
scanf("%d %d", &N, &M);
DFS(0, 1);
return 0;
}
// 조합 벡터로 구현
#include <cstdio>
#include <vector>
int N, M;
std::vector<int> V;
void DFS(int n, int cnt)
{
if (cnt == M) {
for (int i = 0; i < M; i++) printf("%d ", V[i]);
printf("\n");
return;
}
if (n > N) return; // 조건 확인하고 리턴
V.push_back(n);
DFS(n + 1, cnt + 1);
V.pop_back();
DFS(n + 1, cnt);
}
int main()
{
scanf("%d %d", &N, &M);
DFS(1, 0);
return 0;
}
2. 좌표 다루기
=> 어떻게 하면 제자리에 돌아오는지 생각하자!
1행과 N행, 1열과 N열이 연결되어 있는 경우
nx %= N, ny %=N 해주면 무조건 N보다 작은 수가 나온다.
만약 (nx < 1)이면 nx += N 해준다.
=> BOJ 21610 마법사 상어와 비바라기
벽을 만나면 방향 바꾸고 한 칸 전진하는데 속도가 엄청 큰 값이 들어올 수 있는 경우
행과 열의 크기가 다를 때는 진행방향에 따라 나눠서 구해주고 일단 포멧은
speed %= (R - 1) * 2
=> BOJ 17143 낚시왕
이동방향에 칸이 없는 경우,
갔다가 거기에서 더 가는건지 현재 칸에서 방향 틀어서 다시 가는건지 !!
헷갈리지 말것
3. 깨알 팁스
컨테이너 안에 어떤 정보를 담을 것인가 ?
계속 생각하기.
함수 하나 만들고 꼭 디버깅 해라.
꼼꼼하게 해라
심지어 그 함수 복붙해서 여러개 만드는거면 최고로 꼼꼼히 해라.. 알베르토의 추억을 잊지마
++ 바운더리 테스트 꼭 할것
마이 웨이를 가라. 설계하다가 타자 소리 들려도 내 길을 간다. 흔들리지 마
중요한건 꺾이지 않는 마음
4. 벡터 정렬
vector의 pair를 정렬하면
1. 앞의 데이터를 기준으로 오름차순 정렬
2. 뒤의 데이터를 기준으로 오름차순 정렬
벡터는 기본적으로 오름차순 정렬된다.
sort(v.begin(), v.end())
=> 만약 내림차순 정렬하고 싶다면
sort(v.rbegin(). v.rend());
=> 만약 내가 지정해서 정렬하고 싶다면
(배열을 정렬할 때도 똑같이 하면 된다)
sort(v.begin(), v.end(), comp)
이때 comp 함수는 다음과 같이 만든다.
bool comp(const _st &a, const _st &b){
return a.x > b.y;
}
5. 이차원 배열 돌리기
시작위치가 다른 큐브 돌릴 때
// 한번의 길이만큼 돌리고 오프셋 더해주기
void rotate_cube(int x, int y) // 시작점
{
for (int i = 0; i < M; i++) {
for (int j = 0; j < M; j++) {
R[x + i][y + j] = A[x + M - j - 1][y + i];
}
}
}
// 정사각형 회전
rotate_cube(0, 0);
rotate_cube(0, M + 1);
rotate_cube(M + 1, 0);
rotate_cube(M + 1, M + 1);
memcpy(A, R, sizeof(A));
6. BFS
Flood Fill
- 주어진 시작점으로부터 연결된 영역들을 찾는 알고리즘
- 다차원 배열의 어떤 칸과 연결된 영역을 찾는 알고리즘
- 좌표 기준으로 돌릴 수 도 있고, 현재 상태에서 더 발전시킬 수 있는지를 기준으로 판단할 수 있다.
- 1000 * 1000 맵은 플루드필 돌리면 거의 100% 시간초과 난다.
- 1000 * 1000 맵인데 큐를 돌리는 횟수가 최대 1000번이 될 때는 돌릴때마다 버퍼큐 쓰면 안된다.
큐 갈아끼우는 것도 시간초과의 원인이 됨. 상태 발전시킬 맨 마지막 원소들만 버퍼큐에 넣고 한번만 갈아끼워 줘야한다.
값이 있는 좌표를 기준으로 생각하지말고, "값이 없는 좌표"를 기준으로 생각해봐라 !
BOJ 치즈, 백조의 호수, 모래성
- 1000* 1000 맵이어도 BFS는 방문배열 꼭 써줘야 한다 !! 안그러면 메모리/시간 초과 남...
- 아니면 전체 맵 사이즈를 생각해서 특정 시간이 지나면 바로 리턴해주도록 가지치기 할 수 도 있다!!
BFS
- 방문 배열 반드시 필요하다 !
- 그런데 이제 중복 방문할 수 있는 경우,
- 2차원 이상의 방문 배열이 필요한 경우가 있을 수 있다.
- 큐에 데이터 넣을 때 반드시 방문처리 해주기 !!!!!
- (nx, ny) 발전 후 조건 비교할 때 data.move + 1 한 칸 움직인거랑 비교해주어야 한다.
- 변수를 어떤 값으로 초기화 해주어야 하는지 생각하자.
- 0 ? -1 ? 0x7fffffff ?
BOJ 스타트 택시, SWEA 핀볼게임
-같은 시간에 방문했는데 같은 색깔이라면 ? continue
=> 이거 안해주면 메모리 초과 난다
다익스트라 알고리즘
- 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 구하는 알고리즘 이다.
1. 출발노드 지정
2. 최단거리 테이블 초기화
3. 방문한 적 없는 노드 중 최단 거리가 제일 짧은 노드를 선택(혹은 문제의 조건에 맞게 선택)
4. 해당 노드를 거쳐 다른 노드로 가는 거리를 구하여 최단 거리 테이블을 업데이트
언제 우선순위 큐를 사용할까 ?
- 한 노드에서 다른 노드로 향하는데 cost가 다를때.
즉, 가중치가 있을 때
7. 중요한건 꺾이지 않는 마음
맵에서 좌표 1~N까지 할 것인지, 0 ~N-1까지 할 것인지 생각하고 어떻게 코드 짰는지 계속 생각해라...
=> 인덱스 실수하면 자살하는거야 약속하자 진짜 자살하는거다
영역 체크하는 것도 이에 맞게 해야하므로 실수하지 말기
배열 크기!!!! 실수 좀 제발 하지마,...
*** 한 변의 길이가 N인 격자 공간이면 배열이나 구조체 인덱스는 보통 N *N 으로 놓아야 한다
*** 달팽이 사각형 돌릴때는 인덱스 무조건 N*N 설정해야 한다
*** 구조체나 배열 쓸 때 인덱스 최댓값 생각하면서 설정해라
야 인덱스 몇까재 놓아야 하는지 모르겠으면 벡터써
BFS돌릴 때 목적지에 도달하지 않는다는 의미로 -1을 반환했다면 만약 -1을 반환하는 경우는 continue로 제껴주어야 한다 !!!!
절대 실수하지 말것
-> 코드트리 빵
초기화 뭘로했는지 / 뭘로 할건지 (0, -1, ....)계속 생각해
해당 값에 따라서 언제 리턴해주어야 하는지도 계속 생각해
컨테이너 사용했으면 접근할 때 비어있는지 안비어있는지 반드시 확인해줘야 한다.
안그러면 런타임에러남
-> 싸움땅
방향 조작 잘해라 3 넘어가면 %4 꼭 해주기
-> 싸움땅
8. 마지막의 마지막 혹시나 하는 마음이다
**런타임 에러 주의
1. 배열에 할당된 크기를 넘어서 접근했을 때
2. 전역 배열의 크기가 메모리 제한을 초과할 때
3. 지역 배열의 크기가 스택 크기 제한을 넘어갈 때
4. 0으로 나눌 떄 -> 이런거 잘 생각
5. 라이브러리에서 예외를 발생시켰을 때
6. 재귀 호출이 너무 깊어질 때
7. 이미 해제된 메모리를 또 참조할 때
8. 프로그램(main 함수)이 0이 아닌 수를 반환했을 때
9. C/C++에서 반환형이 void가 아닌 main이 아닌 함수에서 아무런 값을 반환하지 않았을 때