코딩공부66 (c++) BOJ 11444번: 피보나치 수 6 https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 개요 백준 10830번: 행렬 제곱 문제를 응용해서 푸는 문제이다. 코드 자체도 비슷하고, 분할 정복 방법도 똑같은 문제이기에 한 번 볼 필요가 있다. 먼저 피보나치와 행렬 간에 어떤 유사점이 있는지 살펴보면 $$ \begin{pmatrix} 0 & 1 \\ 1 & 1 \\ \end{pmatrix} ^{1} = \begin{pmatrix} F_{n-1} & F_{n} \\ F_{n} & F_{n+1} \\ \end{pmatrix} ^{n} $$ 이러한 관계를 가지고 있.. 2024. 1. 12. (c++) BOJ 10830번: 행렬 제곱 https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 분할 정복 1부터 n까지의 합을 재귀를 이용하면 n번 연산을 하게 된다. 여기서 n을 2로 나누어 $$ sum() = 1+2+..+n $$ $$ =(1+2+...+\frac{n}{2}) + ((\frac{n}{2}+1)+...+(\frac{n}{2}+\frac{n}{2}) $$ $$ =( \frac{n}{2} \times \frac{n}{2} + sum( \frac{n}{2} ) && $$ sum(n)=2 \t.. 2024. 1. 11. (c++) 플로이드-워셜 알고리즘 1956번: 운동 https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 문제 해결 모든 정점들에서 자기 자신으로 돌아오는 최단 거리이기에 플로이드-워셜 알고리즘을 사용해야 한다는 것을 알아챘을 것이다. 원래 플로이드-워셜 알고리즘은 자기 자신의 거리를 0으로 초기화시키고 시작하는데 자기 자신으로 돌아오는 거리를 알려면 모두 INF로 초기화해주게 된다면 자기 자신으로 돌아가는 거리 또한 계산에 포함되게 된다. 그렇다면 그중에서 최소를 .. 2024. 1. 10. (c++) 벨만-포드 알고리즘 11657번: 타임머신 https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 벨만-포드 알고리즘 앞선 다익스트라 알고리즘은 기본적으로 음수의 가중치가 없다는 것을 가정한다. 음수 값으로 나오는 사이클을 만난다면 사이클을 돌 때마다 최솟값을 갱신하기 때문이다. 이번에 볼 알고리즘은 위 경우를 해결하고, 최단 경로도 도출할 수 있다. 벨만-포드 알고리즘은 최단 거리의 특성을 이용하여 알고리즘을 구성한다. 시작점에서 .. 2024. 1. 9. (c++) 플로이드 워셜 알고리즘 11404번: 플로이드 https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 플로이드-워셜 알고리즘 앞서 살펴본 다익스트라 알고리즘은 하나의 시작점에 대해서 최단 경로를 살펴보는 알고리즘이다. 정점 전체에 대해서 최단 경로를 살펴보려면 각 정점마다 다익스트라 알고리즘을 적용해야 할까? 그래서 나왔다! 플로이드-워셜 알고리즘 정점의 개수가 V라고 한다면 |V| x |V| 행렬을 만들고 자기 자신을 0으로 초기화한다. dist[v1][v1] = 0 그 외 나머지는 무한 INF.. 2024. 1. 7. 힙 구조, 우선순위 큐 다익스트라 알고리즘을 공부하다가 학교에선 안 배웠던 우선순위 큐를 사용하여 성능 개선을 한 경우를 많이 사용하길래 저번 학기에 배웠던 힙 구조를 복습해보았다. 힙 구조란? 힙은 트리 구조에서의 완전 이진 트리로 부모 노드의 자식이 최대 2개가 가능하며 모든 노드가 2개의 자식을 가지고 있다면 포화 이진 트리 1개의 자식을 가진 부모 노드나 같은 레벨에 자식이 없는 노드가 존재한다면 완전 이진 트리라고 한다. 힙이 되기 위한 조건은 1. 완전 이진 트리 2. Heap Property : 모든 노드는 값을 갖고, 부모 노드의 값은 자식 노드의 값보다 크거나 같다. 반대로 최소 힙은 가장 작은 노드가 상위에 있는 것이다. c++ 은 STL에 내장되어 있는 priority_queue 를 사용한다. #includ.. 2024. 1. 7. 이전 1 2 3 4 5 6 7 ··· 11 다음
