Java

문제 링크 1. 노트에 좀 끄적이다가 아이디어가 떠올라 코드를 쭉 썼다. 아무 생각 없이 제출했으나 시간 초과.. 나는 list를 이용해서 서류 성적을 기준으로 정렬하고 list를 순회하며 값을 비교하기 위해 이중 for문을 사용하였다. 하지만, 이중 for문을 사용하면 $O(N^{2})$ 인데 지원자의 최대 수가 $100,000$ 이므로 시간 초과가 날 수밖에 없다. 결국 이중 for문을 사용하지 않는 방법을 찾아야 하는데 찾지 못해 풀이를 참고하였다. 2. 그 방법은 생각보다 단순했다. 두 성적 순위는 모두 1위부터 N위까지 동석차 없이 결정된다고 가정한다. 문제에서, 동석차가 없다고 하였으므로 사용자 정의 Class를 만들 필요 없이 배열의 인덱스 값을 석차로 설정하면 된다! 그러면 성적 정렬을 할..

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