최대공약수(GCD, Greatest Common Divisor) 최대 공약수란 두 자연수의 공통된 약수 중 가장 큰 수 이다. 두 개 이상의 정수의 최대공약수는 해당 정수들의 공통된 약수 중 가장 큰 값이다. 예를 들어, 8과 12의 최대공약수는 4 이다. 최소 공배수(LCM, Least Common Multiple) 최소 공배수란 두 자연수의 공통된 배수 중 가장 작은 수이다. 두 개 이상의 정수의 최소공배수는 주어진 정수들 중에서 모든 정수가 동시에 나누어 떨어지는 가장 작은 정수이다. 예를 들어, 8과 12의 최소공배수는 24이다. 유클리드 알고리즘 유클리드 알고리즘은 두 정수의 최대공약수를 구하는데 사용되는 알고리즘이다. 두 정수 a와 b에 대해서, a를 b로 나눈 나머지를 구하고, 그 나머지를 ..
문제 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 어떻게 풀 것인가? 이 문제는 (0, 0)에서 bfs를 실행하여 문제에서 주어진 그림 1, 2, 3과 같이 바깥공기와 2면 이상이 닿은 치즈들을 녹이면서 몇 초 후에 치즈가 전부 없어지는지 구하는 문제이다. 여기서 유의해야할 점은 바깥공기와 내부의 밀폐된 공기를 구분해야한다. -1 인 곳 : 바깥 공기가 존재하는 곳 0인 곳 : 안쪽 공기가 존재하는 곳 1인 곳 : 치즈가 존재하..
문제 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 어떻게 풀 것인가? 기존의 다익스트라 알고리즘을 사용해도 무방하나, 다만 최단경로가 지나온 노드들을 보여줘야 하고, 그리고 지나온 노드들의 갯수를 보여줘야 한다. 이에 나는 route로 지나온 노들을 담으며, 이후에 while 문을 이용하여 routes에 정답의 경로들을 전부다 담는 로직을 세웠다. 출발 노드 -> 목적 노드까지는 모든 노드를 거치지 않을 수도..
문제 https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 어떻게 풀 것인가? 처음에 보고 조금 당황스러웠다. DP로 풀기에는 너무나도 큰 수 이다. 아마 처음에 단순 DP로 접근했다면 분명히 시간초과가 발생했을 것이다. 그렇다면 이러한 시간초과 부분을 획기적으로 줄일 수 있는 것이 무엇이 있을까? 바로 행렬이다. 사실 백준알고리즘을 많이 풀어본 이들이라면 위와 같은 피보나치 문제들은 많이 봐왔기 때문에 아래와 같은 점화식은 익숙할 것이다. D(n+2) = D(n+1) + D(n) ( D0 = 0, D1 = 1, n >= 0)..
문제 https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 어떻게 풀 것인가? 문제를 읽어보자. 예제 1에서 "mirkovC4nizCC44" 이라는 문자열에 "C4"라는 문자열이 포함되어있으면 모두 없애야 한다. 케이스로 살펴보자. Case 1 : mirkovC4nizCC44 => mirkovnizCC44 Case 2 : mirkovnizCC44 => mirkovnizC4 Case 3 : mirkovnizC4 => mirkovniz(정..
문제 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 어떻게 풀 것인가? 최단경로 다익스트라 알고리즘을 사용하여 풀어야하는 문제이다. 하지만 무조건 V1와 V2를 지나야 한다. 해결법은 간단하다. 시작점 -> V1 까지 가는 최단경로 비용 V1 -> V2 까지 가는 최단경로 비용 V2 -> 목적지 까지 가는 최단경로 비용 즉, 최단경로를 3번 사용하여 위3개의 최단경로 비용의 합을 구하면 된다. 단 ..
문제 https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 어떻게 풀 것인가? 문제를 잘 읽어보자. 웜홀에 들어가면 시간은 뒤로간다. 그말인 즉슨 현재 간선 간의 가중치가 시간이라는 점에서 웜홀의 간선은 음의 가중치를 갖는 것이다. 다시말하면 다익스트라 알고리즘으로는 풀 수가 없다. 그렇다면 문제에서 요구하는 것은 무엇일까? 바로 벨만 - 포드 알고리즘이다. 즉, 현재 문제가 원하는 것은 벨만 포드 알고리즘을 이용하여 음수 사이클이 발생..
문제 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 어떻게 풀 것인가? LIS와 LDS의 혼합 문제였다. 처음에 LIS를 시행이후에 LDS를 시행하면 문제가 원하는 최장 바이토닉 수열의 길이가 나온다. 간단했다. 아래는 LIS 와 LDS의 정리글이다. https://superohinsung.tistory.com/199 [Algorithm] LIS, LDS (최장 증가 부분 수열, 최장 감소 부분 수열) 최장 증가 부분 수열(LIS, Longest Increasi..
