본문 바로가기

알고리즘 공부 및 문제 풀이/알고리즘(ALGORITHM)

 (8)
[pro] 프로그래머스 level3 12907 거스름돈 (Java) - dp [문제] https://school.programmers.co.kr/learn/courses/30/lessons/12907 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 1원, 2원, 5원이 있고 5원의 거스름돈을 거슬러줘야하는 상황. 1원 - 1 (1가지) 2원 - 1+1, 2 (2가지) 3원 - 1+1+1, 1+2 (2가지) 4원 - 1+1+1+1, 1+1+2, 2+2 (3가지) 5원 - 1+1+1+1+1, 1+1+1+2, 1+2+2, 5 (4가지) 즉 거스름돈 5원을 거슬러주기 위한 경우의 수는 다음과 같다. 1) 1원을 이용 (1+1+1+..
[알고리즘] 소수 판별 알고리즘 - 에라토스테네스의 체 1. 에라토스테네스의 체란? 제목 그대로 소수를 판별하는 알고리즘으로서 소수들을 대량으로 빠르게 구할 수 있는 방법이다. O(N^1/2)의 시간복잡도를 갖는다. 원리 소수란 1과 자기자신만을 약수로 갖는 수를 의미한다. 즉, 1을 제외한 어떤 수의 배수가 되는 수들은 모두 소수가 아니다. 에라토스테네스의 체는 이러한 소수의 특성을 이용한다. 임의의 수 n 까지의 소수를 구하고자 할 때, 2부터 n의 제곱근까지 돌며 모든 배수들을 소수에서 제거시키는 방식으로 동작한다. ※ 왜 n의 제곱근까지만 확인해도 되는지? 2. 구현 (c++) using namespace std; int n; int prime[1001]; void primeNum(){ // prime 배열 초기화 for (int i = 2; i
[알고리즘] 최단 경로 알고리즘(3) - 플로이드 워셜(Floyd-Warshall) 알고리즘 1. 플로이드 워셜 알고리즘이란? 다익스트라 알고리즘이 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이었다면, 플로이드-워셜 알고리즘은 한 번 실행하여 모든 노드 간의 최단 경로를 구할 수 있다. 또한 플로이드-워셜 알고리즘 역시 다익스트라와는 다르게 음의 가중치를 갖는 간선이 있어도 사용 가능하다. 플로이드-워셜 알고리즘은 다이나믹 프로그래밍에 속하여 다음과 같은 점화식을 갖는다. 2. 진행 과정 - 모든 지점에서 다른 모든 지점까지의 최단 경로를 저장하기 위해 2차원 거리 배열을 이용한다. - 최단 거리 테이블의 초기 상태를 저장한다. - 1번 정점을 거쳐서 가는 경우에 대해 최단 거리 테이블을 갱신한다. - 2번 정점을 거쳐서 가는 경우에 대한 최단 거리 테이블을 갱신한다. - ..
[알고리즘] 최단 경로 알고리즘(2) - 다익스트라(Dijkstra) 알고리즘 1. 다익스트라 알고리즘이란? 그래프 상에서 최단 경로(최소 비용)를 찾는 알고리즘 중 하나이다. 그 중 특히, 시작 노드와 도착 노드가 주어졌을 때 두 노드 사이의 최단 경로를 찾을 때 유용하다. 또한 벨만-포드 알고리즘이 음수 간선이 있어도 사용 가능한 데 비해, 다익스트라는 양수의 가중치 값을 갖는 간선에 대해서만 사용할 수 있다! 만약 음수의 가중치값을 가지는 간선이 존재한다면 다익스트라 알고리즘을 이용할 수 없다. 그 이유는 다익스트라 알고리즘의 경우 그리디 알고리즘을 적용하여 현재 방문 정점과 연결된 정점들 중 가장 적은 가중치값을 가지는 정점을 선택해가며 값을 갱신해준다. 그 후에는 방문한 정점에 대해서는 건드리지 않는다. a ---(3) b, a ---(5) c, b ---(x) c 와 같..
[알고리즘] 최단 경로 알고리즘(1) - 벨만 포드(Bellman Ford) 알고리즘 1. 벨만-포드 알고리즘이란? 그래프 상에서 최단 경로를 찾는 알고리즘 중 하나이다. 또 다른 최단 경로 알고리즘인 다익스트라에 비교해서 간선의 가중치가 음수여도 가능하지만 다익스트라에 비해 수행 시간이 더 오래 걸린다는 단점이 있다. 다익스트라 알고리즘이 그리디 알고리즘인 반면 벨만-포드 알고리즘은 다이나믹 프로그래밍을 기본 개념으로 한다. 이전에 계산해 저장된 최단 경로를 이용해서 새로운 최단 경로를 갱신하는 방식이다. 그리디하지 않게 동작하기 때문에, 모든 경우의 수를 탐색하는 동작 방식을 취한다. 시작 노드 s에서 v로 가는 최단 경로는 s에서 u로의 최단 경로 + u와 v 사이에 가중치를 더한 값으로 계산된다. 정점의 개수가 N개라면 N-1 개의 간선을 선택해 값을 갱신한다. (N-1이 아닌 N..
[알고리즘] 세그먼트 트리(Segment Tree) 1. 세그먼트 트리 세그먼트 트리란 특정 구간의 합(최솟값, 최댓값, 곱 등)을 구할 때 사용하는 자료구조이다. 문제 상황은 다음과 같다. (백준 설명) 배열 A가 있고, 여기서 다음과 같은 두 연산을 수행해야하는 문제를 생각해봅시다. 1) 구간 l, r (l ≤ r)이 주어졌을 때, A[l] + A[l+1] + ... + A[r-1] + A[r]을 구해서 출력하기 2) i번째 수를 v로 바꾸기. A[i] = v 수행해야하는 연산은 최대 M번입니다. 세그먼트 트리나 다른 방법을 사용하지 않고 문제를 푼다면, 1번 연산을 수행하는데 O(N), 2번 연산을 수행하는데 O(1)이 걸리게 됩니다. 총 시간 복잡도는 O(NM) + O(M) = O(NM)이 나오게 됩니다. N과 M이 매우 큰 경우, 너무 오랜 시간..
[알고리즘] 백트래킹(Backtracking) 알고리즘 1. 백트래킹 알고리즘 : 해를 찾는 도중에 막히면 되돌아가서 다시 해를 추적해나가는 방법. 되추적(Backtracking)이라고 부른다. 가능한 모든 방법을 탐색하는 것에는 깊이 우선 탐색(Depth First Search)가 있는데, 이는 가능한 모든 곳을 방문하기 때문에 경우에 따라 매우 비효율적일 수 있다. 백트래킹은 해를 찾아가는 도중, 현재 경로가 해가 될 것 같지 않으면 그 경로를 계속 가지 않고 되돌아간다. 따라서 비효율적인 경로를 차단하여 고려하지 않는 효율적인 기법이다. 이를 가지치기(pruning)라고 하는데, 가지치기를 얼마나 잘하느냐에 따라 백트래킹 알고리즘의 효율성이 결정된다. 가지치기(pruning) : 경로를 진행하다 해가 될 가능성이 없다고 판단하면 백트래킹(Backtrac..
[알고리즘] 동적프로그래밍(Dynamic programming) 1. 동적프로그래밍(Dynamic programming) : 큰 문제를 작은 부문제로 나누어서 풀어나가되, 이미 계산했던 연산이라면 다시 하지 않고 기록되어 있는 값을 가져와서 진행하도록 하는 방식이다. 예를 들어, 피보나치 수열을 재귀를 이용해서 풀면 다음과 같다. #include int fibo(int num) { if(num == 1) return 1; else if( num ==2 ) return 1; else return fibo(num-1)+fibo(num-2); } int main() { int num; std::cin >>num; std::cout 원점 -> 목표점) 성능 : 동적프로그래밍은 단방향적 특성으로 인해 효율적임 / 분할통치는 분할 회수 및 중복 연산의 수행이 요구됨. 4. 예제..

티스토리툴바