[알고리즘] 다익스트라(Dijkstra) - 최단거리 알고리즘

다익스트라(Dijkstra) 다익스트라 알고리즘은 음의 가중치(음의 간선, 음의 값)가 없는 그래프에서 최단 거리를 구하는 알고리즘입니다. 가장 짧은 경로를 찾으므로 "길 찾기" 문제에 많이 사용됩니다. 이전 다익스트라의 경우 O(n^2)의 시간복잡도를 가졌었지만, 현재는 우선순위 큐를 이용한 개선된 다익스트라 알고리즘이 탄생해 O(ElogE)의 시간복잡도를 가집니다. ( E는 Node의 간선의 수 ) 만약 음의 간선이 존재한다면 "벨만-포드 알고리즘"을 활용해야 합니다. 다익스트라 알고리즘은 그리디 알고리즘과 다이나믹 프로그래밍 기법을 사용한 알고리즘입니다. 그 이유는 아래의 알고리즘 특징에서 설명하겠습니다. 다익스트라 알고리즘 특징 각 지점은 그래프에서 '노드' 또는 정점으로 표현되고 지점간 연결된 ..

• format_list_bulleted ◼ CS 기초 지식/[알고리즘]
• · 2023. 2. 1.
• textsms

[알고리즘] 라인 스위핑 (Sweeping)

Line SweepingSweeping이라는 단어를 번역하면 "싹슬이 하는"이라는 뜻을 가집니다.즉, "한 쪽 방향부터 시작해서 다른 방향으로 스캔해가면서 쓸어가는 것"입니다.보통  라인스위핑 알고리즘은 좌표 문제에 많이 사용되며 O(nlogN)의 시간 복잡도를 가집니다.  라인 스위핑 알고리즘 문제 (백준 2170 : 선 긋기) 문제 설명매우 큰 도화지에 자를 대고 선을 그으려고 한다.매우 큰 도화지에 자를 대고 선을 그으려고 한다.선을 그을 때에는 자의 한 점에서 다른 한 점까지 긋게 된다.선을 그을 때에는 이미 선이 있는 위치에 겹쳐서 그릴 수도 있는데, 여러 번 그은 곳과 한 번 그은 곳의 차이를 구별할 수 없다고 하자.이와 같은 식으로 선을 그었을 때, 그려진 선(들)의 총 길이를 구하는 프로그..

• format_list_bulleted ◼ CS 기초 지식/[알고리즘]
• · 2023. 2. 1.
• textsms

[알고리즘] 투 포인터(Two Pointers)란?

투 포인터(Two Pointers) 투 포인터는 말 그대로 두 개의 포인터를 사용하여 문자열, 배열, List에서 원하는 값을 찾는 것 입니다. 투 포인터를 활용하기 위한 조건은 주어진 배열에서 연속된(정렬이 아닌) 부분 배열을 통해 문제를 해결할 수 있어야 합니다. 투 포인터 알고리즘을 활용하는 대표적인 예로는 배열에서 특정한 합을 갖는 부분 연속 수열을 찾을 때가 있습니다. 만약 이중 반복문을 통해 부분 연속 수열을 찾는다면 O(n^2)의 시간복잡도가 소요되는 반면 투 포인터를 활용한다면 O(n)의 시간복잡도로 시간을 단축 시킬 수 있습니다. 투 포인터는 두 개의 포인터를 사용하기 때문에 두 개의 인덱스를 가르키는 변수가 필요합니다. 그 변수를 하나는 "시작점을 가르키는 start", 다른 하나는 "..

• format_list_bulleted ◼ CS 기초 지식/[알고리즘]
• · 2023. 1. 27.
• textsms

[알고리즘] LIS(최장 증가 부분 수열)이란 ?

LIS (Longest Increasing Subsequence) 최장 증가 부분 수열 최장 증가 부분 수열은 말 그대로 가장 길게 증가하는 부분 수열으로 즉, 어떤 수열에서 만들 수 있는 부분 수열 중에서 가장 길면서 오름차순을 유지하는 수열을 LIS라고 합니다. 좀 더 이해하기 쉽도록 아래 그림을 봅시다. 만약 위와 같은 배열이 있을 때 만들수 있는 증가 부분 수열은 위와 같으며 최장 증가 부분 수열은 만들 수 있는 증가 부분 수열 중 길이가 가장 긴 [1, 2, 6]이 됩니다. LIS를 구현하는 방법으로는 두가지가 있습니다. DP [알고리즘] 동적 프로그래밍 (DP) 란? feat.동적 계획법 동적 프로그래밍(Dynamic programming) 란? 동적 프로그래밍은 "큰 문제"를 "부분 문제"로..

• format_list_bulleted ◼ CS 기초 지식/[알고리즘]
• · 2023. 1. 26.
• textsms

[알고리즘] 힙 정렬(Heap Sort)이란?

먼저 힙 정렬에 대해 다루기 전에 "힙"에 대한 이해가 필요합니다. 힙에 대해 알고 싶다면 아래 링크를 참고하시면 도움됩니다. 힙(Heap) 자료구조 힙(Heap)이란 ? 완전 이진 트리의 일종으로, 데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 만들어진 자료구조입니다. 힙을 사용하는 이유는 최댓값과 최솟값을 찾기 위해 배열을 사용하는 경 hstory0208.tistory.com 힙 정렬(Heap Sort) 힙 정렬 알고리즘은 삽입과정 없이 삭제과정만이 이뤄집니다. 최대힙(max heap)을 구현한뒤, 루트 노드를 삭제하여 마지막 노드가 루트 노드가 되어 최대힙의 규칙에 맞게 재구조화 되며 정렬합니다. 힙 정렬 알고리즘은 주로 다음과 같은 경우에 유용하게 사용됩니다. 최댓값과 최솟값을 구할 때 최대 k만..

• format_list_bulleted ◼ CS 기초 지식/[알고리즘]
• · 2023. 1. 21.
• textsms

힙(Heap) 자료구조

힙(Heap)이란 ? 완전 이진 트리의 일종으로, 데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 만들어진 자료구조입니다. 힙을 사용하는 이유는 최댓값과 최솟값을 찾기 위해 배열을 사용하는 경우 O(n)의 시간복잡도가 걸리는 반면, 힙을 사용하면 O(logn)의 시간복잡도가 소요되므로 시간적으로 효율적이기 때문입니다. 완전 이진 트리 (Complete Binary Tree)란 ? 이진 트리에 노드를 삽입할 때 왼쪽부터 차례대로 삽입하는 트리로 아래 그림과 같습니다. 만약, 왼쪽이 비어 있고 오른쪽이 채워져있다면 완전 이진 트리라고 할 수 없습니다. 힙의 특징 힙은 최대 힙과 최소 힙으로 나눠집니다. 최대 힙(max heap) : 부모 노드의 값이 자식 노드이 값보다 크거나 같은 완전 이진 트리. ( 부모 ..

• format_list_bulleted ◼ CS 기초 지식/[개발상식]
• · 2023. 1. 21.
• textsms