일지 & 개발

문제 요약 알고리즘 분류: 동적계획법, dp 난이도: Silver1 문제내용: 수의 자리가 오름차순으로 정렬 되어있는 수를 오르막 수이다. 자리수 N개일때 오르막 수 개수를 구해라. 사이트: https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 문제풀이 이번 문제는 10의 1000승 만큼 모든 숫자를 구하는 기에는 무리가 있다. N = int(input()) count = 0 for num in range(0, 1..

문제 요악 알고리즘 분류: 동적 계획법 난이도: Gold5 문제 요약 수열 S가 있다. 수열 S[1] S[N - 1] 만족하는 최장 길이 수열을 구해라 증가 했다가 중간에 감수하는 수열을 구해라 사이트 주소: https://www.acmicpc.net/problem/11054 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 문제 풀이 이번 문제는 동적계획법인데 그 중 LIS 최장 증가하는 수열을 구하는 문제이다. LIS 관한 설명은 아래의 사이트에서 확인 하면 된다. https://jih3508.ti..

이론1. LIS이란? LIS 개념을 이해하기 전에 기본적으로 DP(동적 계획법)또는 이분탐색을 알아야 된다. DP 에 관련 내용은 아래 사이트에 참조하면된다.https://jih3508.tistory.com/89 [알고리즘 이론] 동적계획법(Dynamic Programming, DP)이론 이번에 볼 알고리즘은 동적계획법(Dynamic Programming)이다. 이 알고리즘은 줄어서 dp라고 많이 불리고 코딩테스트에도 자주 나오는 유형이라서 무조건 알아야 되는 알고즘이다. 동적계획법 알jih3508.tistory.com  LIS, 최장 증가 부분 수열은 나열된 배열이나 리스트에서 원소를 몇개 제외하고 오름차순또는 내림차순으로 가징 긴 수열을 말한다 예를 들어 {1, 5, 3, 6, 7, 9, 4, 2, ..