오답 노트 & 새로 알게 된 점 3달 전에 해당 문제를 매개 변수 탐색과 bfs를 사용하여 문제를 해결했다. 이번에 다시 풀면서 알고리즘 분류를 보게 되었는데, "분리 집합" 이 있었다. 저번에 풀었던 여행 가자 문제와 비슷한 느낌이 들었다. 여행 가자 라는 문제에서도 분리 집합이라는 키워드가 있었다. 그래서 해당 문제도 union-find 자료구조를 이용해서 문제를 해결했다. 다만 문제에서는 "한 번의 이동에 최대 중량" 을 구하게 된다. 따라서 가중치를 기준으로 내림차순 정렬을 한다. 정렬된 노드들을 앞에서부터 순차적으로 union 한다. union을 하고 나서 start와 end가 이어진다면, 즉, find(start) == find(end)가 되면 이 때 가중치가 제일 큰 값일 때 이동할 수 있기..

오답 노트 & 새로 알게 된 점 이 문제는 두 가지 풀이를 소개해보겠다. 첫 번째 풀이는 제가 처음 접근했던 풀이법이고, 두 번째는 힌트를 얻어 풀게된 "유니온 파인드"를 사용한 풀이법이다. 첫 번째 풀이 문제에서 서로 그래프가 연결되있느냐를 물어보는 것이었다. 따라서 모든 점에서 bfs를 사용하면서 서로 연결이 되어있는지 확인했다. dist[A][B] 배열을 사용하여, A가 출발 노드, B가 거쳐가는 노드라 생각해서 연결리스트를 사용하면서 출발점은 고정하고, 거쳐가는 노드들을 모두 저장했다. 하지만 반례가 존재한다. 문제에서는 갔던 곳을 또 방문할 수 있다. 즉, 이 말은 여행 노드가 1 1 이렇게 나타날 수도 있다. 아마 문제를 푸시다가 80%에서 틀렸습니다 받으신 분들은 이 부분을 놓쳤을 것이다. ..

오답 노트 & 새로 알게 된 점 처음 문제 봤을 때, N,M 범위도 작아서 BFS 돌리면 바로 답 나오겠다 라는 생각이 들었다. 그러나 메모리 초과가 났다. 여기서 아.. 메모리 제한이 작구나 하면서 dfs를 사용하면서 혹시 목적지를 출발지로 설정하고 반대로 가면 괜찮지 않을까라는 생각이 들었지만 당연하게도 TLE가 났다. 그래서 예시 그림을 자세히 보니 중복해서 지나는 부분이 있었고, dp를 사용하면 되겠다라는 생각까지 했다. 하지만 dp 구현을 어떻게 할지 몰라 블로그들의 다양한 풀이를 참고하여 문제를 해결했다. 그래도 이제는 어떤 알고리즘을 사용해야할지 감은 오니까 다행인 것 같다.. 해당 문제와 같은 유형은 (dfs 또는 bfs + dp)는 자주 나올 수 있기 때문에 숙지하고 있어야겠다. 처음에 ..

오답 노트 & 새로 알게 된 점 백트래킹으로 풀어야지 라는 생각을 했지만 구현을 하지 못했다. 구글의 힘을 빌려서 문제를 해결했다,, 처음에 수식의 길이가 N개라고 하여, 숫자는 결국 N / 2 + 1개가 있게 되고, 거기서 -1을 하면 괄호로 묶을 수 있는 수들의 경우의 수가 된다. 이걸 이용해서 순서, 중복 X인 조합을 구하여 계산하려 했지만 하지 못했다. 다른 풀이에서는 백트래킹을 이용한다. 뒤에 괄호가 있다고 생각 or 뒤에 괄호가 없다고 생각한다. 뒤에 괄호가 있다면 현재 idx에서 다음 idx+1, idx+2의 계산한 값과 현재 idx값을 계산해야한다. 그래서 예제 1번을 디버깅 하여 어떻게 계산이 이뤄지는지 손으로 작성해보았다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14..

오답 노트 & 새로 알게 된 점 해당 문제는 풀이 방법이 두 가지 있다. 첫 번째 방법은 생각하기 쉽지만 시간 복잡도가 다른 방법에 비해 크고, 다른 방법은 와 이걸 이렇게도 풀구나 하면서(나만 그럴 수 있음) 시간 복잡도가 첫 번째 방법에 비해 작다. 첫 번째 풀이 일반적으로 다익스트라를 사용한다. 다만 문제에서 출발할 때의 최소 경로 + 복귀할 때의 최소 경로 중 최댓값을 구하라했다. 일반적으로 나는 이와 같은 문제를 풀 때 다익스트라를 모든 정점에서 구한다(N번) 예제에서 start가 1, 3, 4 (2는 파티정점이므로 제외) 일 때 다익스트라를 구하여 각각 dist[X] 값을 더해주고, 또 start가 2일 때 다익스트라를 구하여 각각 dist[N] 을 더해주었다. 그리고 이 중에 최댓값을 구해줬..

오답 노트 & 새로 알게 된 점 해당 문제는 다익스트라를 이용하여 풀면 되는데, 다른 문제와 다른 점은 최소 경로 값을 출력하는 것이 아니라 가장 먼저 거쳐야 할 노드를 출력하는 것이다. 전체적인 풀이를 말하자면 1 ~ N번 노드까지 다익스트라를 구한 뒤, 각 n번 노드마다 parent를 구하여 정답 배열에 넣어준다. 값을 출력할 때는 행과 열이 같은 지점(대각선) 에는 "-" 을 넣어준다. 즉, 1 - 3 - 2가 최소 경로일 때, (1,2)의 값은 3이 된다. 1 ~ N번 노드까지 다익스트라를 이용하여 최소 경로를 구하면서, 최소 경로가 갱신될 때마다 즉, if(dist[node.idx] != node.dist) continue; if(dist[node.idx] + in.wei >= dist[in.t..

오답 노트 & 새로 알게 된 점 이 문제는 (N,M)의 최소 경로가 아닌 벽을 최소로 부수면서 (N,M)에 도착해야한다. 가중치가 0 또는 1이기 때문에 일반적인 BFS를 사용할 수 없다. ( 0-1 BFS 라는 것이 있다) 따라서 가중치가 0을 포함하는 양수일 때 사용하는 알고리즘인 다익스트라를 사용한다. 방문처리는 dist의 값이 현재 방문할 dist값보다 크거나 같게 되면 continue를 한다. 코드 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 ..

오답 노트 & 새로 알게 된 점 이 문제를 푸는데 6시간이 걸린 듯 하다. 총 23트 끝에 문제를 맞게 됐다. 진짜 끔찍하고 무시무시했던 문제였다. 문제를 정리해보면 1. 숫자를 문자열로 풀어서 입력을 줌 2. 문자열을 숫자로 변환하여 계산을 함 3. 계산된 값을 다시 문자열로 풀어야 함 처음에 문자열을 완탐하면서 연산을 배열에 넣어줬다. 왜? 연산의 갯수가 숫자문자열의 개수보다 많다면 잘못된 수식임을 판별하기 위해서이다. StringTokenizer를 이용하여 연산자를 구분자로 문자열을 파싱하면서, 정답을 출력하기 위해 Stringbuilder에 값을 넣어주면서, 숫자를 변환하여 덱에 넣어주었다. 덱에 넣어준 이유는 값을 계산하기 위해서이다 -> 근데 왜 덱을 사용했을까? -> 계산하기 위해서는 두 개..

오답 노트 & 새로 알게 된 점 MST 응용 문제인 것 같다. 항상 부모 배열을 -1로 초기화하고 부모는 하나 뿐인 MST 문제로 무지성으로 풀었는데, 해당 문제를 이렇게 풀면 바로 틀리게 된다. 여기서는 부모 배열 초기화부터 다르게 한다. 문제에서 발전소가 여러 개 있고, 발전소끼리 연결할 필요가 없다. 따라서 발전소를 각각 부모라고 생각하면 된다. 부모 배열을 모두 0으로 초기화 한 다음에, 발전소 위치 idx에 부모를 나타내기 위해 -1을 넣는다. 그렇다면 당연히 find와 union 메서드가 달라져야한다. 뜻이 달라진 것은 아니지만 안의 기능이 바뀌어야 한다. find 메서드는 부모가 같은지 찾는 메서드로 parent[v] 음수일 경우 발전소와 연결됐으므로 -1 반환 0 아무것도 연결되지 않음. ..

오답 노트 & 새로 알게 된 점 도시를 두 개로 분할해야한다. 다만, 도시 안에 마을끼리는 무조건 연결되어야 한다. 그렇다면 MST를 사용하여 모든 노드들을 연결해준다. 이 때, 가장 큰 가중치 하나를 빼주면 된다. 어차피 MST이기 때문에 모든 노드들은 연결되어있다. 그래새 분할해서도 최소 값을 구하고 싶다면 제일 큰 가중치를 빼주면 된다. 코드 package bfs_dfs; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import ja..

오답 노트 & 새로 알게 된 점 기본 MST 문제이다. 다만 입력 부분에서 두 노드와 가중치를 주는 것이 아닌, 행렬로 주었다. 또한, 가중치가 최대 1억, N이 1000이므로 결과값이 Long이 나올 수 있다. 입력 부분에서 양방향이기 때문에 대각선을 기준으로 대칭이다. ---- 1 | 2 | ------ 1번이나 2번 구역 중 하나의 구역만 선택하여 기본 MST처럼 풀면 된다. 코드 package bfs_dfs; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util...

오답 노트 & 새로 알게 된 점 해당 문제는 처음에 읽고 어떻게 풀어야할지 감이 안왔다. 1. 처음에는 완탐을 생각하면서 일일이 구할 생각을 했지만, 당연히 TLE다. 2. class마다 포인터를 두어 하나하나 탐색하려고 했다. 하지만 이 방법도 1번 방법과 다른 점이 없고, class의 개수는 항상 달라지는데 이걸 구분할 방법도 생각나지 않았다. 결국 풀이를 보고 문제를 해결했다. 문제 해결을 하기 위해 문제를 바꾸는 것이 중요한 부분이다. 모든 학생들을 능력치 오름차순으로 일렬로 정렬을 한다. 여기서 해당 학생은 어느 class에 속해있는지 알아야한다. 일렬로 정렬하고 두 포인터를 이용하여 N개의 class가 모두 포함되면 그 때 능력 차이를 구하면 된다. 코드 1 2 3 4 5 6 7 8 9 10 ..