자료구조와 알고리즘28 BFS/DFS) 1. 타겟 넘버 5개의 숫자 각각을 더하거나 빼서 타겟 넘버를 만드는 DFS 문제입니다.#include #include #include using namespace std;int cnt = 0;int globalTarget = 0;void dfs(const vector& numbers, int idx, int totalSum){ if (idx == numbers.size()) { if (totalSum == globalTarget) { cnt++; } return; } dfs(numbers, idx + 1, totalSum + numbers[idx]); dfs(numbers, idx + 1, totalSum - numbe.. 2024. 11. 5. 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. 이전 1 2 3 4 ··· 7 다음
