목록분류 전체보기 (96)

키베이루's diary

[C++] 백준 15650번 N과 M (2)

1) 문제설명 https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 2) 아이디어 기존 n과 m (1)에서 풀었던 백트래킹을 이용한다. 단 이번에는 중복을 허용하지 않기 때문에 dfs를 돌 때 1부터 순회하는 것이 아닌 그다음수부터 순회하면 중복이 사라진다 ex ) 순회하다가 (2 1 x) , (2 2 x)을 순회하는 것이 아닌 2의 다음수인 (2 3 x) 순으로 순회한다. 3) 코드 #include #include #include #include..
알고리즘/BFS, DFS 2022. 6. 20. 02:30
[C++] 백준 15649번 N과 M (1)

1) 문제설명 https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 2) 아이디어 DFS를 사용하여 백트래킹으로 구현한다. 3) 코드 #include #include #include #include #include #include #include #include using namespace std; int visited[11]; int arr[11]; int m, n; void dfs(int k) { if (k == m) { for (int i =..
알고리즘/BFS, DFS 2022. 6. 19. 00:49
[C++] 백준 2468번 안전 영역

1) 문제설명 https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 2) 아이디어 비가 오는 높이를 0~100까지 전부 반복문으로 돌리면서 BFS를 실행한다. 입력받은 영역이 비가오는 높이보다 크다면 1로 작으면 0으로 설정해주어서 단순화시킨다. 영역 배열을 하나 더 선언해 계속 입력받은 배열로 다시 초기화시켜주는 것이 중요하다. 3) 코드 #include #include #include #include #include #include #include #i..
알고리즘/BFS, DFS 2022. 6. 17. 14:33
[C++] 백준 11724번 연결 요소의 개수

1) 문제설명 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 2) 아이디어 BFS를 사용하여 정점의 개수만큼 BFS를 실행하고 방문하지 않은 정점이 들어올 때마다 카운트를 증가시켜서 연결 요소의 개수를 구하였다. 3) 코드 #include #include #include #include #include #include #include #include using namespace s..
알고리즘/BFS, DFS 2022. 6. 16. 16:33
[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
Prev 1 ··· 5 6 7 8 9 10 11 12 Next