컴퓨터하는 kimmessi

https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 문제 해결 알고리즘 전형적인 위상 정렬 알고리즘을 활용한 문제이다. 작업 시간이 있는 것이 좀 다른데, 이것은 계속해서 결괏값을 먼저 해야할 작업이 걸린 시간 + 현재 해야할 작업이 걸리는 시간과 계속 비교해주면서 더 큰 쪽을 결괏값에 대입해준다. 아래의 링크에 위상 정렬 알고리즘에 대한 자세한 설명이 나와있다. https://kimmessi.tistory.com/207 소스 코드 #in..

https://www.acmicpc.net/problem/14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 문제 해결 알고리즘 전형적인 위상 정렬 문제이다. 아래의 링크에 위상 정렬 알고리즘에 대한 자세한 설명이 나와있다. https://kimmessi.tistory.com/207 [알고리즘] 위상 정렬 (Topology Sort) - BFS 위상 정렬이란? 순서가 정해져있는 작업을 차례로 수행하여야할 때 그 순서를 결정해주기 위해 사용하는 알고리즘이다. 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순 ki..

최장 증가 부분 수열 (LIS)이란? 어떤 수열에서 수열의 일부 원소를 골라 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 수열을 최장 증가 부분 수열이라고 한다. 이 최장 증가 부분 수열 알고리즘을 간단하게 구현하는 방법은 DP를 사용하는 것이다. 다이나믹 프로그래밍을 이용한 최장 증가 부분 수열 for(int i=1;i dp[i]) dp[i] = dp[j] + 1; } result = max(result, dp[i]); } 각 수열의 원소까지의 최장 증가 부분 수열의 크기를 dp배열에 입력을 해주는 알고리즘이다. 처음 원소부터 해당 원소까지 for문을 돌리는데 이때, for문에서 돌리는 원소의 크기보다 해당 원소의 크기가 크고 최장 증가 부분 수열의 크기는 ..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 해결 알고리즘 다이나믹 프로그래밍을 이용해 푼 LIS알고리즘 https://kimmessi.tistory.com/191?category=871925 [알고리즘] 최장 증가 부분 수열(LIS) - DP, 이분 탐색, LIS 출력 최장 증가 부분 수열 (LIS)이란? 어떤 수열에서 수열의 일부 원소를 골라 만든 부분 ..

https://www.acmicpc.net/problem/2011 2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net 문제 해결 알고리즘 0만 없으면 참 간단한 문제인데.. 0 때문에 어려웠다. 구현이 빡셌던 문제 우선 글자 수별로 구분해줘야하는데 글자 수가 1일 때, 2일 때, 3이상일 때로 구분해준다 글자 수가 1일 때, 숫자가 0이면 0을 출력해주고, 0이 아니면 1을 배열 값에 넣어준다. 글자 수가 2일 때, if(num == 10 || num == 20) v[1] = 1; else if((11

https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 문제 해결 알고리즘 모든 배열의 값을 돌 때, 배열의 값만큼 오른쪽에 있는 칸과 아래쪽에 있는 칸에 그 배열로 가는 경로의 수를 더해준다. 소스 코드 #include using namespace std; long arr[101][101]; long dp[101][101]; int N; bool isIn(int x, int y){ return 0

https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 문제 해결 알고리즘 다이나믹 프로그래밍 문제 1부터 구하고자하는 값까지 동전의 최솟값을 차례대로 구해준다. 만약 그 값에 해당하는 인덱스가 -1이라면, 그 값에 해당하는 인덱스에서 동전의 값을 뺀 인덱스의 값에서 +1을 해준다. -1이 아니라면 그 인덱스 값과 동전 값을 뺀 인덱스 값에 + 1한 것 둘 중 최솟값을 인덱스 값에 저장한다. (동전의 값을 뺀 인덱스는 0..

https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 문제 해결 알고리즘 점화식 $$dp[i] = dp[i-2] * 3 + dp[i-4] * 2 + \cdots + dp[0] * 2 $$ $i-2$번째랑 곱할 때만 3을 곱해주고 나머지는 2만 곱해준다. 소스 코드 #include using namespace std; int dp[31]; int main(){ int N; cin >> N; dp[0] = 1; dp[2] = 3; for(int i=4;i=0;j-=2){ if(j == i-2) dp[i] += dp[j] * 3; else dp[i] += dp[j]..

https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 문제 해결 알고리즘 홀수 길이일 때와 짝수 길이일 때를 분류한다. 홀수 길이일 때) 1개일 때는 무조건 팰린드롬이다. 그 양쪽이 같으면 팰린드롬이다. 짝수 길이일 때) 2개가 팰린드롬이면 1로 표시해준다. 거기서부터 양쪽이 같으면 팰린드롬이다. 소스 코드 #include #define MAX 2100 using namespace std; int arr[MAX]; int dp[MAX][MAX]; int main(){ cin.tie(NUL..

https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 문제 해결 알고리즘 초반에는 규칙이 안 보이지만 10번째부터의 규칙이 아래와 같다. $$ dp[i] = dp[i-1] + dp[i-5] $$ 이런 식으로 다이나믹 프로그래밍을 해주어서 주어진 자리의 숫자를 출력한다. 소스 코드 #include using namespace std; int main(){ long long arr[101] = {1, 1, 1, 2, 2, 3, 4, 5, 7, 9,}; int..