목록알고리즘 (76)

키베이루's diary

[C++] 백준 11052번 카드 구매하기

1) 문제설명 https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 2) 아이디어 DP문제는 1부터 차근차근 생각해야 한다. DP [N] : 카드를 N개 갖기 위해 지불해야 하는 금액의 최대로 설정한다. DP [1] = 카드를 1개 갖기 위해 지불해야 하는 최대 금액 = arr [1] * 1 DP [2] = 카드를 2개 갖기 위해 지불해야 하는 최대 금액 = arr [2] * 1 or arr [1] * 2 = dp[0] + arr[2] or dp[1] + ..
알고리즘/DP 2022. 6. 24. 03:25
[C++] 백준 1991번 트리 순회

1) 문제설명 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 2) 아이디어 트리를 구조체가 아닌 2차 배열로 구현하였다. nodes [][0] : 왼쪽 자식, nodes [][1] : 오른쪽 자식으로 설정한다. 왼쪽 입력이. 일 경우 -1을 할당, 마찬가지로 오른쪽 입력이. 일 경우 -1을 할당하고 나머지를 자식들로 할당한다. 이후 순서대로 전위, 중위, 후위 순회 순으로 출력한다. 3) 코드 #include #include #in..
알고리즘/Tree 2022. 6. 22. 17:09
[C++] 백준 16953번 A -> B

1) 문제설명 https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A > a ..
알고리즘/기타 2022. 6. 21. 23:35
[C++] 백준 1655번 가운데를 말해요

1) 문제설명 https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 2) 아이디어 우선순위 큐의 최대 힙과 최소 힙을 둘 다 사용하여 가운데 값을 구해야 한다. 1. 홀수번째 수 일 경우 최대 힙에 값을 넣고 2. 짝수번째 수 일 경우 최소 힙에 값을 넣는다. 3. 최대 힙의 최댓값이 최소 힙의 최솟값보다 작을 경우 두 원소를 바꿔준다. 3) 코드 실패한 코드 : 시간 초과 #include #include #include #inclu..
알고리즘/기타 2022. 6. 20. 19:48
[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
Prev 1 2 3 4 5 6 7 8 ··· 10 Next