본문 바로가기

dp43

[DP/동적계획법] 백준 11722 가장 긴 감소하는 부분 수열 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net 2. 문제 풀이 가장 길게 감소하는 부분 수열을 찾는 문제입니다. 중간에 이전 원소보다 큰 원소가 나와도, 무시하고 진행할 수 있습니다. 10 30 5 10 25 10 예를 들어, 위 수열은 [30, 25, 10]이 가장 긴 감소수열입니다. 2022.04.12 - [Algorithm] - [DP/동적계획법] 백준 11053 가장 긴 증가하는 .. 2022. 4. 14.
[DP/동적계획법] 백준 11055 가장 큰 증가 부분 수열 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수 www.acmicpc.net 2. 문제 풀이 가장 큰 '증가 부분 수열의 합'을 구하는 문제입니다. 1, 5, 3, 20, 13, 100 예를 들어, 위 수열에서 합이 가장 큰 증가 수열의 합은 1+3+20+100 = 124입니다. 2022.02.12 - [Algorithm] - [Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP) [Algorithm] 메모해두고 불.. 2022. 4. 13.
[DP/동적계획법] 백준 11053 가장 긴 증가하는 부분 수열 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 2. 문제 풀이 가장 긴 증가 수열을 찾는 문제입니다. 단, 중간에 작은 원소가 있어도 무시할 수 있습니다. 10 20 10 30 20 50 예를 들어, 위 수열의 '가장 긴 증가 수열'은 [ 10, 20, 30, 50 ] 입니다. 2022.02.12 - [Algorithm] - [Algorithm] 메모해두고 불러와서 사용하는 동적 프로.. 2022. 4. 12.
[수학/DP] 백준 2407 조합 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 2. 문제 풀이 Comb(n, m)의 값을 구하는 문제입니다. from math import comb n, m = map(int, input().split()) print(comb(n, m)) 단순히 라이브러리를 이용하면, 쉽게 풀이하실 수 있습니다. 다만 직접 구현하고 싶다면, 동적계획법을 이용해야 합니다. 2022.02.12 - [Algorithm] - [Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP) [Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP) [ Contents ] 1. .. 2022. 3. 11.
[DP/동적계획법] 백준 12852 1로 만들기 2 - Python [ Contents ] 1. 문제 (링크 참조) 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 2. 문제 풀이 1로 만드는 최소 연산 횟수와 방법을 출력하는 문제입니다. 2022.02.21 - [Algorithm] - [동적계획법/DP] 백준 1463 1로 만들기 - Python [동적계획법/DP] 백준 1463 1로 만들기 - Python [ Contents ] 1. 문제 (링크 참조) 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 2. 문제 풀이 1) 3으로 나누기 2) 2로 나누기 3) 1을 빼기.. star7sss.tisto.. 2022. 2. 28.
[Algorithm] 플로이드-와샬, 모든 쌍의 최적경로 구하기 모든 쌍의 최단 경로를 '플로이드 - 와샬' 알고리즘으로 구하는 방법을 알아보고, 구현 코드도 살펴보겠습니다. [ Contents ] 1. 모든 쌍의 최단 경로 위 그래프 그림에서 '노드(Node)'는 원으로 된 지역이고, '간선(Edge)'은 각 지역으로 이동할 수 있는 경로입니다. 간선마다 이동거리 혹은 이동시간에 따른 가중치가 부여됩니다. '모든 쌍의 최단 경로'는 말 그대로, 지역 간 최단거리를 구하는 작업입니다. 보통은 A에서 B로 바로 가면 빠르지만, 경유지를 거쳐서 가는 게 더 지름길일 때도 있죠. 이런 경우를 모두 고려해서 계산해야 합니다. 예를 들어, 위 경로에서는 1->3으로 바로 가는 것보다, 2를 경유해서 가는 게 더 빠릅니다. 2. 플로이드 - 와샬(Floyd-Warshall) 알.. 2022. 2. 28.
[동적계획법/DP] 백준 9461 파도반 수열 - Python [ Contents ] 1. 문제 (링크 참조) 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 2. 문제 풀이 정삼각형이 나선을 그리며 변의 길이가 늘어납니다. 늘어나는 변의 길이를 '파도반 수열'이라고 할 때, N번째 수를 구해야 합니다. 1 2 3 4 5 6 7 8 9 10 1 1 1 2 2 3 4 5 7 9 문제에서 주어진 P(1) ~ P(10)을 보면 규칙이 보이지 않지만, 좀 더 나열하면 보입니다. P(6) 이후로 P(i-1) + P(i-5)의 규칙이 나타납니다. 11 12 13 14 15 16 17 1.. 2022. 2. 26.
[동적계획법/DP] 백준 2579 계단 오르기 - Python [ Contents ] 1. 문제 (링크 참조) 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 2. 문제 풀이 1. 한 번에 1계단 또는 2계단씩 오를 수 있다. 2. 연속된 3계단을 밟을 수 없다. 3. 마지막 계단은 반드시 밟아야 한다. 계단마다 획득 가능한 점수가 있고, 위 규칙을 따라 최대 점수를 획득해야 합니다. 2022.02.12 - [Algorithm] - [Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP) [Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP) [ C.. 2022. 2. 22.
[동적계획법/DP] 백준 17626 Four Squares - Python [ Contents ] 1. 문제 (링크 참조) 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 2. 문제 풀이 최소의 제곱수 합으로 N을 구하는 문제입니다. 2022.02.12 - [Algorithm] - [Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP) [Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP) [ Contents ] 1. 동적 프로그래밍(Dynamic Programming, 동적계획법) 동적계획법(Dynamic pro.. 2022. 2. 22.

티스토리툴바