본문 바로가기

알고리즘(アルゴリズム）/알고리즘 이모저모(アルゴリズムの緒論)

BFS()는 공짜로 최단 경로를 보장하지 않는다(Feat. Predecessor) https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net [그래프] 26. 최단 경로용 BFS 아래와 같은 빈 큐와 그래프가 있다고 가정하자. 여기에 BFS 알고리즘을 사용할 것이다. 각 Node 의 predecessor 는 보기 편하게 표로 나타내겠다. 먼저 시작점 Node를 방문했다고 표시한다. 시작점은 아무데서도 오지 않았다. 그러니 이전 Node가 없는 것이다. predecessor 는 없다고 표시한다. 시작점 Node A 를 큐에 넣는다. 큐에서 가장 앞에 있는 Node를 꺼.. 더보기
Decision Problem https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 위 문제에서 처음으로 결정 문제(Decision Problem)에 대해 접하게 되었다. 결정 문제의 정의는 다음과 같다. 계산 이론에서 결정 문제(decision problem, 판정 문제)란 어떤 형식 체계에서 예-아니오 답이 있는 질문을 말한다. 예를 들어 "두 숫자 x와 y가 있을 때, y는 x로 나누어떨어지는가?" 하는 질문이 있다. 답은 x와 y 값에 따라 '.. 더보기
Parametric Search Algorithm( 백준 1654번 ) https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 개인적으로, 매우 좋은 문제였다. 최적화 문제를 결정 문제로 변화하여 풀 수가 있다니... 1 | 이진 탐색(Binary Search) 이진 탐색은 정렬된 일련의 값들이 주어졌을 때 그 값들 중에서 원하는 값을 찾는 알고리즘이라고 할 수 있습니다. 이진 탐색은 처음에 중간값을 선택하여 그 값과 찾으려는 값을 비교하여 클 경우 선택했던 중간값을 최솟값으로, 작을 경우 중.. 더보기
점화식은 행렬의 거듭 제곱을 이용해서, DP 보다 빠르게 구할 수가 있다 우리는 고등학교 시절, 점화식을 일반항으로 고치는 방법을 공부하였다. 그러나, 이 작업은 매우 기술적이여서 일반항으로의 변환이 그렇게 쉽지가 않다. 그러나, 행렬을 이용을 하면, 일반항을 매우 쉽게, 그리고 매우 빠른 속도로 구할 수가 있다. 위와 같은 점화식이 있다고 하자! 피보나치 수열의 점화식은 아래와 같다. p == q == 1이므로, 위 식을 아래와 같이 변형할 수가 있다. 위 식을 귀납적으로 표현을 하면 위와 같다. 이 식을 이용을 하면, 피보나치 수열의 (n+2) 번째 항을 알 수가 있다. ( 만약, 이 문제를 DP로 풀게 되면, O(십억)의 비용이 들지만, 행렬의 거듭 제곱을 이진수로 구하게 되면, O(log십억)으로 빠르게 구할 수가 있다.) ( 아래 문제 참조 ) https://www... 더보기
행렬의 거듭 제곱( feat. 단위 행렬) 아래 문제에서 우리는 이진수를 사용하여, 거듭 제곱을 시간 복잡도 O(log N)으로 구하였다. https://jbluke.tistory.com/186 백준 11401번 ( 합동식 ) https://www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 우선, jbluke.tistory.com B=1; // R! 구하기 for(ll i = 1; i 더보기
정적 할당 VS 동적 할당 - 메모리 교환 다차원 배열 선언copy^ 포인터와 배열로 2차원[1] 배열을 만들어 보겠습니다. // using pointer // dynamic array #include #include int main(void){ int **p; p = malloc(sizeof(int*) * 10); for(int i = 0; i 더보기
백준 11401번 ( 합동식 ) https://www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 우선, 이 문제와 같이 복잡한 식( N! * [R!(N-R)!] ^ mod-2) % mod )과 같은 경우에는 식을 최소한으로 간결하게 생각할 필 요가 있다. N! * [R!(N-R)!] ^ mod-2) % mod 은 아래와 같이 변형시킬 수가 있다. 1. N! % mod 2.[ R!(N-R)! ^ mod-2] % mod 3. (1 * 2) % mod(최종식) -> 문제는 2의 식이였다. 위 식을 필자는 아무 생각 없이.. 더보기
pre-condition을 고려하며 function 작성하자!!!! 에러가 발생하는 주요 원인 중 하나로서, 자료형과 데이터 범위가 있다. 고로, 함수를 작성할 때 아래의 pre-condition에 주의하여 함수를 작성하면, 에러를 줄일 수가 있다. pre - condition 1. 함수의 매개 변수로 들어 오는 데이터의 자료형이 무엇인지 2. 매개 변수 데이터의 범위를 파악하여 1에서 정한 자료형이 그 범위를 포함하는 지! 3. 함수 내부의 결과값들이 최악의 경우, 데이터 범위가 어디까지 가는 지! 더보기

티스토리툴바