java
-
[백준 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이다. 집중..
-
[백준 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이하면 ..
-
[백준 2812번] 크게 만들기 (Java 풀이)Algorithm/Greedy Algorithm 2022. 3. 10. 17:45
백준알고리즘 2812번 : 크게 만들기 역시 그리디 알고리즘은 어떻게 풀지 구상하는 것이 실마리의 절반 이상을 차지하는 것 같다. 엄청 애먹었지만 풀이 방식을 몇번 뒤엎은 끝에 stack을 이용해서 문제 해결에 성공했다. 처음 풀었을 때는 '지워야 하는 숫자의 갯수를 기억함과 더불어 check가 필요한 남은 숫자도 기억해야 하는게 아닌가?' 라고 생각했다. 이런 생각을 가지고 풀다보니 지워야하는 숫자와, 남은 문자열의 길이를 함께 계산하여 무지막지한 소스가 완성되었고 뻘짓을 4시간가량 반복했다. 결과적으로는 남은 문자열의 길이는 크게 신경쓸 필요 없으며, 판단해야하는 것은 두가지 뿐이다. 1. 지워야 하는 숫자의 개수를 먼저 소진했는가? 2. 지워야 하는 숫자가 아직 남았는가? 이 조건만 check하고 ..