두 번째 뇌

[ Python ] BOJ 단계별 풀어보기 - 동적계획법 1 본문

개발자 지식/Algorithm

[ Python ] BOJ 단계별 풀어보기 - 동적계획법 1

현파랑 2021. 7. 31. 15:03

1003번 문제 피보나치 함수 접근법

 

1003번: 피보나치 함수

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

www.acmicpc.net

피보나치 수에 적용되는 규칙은? 메모이제이션(Memoization)을 활용해봅니다.

 

9184번 문제 신나는 함수 실행 접근법

 

9184번: 신나는 함수 실행

입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다.

www.acmicpc.net

1003번의 응용입니다.

 

1904번 문제 01타일 접근법

 

1904번: 01타일

지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이

www.acmicpc.net

1003번의 응용입니다.

 

9461번 문제 파도반 수열 접근법

 

9461번: 파도반 수열

오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의

www.acmicpc.net

1003번의 응용입니다.

 

1149번 문제 RGB거리 접근법

 

1149번: RGB거리

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나

www.acmicpc.net

1003번의 응용입니다.

 

1932번 문제 정수 삼각형 접근법

 

1932번: 정수 삼각형

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

www.acmicpc.net

1003번의 응용입니다.

 

2579번 문제 계단 오르기 접근법

 

2579번: 계단 오르기

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점

www.acmicpc.net

완전탐색을 이용하여 풀 수도 있지만, 마지막 계단을 반드시 밟는다는 조건에 유의하여 점화식을 세웁니다. 배낭(Knapsack) 알고리즘을 적용하면 쉽게 풀 수 있습니다.

 

1463번 문제 1로 만들기 접근법

 

1463번: 1로 만들기

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

www.acmicpc.net

2579번 계단 오르기와 동일합니다.

 

10844번 문제 쉬운 계단 수 접근법

 

10844번: 쉬운 계단 수

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

www.acmicpc.net

0, 1, 2자릿수를 기준으로 인접한 모든 자릿수가 1인 경우는 몇 개인지 도출하고 각 수들의 특징을 살펴보고 점화식을 세웁니다.

 

2156번 문제 포도주 시식 접근법

 

2156번: 포도주 시식

효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규

www.acmicpc.net

배낭(Knapsack) 알고리즘을 적용하나, 주어진 조건이 연속으로 3잔을 못 마심에 유의하여 점화식을 세웁니다.

 

11053번 문제 가장 긴 증가하는 부분 수열 접근법

 

11053번: 가장 긴 증가하는 부분 수열

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이

www.acmicpc.net

LIS(Longest Increasing Subsequence)를 적용해봅니다.

 

11054번 문제 가장 긴 바이토닉 부분 수열 접근법

 

11054번: 가장 긴 바이토닉 부분 수열

첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)

www.acmicpc.net

11053의 응용입니다.

 

2565번 문제 전깃줄 접근법

 

2565번: 전깃줄

첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는

www.acmicpc.net

11053의 응용입니다. 왜 LIS의 응용이 되는지 분석하고 점화식을 세웁니다.

 

9251번 문제 LCS 접근법

 

9251번: LCS

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

www.acmicpc.net

LCS(Longest Common Subsequence)을 적용해봅니다.

 

1912번 문제 연속합 접근법

 

1912번: 연속합

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

www.acmicpc.net

연속적인 합은 메모이제이션(Memoization), 배낭(Knapsack) 알고리즘, 구현(Implementation) 등 다양한 방법을 활용할 수 있습니다.

 

12865번 문제 평범한 배낭 접근법

 

12865번: 평범한 배낭

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)

www.acmicpc.net

배낭(Knapsack) 알고리즘이나, 연속적이지 않은 가방도 선택 가능하므로 이를 어떻게 풀어 나갈지 생각해봅니다.
저작자표시

'개발자 지식 > Algorithm' 카테고리의 다른 글

[ JS ] 1010번 다리 놓기  (0) 2021.08.26
[ Python ] 1003번 피보나치 함수  (0) 2021.08.01
[ Python ] BOJ 단계별 풀어보기 - 문자열  (0) 2021.07.31
[JS] DFS : 거리 두기 확인하기(2021 카카오 인턴십)  (0) 2021.07.09
[JS] 투 포인터(Two-Pointers) : 연속 부분수열  (0) 2021.07.04
'개발자 지식/Algorithm' Related Articles more
Comments