본문 바로가기

분류 전체보기330

3주차-6 16637번: 괄호 추가하기 - 주어지는 수에 괄호를 쳐서 가장 높은 수를 제출하는 문제- 모든 경우의수를 체크해봐야 하므로 dfs를 사용한다!- 이 문제의 경우 숫자와 기호를 다른 컨테이너로 분리하고, 인덱스를 통해 계산 순서를 변경하여 처리했다. #include using namespace std;vector num_v;vector oper_v;int n, ret = -987654321;string s;void fastIO(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);}int oper(char a, int b, int c){ if (a == '+') return b + c; if (a == '-') return b - c; .. 2024. 10. 23.
3주차-4 4179번: 불! - 불의 이동 경로와 지훈이의 이동 경로 (최단 거리)를 비교해서 지훈이가 탈출이 가능하다면 최단 거리 출력- 불이 더 빨라서 탈출이 불가능하다면 IMPOSSIBLE을 출력하는 문제 /* 1. 지훈이의 위치, 불이 붙은 위치 2. 탈출할 수 있다면 얼마나 빨리 탈출할 수 있는지, 탈출할 수 없는지 3. 지훈이와 불은 벽을 통과할 수 없음 4. 사람은 1명, 불은 여러 개일 수 있음.*//* 1. BFS -> '#'이면 continue 조건 추가 2. 사람 queue, 불 queue를 따로 생성 2-1. 여러 불의 시작 인덱스를 담을 수 있는 vector 컨테이너 생성 3. 사람이 위치한 좌표값이 '#'이 아니고, BFS 조건이 continue에 걸린다면? 3-1. 사람 BFS값이 불 BFS값보다 작으면.. 2024. 10. 21.
3주차-5 16234번: 인구 이동 - 요약하면 국경선을 공유하는 두 나라의 인구 차이가 l 이상이고, r 이하라면, 인구 이동이 일어난다.- 인구 이동이 일어나면, 각 칸의 인구수는 (연합의 인구수 / 연합을 이루는 칸의 개수)가 된다. #include using namespace std;int day;int n, l, r;int a[54][54];int visited[54][54];int dy[] = {-1, 0, 1, 0};int dx[] = {0, 1, 0, -1};int tot;int cnt;vector > v;void dfs(int y, int x) { visited[y][x] = 1; tot += a[y][x]; cnt++; v.push_back({y, x}); for (int i = 0; i = n.. 2024. 10. 21.
3주차-완전탐색 완전탐색은 brute force 라고 불리는 탐색 방법. 어떤 벽을 4개를 세우고 한 점으로부터의 최단 거리를 구하는 문제라면,완전탐색은 모든 경우의 수를 다 계산해서 따지는 알고리즘이 완전탐색 - 시간복잡도가 1억 미만이면 시도해볼만하다.- 반복문으로 해결할 수 있다면 반복문으로 하는게 좋다.- nC1, nC2 와 같이 조합을 이용하여 경우의 수를 다 계산해야 하는 경우 재귀함수를 사용하는 것이 좋다.    백트래킹은 완전탐색에서 불필요한 부분을 제외한 탐색 방법  - 이 경우의 수는 탐색하지 않아도 될 것 같은데? 라고 가능성이 없는 경우의 수를 제외시키는 것 2024. 10. 21.

티스토리툴바