Algorithm

백준 3967 매직 스타(DFS)

3967번: 매직 스타 매직 스타의 모양이 주어진다. 수가 채워져 있지 않은 곳은 x로, 채워져 있는 곳은 'A'부터 'L'까지 알파벳으로 채워져 있다. i번째 알파벳은 숫자 i를 의미한다. '.'는 매직 스타의 형태를 만들기 www.acmicpc.net 문제는 어렵지 않았지만 시간초과에 대해서 많이 고전한 문제다. 단순히 빈칸에 대해서 사용할 수 있는 알파벳을 하나씩 넣어보고(완전탐색) 합이 26이 되면 종료하는 문제 근데 여기서 문제는 완전탐색을 해버리겠다고 한다면 빈칸에 대해서 넣어볼 수 있는 알파벳 여러개를 한번씩 모두 넣어본다는 것(순열)인데 이 문제는 그런 모든 경우를 구하는 문제가 아니다. 아래 코드에 보면 DFS의 재귀부분에 break;를 넣었는데 이 부분이 매우 핵심적인 부분이다. 문제에..

백준 20055 컨베이어 벨트 위의 로봇(구현)

20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 걸린시간 : 1시간 30분 문제자체는 어렵지 않았는데 어떤 자료구조를 써야되는지 확실하게 정하지 못하고 고민을 너무 많이 하다가시간을 많이 썼다. 원형 돌리기를 만나면 자꾸 python의 deque.rotate()를 먼저 생각하는 버릇이 있어서 Java에서 Collections.rotate()를 쓰려는 버릇이 있는데 고쳐야겠다고 생각이 들었다. ----유의해야할점---- robot은 n-1에서 무조껀 빠지기 때문에 robot을 관리하는 배열의..

백준 1956 운동(Floyd-Warshall)

1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 문제를 보면 가중치가 있는 방향 그래프에서 시작점을 따로 정하지 않고 단순히 두 마을이 사이클을 도는지 확인 하는 문제다. 언뜻보면 사이클이라는 단어에서 Union-Find가 생각날 수 있지만 무방향그래프일 때 사용 가능하며 방향 그래프일 때는 DFS로 자기 자신으로 돌아왔을 떄 해주면 되지만 플로이드-와샬을 이용하면 쉽게 가능 플로이드-와샬 후 (i,j)와 (j,i)가 INF가 아니라면 사이클이 있다는 뜻! package pr..

백준 1238 파티(최단경로 - 다익스트라)★★

1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 가중치가 있는 방향 그래프 문제이며 From 특정 노드 To 다른 모든 노드 : 최단 경로 알고리즘 집 -> 파티장소 파티장소 -> 집 각각의 최단 경로는 다를 수 밖에 없다. 따라서 각각의 다익스트라를 구하고 각 케이스마다 경로를 합하여 가장 큰 값을 출력한다. package practice; import java.io.BufferedReader; import java.io.IOException; import java.io.Inp..

Coding Test(최단 경로 - Dijkstra, Bellman-Ford, Floyd-Warsahall)

다익스트라 알고리즘(Dijkstra Algorithm) 특정한 노드에서 다른 모든 노드로의 최단경로를 구하는 알고리즘 시작 정점에서의 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구함 그리디를 이용한 알고리즘으로 MST의 PRIM()과 유사 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복 가중치 없는 경우 1 BFS 가중치 있는 경우 하나의 정점 양수 Dijkstra 음수 Bellman-Ford 모든 정점 Flod-Warsahall 1. 출발 노드를 설정한다. 2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장한다. 3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다. 4. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신한다. 5. 위 과정..

Coding Test(Prim Algorithm)

Prim의 핵심은 트리 집합을 단계적으로 확장하는 것이고, 새로운 정점을 연결할 때마다 새로운 정점에서 갈 수 있는 아직 연결되지 않은 정점들에 대한 간선을 추가해줘야 한다. PriorityQueue를 이용한 최소 힙으로 구현할 수 있고, 다익스트라 알고리즘과 구현 방식이 유사하다. BFS + PriorityQueue 1. 임의 정점을 하나 선택해서 시작 2. 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택 3. 모든 정점이 선택될 때 까지 1,2과정 반복 프림은 시작점을 정하고, 시작점에서 가까운 정점을 선택하면서 트리르 구성 하므로 그 과정에서 사이클을 이루지 않지만 크루스칼은 시작점을 따로 정하지 않고 최소 비용의 간선을 차례로 대입 하면서 트리를 구성하기 때문에 사이클..