일지 & 개발

문제 요약 알고리즘 분류: 동적계획법, dp 난이도: Silver1 문제내용: N개가 주어지고 1 부터 N까지의 팩의 개수와 가격이 있다. i번째는 팩개수를 나타내고 팩 개수마다 가격이 붙어 있다. N개 카드를 구입할때 가장 비싸게 구입할수있는 가격을 출력해라. 사이트: https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 문제풀이 이번 문제에는 모든 경우의 수를 구해서 풀기가 힘들다. 모든 경우의 수로 풀라면 재귀호출방식으로 해야 하는데 재귀호출시 시간초..

문제 요약 알고리즘 분류: 동적계획법, 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..

문제 요약 알고리즘 분류: 동적계획법, dp 난이도: Gold5 문제내용: 위에서 내려가는데 조건에 맞게 더하면서 내려가야한다. 0: 0, 1 1: 0, 1, 2 2: 1, 2 맨 밑에 값중 최소값과 최대값을 구해라 사이트: https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 문제풀이 이번 문제는 동적계획법 관련 문제이다. 동적계획법의 자세한 설명은 여기에 확인 해보면 된다. dp문제는 구현하는 능력보다 아이디어를 요구하기 때문에 점화식을 짜는 방법만 알면 쉽게..

문제 요약 알고리즘 분류: 동적계획법, dp 난이도: Silver1 문제내용: 스티커가 2 × n개가 있다. 하지만 하나 자르면 상하좌우 사용을 못한다. 사용할수 있는 스티커중 가중치 최대값을 구해라. 사이트: https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 문제풀이 이번 문제는 테스트 개수 T를 주고 길이가 최대 100,000이다. 브루드포스 같은 알고리즘으로 풀면 시간초과가 나서 가장 좋은 방법은 동적계획법으로 해결하는 방법이다...

이론 이번에 볼 알고리즘은 동적계획법(Dynamic Programming)이다. 이 알고리즘은 줄어서 dp라고 많이 불리고 코딩테스트에도 자주 나오는 유형이라서 무조건 알아야 되는 알고즘이다. 동적계획법 알고리즘은 복잡하고 여러개의 연산이 있는데.. 작은 단위를 연산을 한다음 반복되거나 중복 되는 연산은 최소화 해서 풀어 나가는 알고리즘이다. 동적계획법은 시간 복잡도상에서 최적으로 나타낼수있는 강력한 알고리즘이지만 완벽한 알고리즘이라고 할수는 없다. dp로 해결하는 이유는 메모리 절약과 시간복잡도의 최적화로 되어 있지만 문제 푸는데는 어느정도 한계가 있고 이론보다는 접근 방법이나 아이디어가 더 많이 요구되기도 한다. 자세한 설명은 아래 사이트에서 찾아 보면된다. https://ko.wikipedia.or..

문제 요악 알고리즘 분류: 동적 계획법 난이도: 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..

문제 요악 알고리즘 분류: 동적 계획법 난이도: Gold5 문제 요약 전봇대 A, B 사이에 전기줄이 여러개 있다. 교차가 되는 선이 몇개 있는데 최소 몇개의 선을 잘라야 교차 되는 선이 없는기 구해라 사이트 주소: https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 문제 풀이 이번 문제는 동적계획법인데 그 중 LIS 최장 증가하는 수열을 구하는 문제이다. LIS 관한 설명은 아래의 사이트에서 확인 하면 된다. https://jih3508.tistory...

이론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, ..