알고리즘/알고리즘_이론

1. 그리디 알고리즘 (Greedy Algorithm, 탐욕법)이란? : 눈 앞의 이익만을 좇는 알고리즘. 매 선택마다 그 당시 가장 최적인 값을 선택한다. 2. 그리디 알고리즘 특징 1. 백트래킹으로 추가점검 X 백트래킹 : 해를 찾는 도중 해가 아니여서 막히면, 되돌아가서 다시 해를 찾아가는 기법 2. 최적해 ≠ 그리디 인 경우가 많다. 근데 안좋아보이는데 왜쓰냐? -> 정확하게 구하는 것보다 속도가 빠르다..! 따라서 정확한것 보단 근사값 구하는게 더 효율적일 때도 쓰임. (근사값 구하는 알고리즘에는 조합 탐색, 메타휴리스틱 알고리즘 등도 있음.) 3. 그리디 알고리즘을 사용해 최적해가 구해지기위한 조건 ( = 탐욕적 알고리즘의 정당성 증명) a. 탐욕 선택 속성(Greedy Choice Prope..

1. 우선순위 큐에 대해 일반적인 큐와 달리, 먼저 들어간 데이터가 아니라 우선순위가 높은 데이터가 먼저 나오는 자료구조 우선 순위를 적절이 조절함에 따라 일반적인 스택, 큐도 구현이 가능 힙을 통해 구현 가능 힙 : 부모 노드의 키 값이 항상 자식 노드의 키 값보다 큰 완전 이진 트리 배열, 연결리스트를 이용해 구현할 수도 있지만, 시간복잡도 면에서 힙을 통해 구현하는 방식이 효율적이다. 구현방식에 따른 시간 복잡도우선순위 큐 구현 방식 삽입시간 삭제시간 배열 $O(1)$ $O(N)$ 연결리스트 $O(N)$ or $O(1)$ $O(1)$ or $O(N)$ 힙 $O(logN)$ $O(logN)$ 2. 힙의 개념 Complete Binary Tree 루트노드부터 왼쪽 → 오른쪽 자식 노드 순서대로 데이터가..

1. 다익스트라 알고리즘이란 하나의 시작 정점으로부터 다른 모든 정점까지의 최단 거리를 구하는 알고리즘으로, DP와 그리디로 분류된다. 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용 (DP의 특징) 정점 = 노드 = V 간선 = E 음으로 표현되지 않는다. 2. 다익스트라 알고리즘 구현 작동과정 Characters: 1. vector graph// 그래프. graph[출발정점] = {가중치, 도착정점} 2. d[] // 최단거리 테이블 3. priority_queue pq; Operations 1. 출발 정점 설정 2. 출발 정점 기준, 다른 모든 정점까지의 최소 비용 테이블 저장 - 일반적으로 출발정점 → 출발정점 비용 : 0 & 출발 정점 → 다른 모든 정점까지의 최소..