백준 바로가기 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net DP 알고리즘 내 LIS(Longest Increasing Subsequence) 최장 증가 수열 문제입니다. 이해하는데 하루 꼬박걸렸으며 이해까지 도달하는데 효과적인 매체는 아래 유튜브 강의였습니다. 설명이 영어라도 그림만 봐도 이해되는 강의라 보심을 추천드립니다. 링크 출처: https://www.youtube.com/watch?v=CE2b_-XfVDk&list=LL&index=8&t=311s 풀이의 골자는 주어진 수열을 중첩 반복문으로 돌면서 각 index 값을 ..

백준 바로가기 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net DP 알고리즘 이어서 푸는 중입니다. 문제 난이도는 solved.ac 기준 풀었던 것중 최상이었고 Gold5 였습니다. 난이도 체감은 알고리즘 개념보다 수학적 사고능력에 따라 높낮이가 결정되는 것 같습니다. DP를 알고있지만 위 문제는 어떻게 적용해야 할지 감이 오지 않았습니다. DP 알고리즘 문제의 특징인듯 합니다. 따라서 많이 풀어보고 다양한 형태의 문제를 접할수록 유리합니다. 제가 참고한 블로그 입..

백준 바로가기 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net DP(Dynamic Programming) 알고리즘 문제를 풀고 있는데요, DP로 안풀고 저만의 방식으로 풀다가 계속 틀리는 바람에 다른 분들 블로그 보고 DP 방식으로 풀었더니 됩니다. 두 가지 방법으로 풀 수 있는데 반복문 사용은 Bottom-up, 재귀 메서드를 이용한 방법은 Top-down으로 불립니다. 재귀의 경우 DP 배열을 써도 느리니 반복문 사용한 Bottom-up 방법을 추천합니다. 일단 두 가지 방법 모두 다루겠습니다. 문제 들어가기에 앞서 사고의 전환이 필요했습니다. 저는 주어진 N으로부터 3을 최대한 많이 사용해 1로 만드는 로직을 만든 다..