전체 글
-
[백준 1082번] 배 (Java 풀이)Algorithm/정렬(Sort) 2022. 4. 15. 19:36
백준알고리즘 1082번 : 배 (Solved.ac 난이도 Gold5) 박스를 배로 옮기는데 드는 시간의 최솟값을 구하는 문제이다. 이 문제에서 크레인의 무게제한을 비중있게 생각할 필요는 없다. 무게가 많이 나가는 박스부터 옮기되 들수 있는 무게가 적은 크레인이라도 어느 하나의 박스라도 옮길 수 있도록 체크해주면 된다. 따라서 크레인과 박스를 내림차순으로 정렬하고 크레인 배열이 박스 배열을 돌면서 옮겨주면 된다. 옮긴 박스는 체크하고, 크레인 배열이 한 번 돌때마다 시간을 1씩 늘린다. https://www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000..
-
[백준 8979번] 올림픽 (Java 풀이)Algorithm/정렬(Sort) 2022. 4. 13. 21:19
백준알고리즘 8979번 : 올림픽 (Solved.ac 난이도 Silver5) 특정 국가의 올림픽 순위를 출력하는 문제이다. 금메달, 은메달, 동메달 총 3개의 값을 비교하여 적절한 순위를 출력한다. https://www.acmicpc.net/problem/8979 8979번: 올림픽 입력의 첫 줄은 국가의 수 N(1 ≤ N ≤ 1,000)과 등수를 알고 싶은 국가 K(1 ≤ K ≤ N)가 빈칸을 사이에 두고 주어진다. 각 국가는 1부터 N 사이의 정수로 표현된다. 이후 N개의 각 줄에는 차례대로 각 www.acmicpc.net Comparator를 이용하여 2차원 배열의 3개 값을 비교하는 것 까지는 어렵지 않았으나, 동점일 경우에 순위를 확정지을수 있는 방법에 대한 고민이 필요했다. 결과적으로는 2차원..
-
[백준 3273번] 두 수의 합 (Java 풀이)Algorithm/정렬(Sort) 2022. 4. 12. 19:10
백준알고리즘 3273번 : 두 수의 합 (Solved.ac 난이도 Silver3) 더해서 자연수 x를 만족하는 쌍이 몇개 있는지 확인하는 문제이다. https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 처음에는 100만까지 숫자가 주어진다는 것을 확인하여 Int 배열의 크기를 100만으로 만들고, 받아온 숫자값에 1을 넣어서 숫자가 1이면 count한다, 라는 식으로 풀어보았다. 예제를 반영하자..
-
[백준 5052번] 전화번호 목록 (Java 풀이)Algorithm/정렬(Sort) 2022. 4. 11. 19:22
백준알고리즘 5052번 : 전화번호 목록 (Solved.ac 난이도 Gold4) 한 전화번호가 다른 전화번호의 접두어인 경우를 찾는 문제이다. String Type의 실수를 정렬하는 Case를 고민하여 풀 수 있다. ↑클릭시 문제 link로 이동합니다.😊 이 문제를 풀면서 발생한 애로사항 첫번째는 문제의 몰이해다. 문제에서 제시한 제한 조건은 하나의 전화번호가 다른 번호의 '접두어'만 아니여야한다는 것이다. 예를들어 번호 목록이 911과 911123이면 911이 911123의 접두어이므로 NO를 출력해야하는게 당연하나 나는 포함관계가 아니여야한다고 착각하여 911과 11911의 case에도 NO를 출력해야 한다고 판단하고 문제를 풀었다. (시간 초과가 계속 발생하여 틀린줄도 몰랐다..) 역시 소스를 짜기..
-
[백준 2470번] 두 용액 (Java 풀이)Algorithm/정렬(Sort) 2022. 4. 10. 19:25
백준알고리즘 2470번 : 두 용액 (Solved.ac 난이도 Gold5) 여러 용액 중 그 합의 절댓값이 가장 작은 두 용액을 찾아내는 문제이다. 2차원 배열로 값을 담아 for문을 한 번 돌면서 그 합이 가장 낮은 숫자 들을 찾는다. ↑클릭시 문제 link로 이동합니다.😊 시간 제한이 1초라서 이중 for문으로 돌리면 무조건 시간초과가 날 것 같았다. 그래서 떠올린 방법이 2차원 배열로 값을 담되, 값을 담으면서 음수는 미리 check해두는 것이다. 절댓값으로 정렬하고 난 뒤에 for문을 한번만 돌면서 i번째와 i+1번째 값을 비교한다. 이 두 숫자의 합이 가장 작은 경우를 찾는다. (절대값으로 처리된 숫자로는 정확한 합을 구할 수 없기 때문에 양/음수를 check해둔 값을 불러와서 실제 숫자를 호출..
-
[백준 10816번] 숫자 카드 2(Java 풀이)Algorithm/정렬(Sort) 2022. 4. 9. 17:05
백준알고리즘 10816번 : 숫자 카드 2 (Solved.ac 난이도 Silver4) 특정 숫자들의 갯수를 카운트하고 출력하는 문제이다. HashMap을 이용하여 풀수 있다. ↑클릭시 문제 link로 이동합니다.😊 예전에 풀었을 때는 시간초과가 나서 못풀었는데, HashMap을 이용하는 것 뿐만아니라 반복문을 돌면서 단순 출력을 하는것이아니라 StringBuilder에 담는 등의 처리가 필요해보인다. 풀이 과정 1. HashMap에 숫자카드를 담는다. 이때 카드번호를 key값으로 담고 갯수를 value로 담는다. 기존 카드번호가 있다면 key값을 호출하여 갯수를 하나더해준다. 2. 상근이가 가진 값을 받아오면서 해당 key값이 있다면 value를, 없다면 0을 append한다. * 카드번호별 value를..
-
[백준 1149번] RGB거리 (자바)Algorithm/Dynamic Programming(DP, 동적 프로그래밍) 2022. 4. 8. 10:43
백준알고리즘 1149번 : RGB거리 (Solved.ac 난이도 Silver1) 집을 빨강, 초록, 파랑색으로 칠할 때, 그 최소비용을 구하는 문제이다. ↑클릭시 문제 link로 이동합니다.😊 집이 N개 있을 때, N번째 집이 나올 수 있는 색깔의 경우의수를 따져보자. 1. N번째 집이 R(Red)일때, N-1번째 집은 G(Green) or B(Blue)여야한다. 2. N번쨰 집이 G일때, N-1번째 집은 R or B여야한다. 3. N번째 집이 B일때, N-1번째 집은 R or G여야한다. 이것을 각각의 배열로 만들어서 매 회마다 N번째 집이 R일때의 최소 비용, G일때의 최소 비용, B일때의 최소 비용만 선택적으로 따오도록 한뒤, 마지막에 R[N-1], G[N-1], B[N-1]의 비용중 가장 작은 수..
-
[백준 1041번] 주사위 (자바)Algorithm/Greedy Algorithm 2022. 4. 8. 02:03
백준알고리즘 1041번 : 주사위 (Solved.ac 난이도 Gold5) 주사위의 갯수가 커질때마다 나타나는 규칙성을 발견하여 이를 점화식으로 변환하여 풀수 있는 문제이다. ↑클릭시 문제 link로 이동합니다.😊 1. 주사위가 보이는 면적의 갯수는 몇개일까? 1*1*1 = 1개일 경우 : 5(1*1*5)면 2*2*2 = 8개일 경우 : 20(2*2*5)면 3*3*3 = 27개일 경우 : 45(3*3*5)면 4*4*4 = 64개일 경우 : 80(4*4*5)면 2. 주사위별 노출되는 면적은 몇개씩일까? 1개일 경우 : 면 5개 노출(1개 주사위) = 5 8개일 경우 : 면 3개 노출(위 4개 주사위) + 면 2개 노출(1*4=4개) = 12 + 8 + 0 = 20 27개일 경우 : 면 3개 노출(위 모서리 ..