전체 글

문제 링크 1. 어떻게 풀지 조금 고민하다가 문제에서 $N$이 10 이하의 자연수라고 하여서 몇 가지 예를 적어보고 규칙을 찾으면 풀 수 있을 것이라 생각했다. 한 5개 정도 직접 써보며 컴퓨터의 입장에서 어떻게 풀지 고민하였더니 풀렸다. 정답률 $56\%$의 문제로 난이도가 다소 낮은 문제이다. 2. 나는 이 예제를 기준으로 문제를 풀었다. input 5 3 3 0 1 0 output 3 5 4 1 2 1. 1번보다 키가 큰 사람의 수가 3이라면 위치가 3일 수 밖에 없다. (arr인덱스의 0부터 계산) arr 0 0 0 1 0 2. 2번보다 키가 큰 사람의 수가 3이라면 arr 인덱스의 0부터 3개의 빈칸을 두어야 한다. 왜냐하면, 3개의 빈칸에 2번보다 키가 큰 사람을 세워야 하기 때문이다. arr..

문제 링크 1. $(0,0)$부터 끝까지 변환 후 같은지 확인하면 될 것 같은데..라고 생각했지만, 그리디 문제라서 뭔가 좀더 그리디스러운 방법이 존재할 거라고 생각했다. 저 방법 말고는 떠오르지가 않아 방법이 맞는지 해설을 봤더니 맞았다.. 2. 내가 생각했던 데로 $(0,0$에서 부터 끝가지 변환하면 되지만 유의해야 할 점이 있다. $3\times3$ 크기의 부분 행렬을 변환하는 것이라서 $N\times M$ 모두 확인할 필요가 없다. $(0,0$ 에서부터 $(N-3,M-3)$ 까지만 변환하면 된다. 그 이상의 변환은 다시 원래대로 바꾸는 것이므로 불필요한 연산이 된다. 이것을 알았다면 구현은 쉽다. 1. $(0,0$에서부터 $(N-3,M-3)$까지 A와 B의 원소가 다르다면 $3\times3$ 크기..

문제 링크 1. 영상제작 외주를 받아서 잠시 공부를 하지 못했다. 오랜만에 문제를 풀었는데, 문제를 잘못 골랐는지 엄청 힘들었다. 나름 규칙을 찾아 점화식을 세웠는데, 틀렸다. 해설을 찾아 보았는데, 자세한 해설을 적어 놓은 사람을 찾기 힘들었고 적었더라도 이해가 되지 않았다. 풀이 이해하는데만 1시간 넘게 걸린거 같다. 머리가 나쁜건지 문제가 어려운건지.. 이 문제의 정답률은 35% 인데, 좀 높게 잡히지 않았나 싶다. 2. 진짜 엄청 상세한 풀이 블로그를 찾아서 참고에 넣어두었다. 천천히 계속 읽어보자. 3. import java.util.Scanner; public class Main { public static void main(String[] args) throws Exception { Scan..

문제 링크 1. 입력 데이터를 어떻게 처리할지에 대한 고민을 조금 했던 문제이다. 데이터 배열을 만들고 난 후에는 단지번호붙이기 문제와 유사해 쉽게 풀 수 있다. 2. 직사각형의 왼쪽 아래 꼭짓점의 $(x, y)$과 오른쪽 위 꼭짓점의 $(x, y)$가 주어진다. 일단 노트에다가 이를 고려해 찍어보았다. 문제는 이 좌표계를 배열화 시켜야 하는 것인데, 고민해보면 다음과 같은 규칙을 찾을 수 있다. $(2, 0)$ ~ $(4, 4)$ 이라면, data[0][2] ~ data[3][3] $(1, 1)$ ~ $(2, 5)$ 이라면, data[1][1] ~ data[4][1] $(4, 0)$ ~ $(6, 2)$ 이라면, data[4][0] ~ data[1][5] 배열 모양은 좌표계를 x축을 기준으로 대칭시킨 모..

문제 링크 1. 처음 보고 정확한 식은 기억이 안 났지만, 고등학교 확통 시간에 배운 내용이 대략적으로 떠올랐다. 이 문제는 수학과 DP를 섞어 푸는 문제이다. 2. 기억이 안났던 식은 다음 식이였다. $_{n}C_{r}=_{n-1}C_{r-1}+_{n-1}C_{r}$ 이 공식은 파스칼의 삼각형에서도 구할 수 있다. 관련 내용은 아래 참고 블로그에서 공부하자. 3. import java.util.Scanner; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int k = sc.nextInt(); int[][]..

Silver II → Silver I 승급 소요 기간 : 9일 (2020.08.08 - 2020.08.17)

문제 링크 1. 이전에 풀었던 동전 1과 유사한 문제. 해당 문제의 풀이를 보고 복습하며 풀었다. 2. 동전 1 문제의 해설을 보고 이 해설을 보도록 하자. 차이점은 동전 1에서는 k 원을 만들 수 있는 모든 경우의 수를 구하지만, 동전 2에서는 최소한의 동전을 사용해서 만들 때 사용한 동전의 개수를 구하는 문제이다. 이를 위해서 다음과 같은 점화식을 세운다. dp[j] = Math.min(dp[j], dp[j - coin[i]] + 1) 유의할 점은 다음과 같다. 1. dp 배열을 모두 100001로 초기화 한다. 사용한 동전의 개수가 최악일 경우 100,000개이다. (동전의 가치가 최대 100,000원이기 때문이다.) 따라서 이 최대 + 1인 100001로 초기화한다. 2. dp[0] = 0이다. ..

문제 링크 1. 예전에 풀었던 가장 긴 증가하는 부분 수열 (11053)의 응용문제이다. 해당 문제의 풀이법을 잊었었는데, 다시 복습하며 문제를 풀었다. 복습의 중요성을 깨닫는다. 2. 이번에 알게 된 것인데, 가장 긴 증가하는 부분 수열을 구하는 알고리즘을 부르는 명칭이 존재했다. 이는 LIS 알고리즘으로, Longes Increasing Subsequence 의 줄임말이다. 이번 바이토닉 부분 수열을 구할 때에 이 LIS 알고리즘을 잘 적용하여야 한다. 가장 긴 바이토닉 부분 수열은 증가하다가 감소하는 부분 수열의 길이가 가장 긴 것을 구해야 한다. 이를 다시 말하면, 1. 증가하는 부분 수열의 길이 값도 최대로 2. 감소하는 부분 수열의 길이 값도 최대로 하여야 한다. 즉, 증가하는 부분 수열의 d..