전체 글

문제 링크 1. 1시간 소요. 점화식 세우는 아이디어는 금방 떠올라서 코드를 쭉쭉 써내려 갔다. 그러나 오답처리가 되어 질문 검색을 통해 반례를 찾아서 수정하는 데에 오랜 시간이 걸렸다. 점화식을 어떠한 식으로 세워야할 지 감을 잡았다는 점에서 만족한다. 2. 처음 풀었던 코드의 반례는 $2, 1, 5, 6, 7$ 이였다. 기댓값은 $20$ 인데, 나는 $19$ 가 나왔다. $2$ 부터 선택하는 것이 최댓값인데 이를 고려하지 않았던 것이다. dp배열은 해당 index 까지의 증가 부분 수열 합의 최댓값이다. 이해가 안 되면 다음을 명심하자. DP문제는 큰 문제를 작은 문제로 쪼개어 생각하자 문제의 메커니즘은 완성된 dp배열을 보면서 설명하고자 한다. dp[3]을 계산하려면, 1. arr[3] 이전의 원소..

문제 링크 1. 문제를 보고 답을 내는 메커니즘 자체는 쉽게 생각해냈다. 다만, 입력받은 문자열을 어떻게 쉽고 효율적으로 가공할지 몰라서 풀이를 참고하였다. 2. 그리디 알고리즘을 적용하면, 괄호를 넣어 식의 값을 최소로 만들려면 최대한 많은 수를 음수로 만들어야 한다. 즉, $-$가 나오고 다음 $-$가 나오기 전까지 괄호로 묶으면 되는데, 이 말은 곧 $-$와 $-$사이의 $+$를 $-$로 바꾸면 된다. 예를 들어보면, $1+2+3-4+5+6-7+8$ 이라면 $1+2+3-(4+5+6)-(7+8)$ 으로 괄호를 치는 것이 최소가 된다. 이는 곧 $1+2+3-4-5-6-7-8$과 같다. 이를 메커니즘으로 나타내면 다음과 같다. 1. 입력받은 문자열을 $-$를 기준으로 분리 2. 분리한 문자열을 차례대로 ..

문제 링크 1. 30분 소요. 머리속으로 어떻게 풀지 생각하면서 멍때리다가 노트에다가 막 끄적여보았는데 바로 아이디어가 떠올랐다. 써보면서 고민하자. 2. 문제의 예시의 답은 어떻게 나왔을까? 그리디 알고리즘답게 탐욕스러운 사고 기법을 해보았다. $10$만 선택했을 때는 최대 $10$만큼 들어올릴 것이다. $15$만 선택했을 때는 최대 $10$만큼 들어올릴 것이다. $10, 15$를 선택했을 때는 $30$이 아닌 $20$만큼 들어올릴 수 있다. 왜? $w/k$만큼 들어올릴 수 있으므로 $30$이 되면 $10$짜리 로프는 못버티기 때문이다. 즉, 들어올릴 수 있는 무게는 제일 작은 중량을 기준으로 선택해야한다. 다만 문제에서 모든 로프를 사용할 필요가 없다고 했으므로, 1. 내림차순 정렬 2. 1개, 2개..

문제 링크 1. 1시간 소요. 노트에 대략적인 경우의 수를 모두 적어 점화식을 쉽게 구했으나, 오답이었다. 맞게 푼 것 같은데 잘못된 부분을 도저히 못 찾겠어서 다른 사람의 질문을 참고했다. 32의 결과값은 2가 나와야 하는데, 나는 5가 나왔다. 나는 $25+4+1+1+1$ 으로 계산했지만, $16+16$ 이라는 최소 개수가 존재한다. 이를 반영해서 코드를 수정했고 정답 메시지를 받았다. 비록 오류를 스스로 잡지는 못했지만 해설을 보지 않고 푼 것에 만족한다. 대신 코드가 조금 지저분한 것은 사실이다. 2. $1 = 1$ $2 = 1+1$ $3 = 1+1+1$ $4 = 4$ $5 = 4+1$ $6 = 4+1+1$ $7 = 4+1+1+1$ $8 = 4+4$ 규칙이 보이는가? 8을 예로 들면, 8과 가장 ..

문제 링크 1. 1시간 고민하고 점화식을 세우지 못해 해설을 참고했다. dp문제는 정말 너무 어려운 것 같다.. 해설 이해하는 것도 시간이 꽤 걸렸다. 2. 두 가지 배열을 선언 한다. coin배열은 사용할 수 있는 동전의 종류이고, dp배열은 동전을 사용해서 합이 index원이 되도록 하는 경우의 수를 나타낸다. 가장 작은 동전을 사용했을 때 각 dp배열의 각 index원을 만드는 경우의 수를 계산하고, 그 다음 동전을 사용했을 때 경우의 수를 여기에 누적하는 방식으로 진행을 한다. 예를 들어, 1을 사용해서 2를 만드는 경우의 수는 1+1로 총 1가지 이다. 2를 사용해서 2를 만드는 경우의 수는 2로 총 1가지 이다. 1을 사용해서 3을 만드는 경우의 수는 1+1+1로 총 1가지 이다. 2를 사용해..

Silver III → Silver II 승급 소요 기간 : 5일 (2020.08.03 - 2020.08.08)

문제 링크 1. 많이 풀어 봤던 기본적인 그래프 문제. 유기농 배추 문제와 매우 유사해서 쉽게 풀었다. 테스트 케이스는 다 맞고, 전혀 틀린 부분이 없는데 오답처리가 나길래 골치가 아팠다. 원인은 내가 잠시 수정했던 범위였는데 이런 어이없는 실수는 하지 않도록 주의하자. 2. 풀이는 유기농 배추 문제를 참고하면 될 것 같다. (링크 걸어 놓았음) 단, 이 문제에서는 4 방향이 아닌 8 방향을 모두 검사하여야 한다. 3. import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { static int w, h; static int[][] area; public static void main(..

문제 링크 1. 처음 문제를 보았을 때, 방향 그래프 인접 행렬이라는 점에서 조금 복잡하게 생각했다. 2. 자료구조 수업시간 때 인접 리스트 구성한 것을 떠올려 보면, 무방향 그래프에서 1에서 2로 가는 간선이 있다면 2에서 1로 가는 간선도 인접 리스트에 추가를 했었다. 방향 그래프라면 1에서 2로 가는 간선만 추가할 것이다. 이를 통해 그냥 배열을 순회하는 기본적인 BFS 문제와 다를 게 없다고 판단했다. 다만 사이클 생기는 부분을 주의해야 할 것이다. $0$번째 행부터 $n-1$번째 행까지 각 행에 대하여 BFS 탐색을 한다. 3. import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Ma..