새로운 주차가 시작됐다. 계획을 다음과 같이 수립했다.
- 코어 타임(그룹 스터디 타임): 토,월은 컴퓨터 시스템(그 외에는 알고리즘)
- 키워드: 동적 프로그래밍, 그리디 알고리즘
- 컴퓨터 시스템: 3장 프로그램의 기계 수준 표현 (특히 3.4, 3.7, 3.8)
- 공부 타입 및 목표: 개념 코드 위주의 이해, 하 ~ 중 반복 숙달로 문제 작성 가능(그러나 몇몇개념은 문제로 이해)
자리를 전체적으로 옮겼다. 이후 첫번째 문제를 풀어보았고 팀원분들과 함께 코어타임과 코어타임을 어떻게 활용할지 알아보았다.
컴퓨터 시스템은 자신의 담당 범위를 공부하여 코어타임에 공유하기로 했다.
DP의 개념을 공부하고 바로 문제를 풀어보았다. DP는 문제량으로 밀어야 능숙해질 것 같다.
1번 2748 피보나치 수 2
https://www.acmicpc.net/problem/2748
피보나치 수열이며 그전 값을 다시 불러서 계산하는 방식으로 문제를 해결하면됩니다.
import sys
input = sys.stdin.readline
def DP(n):
# N번째 피보나치 수 저장 리스트 공간
dp = [0] * (n + 1)
# 초기값 설정
dp[0] = 0
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n] # N번째 피보나치 수 반환
# 입력 받기
N = int(input().strip())
# 결과 출력
print(DP(N)) 순서는 리스트 공간을 확보, DP 구현, 인풋 순으로 간다.
2번 1904 01타일
https://www.acmicpc.net/problem/1904
맨처음엔 어떤 식으로 반복했는지 몰랐는데, 직접 구해보면 점화식이 보인다. 이문제를 풀기위해선 모듈러 법칙에 따라 각각의 나누기합은 전체 나누기랑 같음을 알아야한다. 또한 if문을 사용하여 예외처리에 신경써야한다.
import sys
input = sys.stdin.readline
def DP(n):
dp = [0] * (n+1)
### 오류가 발생해 해당부분을 추가하여 수정했다.
if n == 1:
return 1
if n == 2:
return 2
###
dp[1] = 1
dp[2] = 2
dp[3] = 3
# DP 사용
for i in range(4,n+1):
dp[i] = ((dp[i-1] + dp[i-2])%15746)
return dp[n]
N = int(input().strip())
print(DP(N))상단에 if문을 쓴이유? 만약, 1,2을 입력할 경우 1은 리스트가 2개여서 계산불가하고 2는 실제 값과 다른 값을 반환한다. (인덱스 에러) 3은 이론상 맞지만, 1이 리스트2개여서 오류가 난다.(n<=일시 에러 발생)
그래서 위의 이유로 dp[0] = 0을 넣어도 오류가 난다.(맨첨엔 이렇게 생각했었다)
3번 9084 동전
https://www.acmicpc.net/problem/9084
이문제는 살펴보니 목표 금액을 기준으로 점화식을 도출해 내면된다. 이건 직접 경우의 수를 계산해보면 점화식을 이끌어내기 수월하다. 동전이 추가될 때마다 증가되는 경우의 수가 일정하다. 헤딩 규칙을 살려서 결론을 도출하면된다.
import sys
input = sys.stdin.readline
def coin_dp(coin, M):
dp = [0] * (M+1)
dp[0] = 1
for coin in coins: # 각 동전에 대해
for i in range(coin, M + 1):
dp[i] += dp[i - coin]
# 해당 수식이 점화식을 말한다. 동전 수가 추가될 때마다 경우의 수가 증가된다.
return dp[M]
T = int(input().strip())
for _ in range(T):
N = int(input().strip())
coins = list(map(int, input().strip().split()))
M = int(input().strip())
print(coin_dp(coins, M))코인을 추가하면 dp[i - coin]만큼의 새로운 방법이 추가된다. 규칙은 다음과 같다.
15:00 ~ 17:00
경기대 교수님의 알고리즘 수업을 듣고 왔다. 아이패드를 참고하면 관련 내용을 알 수 있다.
4번 9251 LCS
https://www.acmicpc.net/problem/9251
LCS(Subsequence)은 부분수열로 문자사이를 건너뛰면서 두 문자의 공통이면서 가장 긴 부분 문자열을 찾으면 됩니다. 만약 ABCDEF와 GBCDFE일 경우 BCDF가 LCS가 됩니다. 참고로 LCS의 마지막 글자인 Subsequence는 건너뛰기가 되고(부분수열) Substring은 건너뛰기가 안됩니다.(이어진 문자만)
LCS관련 문제는 2차원 배열을 만들어서 두 문자를 비교해서 동일하면 표기하는 방식으로 계산함을 알게 되었습니다.
import sys
input = sys.stdin.readline
A = input().strip()
n = len(A) # 6
B = input().strip()
m = len(B) # 6
dp = [[0] * (m + 1) for _ in range(n + 1)] # 7 * 7
for i in range(1, n + 1):
for j in range(1, m + 1):
if A[i - 1] == B[j - 1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
print(dp[n][m])이게 문제 원리는 이해하기 쉬웠는데, 코드 전개가 굉장히 헷갈렸다. 공백을 넣어서 비교하는데에 예외사항이 생기지 않게 해야되고 함수에 -1과 +1을 번갈아 써서 굉장히 헷갈렸다. 그런데 A[]를 각 알파벳을 가르키는 숫자라고 생각하니 이해하기 한결 쉬웠다.
21:00 ~ 23:00
팀원분들과 코어 타임을 가졌다. DP의 상향식과 하향식 방법에 대해서 학습하고, LCS 관련해서 학습을 했다. 다같이 이해하면서 되짚어보니 이해가 쉽게 되었다. 끝으로 동전 관련된 문제에 대해 풀어 나가는 방식에 대해 설명했다.
최근에 LCS를 하는 김에 LCS 관련 자료를 정리해보겠다. 그리고 오늘은 운동을 가야겠다.
다음 포스팅을 참고하세요!
