java
-
[백준 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개 노출(위 모서리 ..
-
[백준 2579번] 계단 오르기 (자바)Algorithm/Dynamic Programming(DP, 동적 프로그래밍) 2022. 4. 7. 18:59
백준알고리즘 2579번 : 계단 오르기 (Solved.ac 난이도 Silver3) 계단을 오를 때 얻을 수 있는 점수의 최댓값을 출력하는 문제이다. ↑클릭시 문제 link로 이동합니다.😊 문제를 푼 후기들을 검색해보면 구현자체는 쉬웠다고하는데 나는 동적 프로그래밍이 아직 익지 않아서 그런지 규칙을 찾고 그것을 쪼개는 게 너무 어려웠다. 처음에는 그리디 알고리즘으로 풀어보려고하였으나, 한번 구현해본 뒤 안된다는 것을 알고 포기. 그리디 알고리즘을 적용하기 위해서는 내가 짠 로직의 결과값이 변화가 없어야하는데, 이 문제는 그렇게 되지 않는다. 예를들어서 계단이 다음과 같이 있다면 [1 2 3 4] 내가 밟아야하는 계단은 (1, 3, 4) 로 총 8점이다. 나는 이걸 딴에는 그리디 알고리즘으로 적용하고자하여,..
-
[백준 9095번] 11726번 : 2xn 타일링 (자바)Algorithm/Dynamic Programming(DP, 동적 프로그래밍) 2022. 3. 30. 19:35
백준알고리즘 11726번 : 2xn 타일링 (Solved.ac 난이도 Gold5) 요약 : 피보나치 수열의 규칙이 있는 DP 문제 ↑클릭시 문제 link로 이동합니다.😊 이 문제는 Dynamic Program 알고리즘 중 Top-down 방식으로 풀어보았다. 큰 단위를 작은 단위의 문제로 쪼개서 풀어야하는데, 내가 적절하게 잘 쪼개는지를 검증하기위해 최소 단위를 내가 직접 풀어보았다. 2xN 의 면적을 1x2의 타일과, 2x1의 타일로 채울 수 있는 집합의 개수를 구하는 문제이다. 따지고보면 경우의 수를 구하는 문제인데, 2x3의 타일부터 규칙이 생길것으로 판단되니(타일의 최대길이가 2이므로) 2x1과 2x2의 경우의 수를 구하고, 2x3의 경우의수가 하위 갯수의 집합의 합이 되는 DP로 구성되는지 검증..
-
[백준 9095번] 1, 2, 3 더하기 (자바)Algorithm/Dynamic Programming(DP, 동적 프로그래밍) 2022. 3. 28. 20:50
백준알고리즘 9095번 : 1, 2, 3 더하기 (Solved.ac 난이도 Silver3) ↑클릭시 문제 link로 이동합니다.😊 DP(Dynamic Programming), 동적 프로그래밍의 기본 문제이다. 동적 프로그래밍을 풀이하는데에는 Bottom-up 방식과 Top-down 방식이있다. 이 문제는 Bottom-up 방식으로 풀어보았다. 문제를 작은 단위의 문제로 쪼개서 풀어야하는 만큼, 최소 단위 정도는 내가 직접 풀어보아야한다. 이 문제는 1,2,3의 숫자만 이용하여 만들수 있는 집합의 개수를 구하는 문제이다. 4부터는 '1+ [3으로 만들 수 있는 집합의 개수] / 2 + [2로 만들 수 있는 집합의 개수] / 3 + [1으로 만들 수 있는 집합의 개수]'로 쪼갤 수 있기때문에, 3까지만 내가..