(6월 과제)
2024.05.19 - [프로그래밍/문제 풀이] - 백준(BaekJoon) 16434번 풀이 - [AP 프로그래밍 - 6월 과제]
백준(BaekJoon) 16434번 풀이 - [AP 프로그래밍 - 6월 과제]
(5월 과제) 2024.03.30 - [프로그래밍/문제 풀이] - 백준(BaekJoon) 1167번 풀이 - [AP 프로그래밍 - 5월 과제] 백준(BaekJoon) 1167번 풀이 - [AP 프로그래밍 - 5월 과제](4월 과제) 2024.04.01 - [프로그래밍/문제 풀이
olzl07.tistory.com
계획 세우기
7월의 과제는 나만의 문제를 설계해보는 것입니다. 어떤 알고리즘을 활용하면 좋을지 고민해보던 중, LIS(최장증가부분수열)라는 것을 알게 되었고, 이를 활용한 문제를 만들어보기로 하였습니다.
문제 설계
문제 상황과 입출력, 간단한 입출력 예시, 도움말을 설정해보도록 하겠습니다. 코드업이나 백준 등을 풀며 느낀 바로는 문제는 상황이 최대한 (자극적)재미있어야 하기 때문에 은은히 웃길만한 문제 상황을 제작해보겠습니다. (문제의 양식은 코드업을 참고하였습니다.)
2218 : 역시 언매 시간에 푸는 정석이 최고야!
시간 제한 : 1 Sec 메모리 제한 : 128 MB
제출 : 12 해결 : 3
| 문제 설명 |
| 수학을 정말 잘하는 정석이는 언어와 매체 시간에 수학 문제집을 푼다. 정석이에게는 수학 문제는 반드시 개념부터 심화까지 차근차근 단계를 올려가며 풀어야한다는 신념이 있다. 수업도 안 듣고 수학 문제나 푸는 주제에 신념이 매우 확고한 정석이는 언어와 매체 시간에도 이 신념을 가지고 문제를 풀려고 한다. 그러나 주어진 언어와 매체 시간은 단 50분, 그 동안 문제집의 모든 문제를 풀기에는 너무 시간이 촉박하기에 정석이는 각 페이지의 문제들의 난이도를 나열한 뒤 그 부분수열 중에서 가장 길이가 긴 증가수열(LIS)의 문제만 풀기로 했다. 이때 정석이가 각 난이도 별로 풀어야 하는 문제 수를 구하시오. 단, 정석이는 수학을 굉장히 잘하기 때문에 어떤 페이지에 LIS가 존재하지 않는다면 해당 페이지에서는 가장 난이도가 높은 문제를 푼다. 또, 어떤 페이지의 LIS가 여러개라면 난이도들의 합이 가장 큰, 즉 LIS 내의 요소들을 다 더했을 때 가장 큰 LIS의 문제들을 푼다. ex) 난이도 : 1 2 7 5 4 5 6 9 4 2 라면 LIS인 1 2 4 5 6 9 총 6문제를 푸는 것이다. |
| 입력 |
| 첫 줄에 정수 n(페이지의 수)이 주어진다. (1<= N<=1000) 이후 n줄 동안 각 페이지에 있는 모든 문제의 난이도가 띄어쓰기로 구분되어 주어진다. 이때 문제의 수는 50개 이하이며 난이도는 20 이하의 자연수이다. |
| 출력 |
| 1에서 20까지 오름차순으로 난이도와 해당 난이도에서 풀어야 하는 문제 수를 띄어쓰기로 구분해 줄 별로 출력한다. |
| 입력 예시 |
| 3 1 6 5 8 17 6 5 9 10 12 18 19 6 20 4 5 6 11 8 6 19 5 14 16 19 17 15 6 |
| 출력 예시 |
| 1 1 2 0 3 0 4 1 5 1 6 2 7 0 8 1 9 1 10 1 11 1 12 1 13 0 14 1 15 0 16 1 17 0 18 1 19 2 20 1 |
| 도움말 |
| LIS를 풀기 위해서는 DP(Dynamic Programming : 동적 계획법)을 사용해야 한다. 그리고 이 문제에서는 길이가 같다면 합이 최대가 되는 LIS를 택해야 하므로 추가적인 작업이 필요하다. |
문제 풀이 전략
문제를 간략히 요약해보자면 N페이지에 걸쳐 50개 이하의 문제 수의 난이도가 입력되면 (난이도는 20 이하 자연수) 그 난이도들의 수열 중 합이 최대인 LIS를 찾고 각각의 난이도 별로 몇 문제를 풀어야하는지 출력하는 문제인 것 같습니다.
이제 문제 풀이 전략을 세워보겠습니다. 만약 Brute Force로 이 문제를 풀게 된다면 m개의 요소가 있는 수열에서 모든 부분수열을 검사하는 경우의 수는 $2^m$개이고, 이를 총 $n$번 반복해야하므로 최악의 경우의 수는 $O(n\times m^2)$입니다. n = 최대 1000, m = 최대 50이므로 이때의 연산 횟수는 약 $1.13 \times 10^{18}$회입니다. 컴퓨터가 1초에 약 1억번의 연산을 한다고 가정하면 최악의 경우 이 문제를 풀기 위한 시간은 약 358년입니다.(못 푼다) 따라서 저는 dp를 이용해 이 문제를 풀것입니다. dp를 활용해 LIS를 찾게 되면 기본적으로 $O(m^2)$의 시간복잡도를 가집니다. 또, LIS를 찾는 것을 $n$번 반복해야하므로 시간복잡도는 $O(n\times m^2)$입니다. n과 m을 대입해보면 총 250만 번 정도의 연산 횟수로 1초 안에 충분히 해결됨을 알 수 있습니다.
먼저, 1로 초기화되어있는 dp 배열과 -1로 초기화되어있는 prev 배열을 만듭니다. dp[i]에는 i번째 요소가 마지막인 LIS의 길이를 저장할것이고, prev[i]에는 i번째 요소가 포함된 LIS에서 i번째 요소 앞에 있는 요소의 인덱스를 저장할 것입니다. 이후 i번째 요소는 n번, j번째 요소는 i번 반복하는 반복문을 통해 LIS를 찾을 것입니다.
만약 i번째 요소가 j번째 요소보다 크다면, 즉 어떤 난이도가 그보다 앞에 있는 난이도보다 크다면 LIS의 길이를 갱신하여야 합니다. 그리고 dp[i]가 dp[j]+1보다 작다면, 즉 i번째 요소가 끝인 LIS의 길이가 더 길다면 단순히 LIS의 길이를 갱신합니다. 혹은 dp[i]가 dp[j]+1과 같다면, 즉 i번째 요소가 끝인 LIS와 j번째 요소가 끝인 LIS의 길이가 같다면 둘 중 합이 더 큰 LIS를 택하여 갱신합니다.
이후 dp 배열의 index가 가장 큰 요소를 찾아 해당 수열을 거꾸로 올라가며 풀어야 할 문제에 추가한 뒤, 이를 출력하면 됩니다.
알고리즘 설명
DP(Dynamic Programming, 동적 프로그래밍)
- DP란?
DP는 복잡한 문제를 간단한 여러 개의 하위 문제로 나누어 푸는 방법입니다. 각 하위 문제의 답을 배열에 저장해두었다가, 동일한 하위 문제가 다시 발생하면 저장해둔 답을 불러와 사용하는 방식으로 계산 시간을 절약할 수 있습니다.
작동방식만 생각해보면 재귀를 사용하는 것과 별반 다르지 않아보이지만 큰 차이점은 재귀를 단순히 사용 시 동일한 문제들이 여러 번 반복되어 비효율적인 계산이 이루어질 수 있다는 접입니다. 피보나치 수열을 구하는 과정을 예로 들어보겠습니다. 피보나치 수열을 구하는 함수를 재귀로 구성하면 f(n) = f(n-1) + f(n-2)로 쉽게 표현할 수 있습니다. 그런데 f(n-1)에서도 또 f(n-2) + f(n-3)을 호출할 것이고 f(n-2)에서도 f(n-3) + f(n-4)을 호출하게 되면 n이 커질수록 호출되는 함수의 횟수는 기하급수적으로 커질 것입니다. 아래 그림과 같이 말이죠.
이렇게 피보나치 수열을 구하게 된다면 n = 100일 때 호출되는 함수의 횟수는 무려 7해(...)번입니다. 그러나 dp를 이용해 f(1), f(2), f(3) ... 값들을 모두 배열에 저장해둔다면 후에 동일한 문제가 발생해도 배열에서 값을 꺼내오기만 하면 되기 때문에 훨씬 빠르게 피보나치 수열을 구할 수 있습니다.
- DP의 사용조건
DP가 적용되기 위해서는 다음 2가지 조건을 만족해야 합니다.
1) Overlapping Subproblems (겹치는 부분 문제)
2) Optimal Substructure (최적 부분 구조)
1) Overlapping Subproblems
DP는 문제를 나누고 나눠진 문제의 결과 값을 재활용해서 전체 답을 구하기 때문에 동일한 작은 문제들이 반복해서 나타나는 경우에만 사용이 가능합니다.
2) Optimal Substructure (최적 부분 구조)
부분 문제의 최적 결과 값을 사용해 최적 결과를 낼 수 있는 경우에만 DP를 사용할 수 있습니다. 따라서 특정 문제의 정답은 문제의 크기에 상관없이 항상 동일하다는 특징도 있습니다.
문제 풀이 과정
이제 문제를 풀어보도록 하겠습니다. 먼저, 합이 최대인 LIS를 찾는 함수를 정의해준 뒤, 각종 배열들을 초기화해주어야 합니다. 앞서 설명했듯이 dp 배열은 1로, prev 배열은 -1로 초기화했고, i번째 요소가 끝인 LIS의 합을 저장해두는 배열은 처음 들어온 난이도의 수열을 복사하여 초기화하였습니다. 그 이유는 가장 길이가 작은 LIS의 합은 그 요소 그 자체이기 때문입니다.
def max_LIS(nums):
n = len(nums)
dp = [1] * n
max_sum = nums.copy()
prev = [-1] * n
이제 dp를 구현해야 합니다. 먼저, 이중 반복문을 구성해줘야 합니다. 어떤 요소보다 앞에 있는 모든 요소에 대해 검사를 해야하기 때문에 i번째 요소는 n번, j번째 요소는 i번 반복할 것입니다. 이후 if문을 통해 LIS를 갱신하는 코드를 짤 것입니다.
LIS를 갱신하는 전제 조건은 i번째 난이도가 j번째 난이도보다 큰 경우입니다. 이후 dp[i]가 dp[j]+1보다 크다면, 즉 i번째 요소가 마지막인 LIS의 길이가 j번째 요소가 마지막인 LIS에 결합한 길이보다 크다면 LIS, 해당 LIS의 합, 그 이전 요소를 갱신해주겠습니다.
for i in range(n) :
for j in range(i) :
if nums[i] > nums[j] :
if dp[i] < dp[j]+1 : # LIS의 길이 갱신
dp[i] = dp[j] + 1
max_sum[i] = max_sum[j] + nums[i]
prev[i] = j
혹은 dp[i]와 dp[j]+1이 같다면, 즉 i번째 요소가 마지막인 LIS의 길이가 j번째 요소가 마지막인 LIS에 결합한 길이와 같으면 합이 더 큰 LIS로 갱신하도록 하였습니다.
elif dp[i] == dp[j]+1 and max_sum[i] < max_sum[j]+nums[i] : # 동일 길이의 LIS에선 최대합으로 갱신
max_sum[i] = max_sum[j] + nums[i]
prev[i] = j
이후 i번째 요소가 마지막인 LIS 중 길이가 가장 긴 것을 찾고, 그 중 최대합이 되는 배열을 찾아주었습니다. 이후 해당 LIS의 요소들을 역으로 따라가 해당 LIS에 있는 난이도에 1씩 더하여 난이도 별 풀어야 할 총 문제 수를 구하였습니다.
max_len = max(dp)
same_len_LIS = [i for i, val in enumerate(dp) if val == max_len]
max_sum_LIS = [max_sum[i] for i in same_len_LIS]
LIS_end_index = same_len_LIS[max_sum_LIS.index(max(max_sum_LIS))]
LIS = []
while LIS_end_index != -1 :
LIS.append(nums[LIS_end_index])
LIS_end_index = prev[LIS_end_index]
LIS.reverse()
return LIS
def solve(n, pages) :
difficulty_count = {i: 0 for i in range(1, 21)}
for page in pages:
LIS = max_LIS(page)
for difficulty in LIS:
difficulty_count[difficulty] += 1
return difficulty_count
마지막으로 입력을 받은 뒤 각 난이도별 문제 수를 출력하는 코드까지 짜주었습니다.
n = int(input())
pages = []
for _ in range(n):
pages.append(list(map(int, input().split())))
difficulty_count = solve(n, pages)
for i in range(1, 21):
print(f'{i} {difficulty_count[i]}')
다음은 전체 코드입니다.
def max_LIS(nums):
n = len(nums)
dp = [1] * n
max_sum = nums.copy()
prev = [-1] * n
for i in range(n) :
for j in range(i) :
if nums[i] > nums[j] :
if dp[i] < dp[j]+1 : # LIS의 길이 갱신
dp[i] = dp[j] + 1
max_sum[i] = max_sum[j] + nums[i]
prev[i] = j
elif dp[i] == dp[j]+1 and max_sum[i] < max_sum[j]+nums[i] : # 동일 길이의 LIS에선 최대합으로 갱신
max_sum[i] = max_sum[j] + nums[i]
prev[i] = j
max_len = max(dp)
same_len_LIS = [i for i, val in enumerate(dp) if val == max_len]
max_sum_LIS = [max_sum[i] for i in same_len_LIS]
LIS_end_index = same_len_LIS[max_sum_LIS.index(max(max_sum_LIS))]
LIS = []
while LIS_end_index != -1 :
LIS.append(nums[LIS_end_index])
LIS_end_index = prev[LIS_end_index]
LIS.reverse()
return LIS
def solve(n, pages) :
difficulty_count = {i: 0 for i in range(1, 21)}
for page in pages:
LIS = max_LIS(page)
for difficulty in LIS:
difficulty_count[difficulty] += 1
return difficulty_count
n = int(input())
pages = []
for _ in range(n):
pages.append(list(map(int, input().split())))
difficulty_count = solve(n, pages)
for i in range(1, 21):
print(f'{i} {difficulty_count[i]}')시행착오
처음에 LIS를 선택하기로 결정하고 문제를 다 만들었으나 어떤 리스트에서 LIS는 여러 개가 나올 수 있다는 치명적인 단점을 발견하는 문제가 있었습니다. 이를 해결하기 위해 수많은 방법들을 고민해보다가 결국 포기하고 다른 알고리즘을 이용할까 생각해보았는데, 친구들과 시행착오를 해결하기 위해 이야기해보고, 스스로도 많은 생각을 해보며 고민한 덕에 합이 최대가 되는 LIS를 찾는 방향으로 문제를 수정하며 이 문제를 해결할 수 있었고, 문제의 완성도 등도 더욱 증가하는 효과를 얻을 수 있었던 것 같습니다.
느낀 점
처음에 나만의 알고리즘 문제를 만들어보라고 했을 때는 어떤 문제를 만들어야할지 감이 잡히지 않아 고민이 많이 되었습니다. 여러 알고리즘들 중 LIS, 매내쳐 알고리즘, 벨만포드 알고리즘, 오일러 회로 등을 고민해봤는데 결국 처음에 고른 LIS를 결정하게 되었다.
이렇게 알고리즘 문제 개발이라는 활동을 해보며 내가 평소에 잘 겪지 못한 여러 알고리즘들에 대해 들어볼 수 있었고, 몇몇 알고리즘은 작동 방식 등에 대해서도 조금이나마 공부해볼 수 있었던 것 같다. 특히, LIS를 고르는 과정에서 발생한 문제를 해결하기 위해 고민하는 시간 속에서 DP에 대한 이해도를 더욱 높일 수 있었던 것 같고, 나 자신의 사고력이나 창의성도 증대되는 듯한 느낌을 받을 수 있었던 것 같다.
앞으로도 여러 알고리즘에 관심을 가지고 이들에 대해 공부해보는 것도 좋은 경험이 될 것 같다고 생각하게 되는 계기가 되었으며 코드업이나 백준 등 여러 온라인 코딩 문제 풀이 사이트에서 알고리즘을 활용한 문제들을 자주 풀어봐야겠다고 생각하게 되었다.
드디어 5달 간의 AP 프로그래밍 과제가 끝났습니다!!!!!!!
행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해행복해
'프로그래밍 > 문제 풀이' 카테고리의 다른 글
| 백준(BaekJoon) 16434번 풀이 - [AP 프로그래밍 - 6월 과제] (0) | 2024.06.01 |
|---|---|
| 백준(BaekJoon) 1167번 풀이 - [AP 프로그래밍 - 5월 과제] (1) | 2024.05.01 |
| 백준(BaekJoon) 1918번 풀이 - [AP 프로그래밍 - 4월 과제] (5) | 2024.04.01 |
| 백준(BaekJoon) 17951번 풀이 - [AP 프로그래밍 - 3월 과제] (3) | 2024.03.23 |
