알고리즘/백준 (109) 썸네일형 리스트형 [BOJ 2981] 검문(Java, 유클리드 호제법, Set) https://www.acmicpc.net/problem/2981 2981번: 검문 문제 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 � www.acmicpc.net 이 문제 풀이의 핵심은 유클리드 호제법이다. 유클리드 호제법은 어떤 수 a와 b가 있을 때(a > b), a와 b의 최대공약수는 b와 a % b와 동일하다. 증명은, 다음 유튜브를 참고하길, https://www.youtube.com/watch?v=J5Yl2kHPAY4 1. 인접한 수들을 정렬한다. * 정렬의 이유는, gcd에 들어가는 매개변수가 음수가 되지 않기 위해서이다. 음수가 되지 않도록 조건을 단다면.. [BOJ 7569] 토마토(JAVA, BFS, QUEUE) https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 1. 익은 토마토 위치 구하고 큐에 넣기 2. 큐에 들은 아이템을 기반으로 BFS 탐색을 통해서, 더 이상 익은 토마토가 추가되지 않으면 종료. * 큐에 들은 아이템을 이용, 토마토 배열을 탐색하면 시간초과 발생. 해설코드(C++). 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 3.. [BOJ 11652] 카드(자바 적응기, 자료구조, Hashmap sort by key and value) https://www.acmicpc.net/problem/11652 11652번: 카드 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지 www.acmicpc.net 1. ==은 equals와 다르다. - 자바에서는 ==은 reference를 의미하기 때문에, value 비교가 아니다. 따라서, equals를 사용해야 한다. 2. Hashmap 자료구조 키와 값으로 정렬하기 - 새로운 Comparator를 만들고, compare 함수를 오버라이딩한다. 해설코드(Java) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19.. [BOJ 1449] 수리공 항승(C++) https://www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net 물이 새는 곳을 다 막을 수 있는 테이프의 최소 개수를 알아봐야 한다. 구멍난 곳부터 시작해서 막는 것이 더 많은 범위를 커버할 수 있다. (그리디 알고리즘) 해설코드(C++). 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 #include #include #in.. [BOJ 2437] 저울(C++, 자세한 설명) https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓� www.acmicpc.net 해설코드(C++). 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 #include #include #include using namespace std; vector v; int val, next = 0, N; int main() { cin >> N; for(int i = 1; i > val; v.push_back(val); .. [BOJ 1783] 병든 나이트(C++) https://www.acmicpc.net/problem/1783 1783번: 병든 나이트 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 이 문제는 체스가 위와 아래로 움직일 때, 항상 오른쪽으로 간다. 다양한 케이스를 코드로 구현하면 되는 문제이다. 해설코드(C++). 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 #include using namespace std; long long N, M; long long answer = 1; int main() { cin >> N >> M; if(N >= 3){ if(M .. [BOJ 1138] 한 줄로 서기(C++). https://www.acmicpc.net/problem/1138 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 � www.acmicpc.net N번째 사람부터 놓기 시작하면, 현재의 상황만 보고 순서를 고려하면 된다.(그리디) i번째를 놓을 때, i + 1번째부터 N까지 놓아졌다면 모든 수는 i보다 크므로, 아래의 코드를 작성할 수 있다. 해설코드(C++). 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35.. [BOJ 2624] 동전 바꿔주기(C++, 다이나믹 프로그래밍) https://www.acmicpc.net/problem/2624 2624번: 동전 바꿔주기 명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방법은 여러 가지가 있을 www.acmicpc.net 해설코드(C++). 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 #include #include #include using namespace std; int T, k; int dp[.. 이전 1 2 3 4 5 6 7 ··· 14 다음