CS/알고리즘

Dijkstra algorithm

데이크스트라(다익스트라) 알고리즘 - Dijkstra algorithm 다이나믹프로그래밍기법을 사용한 알고리즘 기법 대표적인 최단 경로(Shortest Path) 탐색 알고리즘이다. 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 특징 1. 현재 노드에서 다른 노드로 가는 최단 거리( 가중치는 음의 간선을 포함하지 않는 양수만 가짐) 2. (현재노드까지 비용 + 다음 노드로 가는 비용) < (다음 노드로 가는 기존 비용) 이라면 갱신 3. 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다는 특징이 있다. 구체적인 동작 과정 1. 출발 노드 설정 2. 출발 노드 기준 각 노드의 최소 비용을 저장 3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드 ..

Backtracking

백트래킹이란? 해를 찾는 도중 해가 아니어서 막히면 되돌아가서 다시 해를 찾아가는 기법. 최적화 문제와 결정 문제를 푸는 방법이다. 특징 - 해를 찾아가는 도중, 지금의 경로가 invalid 하다면 그 경로를 더이상 가지 않고 되돌아감. -> 즉 답이 될 만한지 판단하고 그렇지 않으면 그 부분까지 탐색하는 것을 하지 않고 가지치기 하는 것 가지치기를 얼마나 잘하느냐에 따라 프로그램의 효율이 달라짐 - DFS보다 효율적이다. 예시 1: BOJ 15649번: N과 M(1) https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한..

Priority Queue

Priority Queue 앞에서 공부 했던 큐(Queue)는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조다. 우선 순위 큐(Priority Queue)는 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다. 우선 순위 큐의 속성 모든 항목에는 우선순위가 있다. 우선 순위가 높은 원소는 낮은 원소보다 먼저 queue에서 제외된다. 두 요소의 우선 순위가 같으면 queue의 순서에 따라 제공된다. 보통 Heap을 기반으로 구현됨 선언 방법 - Java // default : 우선순위가 낮은 숫자 먼저 나옴(오름 차순) PriorityQueue pQ = new PrioryitQueue(); // 내림차순 Priority..

Stack & Queue 알고리즘 공부

Stack & Queue Stack 스택의 특징: 후입선출(LIFO : Last In FIrst out) 구조 단방향 입출력 - 데이터의 들어오는 방향과 나가는 방향이 같음 데이터를 하나씩만 넣고 뺌 Monotonic Stack(단조 스택) → 기본적인 스택 기능을 가지면서 모든 원소들이 오름차순(혹은 내림차순)을 유지하도록 한다. 쉽게 얘기해서 원소들은 특정 원소를 제거해서 정렬하는 방식 문제 1 : BOJ 10773 제로: 10773번: 제로 → 가장 쉬운 문제 알고리즘 설명 정수 K를 입력 받는다. 입력 받은 값이 0일 경우 pop() 아닐 경우 push() → 스택을 쓰지 않고도 변수를 선언해서 계산이 가능함 문제 2 : BOJ 2494 탑: 2493번: 탑 → 위에서 설명한 Monotonic S..