[정글] WEEK 04 | 알고리즘 마지막 주차!

알고리즘 마지막이라고 제가 신난 것처럼 보이시나요? 잘 보셨네요. ( ͡° ͜ʖ ͡°)

 

WEEK 04 키워드
동적 프로그래밍, 그리디 알고리즘

🎈 개념 정리

다이나믹 프로그래밍

• 최적 부분 구조 : 큰 문제를 작은 문제로 나눌 수 있나?
• 중복되는 부분 문제 : 동일한 작은 문제를 반복적으로 해결할 수 있나?

메모리제이션 (=캐싱)

• 한번 계산한 결과를 메모리 공간에 기록하는 것
• 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져옴

탑다운 VS 보텀업

• 탑다운 (메모리제이션, 하향식)
• 보텀업 (상향식)

DP 문제 접근법

• 주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이 중요함
• 먼저 그리디, 구현, 완전 탐색 등의 아이디어로 해결 가능한지 검토
• 다른 알고리즘을 이용한 풀이 방법이 떠오르지 않으면 다이나믹 프로그래밍 검토
• 일단 재귀로 작성, 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면 코드 개선

 

냅색 (Knapsack) 알고리즘

• 담을 수 있는 무게의 최댓값은 정해져있고, 일정 무게와 가치가 있는 짐들을 넣는 상황
• 담을 수 있는 물건이 나눌 수 있을 때 : 분할 가능 배낭문제
• 담을 수 있는 물건이 나누어 질 수 없을 때 : 0-1 배낭문제

Weight	Value	1	2	3	4	5	6	7
6	13	0	0	0	0	0	13	13
4	8	0	0	0	8	8	13	13
3	6	0	0	6	8	8	13	14
5	12	0	0	6	8	12	13	14

 

비트마스킹

1. 빠른 수행시간, 2진수이기 때문에 연산속도(삽입, 삭제, 조회)가 빠름
2. 적은 메모리, 배열을 이진수 하나로 표현 가능
3. 비트 연산자를 이용한 깔끔하고 간결한 코드
4. 비트마스크를 이용한 정수 표현으로 다이나믹 프로그래밍이 가능

[1, 0, 0, 1, 1, 1, 0, 0, 1, 1] -> 1001110011

1 << n 				// n+1만큼 초기화
(1 << n) - 1 			// n 개수
visited & (1 << i)		// visited에 i가 있는지 체크
visited | (1 << i)		// visited에 i 추가

 

그리디 알고리즘

• 현재 상황에서 가장 좋은 걸 선택하는 알고리즘
• 매 순간마다에서 가장 좋은 걸 선택하는 것이 해당 문제에 적합한지 증명해야 함

---

🎈 알고리즘 주차를 마무리하면서

 

알고리즘? 별거 아니겠지. 라고 생각했던 난 어리석었다. 내 욕심으로는 모든 문제를 풀이를 보지 않고 풀고 싶었는데, 그렇게 하면 시간이 너무 많이 들어서 그럴 수 없었다. 코치님이 한 문제를 30분 이상 붙잡고 있다는 건 모르는 거라고 하셨다. 네. 한 문제를 오래 붙잡고 있는 건 바보같은 일이었슴미다.

회사에 있을 때 다른 사람의 코드를 보면서 배우곤 했었다. 지난 한달 동안에도 다른 팀원이 푼 코드를 보면서 '저렇게 풀 수도 있구나', '이렇게 풀면 쉽게 풀리네?'와 같은 생각을 자주 했다.

컴퓨팅 사고로의 전환이라니. 너무 찰떡같은 제목이다.