문제 https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 어떻게 풀 것인가? 처음에 문제를 보았을 때 난처했다. 무엇을 말하고자 하는지 잘 모르겠다는 생각이 들어서, 아래에 알고리즘 분류를 참고하였다. 위상정렬?? 이라고 하는 알고리즘에 대해서 공부하게 되었다. 그래프가 주어졌을때, 노드마다 연결된 간선에 방향이 존재하고, 어떤 특정한 노드를 방문하기 위해서는 해당 노드에 진입 가능 이후에 방문이 가능할때 위상정렬을 사용한다고 한다. 위 문제..
소수(Prime Number) 소수란 보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수다. 예를 들어, 5는 1×5 또는 5×1로 수를 곱한 결과를 적는 유일한 방법이 그 수 자신을 포함하기 때문에 5는 소수이다. 그러나 6은 자신보다 작은 두 숫자의 곱(2×3)이므로 소수가 아닌데, 이렇듯 1보다 큰 자연수 중 소수가 아닌 것은 합성수라고 한다. 1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수로 정의하기도 한다. 에라토스테네스의 체 소수를 빨리 찾을 수 있는 알고리즘이다. 과정 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 자기 자신을 제외한 2의 배수를 모두 지운다. 자기 자신을 제외한 3의 배수를 모두 지운다. 자기 자신을 제외한 5의 배수를 모두 지운다. 자기 자신을 제..
최대공약수(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..
최장 증가 부분 수열(LIS, Longest Increasing Subsequence) 최장 증가 부분 수열(LIS, Longest Increasing Subsequence)은 주어진 수열에서 요소들이 증가하는 순서대로 선택되는 가장 긴 부분 수열을 말한다. 즉, 주어진 수열에서 원래 순서를 유지하면서 순서대로 증가하는 숫자들을 선택하여 만들 수 있는 가 장 긴부분 수열을 찾는 문제이다. 예를 들어 수열 {3, 1, 5, 2, 4}가 주어졌을 때, 이 수열의 최장 증가 부분 수열은 {1, 2, 4}가 된다. 이 부분 수열은 원래 수열의 순서를 유지하면서 각 요소가 증가하는 순서대로 선택되었기 때문에 최장 증가 수열 부분이라고 할 수 있다. 최장 증가 부분 수열은 다이나믹 프로그래밍(DP)와 이분탐색을 이..
동적 계획법(Dynamic Programming) 동적 계획법(Dynamic Programming, DP)란 컴퓨터 프로그래밍 기법 중 하나로, 주로 최적화 문제나 중복되는 부분 문제를 효율적으로 해결하는 데 사용되는 알고리즘 설계 기법이다. 이는 큰 문제를 작은 부분 문제로 쪼개어 해결하는 분할 정복(Divide and Conquer)과 유사하지만, DP는 중복되는 부분 문제들을 한 번만 계산하고 이를 이용하여 전체 문제를 해결한다. 즉,한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘. -> 점화식을 요구하는 이유이기도 하다. DP의 핵심 아이디어는 "작은 문제들의 해를 저장하고 재활용함으로써 전체 문제의 해를 구하는 것"이다. 이를 통해 중복 계산을 피하고 실행 시간을 크게 줄일 수 있습니다..
