목록알고리즘 (76)

키베이루's diary

[C++] 백준 1021번 회전하는 큐

1) 문제설명 2) 아이디어 STL의 덱을 사용하여 문제를 해결하였다. 덱에 1~N까지 숫자를 차례대로 저장하고 내가 찾고자 하는 숫자의 인덱스를 저장하고 그 값이 덱 사이즈의 절반보다 작다면 2번 연산을 실행, 절반보다 크다면 3번 연산을 실행하고 그 횟수를 카운트하여 출력한다. 3) 코드 #include #include #include #include #include #include #include #include using namespace std; deque dq; int n, m; int k; int arr[51]; int cnt = 0; void secal() { // 왼쪽으로 한 칸 이동시키는 함수 int temp; temp = dq.front(); dq.pop_front(); dq.push..
알고리즘/기타 2022. 9. 30. 09:50
[C++] 백준 2805번 나무 자르기

1) 문제설명 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 2) 아이디어 m미터의 나무를 잘라서 가져가야 하므로 이진 탐색을 이용하여 입력받은 배열들에서 mid를 빼고 그 값들(temp)을 다 더해 필요한 양만큼 가져가야 한다. 가져가야 할 양보다 temp 가 더 작다면 나무를 더 작게 잘라야 하고 가져가야 할 양보다 temp가 크거나 같다면 나무를 더 크게 잘라야 한다. 이분 탐색을 계속 돌면서 높이..
알고리즘/기타 2022. 7. 19. 23:39
[C++] 백준 1654번 랜선 자르기

1) 문제설명 2) 아이디어 입력받은 값들 중 가장 큰 값을 1부터 이분 탐색을 실시한다. 1과 가장 큰 값의 중간값으로 배열의 값을 나누어 그 몫의 합이 n보다 작다면 적 은값으로 다시 이분 탐색을 실시하고 크다면 큰 값으로 이분탐색을 실시한다. 이분탐색을 진행하며 중간값의 최댓값을 출력한다. 3) 코드 #include #include #include #include #include #include #include #include using namespace std; long long arr[1000001]; long long k, n; // k : 잘라야하는 랜선의 갯수, n : 필요한 랜선의 갯수 long long result; void binary_search(long long start, lon..
알고리즘/기타 2022. 7. 18. 22:34
[C++] 백준 10816번 숫자 카드 2

1) 문제설명 https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 2) 아이디어 이분 탐색을 이용하여 배열 안의 키 값을 찾는다. 단 겹치는 숫자카드의 개수를 세어야 하므로 이분 탐색을 실행하면서 찾고자 하는 키값들 중 배열의 맨 처음 인덱스와 마지막 인덱스의 차이를 출력한다면 그 키값이 배열 안에 몇 개 있는지 알 수 있으므로 이를 이용한다. up_binary_search : 배열 안의 키값의 맨 마지막 인덱스를..
알고리즘/기타 2022. 7. 16. 18:17
[C++] 백준 1707번 이분 그래프

1) 문제설명 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 2) 아이디어 이분 그래프는 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지의 색으로 칠할 수 있는 그래프를 말한다. 이분 그래프를 구현하기 위해서 bfs를 사용하고 bfs로 정점들을 방문하되 번갈아 가면서 색을 칠해준다. visited배열에 red는 1로 blue는 2로 인접한 정점을 방문하면서 저장하였다. 이후 정점들을 차례로 방문하면서 인접한 정점이 색이 같다면 ..
알고리즘/BFS, DFS 2022. 7. 16. 17:13
[C++] 백준 4963번 섬의 개수

1) 문제설명 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 2) 아이디어 BFS 혹은 DFS를 이용해 순회하면서 섬의 개수를 찾는 문제이다. BFS를 사용하여 순회하고 BFS가 종료되면 카운트를 세주는 방식으로 구현하였다. 여러 번의 테스트 케이스를 사용해야 하기 때문에 전역 변수로 선언된 큐와 배열을 초기화하는 것을 잊지 말자. 3) 코드 #include #include #include #include #include #include..
알고리즘/BFS, DFS 2022. 7. 13. 14:16
[C++] 백준 13398번 연속합 2

1) 문제설명 https://www.acmicpc.net/problem/13398 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 2) 아이디어 DP를 2중 배열로 선언한 뒤 숫자를 제거했을 때와 제거하지 않았을 때를 따로 저장한다. DP [0][X] : 숫자를 제거하지 않은 연속합 DP [1][X] : 숫자를 하나 제거한 연속합 3) 코드 #include #include #include #include #include #include #include #include using namespace std; int d..
알고리즘/DP 2022. 7. 13. 09:13
[C++] 백준 11057번 오르막 수

1) 문제설명 https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 2) 아이디어 전에 풀었던 쉬운 계단 수와 비슷한 문제이다. https://kiveiru.tistory.com/16?category=557953 [C++] 백준 10844번 쉬운 계단 수 1) 문제설명 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈..
알고리즘/DP 2022. 7. 12. 10:36
Prev 1 2 3 4 5 6 ··· 10 Next