SW
-
[백준 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까지만 내가..
-
[백준 1012번] 유기농 배추 (Java 풀이)Algorithm/DFS 2022. 3. 26. 16:21
백준알고리즘 1012번 : 유기농 배추 (Solved.ac 난이도 Silver2) ↑클릭시 문제 link로 이동합니다.😊 DFS의 기본이 되는 문제라고 볼수있겠다. 나는 기본이 없었던 것 같다.(...) 3년전에 풀었던 문제도 이렇게 헤매다보니 역시 알고리즘은 꾸준히 해야한다는 것을 깨닫는다. 복잡한 DFS 문제와는 다르게 1, 즉 배추가 있는 곳만 잘 찾아서 근처 상하좌우로 탐색을 하면서 '추가로 인접한 배추가 있는가?' 라는 것만 check하여 0으로 바꿔주면 된다. 따라서 탐색이 몇번 이루어졌는지 알필요가 없다는 점에서 깊이 우선 탐색 문제 중 간단한 편에 속한다고 생각한다. 풀이 과정 1. 배추밭을 2차원 배열로 정의하고, 배추가 있는 곳마다 값을 1로 대입한다. 2. 2중 for문으로 배추가 있..
-
[백준 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이다. 집중..