https://www.acmicpc.net/problem/11053

 

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

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

www.acmicpc.net

문제 해결을 과정

이 문제의 경우 기존에 비슷한 문제를 포스팅 한게 있어서 그것으로 대체 하도록 하겠습니다.

https://bgspro.tistory.com/33?category=981927 

 

가장 긴 증가하는 부분 수열 - Longest Increasing Subsequence (Python)

개념 가장 긴 증가하는 부분 수열 다시 말하면 LIS라고도 하는 이것은 다이나믹 프로그래밍 기법 중에 하나입니다. 말 그대로 어떤 수열이 주어졌을 때 해당하는 수열에서 오름차순 혹은 내림차

bgspro.tistory.com

 

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 1912번: 연속합(Python)  (0) 2022.01.25
백준 알고리즘 1149번: RGB거리(Python)  (0) 2022.01.24
백준 알고리즘 2579번: 계단 오르기(Python)  (0) 2022.01.19
백준 알고리즘 1003번: 피보나치 함수(Python)  (0) 2022.01.19
백준 알고리즘 7569번: 토마토(Python)  (0) 2022.01.15

https://www.acmicpc.net/problem/18353

 

18353번: 병사 배치하기

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다.

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 가장 긴 증가하는 부분 수열  알고리즘을 알고 있다면 쉽게 해결할 수 있는 문제입니다. 해당 알고리즘에 대해서는 포스팅을 해 놓았습니다. 링크는 다음과 같습니다. https://bgspro.tistory.com/33?category=981927

 

가장 긴 증가하는 부분 수열 - Longest Increasing Subsequence (Python)

개념 가장 긴 증가하는 부분 수열 다시 말하면 LIS라고도 하는 이것은 다이나믹 프로그래밍 기법 중에 하나입니다. 말 그대로 어떤 수열이 주어졌을 때 해당하는 수열에서 오름차순 혹은 내림차

bgspro.tistory.com

먼저 문제의 경우 내림차순으로 배치를 하고자 한다고 합니다. 그러나 가장 긴 증가하는 부분 수열의 경우 오름차순에 대해서 하는 경우가 좀 더 일반적입니다. 따라서 입력받은 리스트를 reverse 함수를 이용해서 역순으로 바꾼 후 LIS 알고리즘을 사용하면 됩니다.

문제 해결을 위한 팁

LIS 알고리즘을 사용할 때 이중 for문을 통해 해결하는데 바깥 for문은 1번째 원소부터 n번째 원소까지, 안쪽 for문은 0번째 원소부터 바깥 for문의 인덱스까지 조회하는 방식으로 해결합니다.

소스코드

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
n = int(input())
data = [0]
ans = [0]*(2+n)
for i in range(1, n+1):
  t, p = map(int, input().split())
  data.append((i, t, p))
 
for i in range(1, n+1):
  day, t, p = data[i]
  if day + t <= n+1:
    ans[i] += p
    for j in range(day+t, n+1):
      ans[j] = max(ans[day], ans[j])
 
print(max(ans))
 
 cs

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 1715: 카드 정렬하기 (Python)  (0) 2021.01.11
백준 알고리즘 2437: 저울 (Python)  (0) 2021.01.03
백준 알고리즘 14501: 퇴사 (Python)  (1) 2020.12.19
백준 알고리즘 1932: 정수 삼각(Python)  (0) 2020.12.18
백준 알고리즘 2110: 공유기 설치 (Python)  (0) 2020.12.18
개념

가장 긴 증가하는 부분 수열 다시 말하면 LIS라고도 하는 이것은 다이나믹 프로그래밍 기법 중에 하나입니다. 말 그대로 어떤 수열이 주어졌을 때 해당하는 수열에서 오름차순 혹은 내림차순으로 가장 긴 증가하는 부분의 숫자가 몇 개가 존재하는지를 카운트하는 알고리즘입니다. 예시와 함께 알아보겠습니다.

 

array = [10, 20, 10, 30, 20, 50]일때 가장 긴 증가하는 부분의 숫자를 출력하시오 라는 문제가 있다고 가정하면 10, 20, 30, 50 즉 4가 정답입니다. 이중 for문이 있다면 쉽게 해결할 수 있습니다. array의 길이만큼의 리스트 dp를 1로 초기화한 후 이중 for문으로 조회하면서 해당하는 값에 1을 더한 값과 원래 값의 max값을 넣어주면 되는 것입니다.

소스코드는 다음과 같습니다.

소스코드
1
2
3
4
5
6
7
8
9
10
11
arr = [10, 20, 10, 30, 20, 50]
n = len(arr)
dp = [1] * n
 
for i in range(1, n):
  for j in range(i):
    if arr[j] < arr[i]:
      dp[i] = max(dp[i], dp[j]+ 1)
 
print(dp)
print(max(dp))
cs

'알고리즘 > 알고리즘 이론' 카테고리의 다른 글

편집거리 알고리즘 (Python)  (0) 2020.12.22
에라토스테네스의 체를 이용한 소수 판별 (Python)  (0) 2020.12.21
이진탐색 (Python)  (0) 2020.12.16
bisect 라이브러리를 이용한 손쉬운 이진탐색 (Python)  (0) 2020.12.15
BFS 너비 우선탐색 (Python)  (0) 2020.12.03

+ Recent posts

티스토리툴바