본문 바로가기

자료구조와 알고리즘/[Inflearn_큰돌] 10주 완성 C++ 코딩테스트15

5주차-그리디 알고리즘 탐욕법이라고 불리는 그리디 알고리즘은, 현재 선택에서 가장 좋은 선택을 하는 것이 전체적인 결과에 대해서 좋은 방향으로 갈 것이다 라는 것을 상정한다. 이렇게 하면 풀릴 것 같은데? 라는 현실적인 명제를 가지고 구현을 하는 것이 그리디 알고리즘의 접근법! 그리디 알고리즘은 정렬, 우선순위큐(pq)를 사용하면 풀리는 경우가 대다수이다! 2024. 10. 23.
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.

티스토리툴바