코딩성장스토리

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 이 문제는 다이나믹 프로그래밍으로 푸는 것이다. 라고 생각해서 접근했지만 후...모르겠어서 다른 글을 참고했다.. 풀이는 말그대로 다이나믹 프로그래밍으로 푸는 것이다 두 문자열 ACAYKP CAPCAK 가 있다고 하였을 때, 맨 처음 부분 문자열 A,AC,ACA... 와 C,CA,CAP.. 로 비교해가면서 푸는 것이다. 즉 부분 집합에서 최적해를 찾아가..

https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 이 문제는 실버 3 문제이고 다이나믹 알고리즘을 통해 부는 것이다. 엄청 오랜만에 알고리즘 문제를 보니 순간 머리가 띵햇다... 진짜 엄청 고민한거 같넹... (이제 부터 스프링 공부랑 병행하면서 해야할듯욤..) 일단 사실 피보나치랑 같은 개념이다. 천천히 생각해보자 (뒤에만 타일을 붙인다고 해도 무방) 괜히 앞에다가 붙이고 복잡하게 생각하지말자... 조건 1. 00타일만 붙일 수 있다. 조건 2 , ..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 이 문제는 다이나믹 프로그래밍 문제로 큰문제를 작은 문제로 나누어서 풀면 된다 즉 n짜리 문제를 n-1짜리로 n-2 짜리로 ... 짜리로 나누어서 작은 문제로 푸는 것이다. 이 문제는 세가지 연산이 가능하다 n이 3으로 나누어 떨어질때 3으로 나눈다. 즉 d[n]=d[n/3]+1 n이 2로 나누어 떨어질때 2로 나눈다 d[n]=d[n/2]+1 n에 1을 뺀다 d[n]=d[n-1]-1 즉 이 세가지 중에서 최솟값을 구하면 된다. 이 문제를 풀 때 재채점이 되었고 틀리게 나왔다. 그 이유는 3으로 나누는게 2로 나..

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 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤..