전공/알고리즘
-
백준 5582(공통 부분 문자열)전공/알고리즘 2020. 11. 16. 15:39
www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net LCS 공통 부분 수열과는 다른 문제이다. subsequence 는 부분 수열로 수열에서 그냥 임의의 갯수를 삭제해서 만들고, substring 은 부분 문자열로 문자열의 처음과, 끝에서 인접한 임의의 갯수를 삭제할 수 있다. 이건 n^2 dp로 구할 수 있는데, 만약에 같으면 그냥 +1을 해주면 된다. 그리고 다른 경우 바로 초기화를 해준다. 모든 계산 가능한 구간에 대해서 알아보는 n^2이다. #..
-
백준 20130 (Metroidvania Extreme)전공/알고리즘 2020. 11. 11. 14:21
www.acmicpc.net/problem/20130 20130번: Metroidvania Extreme 첫 번째 줄에는 지금까지 기록한 좌표의 수 k을 출력한다. 이후 k개의 줄에 걸쳐 기록한 순서대로 방문한 칸의 행 번호와 열 번호를 공백으로 구분하여 출력한다. www.acmicpc.net 이 문제를 풀면서 감탄을 정말 많이 했다. 일단 bfs문제인데, bfs의 성질을 잘 알아야 순간이동이 무슨소리인지 이해가 될거라고 생각한다. 개인적으로 무슨 소리인지 모르겠으면 혼자 깨달을때까지 생각해보는거 추천 이 문제의 핵심은 bfs로 풀 수 있다는 걸 아는 것이라고 생각한다. 그리고 a가 없이 A를 만났을때 어떻게 해야할지 아는것? 생각하면 된다. 그냥 어떻게 자료를 저장하고 후에 처리를 할지 생각해보자 자료..
-
백준 20130 (Metroidvania Extreme)전공/알고리즘 2020. 11. 11. 14:21
www.acmicpc.net/problem/20130 20130번: Metroidvania Extreme 첫 번째 줄에는 지금까지 기록한 좌표의 수 k을 출력한다. 이후 k개의 줄에 걸쳐 기록한 순서대로 방문한 칸의 행 번호와 열 번호를 공백으로 구분하여 출력한다. www.acmicpc.net 이 문제를 풀면서 감탄을 정말 많이 했다. 일단 bfs문제인데, bfs의 성질을 잘 알아야 순간이동이 무슨소리인지 이해가 될거라고 생각한다. 개인적으로 무슨 소리인지 모르겠으면 혼자 깨달을때까지 생각해보는거 추천 이 문제의 핵심은 bfs로 풀 수 있다는 걸 아는 것이라고 생각한다. 그리고 a가 없이 A를 만났을때 어떻게 해야할지 아는것? 생각하면 된다. 그냥 어떻게 자료를 저장하고 후에 처리를 할지 생각해보자 자료..
-
백준 20128(Parity Constraint Shortest Path)전공/알고리즘 2020. 11. 10. 17:09
www.acmicpc.net/problem/20128 20128번: Parity Constraint Shortest Path 첫째 줄부터 N개의 줄에 걸쳐, i번째 줄에 1번 정점에서 i번 정점으로 이동하는 최소의 홀수 경로의 비용과, 최소의 짝수 경로의 비용을 공백으로 구분하여 출력한다. 해당 경로가 존재하지 않는 www.acmicpc.net 1번 정점에서 다른 모든 정점까지 이동하는데, 그 경로의 비용이 짝수인 최소비용, 홀수인 최소비용을 출력하는 문제이다. 우선 다익스트라를 안다면 딱봐도 다익스트라일 수 있겠다라는걸 알 수 있다. 일단 문제가 좋았다 다익스트라를 푼지도 오래되었고, 경로의 값이 짝수이려면 어떻게 해야할지 홀수이려면 어떻게 해야할지 생각하는 과정에서 이해가 많이 는것같은 기분 처음에는..
-
백준 20127(Y-수열)전공/알고리즘 2020. 11. 10. 14:55
www.acmicpc.net/problem/20127 20127번: Y-수열 N개의 정수로 이루어진 수열 a1, ... , aN이 있다. 택희는 해당 수열이 증가수열 혹은 감소수열이 되게 만들고 싶다. 증가수열은 모든 i(1 ≤ i < N)에 대해서 ai ≤ ai+1을 만족하는 수열이고, 감소수열 www.acmicpc.net 음 그냥 봤을때 그리디로 O(N)의 풀이가 생각난다. 일단 말로 표현을 해보자 처음부터 k개의 증가하는 부분수열을 맨뒤에 붙였을때 전체 수열이 증가하는 수열이 되도록 만드는 것이다. 만약에 증가에 대해서 불가능 하려면 증가 감소 증가 감소 이런식으로 증가에서 감소가 되는 지점이 2개 이상이면 불가능 하다. 따라서 우리는 수열이 증가하는지 감소하는지 판단해서 짜면 될것같다. 그렇게 구..
-
백준 13751(Barbells)전공/알고리즘 2020. 10. 26. 14:18
www.acmicpc.net/problem/13751 13751번: Barbells Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. The first line of input contains two integers, b and p (1 ≤ b,p ≤ 14), representing the number of bars and plates. Then, there are b li www.acmicpc.net 알고리즘 처음 시작할때 풀었었는데 계속 시간초과 났던 문제. 지금 보니 너무 쉬운데 그때는 그게 그렇게 안 보였다. 근데 사실은 방금 전까지도 답이..
-
백준 2186(문자판)전공/알고리즘 2020. 10. 25. 17:06
www.acmicpc.net/problem/2186 2186번: 문자판 첫째 줄에 N(1 ≤ N ≤ 100), M(1 ≤ M ≤ 100), K(1 ≤ K ≤ 5)가 주어진다. 다음 N개의 줄에는 M개의 알파벳 대문자가 주어지는데, 이는 N×M 크기의 문자판을 나타낸다. 다음 줄에는 1자 이상 80자 이하의 www.acmicpc.net 좀 전형적인 dp문제인것 같다. 그냥 점화식 자체가 그래프 + dp를 하게되면 top-down으로 기저조건 잘 넣고 [][][]이런식으로 몇번째 몇번째 칸을 몇번째 순서로 들어갈지 이런식으로 코드를 짜면 된다. 여기서 dp[i][j][num] 에는 마지막에서 (i,j)로 돌아왔을때 경우의 수가 저장된다. 설명이 이상한데 그냥 점화식을 쓰면 dp[i][j][num] += 모든..
-
백준 17845(수강 과목)전공/알고리즘 2020. 10. 25. 14:47
www.acmicpc.net/problem/17845 17845번: 수강 과목 첫줄에 서윤이의 최대 공부시간 N (1 ≤ N ≤ 10,000), 과목 수 K (1 ≤ K ≤ 1,000)이 공백을 사이에 두고 주어진다. 이후 K개의 줄에 중요도 I (1 ≤ I ≤ 100,000), 필요한 공부시간 (1 ≤ T ≤ 10,000)이 www.acmicpc.net xkdlaldfjtnl.tistory.com/122?category=903992 위 4190이랑 같은 문제이다. 정해진 범위가 있고, 하나하나 추가하면서 dp에 저장하는 문제. #include #include #include #include using namespace std; #define MAX 1005 int N, K; int dp[100001];..