백준

문제 링크 1. 다익스트라 알고리즘. 처음 접해보는 알고리즘이다. 유튜브 영상과 해답을 보며 공부하였다. 자료구조 시험칠 때 친구랑 얘기하다가 다익스트라 관련 얘기가 나왔었는데, 나는 그게 뭐냐고 안 배웠다고 하고 친구는 그걸 왜 모르냐고 중요한 건데 했던 웃픈 사연이 있는 알고리즘이다. 우리 교수님은 안 알려주셨는데 다른 교수님 수업에서는 가르쳐줬다고 한다. 중요한 알고리즘이다. 흔히 우리 주변에서 접할 수 있는 지도의 최단 경로를 구할 때도 이 알고리즘이 적용된다. 오늘 배우긴했지만 또 복습하자. 2. 그래프를 인접 행렬로 구성하면 안 된다. 문제의 조건 범위가 $0\leq V\leq20000$ 인데, 인접 행렬로 구성하게 되면 $20000\times20000=$ 대략 4억으로 메모리 초과가 난다. ..

문제 링크 1. 이전에 풀었던 기본적인 그래프 문제. 항상 BFS로만 풀어와서 이번에는 DFS로 풀어보았다. DFS가 좀 더 직관적인 것 같다. 2. 1. 가장 큰 높이 $h$ 부터 가장 낮은 $1$ 까지 높이를 하나씩 낮춰주며 기준을 잡는다. 2. 기준 높이 $h$ 보다 큰 영역은 물에 잠기지 않으므로 그러한 영역의 개수를 구한다. 3. 영역의 개수의 최대값을 출력한다. 이하 코드 참고 3. import java.util.Scanner; public class Main { static int[][] area; static int n; public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); ..

문제 링크 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를 사용해..

문제 링크 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(..