목록분류 전체보기 (96)

키베이루's diary

[C++] 백준 1049번 기타줄

1) 문제설명 2) 아이디어 상점에서 파는 기타 줄의 패키지와 낱개의 개수가 제한이 없으므로 패키지 또는 낱개의 가격이 가장 저렴한 것만 구입을 한다고 생각하면 쉽게 풀린다. 3) 코드 #include #include #include #include #include #include #include #include using namespace std; int n, m; int result, temp; int arr[10001], brr[10001]; int main() { cin >> n >> m; for (int i = 0; i > arr[i] >> brr[i]; } sort(arr, arr + m, less()); sort(brr, brr + m, less()); // 패..
알고리즘/Greedy 2022. 10. 17. 13:22
[C++] 백준 3085번 사탕 게임

1) 문제설명 2) 아이디어 가로/세로 인접한 글자가 다를 때마다 바꾸고 인접한 문자의 개수를 센다. 3) 코드 #include #include #include #include #include #include #include #include using namespace std; int n; char arr[51][51]; int check() { // 가로 세로 중복확인 함수 int maxt = 0; int v1_cnt = 0, h1_cnt = 0; for (int i = 0; i < n; i++) { int v_cnt = 0, h_cnt = 0; // 가로 중복확인 for (int j = 0; j < n; j++) { if (arr[i][j] == arr[i][j + 1]) { v_cnt++; } el..
알고리즘/기타 2022. 9. 30. 15:27
[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
Prev 1 2 3 4 5 6 7 8 ··· 12 Next