목록알고리즘 (76)

키베이루's diary

[C++] 백준 13023번 ABCDE

1) 문제설명 https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 2) 아이디어 정점들을 입력하고 모든 정점에서 DFS를 따로따로 돌려주어서 DFS를 실행한 횟수가 4번 이상이면 친구의 친구가 4번있다는 뜻이다. 3) 코드 #include #include #include #include #include #include #include #include using namespace std; int visited[2001]={0,}; vector v[2001]; int flag = 0; int maxt = 0; void dfs(int x, int cnt) {..
알고리즘/BFS, DFS 2022. 6. 14. 13:28
[C++] 백준 2298번 동전 1

1) 문제설명 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 2) 아이디어 DP문제는 항상 기준을 정해두고 생각해야 한다. 이번 문제 같은 경우 DP [X원이 될 수 있는] = 경우의 수로 놓고 생각하였다. 순차적으로 생각해보면 DP [1] : 1원이 될수있는 경우의 수는 1원짜리 하나로 만들수있기때문에 DP[1] = 1이 된다. DP [2] : 2원이 될수있는 경우의 수는 1원짜리 2개 | 2원짜리 1개로 만들 수 있다. DP[2] = 2 D..
알고리즘/DP 2022. 6. 13. 18:50
[C++] 백준 2206번 벽 부수고 이동하기

1) 문제설명 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 2) 아이디어 벽을 한 번만 부술 수 있기 때문에 처음에는 단순히 벽이 가로막고 있고 그 벽 다음이 뚫려있다면 벽을 뚫고 BFS를 순환하도록 구현하였는데 철저하게 틀린 답이었다. 먼저 벽을 뚫었을 때의 거리와 벽을 뚫지 않았을 때의 거리 중 뭐가 최소가 나오는지 알 수 없었고 벽을 먼저 뚫고 지나가면 나중에 나오는 벽을 뚫을 수없어 목표지점에 도달하지 못할 ..
알고리즘/BFS, DFS 2022. 6. 13. 12:07
[C++] 백준 2579번 계단 오르기

1) 문제설명 2) 아이디어 bottom - up 구조의 for문 DP사용 d [0] = 첫 번째 계단 d [1] = 첫 번째 계단 + 두 번째 계단 d [2] = 첫 번째 계단 + 두 번째 계단 or 두번째 계단 + 세 번째 계단 중에 큰 것. d [i] = i-2번째 계단까지의 최대 + i번 계단 or i-3번째 계단까지의 최대 + i-1번째 계단 + i번째 계단. 3) 코드 int main() { int n; int* arr; cin >> n; arr = (int*)malloc(sizeof(int) * n); for (int i = 0; i > arr[i]; } d[0] = arr[0]; // 10 d[1] = arr[0] + arr[1]; d[2] = max(arr[..
알고리즘/DP 2022. 6. 12. 14:08
[C++] 백준 16928번 뱀과 사다리 게임

1) 문제설명 2) 아이디어 주사위를 최소로 굴리는 횟수를 출력해야 하기 때문에 BFS를 사용했다. 반복문을 사용하여 주사위를 굴려서 도착한 곳이 사다리 or 뱀이 있는 곳이면 사다리 or 뱀의 목표지점으로 이동한다. 방문처리에 유의하며 BFS를 구현하면 문제없이 해결할 수 있다. ※ 서로 다른 위치의 사다리에서 같은 곳으로 이동할 수 있고 뱀을 타고 내려가도 최소 횟수로 이동할 수 있는 점을 유의한다. 3) 코드 #include #include #include #include #include #include #include #include using namespace std; int arr[120]; int range[120] = { 0, }; int n, m; int result; queue a; i..
알고리즘/BFS, DFS 2022. 6. 11. 12:50
[C++] 백준 7579번 토마토

1) 문제설명 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 2) 아이디어 기존 7576번의 토마토에서 층을 더 쌓아올린 문제이다. 풀이는 기존 7576번의 토마토와 같다. 7576번 토마토 참고 : https://kiveiru.tistory.com/32?category=557954 [C++] 백준 7576번 토마토 1) 문제설명 2) 아이디어 1. BFS의 시작점이 여러 곳이다 2. 전개가 막혀있는 부분이 있다. 3...
알고리즘/BFS, DFS 2022. 6. 11. 05:53
[C++] 백준 1697번 숨바꼭질

1) 문제설명 2) 아이디어 동생을 찾는 가장 빠른 시간을 찾기 위해서 BFS를 사용했다. 시작 지점에서 +1, -1, +현재 좌표로 식을 세워서 BFS 탐색을 실시하면 쉽게 구할 수 있다. 3) 코드 #include #include #include #include #include #include #include #include using namespace std; int arr[100001]; int range[100001]; int cnt = 0; int dfs(int x, int k) { queue q; arr[x] = 1; q.push(x); if (x == k) { return 0; } while (!q.empty()) { x = q.front(); q.pop(); int dx[] = { -1,..
알고리즘/BFS, DFS 2022. 6. 10. 17:39
[C++] 백준 7576번 토마토

1) 문제설명 2) 아이디어 1. BFS의 시작점이 여러 곳이다 2. 전개가 막혀있는 부분이 있다. 3. 전개가 막혀서 0(익지 않은 토마토)을 1(익은 토마토)로 바꾸지 못할 경우 -1을 출력한다. 정도만 해결한다면 기본 BFS문제와 다른 점이 없다. 1번의 경우 시작점을 미리 큐에 넣어둠으로써 해결하였고 2번의 경우 if문으로 예외 처리하였다. 3번의 경우는 BFS를 사용해서 0 (익지않은 토마토)을 1 (익은 토마토)로 교체해 준다음에 배열 처음부터 끝까지 순회하면서 0이 있다면 -1을 출력하는 것으로 해결하였다. 3) 코드 #include #include #include #include #include #include #include #include using namespace std; int a..
알고리즘/BFS, DFS 2022. 6. 10. 14:40
Prev 1 ··· 3 4 5 6 7 8 9 10 Next