모항이코딩한다

풀이방법 사용된 것: 정렬 HashSet 2022.03.23 오답노트 #1337 : 올바른 배열 풀이방법 및 문제점 2022.03.21 주어진 수열을 오름차순 정렬한 뒤, 정렬된 주어진 수열에 포함된 가장 긴 연속하는 수열을 찾아서, 그 수열의 길이가 5 이상이라면 0을 출력하고, 5 미만이라면 5에 blowupmomo.tistory.com 일단, 전체 배열을 오름차순으로 정렬한다. 정렬된 전체 배열을 1~5번째, 2~6번째 ... n-4~n번째 요소의 묶음 순으로 탐색할 것이다. 각 묶음을 탐색하는 방법은 다음과 같다. 이번에 탐색할 묶음이 아래와 같이 arr[3]~arr[7]이라고 하자. arr[0] arr[1] arr[2] arr[3] arr[4] arr[5] arr[6] arr[7] arr[8] ..

풀이방법 및 문제점 2022.03.21 주어진 수열을 오름차순 정렬한 뒤, 정렬된 주어진 수열에 포함된 가장 긴 연속하는 수열을 찾아서, 그 수열의 길이가 5 이상이라면 0을 출력하고, 5 미만이라면 5에서 해당 수열의 길이를 뺀 값을 출력하였다. 그러나, 이렇게 하면 1 2 3 위와 같은 연속되는 수열이 있을 때에는 2를 잘 출력하지만 1 3 5 위와 같은 경우를 캐치하지 못한다. 2, 4를 넣으면 연속되는 길이 5의 수열이 될 수 있다는 것을 알아내고 2를 출력해야 하는데, 그냥 무의미한 수들로 판단해버리기 때문이다. 저렇게 띄엄띄엄 연속되는 경우를 어떻게 해야 잡아낼 수 있을까? 알고리즘 분류에 투 포인터가 있던데 그걸 힌트 삼아서 잘 생각해봐야겠다. 2022.03.23 해결되었다. 정답 게시물 바..

풀이방법 사용된 것: 정렬 2022.03.21 심판 5명의 점수를 읽어와 int[] 배열에 저장한다. Arrays.sort()를 사용하여 배열의 요소들을 오름차순으로 정렬한다. 배열의 네 번째 요소에서 두 번째 요소를 뺀 값이 4 이상인지 체크한다. 4 이상이라면 "KIN"을, 4 미만이라면 배열의 두 번째, 세 번째, 네 번째 요소를 더한 것을 출력 문자열에 추가한다. 코드 Java(2022.03.21) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main..

풀이방법 사용된 것: 다이나믹 프로그래밍(DP) 2022.03.15 k번째 계단에 도달하는 방법의 수는 다음의 두 가지가 있다. 각 계단에 대하여, 해당 계단까지 도착하는 위의 두 가지 방법 중 더 큰 점수를 모아올 수 있는 쪽을 선택하면 된다. 이 방법을 이용하여, 각 계단마다 각각의 계단에 도달하기까지 모아올 수 있는 최대의 점수를 각각 구한다. 나는 이 값을 max_score[] 배열에 저장하였다. (max_score[i] = i번째 계단에 도달하기까지 모아올 수 있는 최대의 점수) 그럼 max_score[마지막 계단의 번호]의 값이 바로 정답이다. 코드 Java(2022.03.15) import java.io.BufferedReader; import java.io.IOException; impor..

풀이방법 사용된 것: 다이나믹 프로그래밍(DP) 2022.03.14 버튼을 k번 눌렀을 때의 결과값은 k-1번 눌렀을 때의 결과값을 이용하여 구해야 한다. k-1번 눌렀을 때의 결과값은 또다시 k-2번 눌렀을 때의 결과값을 이용하여 구해야 한다. ... 결국 1번 눌렀을 때의 결과값부터 모두 살펴야 한다. 이걸 매번 반복했다가는 시간초과가 난다. 즉, 가능한 답을 미리 구해놓고 출력 시에 꺼내오는 방식으로 풀어야 한다. 따라서 다이나믹 프로그래밍을 쓰기에 매우 적합한 문제이다. 주어지는 k의 최댓값은 45이다. 45번의 반복문을 돌려, 버튼을 1번, 2번, ... , 45번 누를 때의 A와 B의 개수를 모두 미리 구해서 배열에 저장해놓고, k값에 맞게 그 배열에서 정답을 꺼내오면 된다. 코드 Java(2..

풀이방법 사용된 것: 정렬 그리디 알고리즘 2022.03.05 N의 최댓값까지 커버하려면 $f_{44}$까지만 미리 구해놓으면 된다. 길이가 45인 Long 정수 배열을 선언하고, 이 안에 $f_0$부터 $f_{44}$까지를 미리 다 구해 저장해둔다. 이 피보나치 수 배열을 내림차순으로 정렬한다. 입력값으로 수 N이 주어졌다고 하자. 피보나치 수 배열의 앞부터(큰 수부터) 방문하며, N보다 작거나 같은 피보나치 수가 발견되면 즉시 해당 수를 출력할 수 배열에 추가하고, N에서 그 수를 빼준다. 이를 N == 0이 될 때까지 반복한다. 이렇게 구해진 수들을 오름차순으로 정렬한 뒤에 출력하면 된다. 코드 Java(2022.03.05) import java.io.BufferedReader; import jav..

풀이방법 사용된 것: 정렬 두 개의 포인터(two pointers) 2022.03.05 주어진 정수 배열을 일단 오름차순 정렬한다. 그 후 다음과 같은 방법으로 차근차근 합을 살펴본다. 빨간 화살표로 표시된 놈과 파란 화살표로 표시된 놈을 더해보고, 그 합이 X와 동일하면 경우의 수를 1 증가시킨다. 편의를 위해 빨간 화살표로 표시된 수를 앞놈이라고 하고 파란 화살표로 표시된 수를 뒷놈이라고 부르겠다. 앞놈, 뒷놈의 위치를 각각 가리키는 정수형 변수 두 개(아래의 코드에서는 i와 j)를 사용한다. 이중 반복문을 돌리며 앞에서부터(즉 작은 수부터) 앞놈과 뒷놈의 합을 점검해주면 된다. 이 때, 수열을 오름차순 정렬해두었으므로, 앞놈의 값이 이미 X보다 크거나 같은 경우 어떤 뒷놈을 선택하더라도 그 합이 X..

풀이방법 사용된 것: 두 개의 포인터(two pointers) 2022.03.05 살펴볼 구간의 시작 인덱스, 끝 인덱스를 각각 가리키는 두 개의 int형 변수(아래의 코드에서는 i와 j)를 이용한다. 두 개의 반복문을 돌리며 합계값을 구하여 m과 비교하면 된다. 코드 Java(2022.03.05) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int n, m, ans;//수열의 길이, 목표 정수, 출력할 답 static int[] nums;//수열 static StringTok..

풀이방법 사용된 것: Comparator 오버라이딩 2022.03.05 문제에서 제시하는 기준에 맞게 정렬하는 Comparator를 정의하여 사용해주면 된다. 이 때, str1.compareTo(str2);를 사용하였는데, 이 함수는 str1이 사전순으로 str2보다 앞설 때는 음수를, 그렇지 않을 때는 양수를 리턴한다. 코드 Java(2022.03.05) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Comparator; public class Main { static int n;//기타 개수 static St..

풀이방법 사용된 것: 큐 2022.03.02 큐를 활용했다. 이번 턴에 뱀 머리가 새롭게 이동해야 하는 칸의 좌표가 (row, col)이라 하자. 만약 (row, col)의 위치에 뱀의 몸이 있거나 벽이 있다면 게임을 종료하고, 현재 시간을 화면에 출력한다. 만약 (row, col)의 위치에 아무것도 없다면, 큐에 (row, col)을 넣어주고 큐의 반대쪽 끝에서 요소 하나를 poll 한다. 만약 (row, col)의 위치에 사과가 있다면, 큐에 (row, col)을 넣어주고 큐에서 아무것도 poll 하지 않는다. 방의 각 좌표에 무엇이 있는지는 2차원 정수 배열로 기록하였다. 해당 칸에 아무것도 없다면 0을, 뱀의 몸이나 머리가 있다면 1을, 사과가 있다면 2를 저장하였다. 코드 Java(2022.03..