2609번: 최대공약수와 최소공배수

2609번: 최대공약수와 최소공배수사용 언어: C++문제 요약두 수의 최대공약수와 최소공배수를 출력하라!풀이문제는 브론즈 수준이지만, 일단 최대공약수와 최소공배수를 구하는 가장 효율적인 방법을 아는 것은 중요한 법!유클리드 호제법을 통해 최대공약수(GCD)를 구하고, 이를 이용해 최소공배수(LCM)를 구할 수 있다. 유클리드 호제법은 다음과 같다.두 수 a, b의 GCD는 다음 재귀 공식으로 구한다.GCD(a, b) = {a (if b =0) {GCD(b, a%b) otherwise코드로 표현하면 다음과 같다.int gcd(int a, int b){ if(b==0) return a; return gcd(b, a%b);}그리고 LCM는 GCD를 이용해서 ..

1865번: 웜홀

1865번: 웜홀사용 언어: C++문제 요약시간 여행을 매우 좋아하는 백준이는 한 가지 궁금증에 빠졌다. 한 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 돌아왔을 때, 출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는지 없는지 궁금해졌다. 여러분은 백준이를 도와 이런 일이 가능한지 불가능한지 구하는 프로그램을 작성하여라.벨만-포드 설명문제를 읽어보면 간단하게 정리하자면 출발점으로 돌아왔을 때 시간이 역행하는 경로가 있냐 -> 즉, 음수 사이클이 존재하는지 확인하는 문제.벨만-포드 요약1. 단일 출발점 최단 거리 계산 알고리즘2. 음수 간선 포함 가능3. 음수 사이클 탐지 가능구현 흐름1. 거리 배열 초기화vector dist(N+1, 0); // 모든 노드를 시작점처럼..

11403번: 경로 찾기

11403번: 경로 찾기사용 언어: C문제 요약가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i,j)에 대해 i -> j 로 가는 양수의 경로가 있는지 구하는 프로그램을 작성하시오.풀이일단 문제에서 모든 정점에 대해 어떠한(모든) 길로 가는지 알아내라는 문제. 일단 그래프 문제인건 확실하고, 그 중에서 BFS, DFS, Dijkstra, 플로이드 워셜 등을 생각해볼 수 있는데 이런 경우 (모든 -> 모든)을 검사하는 문제는 플로이드 워셜이 적합하다.플로이드 워셜은 모든 정점 쌍에 대한 최단 경로를 구하는게 원래 목적인데, 해당 문제에서는 단순히 경로가 존재하는지로만 쓸 것이다.원리:1. i -> j 로 가는 기존 경로 거리 arr[i][j]2. 중간 노드 k를 거쳐 i -> k -> j 경로를..

17070번: 파이프 옮기기 1

17070번: 파이프 옮기기 1사용 언어: C++문제 요약문제 요약이 어려우므로 문제 확인 요망풀이DP로 테이블을 채우면서 파이프를 옮기면 해당 칸 업데이트.dp[r][c][dir]: 파이프 끝이 (r, c)에 있고, dir 방향일 때의 경우의 수. (dir 0 : 가로, 1 : 세로, 2 : 대각선)예를 들어 시작이 (1,1), (1,2)에 파이프가 하나 있으니까 dp[1][2][0] = 1;로 초기화하는 것.또한, 이 문제는 오른쪽과 아래, or 오른쪽-아래로만 움직이니까 dp[1][2]면 자동으로 (1,1)에 다른 쪽 파이프가 있다고 가정 가능.답#include #include using namespace std;int N;int house[17][17];int dp[17][17][3];int ma..

1326번: 폴짝폴짝

1326번: 폴짝폴짝사용 언어: C++문제 요약개구리가 일렬로 놓여 있는 검다리 사이를 폴짝폴짝 뛰어다니고 있다. 징검다리에는 숫자가 각각 쓰여 있는데, 이 개구리는 매우 특이한 개구리여서 어떤 징검다리에서 점프를 할 때는 그 징검다리에 쓰여 있는 수의 배수만큼 떨어져 있는 곳으로만 갈 수 있다.이 개구리는 a번째 징검다리에서 b번째 징검다리까지 가려고 한다. 이 개구리가 a번째 징검다리에서 시작하여 최소 몇 번 점프를 하여 b번째 징검다리까지 갈 수 있는지를 알아보는 프로그램을 작성하시오. 첫째 줄에 징검다리의 개수 N(1≤N≤10,000)이 주어지고, 이어서 각 징검다리에 쓰여 있는 N개의 정수가 주어진다. 그 다음줄에는 N보다 작거나 같은 자연수 a, b가 주어지는 데, 이는 개구리가 a번 징검다리..

10830번: 행렬 제곱

10830번: 행렬 제곱사용 언어: C++문제 요약크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.첫째 줄에 행렬의 크기 N과 B가 주어진다. (2 ≤ N ≤ 5, 1 ≤ B ≤ 100,000,000,000)둘째 줄부터 N개의 줄에 행렬의 각 원소가 주어진다. 행렬의 각 원소는 1,000보다 작거나 같은 자연수 또는 0이다.첫째 줄부터 N개의 줄에 걸쳐 행렬 A를 B제곱한 결과를 출력한다.풀이행렬 제곱을 단순하게 구현하면 A를 B번 곱할 수 있는데 B는 최대 10^11이므로 불가능하다.그래서 분할 정복 거듭제곱을 적용하면 되는데,B가 짝수 지수일 때A^B = (A^(B/2)) ..

11401번: 이항 계수 3

11401번: 이항 계수 3사용 언어: C++문제 요약자연수 N과 정수 K가 주어질 때, 이항 계수 NCK를 1,000,000,007로 나눈 나머지를 구하는 문제입니다.N은 최대 4,000,000까지 주어질 수 있어, 단순 계산으로는 해결이 어렵고1,000,000,007은 소수(prime number)라는 점이 이 문제의 핵심풀이일단 모듈려 연산은 나눗셈에 대해 분배법칙이 성립하지 않고, 계산 자체도 N이 400만까지 가서 단순 계산은 불가능.그래서 해결 방법이 모듈러 곱셈 역원을 쓰는 건데, 이게 어떤 수 B로 나누는 것은, B의 역원(B^-1)을 곱하는 것과 같다는 거고, 이를 이루기 위해 쓰는 것이 페르마의 소정리. 페르마의 소정리페르마의 소정리는, P가 소수이면, a^(P−1) ≡ 1(modP) ..

1717번: 집합의 표현

1717번: 집합의 표현사용 언어: C++문제 요약초기에 0, 1, 2, ..., n의 원소 각각이 자기 자신만 담은 n+1개의 서로 집합으 ㄹ이룬다. 두 연산을 m번 처리한다.1. 합집합 연산 : o a b -> a 가 속한 집합과 b가 속한 집합을 합친다.2. 동일 집합 질의: 1 a b -> a와 b가 ㅈ같은 집합에 속하면 YES, 아니면 No를 출력. 제한은 n 풀이합집합을 하고 해당 두 수가 같은 집합에 있는지 찾는 최적의 방식은 유니온 파인드다.유니온 파인드의 핵심 연산은 두 가지다.1. find(x)- 원소 x가 속한 집합의 대표(root)를 찾는다int find_parent(vector& parent, int x){ if(parent[x] == x) return x; re..