알고리즘

다익스트라(Dijkstra) 알고리즘 DP를 활용한 최단 경로 탐색 알고리즘 다익스트라 알고리즘은 특정한 정점에서 다른 모든 정점으로 가는 최단 경로를 기록한다. 여기서 DP가 적용되는 이유는, 굳이 한 번 최단 거리를 구한 곳은 다시 구할 필요가 없기 때문이다. 이를 활용해 정점에서 정점까지 간선을 따라 이동할 때 최단 거리를 효율적으로 구할 수 있다. 다익스트라를 구현하기 위해 두 가지를 저장해야 한다. 해당 정점까지의 최단 거리를 저장 정점을 방문했는 지 저장 시작 정점으로부터 정점들의 최단 거리를 저장하는 배열과, 방문 여부를 저장하는 것이다. 다익스트라의 알고리즘 순서는 아래와 같다. 최단 거리 값은 무한대 값으로 초기화한다. for(int i = 1; i

비트마스크(BitMask) - 집합의 요소들의 구성 여부를 표현할 때 유용한 테크닉 왜 비트마스크를 사용하는가? - DP나 순열 등, 배열 활용만으로 해결할 수 없는 문제 - 작은 메모리와 빠른 수행시간으로 해결이 가능 (But, 원소의 수가 많지 않아야 함) - 집합을 배열의 인덱스로 표현할 수 있음 - 코드가 간결해짐 비트(Bit)란? 컴퓨터에서 사용되는 데이터의 최소 단위 (0과 1) 2진법을 생각하면 편하다. 우리가 흔히 사용하는 10진수를 2진수로 바꾸면? 9(10진수) → 1001(2진수) 비트마스킹 활용해보기 - 0과 1로, flag 활용하기 [1, 2, 3, 4 ,5] 라는 집합이 있다고 가정해보자. 여기서 임의로 몇 개를 골라 뽑아서 확인을 해야하는 상황이 주어졌다. (즉, 부분집합을 의..

[알고리즘] LCA(Lowest Common Ancestor) 최소 공통 조상을 찾는 알고리즘 → 두 정점이 만나는 최초 부모 정점을 찾는 것! 트리 형식이 아래와 같이 주어졌다고 하자 4와 5의 LCA는? → 4와 5의 첫 부모 정점은 '2' 4와 6의 LCA는? → 첫 부모 정점은 root인 '1' 어떻게 찾죠? 해당 정점의 depth와 parent를 저장해두는 방식이다. 현재 그림에서의 depth는 아래와 같을 것이다. [depth : 정점] 0 → 1(root 정점) 1 → 2, 3 2 → 4, 5, 6, 7 parent는 정점마다 가지는 부모 정점을 저장해둔다. 위의 예시에서 저장된 parent 배열은 아래와 같다. // 1 ~ 7번 정점 (root는 부모가 없기 때문에 0) int parent..

알고리즘 문제를 풀면서 최적화에 신경을 써야할 때가 있다. (시간이나 메모리를 줄이는 것이 중요한 B형처럼..) 1. for문의 ++i와 i++ 차이 for(int i = 0; i < 1000; i++) { ... } for(int i = 0; i < 1000; ++i) { ... } 내부 operator 로직을 보면 i++은 한번더 연산을 거친다. 따라서 ++i가 미세하게 조금더 빠르다. 하지만 요즘 컴파일러는 거의 차이가 없어지게 되었다고 한다. 2. if/else if vs switch case '20개의 가지 수, 10억번의 연산이 진행되면?' if/else 활용 : 약 20초 switch case : 약 15초 switch case가 더 빠르다. (경우를 찾아서 접근하기 때문에 더 빠르다) if..

[백준 1261] 알고스팟 문제 출처 : 링크 경로를 이동하는 걸 생각하면 DFS나 BFS를 활용해야 될 것 같다. 하지만 기존의 문제와는 다르게, '가중치'가 존재한다. 1인 값을 가지고 있는 곳을 지날 때는 벽이 있는 것이므로 부수고 지나갈 수 밖에 없다. 따라서 그냥 움직이는 것이 아닌, 1인 곳을 지나갈 때마다 값을 변경시켜나가야 하는 문제다. 우선 미로탐색처럼 BFS와 유사한 방식으로 나아가지만, 이 가중치 값을 최소화 시키기 위해 그냥 큐가 아닌 우선순위 큐를 사용해서 저장한다. (우선순위를 위해 comperable 활용) 123456789101112131415161718class Spot implements Comparable{ int y; int x; int cost; public Spot..

서로소 집합(Disjoint-sets) [알고리즘] 서로소 집합(Disjoint-sets) 서로소 or 상호배타 집합서로 중복 포함된 원소가 없는 집합(= 즉, 교집합이 없는 것) 대표자(representative)집합에 속한 하나의 특정 멤버를 통해서 각 집합들을 구분 상호배타 집합 표현 방법연결 리스트트리 상호배타 집합 연산Make-Set(x), Find-Set(x), Union(x,y) 트리를 이용해 상호배타 집합 표현된 모습부모는 해당 노드의 Find-Set 값 연산Make_Set(x) : 유일한 멤버 x를 포함하는 새로운 집합을 생성하는 연산Find_Set(x) : x를 포함하는 집합을 찾는 연산(해당 노드의 부모 정보 갱신)Union(x,y) : x와 y를 포함하는 두 집합을 통합하는 연산 M..

[알고리즘] 트라이(Trie) 트라이(TRIE) 트라이(TRIE)retrieval 문자열의 집합을 표현하는 트리를 말한다모든 문자열은 다른 문자열의 접두어가 아니라고 가정 부분 문자열 검사ba가 abac의 부분 문자열인가?두개 접두사의 최장 공통 접두어 찾기abac와 ac의 최장 공통 접두어는?사전적 순서로 정렬된 k번째 접미사 찾기abac의 3번째 접미사는? : abac, ac, bac, c (정답 : bac) 각 간선은 하나의 문자에 대응한다같은 노드에 나오는 간선들은 같은 레벨을 갖지 않음각 문자열은 단말 노드에 대응한다 Compressed Trie노드들과 간선들을 부분 문자열로 압축(= 접미어 트리(Suffix Tree)) 문자열 S = {xabxac}에 대한 접미어 트리 발생하는 문제점 해결책하..

[알고리즘] 다익스트라(Dijkstra) 다익스트라(Dijkstra) : 하나의 선택한 정점에서 각 정점까지 갈 수 있는 최단거리를 구하는 알고리즘 경로를 찾을 때 가중치가 있으면 사용하자 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657import java.util.Arrays; /** * Dijkstra : 하나의 선택한 정점에서 각 정점까지 갈 수 있는 최단거리를 구하는 알고리즘 * * Greedy 방식, 음이 아닌 가중치일 경우만 사용가능 * 음의 가중치가 있는 경우 => 벨만포드 알고리즘을 통해서 구해야 한다 * 시간복잡도 O[n^2] */ public cl..

[알고리즘] 백트래킹(Backtracking) [알고리즘] 백트래킹(Backtracking) 백트래킹이란?모든 경우의 수를 검색하는 알고리즘'특정조건'을 만족하는 모든 경우의 수를 찾고 싶을 때 유용DFS(깊이 우선 탐색)을 기반으로 하는 알고리즘 후보해 집합에서 최적해 집합을 찾아내는 문제에 적용 가능!후보해 : 정답이 될 가능성이 있는 모든 조합최적해 : 문제의 답으로 기준을 만족하는 해 DFS는 Brute Force 알고리즘으로, 재귀함수를 통해 그냥 모두 다 검사해서 찾음 DFS와 백트래킹의 차이점은 '가지치기'가지치기를 이용하기 때문에 DFS처럼 모든 경우의 수를 확인하는 알고리즘은 아님! 가지치기는 어렵게 생각하지말고 반복문에서 break나 return에 해당한다고 생각하자 백트래킹 대표 문제..

[git] 백준 1149, RGB거리 문제 출처 - https://www.acmicpc.net/problem/1149 문제 RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이다. 처음 집과 마지막 집은 이웃이 아니다. 각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠할 때 드는 비용의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 집의 수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 각 집을 빨강으로 칠할 때, 초록으로 칠할 때, 파랑으로 칠할 때 드는 비용이 ..