알고리즘(アルゴリズム）/자주 까먹는 알고리즘(よく忘れるアルゴリズム） 썸네일형 리스트형 벨만-포드 알고리즘(가중치가 음수일 때의 최단경로) https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net import java.io.*; import java.util.*; // 벨만-포드에 대해서는 https://velog.io/@kimdukbae/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B2%A8%EB%A7%8C-%ED%8F%AC%EB%93%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Bellman-Ford-Algorithm .. 더보기 플로이드 - 워샬 알고리즘 https://www.acmicpc.net/problem/11404 [모든] 정점과 정점 사이의 최단 거리를 알고 싶을 때 사용 (시간 복잡도 O(N^3)으로 그렇게 성능이 좋지 않다) 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net import java.io.*; import java.util.*; public class Main { private static int n,m; private static BufferedReader br = new BufferedReader(new InputStreamReader.. 더보기 0-1 BFS 특징 1. 가중치가 0과 1로만 이루어 져 있을 때에만 사용이 가능 2. 일반적인 큐가 아닌 데큐(Deque)를 사용해야 한다. 알고리즘의 핵심 포인트 1. 가중치 그래프이므로, 기존의 BFS로 최단 경로를 구할 때와 같이 [깊이]가 아닌, [가중치의 최소합]이 최단 경로의 길이가 된다. 2. 위 1의 [가중치의 최소합]을 구하기 위하여, a) 가중치의 합이 0인 경로... b) 가중치의 합이 1인 경로.. c) 가중치의 합이 2인 경로.. -> 가중치의 합이 0인 경로부터 시작하여 , +1씩하여 1인 경로를 탐색한다. 3. 데큐(Deque)로부터 removeFirst()를 한 노드가 target 노드이면 알고리즘 종료! 아래의 문제를 기준으로, 그림을 그려보았다. https://www.acmicpc.n.. 더보기 다익스트라 알고리즘 다익스트라 알고리즘은 최소 비용 신장 트리(MST)와는 달리 방향 그래프만 아니라, [무방향] 그래프에서도 적용이 가능하다. import java.io.*; import java.util.*; public class Main { private static final int INF = 10000; //다익스트라 최단 경로 // 1. 하나의 시작 정점을 두고, 다른 모든 정점을 목적지로 하여 최단 경로를 구하는 것이다 // -> 모든 정점을 시작점으로 두고, 다른 모든 정점까지의 최단 경로는 [플로이드-워샬] 알고리즘으로 구한다. // 2. 가중치가 있는 가중치 그래프를 전제로 한다.(가중치가 없으면, BFS로 최단 경로 구하면 됨) // -> 시작 노드에서 목적지 노드까지의 가중치의 합이 최소인 경로가 최.. 더보기 이진수를 이용하여 O(log n)으로 거듭 제곱 빠르게 계산하기 일단 코드부터 살펴 보자 def answer(a, b): ret = 1 while b: if b % 2 == 1: ret = ret * a a = a * a b //= 2 return ret ex) 3의 13승을 이진수를 이용하여 구해 보자 13은 2진수로 1101(2)로 변환된다. 즉, 3의 1101(2) 승을 구하는 것이다. 3^1101(2) = ( 0 or 1 ) 3^1 x ( 0 or 1 )3^10(2) x( 0 or 1 ) 3^100(2) x ( 0 or 1 )3^1000(2) ( 지수의 자릿수만큼의 항이 만들어 진다.) 10(2)는 1(2)의 2승이고, 100(2)는 10(2)의 2승, 1000(2)은 100(2)의 2승이다. 4번의 반복을 통해 1101(2)의 각 자릿수\( 0 or 1)를 .. 더보기 조합론(Combination) == 이항 계수(binomial Coefficient) 조합론에서 이항 계수(二項係數, 영어: binomial coefficient)는 이항식을 이항 정리로 전개했을 때 각 항의 계수이며, 주어진 크기의 (순서 없는) 조합의 가짓수이다. https://www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 위 문제와 같이 nCr을 구함에 있어서, n과r이 크기가 매우 큰 경우에는 모듈 연산과 페르마의 소과 거듭 제곱의 분할 정복을 통하여 구할 수가 있다. ( 알고리즘 문제에서 대부분의 경우, 데이터가 매우 큰 경우에 반드시 모듈 연산을 시킨다.. 더보기 Quad Tree - 2D 공간을 트리로 표현 Quad Tree의 특징 1. 재귀적(recursive)으로 2D 공간을 4개의 공간으로 분할(문제에 따라서 꼭 4개가 아닌 n개로 분할할 떄도 있음) 2. 부모 노드는 일반적으로 4개의 자식 노드(분할 횟수에 따라 자식 노드 갯수는 달라짐)를 가지고 있다. Quad Tree의 활용 1. 2D 물체(ex. 게임 캐릭터)의 위치를 빨리 탐색할 때! -> 만약, 게임 속 전체 맵 속에 게임 오브젝트가 100만 개가 있다고 하자. 나의 캐릭터가 맵 속을 이동할 떄마다 실시간으로 그려져야 할 게임 오브젝트를 연산하여 모니터에 렌더링을 해 줘야 한다. 그러나, 100만 개의 게임 오브젝트를 전부 검사하여 렌더링 해줄지의 여부를 결정하게 되면, 매우 느리다. 그래서 나의 캐릭터의 위치가 4분할된 영역 중, 어디에 .. 더보기 Stack과 Queue에 대한 고찰!!! 필자는 Stack과 Queue가 어떠한 상황에서 사용하면 될지에 대한 생각을 해 보았다. Stack -> 어떠한 문제를 풀기 위해서 가장 마지막의 데이터를 먼저 풀고 점진적으로 가장 처음의 데이 터를 풀어야 할 떄! 위와 같은 방법을 사용하기 위해서는, Stack과 같은 Last In First Out과 같은 구조로 Stack에 쌓여 있는 데이터들이 단방향으로 보관되어야 할 필요가 있다. ex) 1. 재귀 함수(리프에서 시작하여 위로 올라오는 재귀함수)를 for문으로 고칠 떄! 2. DFS(); Queue -> 어떠한 문제를 풀기 위해서 장 처음의 데이터를 먼저 풀고 점진적으로 가장 마지막의 데이터를 풀어야 할 떄! 위와 같은 방법을 사용하기 위해서는, Queue와 같은 First In First Out.. 더보기 이전 1 2 다음
