준카판다

https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 기본적인 bfs문제이다. 하지만, bfs가 아닌 union, find로도 해결 가능한 문제이다. 이것을 이해하는데 오랜 시간이 걸렸다. 그 방법에 대해서 알아보자. 방법 1. bfs bfs를 100번 돌리면 된다. 근데 딱봐도 비효율적으로 보이지 않는가? 이것을 보완해주는 것이 union, find이다. #include #include int main(void) { int N, M[100][100], R..

https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 기본적인 bfs문제이다. 주어진 값을 bfs하여 최단 거리를 출력하면 되는 문제이다. 이 문제의 특성을 이용하면 보다 효율적인 방법으로 해결할 수 있는 것이 존재하여 그 방법을 소개하려 한다. 솔직히 방법 1과 방법2의 방식이 별 다르지 않다. 방법 1은 T만큼 계속해서 bfs를 돌리는 것이고, 방법 2는 bfs를 한번 진행해, 그 값을 이용해 출력하는 것이다. 방법 1. bfs 진짜 T만큼 bfs..

https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 그냥 전형적인 우선순위 큐 문제이다. 방법이 2가지가 존재해서 그 방법을 소개하려고 글을 작성한다. 방법 1. 우선순위 큐 2개 사용. 방법 2. 우선순위 큐 정렬 기준 변경. 우선순위 큐에 대해 자세히 알고 싶다면 다음 글을 참고하자. https://jhcard.tistory.com/69 [C++] queue 라이브러리 queue는 list자료구조와 매우 유사하다. list..

유클리드 호제법의 확장 개념이다. 우선 유클리드 호제법의 개념을 알고 오자. https://jhcard.tistory.com/200 [알고리즘] 유클리드 호제법 2개의 자연수의 최대공약수를 구하는 알고리즘이다. 일반적으로 최대공약수는 A와 B를 소수들을 전부 구한 뒤, 그 값을 이용하여 최대공약수를 구할 것이다. 이 방식은 특정 A와 B의 값이 커질경 jhcard.tistory.com 이 알고리즘의 결론부터 알아보자. 어떤수 A와 B가 있다면 A*x + B*y = c에서 정수의 해 (x, y)에 대해 알아보는 것이다. 그냥 이거 끝이다. 더 이상 아무것도 없다. x, y의 값이 정수로 만족되는 값이 무엇일까? 그것을 알 수 있는 개념이 이 확장 유클리드이다. 이 개념에 대해 알기 위해서 여러가지 알아야 ..

https://www.acmicpc.net/problem/6064 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net ㅋㅋㅋㅋ 이 문제 쉽게 생각하면 쉽다. 하지만, 이 문제를 어렵게 풀려면 어렵게 풀 수 있다. 2가지 방법으로 해결할 수 있다. 방법 1. 일반적인 유클리드 호제법을 이용한 최대공약수, 최소공배수를 이용한 문제 해결 방법 2. 유클리드 확장을 이용한 중국인의 나머지 정리 사용이다. 방법 2의 경우 중국인의 나머지 정리를 처음 접하여 혼란스럽기도 하였고, 유클리드 확장이라는 새로운 알고리즘을 접하게 되..

2개의 자연수의 최대공약수를 구하는 알고리즘이다. 일반적으로 최대공약수는 A와 B를 소수들을 전부 구한 뒤, 그 값을 이용하여 최대공약수를 구할 것이다. 이 방식은 특정 A와 B의 값이 커질경우 소수를 구하는데 많은 시간이 소요된다. 하지만, 이러한 단점을 유클리드 호제법이 없애준다. 이 알고리즘에 대한 설명을 해보겠다. 자. 이제 이렇게 되는 그 이유를 알아보자. 증명단계이다. 즉, A % B = r이라 하면 r과 B의 최대공약수가 A와 B의 최대공약수와 같다는 것이다. 하지만, r과 B가 서로소가 아니라면 계속해서 이 과정을 반복하여 최대공약수를 얻어내려고 하는것이 목표이다. 즉, 다음과 같은 함수가 만들어지게 된다. int gcd(int a, int b){ return b ? gcd(b, a % b..

https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 전형적인 DP문제이다. 하지만, DP를 조금만 변형하면 더 효율적인 방법으로 구현할 수 있어 그 방법을 소개할려고 한다. dp방식이다. 빨간색이 dp[2][0] 파란색이 dp[2][1] 초록색이 dp[2][2] 이 된다. N = 1일때의 dp의 상태에서 힌트를 주었는데 뒤쪽의 3개의 배열의 의미는 가장 아래에 있는 동물원에 사자가 아예 없는 경우가 [N][0], 왼쪽에 있는 경우가 [N][1], 오른쪽에 있는 경우가 [N][2]가 된다. 이것을 가지고 계산을 해보면, 가장 아래가 아무것도 없는 경우가 N-1의 0, 1, 2를 더한..

https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 문제를 보면 기본적으로 bfs로 해결 가능한 문제이다. 하지만, bfs를 사용하지 않고도 문제를 해결할 방법이 존재한다. 그 방법을 소개하려 한다. 방법 1. bfs 기본적으로 할 줄 안다고 판단하기 때문에 코드만 보여주겠다. #include #include int main(void) { int F, S, G, U, D, R = 0; scanf("%d %d %d %d %d", &F, &S, &G, &U, &D..