Mhwan's Study/Algorithms
-
[알고리즘/토끼와 거북이] 플로이드의 토끼와 거북이 (Floyd's Tortoise and Hare) 알고리즘Mhwan's Study/Algorithms 2021. 4. 16. 00:32
이번 포스팅은 플로이드의 토끼와 거북이 알고리즘입니다. 이 알고리즘은 Linked List에서 사이클이 있는지 확인, 사이클의 시작점, 사이클의 길이를 O(N) 시간복잡도 (공간복잡도는 O(1))로 알아낼 수 있습니다. 개인적으로 색다른 알고리즘이기도, 다양한 알고리즘 문제에서 활용하고 있는 알고리즘으로, 확실히 공부하고 싶은 마음에 올립니다. 위와 같은 사이클이 있는 연결리스트가 있다면 사이클의 시작점은 2, 사이클의 길이는 4입니다. 이를 알아내는 방법은 아래와 같습니다. # 사이클이 있는지 판단 1. 연결리스트의 시작점에 2개의 포인터를 놓습니다. (하나의 포인터는 토끼, 하나는 거북이라 부르겠습니다.) 2. 토끼라는 포인터는 한번 이동할때 2칸씩, 거북이는 한번에 한칸씩 이동합니다. 3. 이를 반..
-
[알고리즘/플로이드] 플로이드-와샬(Floyd-Warshall) 알고리즘Mhwan's Study/Algorithms 2021. 2. 12. 03:49
플로이드 와샬 알고리즘은 다익스트라, 벨만포드 알고리즘과는 달리 모든 정점간의 최단거리를 구하는 알고리즘입니다. 이 알고리즘은 동적 프로그래밍 기법을 사용한 알고리즘으로 O(V^3)이라는 시간복잡도가 필요하며, 다익스트라 알고리즘을 모든 정점 V만큼 반복한 것보다 더 빠릅니다. 또한 음의 가중치 간선은 존재할 수 있으나 음의 가중치 사이클은 없다고 가정합니다. # 경유점 경유점이라는 개념은 플로이드 와샬 알고리즘의 핵심입니다. 어떤 경로든 최단 경로사이의 경유지가 존재할 것입니다. 위 그래프를 가정하면 1->2를 가는 최단 경로는 (1->3->4->2)가 되고, 3, 4는 1->2사이의 경로에 존재하는 경유점이 됩니다. 즉, u->v로 가는 최단 경로가 있다면 이것은 크게 두가지로 나뉠겁니다. 1. 경로..
-
[알고리즘/벨만포드] 벨만-포드(Bellman-Ford) 알고리즘Mhwan's Study/Algorithms 2021. 1. 23. 03:12
벨만-포드 알고리즘은 이전에 한 다익스트라 알고리즘처럼 단일 시작점에서 모든 정점까지의 최단거리를 구하는 알고리즘입니다. 이 알고리즘은 다익스트라와 달리 가중치가 음수인 간선을 포함하는 그래프에서 최단 경로를 정확히 구할 수 있고, 음수인 사이클을 판별해낼 수 있습니다. 다익스트라 알고리즘에 비해 시간복잡도가 좋지 않으므로, 음수인 간선을 갖는 그래프나 음수인 사이클을 판별할 때 사용하는 것이 좋습니다. # 완화 (Relaxation) 이 알고리즘의 가장 핵심이 되는 특성입니다. u에서 v까지의 최단거리 dis[v] cur.weight + nextNode.weight이 만족할 경우에만 우선순위 큐에 넣었습니다. 1 2 3 4 5 6 7 for (Node nextNode : graph.sparseList...
-
[알고리즘/다익스트라] 다익스트라(Dijkstra) 알고리즘Mhwan's Study/Algorithms 2021. 1. 15. 04:10
그래프를 탐색하는 알고리즘에는 대표적으로 DFS, BFS가 있고 이들은 모두 간선을 이용할때 가중치가 없는 경우이다. 특히 BFS의 경우 가중치가 없는 경우 최단경로를 구할때 사용하지만 노드 사이의 간선을 이용할 때 가중치가 있는 그래프가 있고, 시작점으로 부터 목적지까지의 최소한의 가중치 비용을 갖는 최단 경로를 계산해야할 때는 다익스트라 알고리즘, 플로이드-와샬 알고리즘, 벨만-포드 알고리즘을 사용해야합니다. 오늘부터 이 세개의 알고리즘을 공부하며 포스팅 할 계획으로, 다익스트라 알고리즘부터 시작하겠습니다. 먼저, 다익스트라 알고리즘은 하나의 시작점에서 다른 모든 정점까지의 최단 거리를 구할 수 있습니다. 단, 간선의 비용은 음수이면 안됩니다. (음수의 간선일 경우 플로이드-와샬 알고리즘을 사용합니다..
-
[알고리즘/투 포인터] 2020 카카오 인턴십 - 보석 쇼핑Mhwan's Study/Algorithms 2021. 1. 6. 21:39
본래 알고리즘 문제 같은 경우 따로 올리지 않으려 했지만, 꼭 알고 넘어가고 싶은 의미에서 올려봅니다. https://programmers.co.kr/learn/courses/30/lessons/67258 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 이 문제도 투 포인터 기법을 활용한 방법으로 이 방법을 활용해야 효율성을 통과할 수 있습니다. 투 포인터 기법이란 아래 글에서 확인하시기 바랍니다 mhwan.tistory.com/57 [알고리즘/투포인터] 투포인터 알고리즘 투 포인터 알고리즘 또는 슬라이딩 윈도우 기법 또는 지렁이 알고리즘 등 이름이 참 많은..
-
[알고리즘/투포인터] 투포인터 알고리즘Mhwan's Study/Algorithms 2021. 1. 6. 20:00
투 포인터 알고리즘 또는 슬라이딩 윈도우 기법 또는 지렁이 알고리즘 등 이름이 참 많은 알고리즘입니다. 개인적으로 이 알고리즘과 인연이 깊습니다. 알고리즘을 공부하며 처음 소름돋았던 알고리즘이기도 하며 대충 공부했었는데, 운이 좋게도 얼마 지나지 않아 응시했던 Kakao 공채 1차 코테에서 이걸 활용해 풀었습니다. 이 문제 덕분에 제 첫 코테를 통과라는 기쁨을 누렸고, 그 이후 여러 코테에서 비슷한 유형으로 마주쳤던 기억이 납니다. 솔직히 매번 쓸때마다 헷갈렸는데, 이번 기회에 제대로 학습해 올립니다. www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[..
-
[알고리즘/Stack/Queue] Stack으로 Queue 구현, Queue로 Stack 구현Mhwan's Study/Algorithms 2021. 1. 6. 02:08
스택 2개로 큐를 만들 수 있고, 큐 2개로 스택을 만들 수 있다. 개인적으로 이 알고리즘을 처음 알았을 때 참신함에 소름이 돋았던 기억이 난다. 스택은 LIFO형태이고, 큐는 FIFO형태 이므로 들어오고 나갈때 저장된 순서를 뒤집을 수 있다면 스택으로 큐를 구현할 수 있고, 큐로 스택을 구현할 수 있다. 그래서 2개가 필요한것이다. # Stack으로 Queue 구현 (뺄때 다른 스택으로 옮겨서 빼자!) 두개의 스택인 A, B 스택이 있다. - enQueue : A스택에 push - deQueue : B 스택에 남은게 있다면 B에 있는 것을 pop하고, 남은게 없다면 A스택에 있는 것을 모두 pop해서 B로 push하고 B에 있는 것을 pop한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 1..
-
[알고리즘/Stack] 유효한 괄호가 있는지 판별Mhwan's Study/Algorithms 2021. 1. 6. 01:32
이것도 스택을 이용한 대표적인 알고리즘 중 하나이다. 유효한 괄호는 [(()){}] 와 같이 여는 괄호와 닫는 괄호의 갯수가 같고, 각 여는 괄호와 닫는 괄호의 짝이 맞아야한다. # 대략적인 과정 1. 여는 괄호가 나올 경우 Stack에 push 2. 닫는 괄호가 나올 경우 스택에 pop해서 비교한다. (닫는괄호와 여는 괄호가 서로 짝이 다르거나, 스택이 비어있다면 괄호의 개수가 맞지 않아 모두 유효하지 않은 괄호식인 것이다.) 아, 그리고 이 과정을 모두 반복했는데 스택에 남아있는 괄호가 있어도 짝이 맞지 않은 것이고, 스택이 비어있어야 유효한 괄호인 것이다. # 소스코드 12345678910111213141516171819public boolean checkParentheses(String str) ..