본문 바로가기

DP33

[BAEKJOON]2096 내려가기 문제 요약 알고리즘 분류: 동적계획법, 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문제는 구현하는 능력보다 아이디어를 요구하기 때문에 점화식을 짜는 방법만 알면 쉽게.. 2023. 1. 26.
[BAEKJOON] 9465 스티커 문제 요약 알고리즘 분류: 동적계획법, dp 난이도: Silver1 문제내용: 스티커가 2 × n개가 있다. 하지만 하나 자르면 상하좌우 사용을 못한다. 사용할수 있는 스티커중 가중치 최대값을 구해라. 사이트: https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 문제풀이 이번 문제는 테스트 개수 T를 주고 길이가 최대 100,000이다. 브루드포스 같은 알고리즘으로 풀면 시간초과가 나서 가장 좋은 방법은 동적계획법으로 해결하는 방법이다... 2022. 12. 14.
[알고리즘 이론] 동적계획법(Dynamic Programming, DP) 이론 이번에 볼 알고리즘은 동적계획법(Dynamic Programming)이다. 이 알고리즘은 줄어서 dp라고 많이 불리고 코딩테스트에도 자주 나오는 유형이라서 무조건 알아야 되는 알고즘이다. 동적계획법 알고리즘은 복잡하고 여러개의 연산이 있는데.. 작은 단위를 연산을 한다음 반복되거나 중복 되는 연산은 최소화 해서 풀어 나가는 알고리즘이다. 동적계획법은 시간 복잡도상에서 최적으로 나타낼수있는 강력한 알고리즘이지만 완벽한 알고리즘이라고 할수는 없다. dp로 해결하는 이유는 메모리 절약과 시간복잡도의 최적화로 되어 있지만 문제 푸는데는 어느정도 한계가 있고 이론보다는 접근 방법이나 아이디어가 더 많이 요구되기도 한다. 자세한 설명은 아래 사이트에서 찾아 보면된다. https://ko.wikipedia.or.. 2022. 12. 14.
[BAEKJOON] 11054 가장 긴 바이토닉 부분 수열 문제 요악 알고리즘 분류: 동적 계획법 난이도: 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.. 2022. 11. 7.
[BAEKJOON] 2565 전깃줄 문제 요악 알고리즘 분류: 동적 계획법 난이도: Gold5 문제 요약 전봇대 A, B 사이에 전기줄이 여러개 있다. 교차가 되는 선이 몇개 있는데 최소 몇개의 선을 잘라야 교차 되는 선이 없는기 구해라 사이트 주소: https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 문제 풀이 이번 문제는 동적계획법인데 그 중 LIS 최장 증가하는 수열을 구하는 문제이다. LIS 관한 설명은 아래의 사이트에서 확인 하면 된다. https://jih3508.tistory... 2022. 11. 3.
[알고리즘 이론] LIS(Longest Increasing Subsequence) 최장 증가 부분 수열 이론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, .. 2022. 11. 2.

티스토리툴바