3주차 키워드
다이나믹 프로그래밍, 그리디 알고리즘
DP
사용 조건
1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
다음의 문제들은 알고리즘 바이블 CLRS을 읽다가 상당히 흥미로워서 이렇게 WIL에 남기게 되었다.
개인적으로 DP란 저런게 아닐까 하는 문제들이기에 꼭 풀어보는 걸 추천한다.
1.행렬 곱셈 순서
2차원 dp 테이블을 대각선으로 채워가며 푸는 문제.
처음보면 어떻게 떠올리지 싶은 그런 느낌을 주는데 막상 익숙해지면 느낌이 온다.
import sys
input = sys.stdin.readline
n = int(input())
p = []
for i in range(n):
p.append(list(map(int,input().split())))
dp = [[0] * (n+1) for _ in range(n+1)]
def minimumi(i , j):
global dp
mini = 2 ** 32
for k in range(i, j):
k_cost = (dp[i][k] + dp[k+1][j]) + (p[i-1][0] * p[k-1][1] * p[j-1][1])
if k_cost < mini:
mini = k_cost
return mini
for l in range(1,n): # 길이는 1부터 n-1 까지
for i in range(1,n-l+1):
j = i + l
dp[i][j] = minimumi(i,i+l)
print(dp[1][n])좀 더 쉬운 문제로는 백준에서 팰린드롬 문제가 있다.
밑의 문제 먼저 도전해보시는 걸 추천한다.
10942번. 팰린드롬?
https://www.acmicpc.net/problem/10942
2. 최적 이분 검색 트리(OBST)
DP지만, 생각해내기 참 어려운 문제이다. 이해도 쉽지않다.
책에서 개념 부분은 3번 정도 다시보고 이해한 것 같다.
유튜브에서 손풀이를 자세하게 해주시는 분을 찾았다!
해갈한다면 DP가 무엇인지 확실히 감이 올 것이다.
WEEK REVIEW
1. 알고리즘은 꾸준히!
이렇게 알고리즘 주차가 종료되었다.
물론 당연하게도 알고리즘은 앞으로 남은 시간동안 쭉 열심히 해야한다.
시간이 없어서 못하는 경우는 없다. 가장 중요한 것을 두고 할 시간이 없을 이유는 없으니 말이다.
2. 적응을 경계하자
점점 잡담의 시간, 딴 짓의 시간이 늘어나는 것 같다.
친해지는 사람도 점점 늘고, 적응도 되니 마음의 여유가 생기는 탓일까.
나는 여기 내 실력을 키우기 위해 왔다. 남이 시켜서 한 것도 아니다. 내가 원해서 왔다.
순간에 최선을 다해야만 내 목표를 이룰 수 있다는 사실을 잊지 말자.
첫 주차에 대한 나의 다짐을 잊지 말고 꾸준히 열심히 하자.
3. 좋은 개발자가 되기 위한 습관은 지금부터!
유튜브에서 우연히 본 영상에서 아래의 7가지 습관에 대해 제시한다.
1. 코드에 대한 애착이 없다는 건 자신이 짠 코드를 리팩토링하는 것을 두려워 하지 않고 피드백을 쉽게 받아들이며 변화에 대응한다는 것이다.
2. 유저를 위한 코드. 즉, 문제를 해결하고 기능을 제공하는 것에 대해 고민한다.
3. 모두가 컴퓨터가 이해하는 코드를 작성한다. 하지만 좋은 개발자는 동료들, 그리고 미래의 내가 알아보기 쉬운 코드를 작성한다.
4. 일관적이어야 읽고 수정하기 쉽다.
5. 예기치 않은 결과를 가져오지 않는다.
6. 시스템은 혼자 만들지 못한다는 걸 안다. 그리고 소통으로 자신의 빈틈을 채운다.
7. 프로젝트는 빠르게 완수하지만 코딩 자체는 느리게 한다. 원칙을 고수하고 소통하는 것에 시간을 쏟기 때문이다. 그리고 이 쏟은 시간은 결국 프로젝트 완수 시간 절약으로 이어진다.
내 목표인 좋은 개발자가 되기 위한 구체적인 원칙들을 배웠다.
지금부터 지키도록 노력하자!
