Algorithm/Greedy Algorithm
-
[백준 11727번] 2×n타일링2 (자바)Algorithm/Greedy Algorithm 2022. 4. 16. 18:35
백준알고리즘 11727번 : 2Xn 타일링 2 (Solved.ac 난이도 Silver3) https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 2xn 타일링1 문제를 풀었으면 이 문제도 어렵지 않게 풀수 있을 것 같다. 역시 dp 알고리즘의 기본은 쪼개기다. 다만 이번에는 2xn 타일링1 문제때와는 달리 '2x1 막대가 오는 경우와 1x2 막대가 오는 경우'로 나누지 않고 '2x1 막대가 오는 경우와 2x1 막대가 오지 않는 경우'로 나눠주었다. 이렇게 나눈 이유는 이번 문제에는..
-
[백준 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개 노출(위 모서리 ..
-
[백준 12904번] A와 B (자바)Algorithm/Greedy Algorithm 2022. 3. 18. 02:14
백준알고리즘 12904번 : A와 B (Solved.ac 난이도 Gold5) A와 B로만 이루어진 문자열 S는 문자열 T로 변환가능한가?를 맞춰야하는 문제이다. 역시나 이런 문제는 문자열 S를 어떻게 T로 만들까를 고민하기보다는 문자열 T를 S로 되돌릴수있느냐, 를 판별하는 것이 쉽다. 문자 A를 제거할 경우에는 문자열의 순서가 바뀌지 않지만 문자 B를 제거하는 경우, 문자열의 순서가 바뀌므로 Stack이든 Queue든 Deque든 두개 이상의 변수를 설정하여 바뀔때마다 각 문자들의 위치를 바꿔주면 어렵지 않게 맞출수 있을 것같다. - 정답 소스 중StringBuilder를 이용해서 필요할때마다 끝 문자를 자르고 문자열 위치를 reverse시켜주는 엄청 깔끔한 코드를 보았다. T = new StringB..
-
[백준 11497번] 통나무 건너뛰기(자바)Algorithm/Greedy Algorithm 2022. 3. 17. 20:08
백준알고리즘 11497번 : 통나무 건너뛰기 두 통나무 간의 최대 높이의 차를 최소한으로 줄여야하는 문제이다. 다만 통나무가 원형으로 이어져있으므로 단순 정렬만으로는 N[0] 과 N[N.length-1] 간의 차이가 극대화되므로 오답이 발생한다. 나는 통나무간의 간격을 줄이기 위해서는 최저점 N[0]과 최고점 N[N.length-1] 간의 지점들을 두 부류로 나누어서 찾아야한다고 생각했다. 즉 최저점과 최고점을 연결하는 선이 두개가 되도록 해야, 최대 높이의 차를 줄일수 있다고 판단하였다. 따라서 N[0], N[2], N[4] ... N[N.length-1] 간의 비교와 N[0], N[1], N[3] ... N[N.length-1] 간의 비교를 동시에 해주도록하였다. 풀이 과정 1. 통나무 목록을 오름차..
-
[백준 15903번] 카드 합체 놀이(자바)Algorithm/Greedy Algorithm 2022. 3. 16. 19:47
백준알고리즘 15903번 : 카드 합체 놀이 이 문제는 매회 숫자가 더 작은 카드를 골라서 덧셈하도록하여 카드들의 총합을 작게 만드는 것이 목표이다. 오름차순으로 정려한 뒤에, 최초 카드들중 가장 작은 숫자들끼리 더했을 때, 그 숫자가 새로운 작은 숫자일수도, 그렇지 않을 수도 있기 때문에 이를 비교하기위해 더해서 새롭게 생성된 숫자는 queue에 담아서 별도로 비교해주도록 하였다. 풀이 과정 1. 숫자를 배열에 담고 오름차순으로 정렬한다. 2. 카드 합체 횟수 M만큼 for문을 돌며, queue가 비어있거나 queue의 peek값이 배열의 비교대상보다 크면 배열 card의 값을, 크지 않으면 queue의 poll값을 합체 대상으로 뽑는다. 3. 2번의 행위를 2번 반복하여 더 해진 값을 queue에 두..
-
[백준 2212번] 센서(자바)Algorithm/Greedy Algorithm 2022. 3. 12. 16:54
백준알고리즘 2212번 : 센서 센서가 커버 가능한 수신 가능 영역을 잘 쪼개보니 실마리를 찾을 수 있었다. 센서의 위치를 정렬한뒤, 위치별 차이(즉 센서별 수신이 필요한 영역)를 새로운 배열로 정의한다. 새로운 배열(gap)의 값 중 큰 것부터 집중국의 개수-1 만큼 차감하여 합의 최솟값을 구한다. (집중국이 1개일때 차감없이 모든 영역을 커버할 수 있다.) 센서의 위치가 각 1 3 6 7 9 라고 한다면 각 센서의 차이는 2 3 1 2 이다. 집중국이 1개일때, 수신 가능 영역의 길이의 합은 2 + 3 + 1+ 2 = 8이다. 집중국이 2개일때, 수신 가능 영역의 길이의 합은 2 + 0 + 1+ 2 = 5이다. 집중국이 3개일때, 수신 가능 영역의 길이의 합은 2 + 0 + 1+ 0 = 3이다. 집중..
-
[백준 2437번] 저울 (Java 풀이)Algorithm/Greedy Algorithm 2022. 3. 11. 18:00
백준알고리즘 2437번 : 저울 이런 Greedy Algorithm 문제가 Algorithm Test를 준비하기 위한 문제인 동시에 매몰 당하지 않아야하는 문제인것 같다. Test에 유용한 문제인 이유는 특정한 수학적 공식을 알지 못하면 풀기 몹시 어렵기 때문이고 ㄱ매몰 당하지 않아야하는 문제인 이유도 위와 동일하다. 바꿔말하면 공식을 알기만 하면 쉽게 풀리기 때문에.. 고민하는 데 많은 시간을 쏟는게 좀 허탈하게 느껴지기도 했다. 그래도 개중에는 많은 고민을 거듭한 끝에 수학적 규칙을 간파하는 사람이 있을것이기 때문에, 내가 아직 그런 경지에 이르지 못한 것을 탓해야겠다. 결과적으로 필요한 공식은 'a1=1이고, a(n+1) > S(n)+1일 때 측정할 수 없는 최소값은 S(n)+1이다.' a(n)이 ..
-
[백준 1783번] 병든 나이트 (Java 풀이)Algorithm/Greedy Algorithm 2022. 3. 11. 00:44
백준알고리즘 1783번 : 병든 나이트 처음 보았을 때 조금 까다롭게 느껴졌는데, 규칙을 찬찬히 쪼개면서 생각해보니 어렵지 않게 풀렸다. 드물게 switch~case문을 사용하기에 적합한 문제였던 것으로 보인다. 풀이 과정 1. 나이트는 오른쪽으로만 간다. 2. 나이트는 위아래로 2칸이내에서만 움직이므로, 세로길이가 3이상이면 모든 이동방법을 사용할 수 있다. 3. 이동 횟수가 4이상(가로칸이 5이상)이라면 이동 방법을 모두 한번씩 사용해야하므로, 가로길이가 7이상이면 적어도 2 번은 오른쪽으로 2칸씩 이동해야한다. 4. 2번 3번 규칙에 입각하여, 세로길이(N)가 3이상이고 가로길이(M)가 7이상이라면, 나이트의 방문 최댓값은 M-2이 될것이다. 5. 세로길이가 3이상이고, 가로길이가 4이상 6이하면 ..