본문 바로가기

🔎 Algorithm/💻 문제 풀이16

[백준] 1520. 내리막길 문제 풀이 먼저 모든 경로의 수를 구해야하기 때문에 DFS를 사용해 경로를 구했다. 하지만 모든 경우의 수를 탐색하게 되는 경우 시간초과가 발생하기 때문에 이를 줄이기 위한 방법이 필요하다. 생각한 아이디어는 한 번 방문했던 좌표를 x,y라고 했을 때, (x,y) 에서 (N-1, N-1)까지의 경로는 이미 구해져있고 변하지 않기 때문에 다시 탐색할 필요가 없다는 점이다. 따라서 dfs를 진행하며 방문체크를 하고, 방문체크가 된 곳인 경우 저장되어 있는 경우의 수를 그대로 사용함으로써 시간을 줄일 수 있다. 하지만 주의할 점이 있다. 초기 작성한 코드는 다음과 같다. import java.io.BufferedReader; import java.io.IOException; import java.io.Inpu.. 2021. 4. 1.

[백준] 2629. 양팔 저울 문제 풀이 오랜만에 푸는 DP문제였다. 먼저 추를 넣었을 때 만들 수 있는 추의 무게를 저장하기 위한 Cache배열을 유지했다. 이 때 해당 추에 대해 만들 수 있는 경우 수는 다음과 같다. 현재 추만 넣은 경우 이전 단계에서 만들었던 무게를 그대로 사용하는 경우 이전 단계에서 만들었던 무게에 현재 추를 더하는 경우 이전 단계에서 만들었던 무게에 현재 추를 빼는 경우 (물체쪽에 추를 놓는 경우) 최종적으로 마지막 추를 넣었을 때 가능한 무게를 구할 수 있다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { // Input 받기 위한 Buffered Re.. 2021. 4. 1.

[백준] - 2206. 벽부수고 이동하기 문제 풀이 이 문제는 예전에 BFS를 한창 풀었을 때에는 못 풀었던 문제였는데 이와 유사한 문제인 1600. 말이 되고픈 원숭이문제를 풀고 영감을 얻어서 다시 도전했더니 쉽게 풀렸다. 이 문제가 일반적인 BFS보다 까다로운 이유는 어떤 좌표에 올 수 있는 경우의 수가 2가지(이전에 벽을 부신 경우, 이전에 벽을 부수지 않은 경우)라는 점이다. 따라서 2차원 방문 배열로는 처리가 불가능하고 3차원 배열을 사용하여 문제를 해결하였다. 3차원 배열에서 0번쨰 인덱스는 벽을 이미 부수고 온 경우, 1번째 인덱스는 벽을 아직 부수지 않은 경우이다. bfs를 진행하며 다음의 3가지 경우에 대해서 처리해주었다. 현재 벽을 부술 수 있는 기회가 남아있고 다음 방문할 좌표가 벽인 경우, 기회를 소진하고 벽을 방문 기회가.. 2021. 3. 24.

[백준] - 1277. 발전소 설치 문제 풀이 1번 발전소부터 N번째 발전소까지의 최소 비용을 구하는 문제이기 때문에 다익스트라 알고리즘을 사용하여 해결하였다. 먼저 각 발전소의 좌표를 저장(plant)하고, 연결되어 있는지 여부를 저장(connected)하였다. 다음으로 다익스트라 알고리즘을 수행하기 전, 1번부터 각 정점까지의 거리를 나타내는 distance 배열을 연결된 경우에는 0, 연결되지 않은 경우에는 INF로 초기화해주었다. 다익스트라 알고리즘을 수행하면서 가중치를 더해주는 부분은 각 좌표간의 거리이기 떄문에 두 점 사이의 거리를 구하는 공식을 통해 구했다. 추가적으로 인접한 행렬에서 찾는 일반적인 경우와 달리 모든 발전소의 거리를 계속해서 갱신해 줄 필요가 있기 때문에 1~N까지 자기 자신을 제외하고 거리를 갱신해주었다. 풀.. 2021. 3. 24.

[백준] 1799. 비숍 문제 풀이 처음에 생각했던 방법은 완전 탐색을 통해 최대 수를 찾는 방법이었다. 중간에 가지치기를 통해 시간을 줄일 수 있겠지만 n의 최대값이 100이고 (모든 점에 대해 놓는 경우/ 놓지 않는 경우) * (놓을 수 있는지 판단하기 위해 양 대각선을 탐색하는 경우)를 하게 되면 O(2^n * n)이기 때문에 시간초과가 발생할 것 같아서 다른 방법을 생각해봤다. 생각한 방법은 N-Queens에서 모든 행렬을 저장하지 않고 해당 idx에는 하나의 값만 올 수 있도록 한다면 시간을 줄일 수 있다는 생각을 했고 데이터를 어떻게 묶어야 할지 고민을 해봤다. N-Queens에서 queen은 가로,세로를 갈 수 있었고 이로 인해 하나의 행에 퀸을 놓을 경우에는 같은 행에는 퀀이 존재하지 못하는 성질을 이용했었다. 이.. 2021. 3. 7.

[백준] 1967. 트리의 지름 문제 풀이 처음 시도했던 방법은 1번의 자식노드들을 시작점으로 잡아 DFS를 통해 탐색하면서 왼쪽 자식과의 거리, 오른쪽 자식과의 거리, 부모와의 거리 중에 상위 2개의 값을 골라 최대값을 갱신하는 방법으로 진행하였다. 그리고 그 최대값이 1번의 다른 줄기와 연결할 수 있는지(notCompleted), 아니면 이미 완성된 지름인지(completed) 판별하는 flag를 통해 최대 지름을 구하려고 했다. 이 방법이 잘못된 이유는 먼저 문제에서 이진 트리라는 조건이 없는데 이진트리라고 가정하고 풀었기 때문이고, 또한 위의 그래프에서 4-7 : 100 / 4-8 : 100으로 수정한 경우 왼쪽 줄기의 최대값이 200이 나와야하는데 4의 부모노드인 2가 자식이 하나밖에 없기 때문에 200 + 5로 갱신되는 문제.. 2021. 3. 6.

이전 1 2 3 다음

티스토리툴바