Algorithm Study9 최단 경로 알고리즘(다익스트라 알고리즘) 🌱 최단 경로 알고리즘 최단 경로 알고리즘(Shortestest Path)은 가장 적은 비용(Minimum Cost)으로 연결하는 간선들을 찾는 문제입니다. 대표적인 최단 경로 알고리즘 문제로, 다익스트라, 벨만-포트, 플로이드-워셜, A* 알고리즘이 있습니다. 이번 포스팅에서는 다익스트라 알고리즘(Dijkstra) 위주로 공부해볼 예정입니다. 🚀 다익스트라 알고리즘 구현하기 다익스트라 알고리즘은 시작노드에서부터 최단 경로를 구하는 알고리즘입니다. 첫번째 문제는 특정노드에서 모든 노드의 최단 경로를 찾는 프로그래머스 - 배달↗ 문제입니다. 문제를 통해 동작 방식을 이해해보도록 하겠습니다. 해당 문제는 1번 노드부터 5번 노드까지의 간선과 연결된 노드가 담긴 리스트 `road`와 노드의 갯수 `N` 제한 .. 2024. 4. 19. 백트래킹(BackTracking) 🌱 백트래킹 백트래킹(BackTracking)은 다른 알고리즘 정도는 아니라 일종의 기법, 전략입니다. 백트래킹(Backtracking, 퇴각 검색)은 일종의 해를 찾기 위해 재귀적으로 문제를 풀어나가다가 제약 조건에 위배가 된다면 제외 표시를 하고 다음 단계로 넘어가는 방법입니다. 구현하는 방법 결론적으로, 백트래킹 기법은 제약 조건을 만족하는 경우를 탐색하기 때문에 DFS와 BFS와 같은 완전 탐색 기법으로 구현이 가능합니다. 그러나, 특성상 제약조건에 만족하지 않으면 다시 이전 노드로 돌아와야 하기 때문에 BFS보다는 DFS로 구현하기 편합니다.물론 시간이 부족한 경우엔 BFS로 풀어야합니다. 그리고 만약 제약조건에 만족하지 않는 경우 다른 루트로 돌아가야 합니다. 이때, 조건에 만족하는지 확인하는.. 2024. 4. 16. DFS, BFS 그래프 탐색 알고리즘 1 그래프 자료구조 간단 정리 그래프 구현 방법의 차이 그래프(Graph)는 정점(Vertax, Node)과 간선(Edge)으로 이루어진 그래프이며 정점 간 연결관계를 간선으로 나타낸다. 그래프는 연결 상태에 따라 양방향, 방향 가중치, 완전 그래프등으로 분류된다. 그렇다면 그래프를 구현하는 방법으로 어떤 것들이 있을까? 인접 행렬 (Adjacency Matrix) : 간선의 개수와 무관하게 V^2의 공간 복잡도를 가지며 O(1)로 위치의 값을 찾아낼 수 있는 행렬식 구조이다. 인접 리스트 (Adjacency List) : 해당 정점에 연결된 다른 정점들을 찾는 방식으로 공간 복잡도는 O(E+V) 지만 확인하는데 오래걸린다. 그래프의 특징 사이클이 있거나 없을 수 있다. 만약 없는 경우, 트리 구조라고 한다.. 2024. 3. 21. 트리 순회 알고리즘 트리(Tree) 트리는 노드(Node)와 그 노드들을 연결하는 간선(Edge)로 이루어진 자료구조이다. (노드가 N개인 경우 간선은 N-1개이다.) 트리는 계층적 관계로 이루어져 있기 때문에 그래프와 다르게 사이클이 이루어지지 않는다. 사이클이 이루어지지 않고 방향성이 정해져 있기 때문에 트리는 그래프 중에서 DAG에 속하는 그래프이다. 트리는 그럼 어떻게 이루어져 있는가? 트리의 구성은 다음과 같다. 가장 최상단에 루트 노드(Root Node)가 있고 밑으로 내려갈수록 자식 노드가 있으며 최하단의 노드는 리프노드(Leaf Node, 단말노드;)라고 부른다. 가장 헷갈려하는 구성요소는 높이와 깊이이다. 높이는 말그대로 트리의 최대 높이를 말한다. 레벨과 동일하며 깊이는 노드를 중심으로 경로의 길이를 의미.. 2024. 3. 14. [코테스터디] 정렬 팀 정렬(Tim Sort) 파이썬에서 주로 사용되는 고성능 정렬 알고리즘이다. 주로 `sorted`와 `sort` 이 두가지로 사용되며 이 둘은 차이점이 존재한다. `sort`는 리스트 자체를 정렬하는 제자리 정렬(in-place Sort)이므로 결과를 리턴할 필요 없이 정렬 후 적용 시켜버린다. `sort`와 `sorted`의 인자인 `key`에 함수를 넣을 수 있다. 일반적으로 람다 함수를 넣는 경우가 있는데 직접 함수를 만들어서 넣어도 된다. 만약 특정 조건으로 정렬을 하고 싶을 때 다음과 같이 사용하면 된다. 공식문서 참조↗ 계수 정렬(Counting Sort) 시간 복잡도 공간 복잡도 O(N) O(N) 배열의 인덱스를 특정 값으로 사용하는 정렬 알고리즘이다. 예를 들어 다음과 같이 첫번째 줄은 .. 2024. 3. 11. 우선순위 큐와 힙의 차이를 알아보자. 이번 포스팅에는 스택, 큐, 힙 알고리즘 문제를 풀어본 궁금증으로 비슷한듯 다른 우선순위큐와 힙의 차이에 포스팅해보려고 한다. 먼저 결론적인 개념은 다음과 같다. 큐(Queue) : 먼저 들어오는 데이터가 먼저 나오는 선입선출(FIFO) 구조 우선순위 큐(Priority Queue) : 우선순위가 높은 데이터가 먼저 나가는 구조 힙(Heap) : 루트 노드에 최대값이나 최소값을 저장하고 있는 완전이진트리 Queue 큐 자료구조 관련 문제 : 트럭 관련 문제로 [백준]트럭↗ 문제와 [프로그래머스]다리를 지나는 트럭↗ 문제가 있다. 트럭 문제는 트럭들의 최대하중을 기준으로 최대 하중보다 크면 다리 큐(Queue)에 0을 추가(Push)하고 적으면 다음 트럭을 추가하는 문제이다. Push : 다리 하중을 버틸.. 2024. 2. 24. [코테스터디] 이진 탐색 이진 탐색 이진 탐색(이분 탐색) 문제는 전체 데이터가 정렬된 상태에서 사용할 수 있는 알고리즘이다. 문제에서 순차탐색을 이용해 풀려고 했을 때, 탐색할 데이터가 너무 커서 탐색하기 어려울 때 이분탐색을 이용해 빠르게 문제를 풀 수 있다. 이진 탐색은 그러므로 O(logN)의 시간 복잡도로 빠르게 순회할 수 있다. 보통 이진 탐색 문제는 다익스트라와 연계하여 나올 수 있다. 중간 점 찾기 이진 탐색 문제는 시작점, 끝점, 중간점으로 변수 3개를 이용해 빠르게 데이터를 찾을 수 있다. 중간점은 시작점과 끝점을 합해 2로 나눈 값으로 웬만하면 외워두는게 좋다. while left mid: # x가 중앙값보다 큰 경우 start = mid+1 else: # x가 중앙값보다 작은 경우 end = mid-1 더보.. 2024. 1. 8. [코테스터디] 다이나믹 프로그래밍(DP) 다이나믹 프로그래밍(동적 계획법) 보통 알고리즘 문제를 풀 때 시간과 메모리를 절약하면서 효율적인 알고리즘을 작성한다. 다만, 어떤 문제는 메모리 공간을 좀 사용해서 푸는 문제가 있는데 그 문제가 다이나믹 프로그래밍(DP) 문제이다. 다이나믹 프로그래밍 문제는 한번에 해결하는 문제가 아니라 조금씩 점차적으로 풀어가는 문제이므로 점화식을 생각하면서 풀어야 한다.다이나믹 프로그래밍 문제를 푸는 유형에는 탑다운(Top-down)과 보텀업(Bottom-up)이 있다. 개인적으로 선호하는 방식을 택하면서 풀면 된다. 물론, 연습할 때 두가지를 이용해 풀어보면 좋을 것이다. 탑다운, 하향식(Top-down) 재귀 함수를 이용해 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식이다. 메모이제이션을 이용해 재귀함수를.. 2024. 1. 4. [코테스터디] 그리디(Greedy) 그리디 문제는 현재 상황에서 가장 좋은 것만 고르는 방법 즉, 탐욕적으로 문제 푸는 방법을 의미한다. 부분적으로 구한 해를 통해 전체 해를 구하면 된다. 보통 정렬이나 우선순위 큐(`heapq`)를 이용해 푸는 문제들이 많다. 사실 그리디 문제는 유형이 없는 것 같다. 간단한 문제들도 있지만 복잡한 문제들도 많으니 많이 풀어봐야 한다. 더보기 그리디 문제에서 나오는 우선순위 큐 우선순위 큐를 구현하기 위해 힙(Heap)이라는 자료구조를 사용한다. 우선순위 큐는 스택이나 큐와 다르게 우선순위가 높은 데이터를 가장 먼저 처리한다.대표적으로 아래 먹방 라이브 문제가 우선 순위 큐를 사용하는 그리디 문제이다. `import heapq`를 통해 최소 힙 모듈을 불러와 사용할 수 있다. 데이터가 회전 초밥처럼 돌아.. 2024. 1. 3. 이전 1 다음
