알고리즘

Union-Find

minimax 알고리즘

파라메트릭 서치 (BOJ 1477)

import java.io.*; import java.util.*; public class Main { static int L,R; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int N = Integer.parseInt(st.nextToken()); int M = Integer.parseInt(st.nextToken()); R= Integer.parseInt(st.nextToken()); int [] arr = n..

KMP알고리즘

코드 import java.io.*; import java.util.*; public class Main { static int[] arr; static int N; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String a = br.readLine(); String b = br.readLine(); KMP(a,b); System.out.println(0); } static void KMP(String parent, String pattern) { int[] table = makeTable(pattern); int..

위상정렬(topology) 알고리즘

위상정렬은 순서를 찾아주는 알고리즘이다. 가령 정확한 순서를 모를 때 대략적인 순서를 만들어주는 알고리즘이다. 우선 이 알고리즘은 선행과 후행이 나온다. 선행과목이 있어야 후행과목이 있는 것처럼 쉽게 말해 순서가 주어진다. 주어진 순서를 보고 queue와 InDegree를 활용하는게 핵심인데 이것은 진입 차수다. 만약 1->3 2->4 3->4 1->2이렇게 있으면 진입차수는 1 2 3 4 0 1 0 2 이다. 순서가 어떨진 모르겠지만 진입차수가 0인 것은 내 앞에 어떤 것도 거칠 필요가 없다는 뜻이다. 그러니 queue에 제일 먼저 집어넣어준다. queue ( 1, 3) 1이 들어온 후 1를 큐에서 빼주고 제일 먼저 순서에 넣는다. 순서 = 1 그리고 1에서 또 진입할 수 있는 녀석을 찾아준다. 1에서..

다익스트라(dijkstra) 알고리즘

다익스트라는 임의의 한 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘이다. 작동원리는 임의의 한 점에서 다른 한 점까지 최단 거리를 갱신해주는 것이다. 최단 거리는 여러 정점을 타고 수차례 갱신될 수 있다. 이 설명은 그림이 좀 많이 필요한데 시간이 없다. 내일 시험이라서 나중에 수정해서 올리겠다. (여유가 생기면) 혹시 그럴 일은 없겠지만 내 블로그 애청자가 있다면 쪽지보내면 직접 설명 해주겠다. https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 ..

프림(Prim) 알고리즘

프림 알고리즘은 크루스칼 알고리즘과 마찬가지로 최소신장 트리를 만드는 알고리즘이다. 방법은 *모든 것은 minEdge[정점수]에 저장된다. //정점으로 가는 최소간선이라는 뜻 1. 임의의 정점 하나를 선택한다. 2. 현재 정점에서 연결된 다른 정점으로의 간선이 더 짧으면 민엣지에 값을 갱신한다. 3. 2번을 계속 반복한다. https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net package practic..

크루스칼(kruskal) 알고리즘

크루스칼 알고리즘은 최소신장트리를 만드는 문제이다. 신장트리는 모든 정점(Vertex)이 간선(Edge)로 이어진 그래프이다. 굳이 영어를 끼워넣은 것은 내가 헷깔려서 그렇다. 모든 정점을 잇는 간선의 값을 최소한으로 해서 연결하면 그게 최소신장 트리가 되고 이것을 만드는 것이 크루스칼 알고리즘이다. 크루스칼 알고리즘에는 서로소 집합을 구현해야 한다. 서로소 집합은 각 정점끼리 부모를 찾아주는 집합으로 보통 Union-Find함수로 많이 구현한다. https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타..

백트래킹

백트래킹 역시 특정 알고리즘으로 정해져 있는 것이 아니다. 짜여진 코드에 불필요한 계산이 포함되어 있는지 확인하고 삭제함으로써 연산 속도를 줄여서 시간초과를 피하는 것이다. 대표적으로 n-queens문제가 있다. 이런 체스판에 각 퀸이 서로를 공격하지 못하도록 퀸을 배치하는 것이다. 이때 가능한 경우의 수는 수백억이 넘는다. 하지만 실제 가능한 해는 92개? 정도 밖에 안된다. 92개를 찾으려고 수백억개를 계산할 필요가 있는가? 수백억은 컴퓨터로 계산해도 시간이 1분가까이 걸린다. 이런 문제점을 해결하기 위해서 사람들이 시간을 줄이려고 노력했고, 이런 과정자체가 하나의 백트래킹이 된 것이다. 백트래킹은 다른 말로 가지치기라고도 한다. 하지만 퀸을 놓을때 상하좌우,대각선으로 겹치는 퀸이 있는지 확인하면 대..

순열/조합/부분집합

줄여서 순조부라고 한다. 대부분 코테를 준비할 때 처음 마주하게 되는 영역이다. 출제비중이 그리 높진 않지만 이 개념을 모르고 구현도 못하는 상태로 코테를 보면 떨어질 것이다. 뿐만 아니라 이 개념을 알고 있으면 사고의 범위가 확장되고 문제를 풀 수 있는 카드가 하나 더 생긴다. 순열(Permutaition) 순서를 고려해서 나열할 수 있는 모든 경우의 수를 구하는 것이 순열이다. 순열은 n팩토리얼의 경우의 수를 가진다. 예를 들어 A,B,C가 있다고 가정하면 이를 나열 할 수 있는 경우는 ABC ACB BAC BCA CAB CBA 6가지가 나온다. 즉 3! 이다. 보통 n이 11일때까지 4천만개정도의 경우로 시간 복잡도를 구할 수 있고 12부터는 4억을 초과하기때문에 다른 풀이를 고려해 봐야한다. ht..