본문 바로가기

🔎 Algorithm21

[백준] 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.

[개념 정리] 투 포인터 최근 알고리즘을 풀면서 시간 초과와 예외처리로 인해 상당히 애를 먹었던 문제가 있다. 해당 문제의 다른 풀이를 찾아보니 투 포인터 알고리즘을 통해 간단하게 구현할 수 있다는 점을 알았고 이에 대해 정리해보고자 한다. 투 포인터 알고리즘은 하나의 배열에서 두 개의 인덱스 포인터를 조작하는 알고리즘을 의미한다. 문제를 예시로 들어서 설명하면 다음과 같다. 백준 - 2467. 용액 이 문제에서 0과 가장 가까운 거리의 합을 가지는 두 원소를 구하는 방법은 먼저 O(N^2)의 시간복잡도를 가지는 방법이 존재한다. 하지만 문제처럼 N의 크기가 O(N^2)으로 해결할 수 없는 경우에 투 포인터 알고리즘을 사용하면 O(N)에 해당 값을 구할 수 있다. (이 문제는 정렬이 필요하기 때문에 전체 문제의 시간복잡도는 O(.. 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.

[개념 정리] 최단 거리 알고리즘 - 다익스트라 가중치가 없는 그래프의 최단거리 문제는 대부분 BFS로 해결할 수 있습니다. 하지만, 간선에 가중치가 존재한다면 BFS가 아닌 최단거리 알고리즘을 통해 접근해야 합니다. 일반적으로 가중치 그래프의 최단거리 문제는 다음과 같은 유형이 존재합니다. 두 정점 간의 최단 거리를 구하는 문제 하나의 정점에서 다른 모든 정점과의 최단거리를 구하는 문제 하나의 정점으로 가는 모든 최단 경로를 구하는 문제 정점 간의 모든 최단 경로를 구하는 문제 - 플로이드-와샬 저번 글에서는 4번 유형을 해결하기 위한 플로이드-와샬 알고리즘에 대해 알아보았습니다. 이번 글에서는 2번 유형을 해결할 수 있는 다익스트라 알고리즘에 대해서 알아보겠습니다. 다익스트라 알고리즘은 간단하게 설명하면 시작 정점에서 거리가 최소인 정점을 선택해 .. 2021. 3. 22.

이전 1 2 3 4 다음

티스토리툴바