알고리즘
-
다익스트라 알고리즘알고리즘/이론 2021. 1. 6. 23:55
다익스트라 알고리즘 📄 설명 다익스트라 알고리즘은 가중치가 있는 그래프에서 최단 거리를 찾는 알고리즘입니다. 음수 가중치가 있는 그래프에서는 정확한 최단 거리를 구할 수 없으므로 사용하면 안됩니다.(그럴 땐 벨만-포드) 단일 정점에서 다른 정점으로의 최단거리를 구하는 알고리즘이기 때문에 모든 정점들 간의 최단거리를 알고 싶다면 플로이드-와샬 알고리즘을 사용하는 것이 구현이 편합니다 우선순위큐를 이용한 정렬을 이용하기 때문에 O(ElogV)의 시간 복잡도를 가지게 됩니다. 💡동작 과정 각각의 정점마다 현재까지 발견한 최소 경로를 저장할 dist 배열을 만듭니다. 최단 경로를 구해야 하기 때문에 처음에는 모든 값을 아주 큰 값으로 초기화 시킵니다. 여기서는 1번 정점을 시작점으로 정했기 때문에 dist[1]..
-
[백준]10021. Watering the Fields알고리즘/백준 2021. 1. 5. 01:22
📄 링크 Watering the Fields 💡 문제 분석 최대 2000개의 정점을 가진 그래프의 MST를 구하는 문제입니다 정점들 사이의 거리를 구하고 입력에 주어진 C값으로 간선의 수를 제한하고 있지만, 상당히 많은 간선이 생길 것 같아 프림 알고리즘을 사용하기로 했습니다. 프림 알고리즘 모든 정점들에 굉장히 큰 값을 주고 시작합니다 임의로 시작 정점을 골라 연결되어 있는 정점들의 가중치를 갱신합니다 정점들 중 가장 가중치가 작은 정점을 골라 이를 반복합니다.(우선순위 큐를 사용할 수도 있습니다) 모든 정점을 갱신했다면 종료 → 이 문제에서는 그래프가 연결되어 있지 않은 경우가 존재하기 때문에 모든 정점을 검사하여 한 번도 갱신되지 않은 정점이 있다면 분리되어 있다고 판단하여 -1을 출력하도록 하였습..
-
[백준]20530. 양분알고리즘/백준 2021. 1. 5. 01:01
📄 링크 양분 💡 문제 분석 이런 문제가 왜 골드2인지 모를 정도로 힘든 문제였습니다. 처음엔 아무 생각 없이 dfs로 모든 경로를 다 찾아보려 했지만 정점이 200000개.. 당연히 시간초과가 떴습니다 이 문제의 핵심은 간선의 개수가 정점의 개수와 같기 때문에 반드시 하나의 사이클이 존재한다는 것입니다. 예제 입력을 그래프로 그려보았습니다. 어떤 두 정점으로 가는 단순 경로는 사이클이 하나이기 때문에 2개 또는 1개 밖에 나올 수 없습니다 2가지가 나오는 경우 두 정점이 모두 사이클에 속해 있는 경우 양 방향으로 갈 수 있기 때문에 2가지 경로가 존재합니다 LCA(최소 공통 조상)이 다른 경우 사이클을 구성하고 있는 정점들을 루트로 아래쪽 부분을 서브트리라고 생각했을 때 다른 루트에서 뻗어나왔다면 사이..
-
[백준]1904. 01타일알고리즘/백준 2021. 1. 5. 00:58
📄 링크 01타일 💡 문제 분석 입력 N이 100만으로 꽤 큰 숫자입니다. 기존 숫자에서 00을 더할지 1을 더할지를 선택하는 방법으로 메모이제이션을 사용했었는데 재귀로 문제를 풀면 스택 오버 플로가 발생하였습니다. 어쩔 수 없이 반복적 dp를 사용하였습니다. 덧셈을 할 때 계속 15746으로 나누어 주지 않으면 오버플로가 발생하게 됩니다 ⌨️ 코드 import java.util.Scanner; public class _1904_01타일 { static int[] cache = new int[1000001]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); cache[1] =..
-
[백준]10971. 외판원 순회2알고리즘/백준 2020. 12. 21. 23:39
📄 링크 외판원 순회2 💡 문제 분석 알고리즘의 대표적인 문제입니다. 모든 도시를 방문하고 시작 지점으로 돌아 오는데 필요한 최소 비용을 구하는 문제입니다. 완전 탐색으로 모든 경로를 계산해서 최소 비용을 구하는 방법을 사용할 수 있지만, 이럴 경우 O(N!)의 시간 복잡도가 소요됩니다. 이 문제에서는 N의 최대값이 10이기 때문에 10! = 3628800으로 시간 초과가 나지 않지만, N이 12를 넘어가게 되면 약 5억으로 시간 초과가 날 것입니다. 그렇기 때문에 부분문제로 쪼개서 동적 계획법을 사용하기로 했습니다. tcp(cur, visited) = 현재 방문한 도시들이 visited이고 현재 위치가 cur일 때 모든 도시를 방문하고 시작 지점으로 돌아가는데 필요한 최소 비용 이렇게 최적 부분 구조로..
-
알고리즘 풀이 기초알고리즘/이론 2020. 12. 21. 22:29
문제 해결 과정 문제 읽고 이해하기 계획 세우기 알고리즘 선택 자료구조 선택 계획 검증하기 키보드를 잡기 전에 계획을 검증하자 시간 복잡도, 공간 복잡도 확인 구현하기 회고하기 어떤 방식으로 접근했는가 문제의 해답을 찾는 결정적이었던 깨달음은 무엇인가 틀렸다면 오답 원인 기록하기 문제 접근하기 예전에 비슷한 문제를 풀어본 적이 있는가 문제의 목적을 보고 적절한 접근 방법을 선택하기 위해서는 어떤 문제가 최적화 문제인지, 경우의 수를 구하는 문제인지, 검색 문제인지 등을 분류하는 방법을 익히고, 각 알고리즘들이 어느 경우에 사용될 수 있는지 체계적으로 공부해야 함. 무식하게 풀 수 있는가 단순한 알고리즘을 기반으로 문제를 구성한 뒤, 좀 더 효율적인 자료구조를 사용하거나, 계산 과정에서 같은 정보를 두 번..