오답 노트 & 새로 알게 된 점 해당 문제는 아마 O(N^2)로도 풀 수 있지만 TLE 때문에 안된다. 그래서 O(N)의 방법으로 풀어야하는데, 그것이 두 포인터를 이용하는 것이다. 일반적인 두 포인터와 똑같다. sum은 [ L..R ] 범위에서, 만약 sum이 S보다 크거나 같으면 갯수를 갱신해주고, 아니면 L을 하나씩 늘리면서 해당 L을 빼줘야한다. 기본적인 두 포인터를 배웠다면 어렵지 않게 풀 수 있는 문제이다. 물론 index 접근이 너무 어렵다.. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49..

오답 노트 & 새로 알게 된 점 이 문제를 풀면서 possible에서 구현 생각하는게 좀 힘들었다. 처음에는 가로등의 count 개수에 따라 문제를 풀었는데, 틀렸다. 다시 생각해보니 가로등의 개수는 고정되있다. possible은 높이에 따라 비출 수 있는지 없는지 true, false를 반환해야한다. 그래서 높이가 N보다 크거나 같으면 당연히 모두 비출 수 있고, 일정 높이 이상이면 무조건 true이다. 이제 true에서 가장 왼쪽 값(최소 높이)를 구하면 된다. possible에서 이제 어떻게 N까지 비출 수 있는지 확인해야한다. last라는 마지막에 비추는 값을 의미하는 변수를 만든다. 가로등이 있는 위치에서 last를 뺀 값이 높이보다 작거나 같으면 앞이 다 비춰진다. 그래서 last에 가로등이 ..

오답 노트 & 새로 알게 된 점 해당 문제는 매개 변수 탐색 방법을 사용하여 해결했다. 다른 매개 변수 탐색과 똑같은 문제였다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 package Binary_Search; import java.io.*; import java.util.*; public class BOJ13702 { static int atoi(String str) { return Integer.parseInt(str); } static int ..

오답 노트 & 새로 알게 된 점 해당 문제는 매개 변수 탐색 방법을 사용하여 풀었다. 이분 탐색의 범위 정하는거 중요했다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 package Binary_Search; import java.io.*; import java.util.*; public class BOJ6236 { static int atoi(Stri..

오답 노트 & 새로 알게 된 점 해당 문제는 매개 변수 탐색 방법을 사용하여 풀었다. possible 메서드 안에서 어떻게 반환할지 매우 헷갈렸다. cnt = M인지 말이다. 이렇게 생각하면 될 것 같다. target 즉, 블루레이의 크기가 커질수록 cnt가 작아진다. 우리가 구하고 싶은 것은 크기의 최솟값이다. true인 것들 중에 가장 왼쪽 값이다. 그래서 cnt가 작을 때 true을 반환한다는 것은 블루레이의 크기가 일정 이상이면 모두 true이고, 거기서 가장 작은 값을 구하는 것이다. 실수했던 부분은 정렬을 하면 안된다. 왜냐하면 문제에서 강의를 순서대로 넣는다고 했기 때문이다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24..

오답 노트 & 새로 알게 된 점 위 문제는 이분 탐색으로 lowerbound를 구하는 문제이다. B의 숫자 중에 A의 숫자보다 작은 것들을 구하면 된다. 시간 복잡도는 B를 정렬해야하므로 MlogM B에서 이분 탐색을 실시할 때 logM, 이와 같은 연산을 A의 개수만큼 즉 N만큼 해야하므로 NlogM 둘을 더하면 (N+M)logM 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 import java.io.Buffere..

오답 노트 & 새로 알게 된 점 이 문제는 가중치가 >= 0 이므로 BFS가 아닌 다익스트라를 이용하였다. 이차원 배열을 이용하여 시작점에서 도착점까지 최소 비용을 구하는 문제이다. dist 이차원 배열을 만들어 INF로 초기화하고, 옮기는 곳의 dist와 현재 dist에서 옮기는 곳의 arr값을 비교하여 값을 구한다. 보통 BFS와는 다르게 visit를 사용하지 않는다. 왜? visit를 사용하면 다음 방문 시에 최솟값이 나올 수 있는데, 그 부분을 놓치게 된다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 ..

오답 노트 & 새로 알게 된 점 다익스트라의 기본 문제이다. 1번 정점에서 시작하여 특정한 두 정점을 지나서 N에 도착할 때의 길이를 구하는 것이다. 모든 정점을 갈 때마다 최단 경로로 이동해야한다. 그래서 1번 정점, 특정한 두 정점을 각각 시작점으로 하는 다익스트라를 사용했다. dist를 2차원 배열로 만들어 dist[N][0]에는 1번 정점의 각 노드마다 경로, dist[N][1], dist[N][2]에는 특정한 두 정점의 최단 경로 데이터를 넣었다. 그리고 실수할 수 있는 부분은 하나라도 연결되있지 않으면 즉, 필요하는 dist의 값이 INF값이면 -1을 출력해야한다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 ..

오답 노트 & 새로 알게 된 점 해당 문제도 전에 풀었던 최단경로와 유사한(?) 거의 비슷한 문제이다. 다익스트라 알고리즘을 제대로 알고 있다면 쉽게 풀 수 있다. 2021.12.27 재풀이 다익스트라를 짜면서 TLE, MLE를 다 보았다. 1번을 if절이라 하고, 2번을 =을 안붙일 때라고 말하겠다. 처음 코드에는 1번과 2번 모두 없었다. 그래서 제출을 하면 TLE가 났다. 1번 코드를 작성한 뒤 제출하면 이제 MLE가 난다. 그래서 2번 코드를 작성하고 나니까 AC를 받았다. 다익스트라를 하면서 최적화?라고 해야하나 이게 필요한 것 같다. 앞으로 다익스트라를 풀면서 1번과 2번의 조건은 절대 까먹지 말아야겠다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1..

오답 노트 & 새로 알게 된 점 이번에는 최단 경로를 구하는 알고리즘 중 다익스트라를 공부했다. 최단경로 문제는 다익스트라를 이용하는 웰노운 문제로 다익스트라를 제대로 알고있다면 쉽게 풀 수 있는 문제이다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 package Grap..

오답 노트 & 새로 알게 된 점 해당 문제는 나이트의 이동이랑 문제가 있었던 것 같은데, 그것도 비슷한 문제이다. 처음에 풀 때는 참 복잡하게 풀었다. 문제에서는 입력된 상대편 말의 위치에 따라 최소 횟수를 출력하라고 했다. 그래서 나는 처음에 arr 배열을 char로 한 뒤에 K와 E를 넣고, bfs를 돌리면서 만약에 큐에서 꺼낼 때 이게 E에 도착하면 enemy라는 배열(출력을 입력순대로 하여 좌표를 저장함)을 처음부터 탐색하여 일치하는 것을 count배열(입력순대로 enemy와 index를 일치시켜 count를 출력하기 위함)에 저장한다. 그리고 arr배열을 '0'으로 바꿔주고 cnt++를 한다. 그리고 cnt가 M의 갯수와 같으면 반복문을 종료한다. 근데 풀고나보니, 그냥 처음부터 모든 배열에 최..

오답 노트 & 새로 알게 된 점 해당 문제는 MST알고리즘 기본 문제이다. 왜 이 문제가 MST 문제인지를 알아야할 것 같다. 보면 문제에서 모든 컴퓨터가 연결이 되어 있어야 한다. 모든 컴퓨터를 연결하는데 필요한 최소비용을 출력하라. 라는 말이 MST를 이용하라는 것 같다. 최소 비용으로 연결하기 위해서는 간선을 최소화시켜야하고, 그 중에서 가중치를 제일 낮은 것들을 선택해야한다. 또한, 컴퓨터가 모두 연결이 되어 있어야한다는 조건도 말이다. 그래서 크루스칼 알고리즘을 사용하여 findSet, unionSet 자료구조를 직접 구현하고, 출발과 끝, 가중치를 저장하고 있는 ArrayList를 가중치에 따라 오름차순으로 정렬하고, parent 배열을 이용하여 구현했다. 여기서 유심히 보아야 할 점은 uni..