저번에 이어 이번에도 알고리즘 강연이 왔다

서문으로 알려줄 건 없고

하다보면 된다고 한다

저 드넓은 바다 너머 원주민들의 기우제가 생각나는 방식이라 할 수 있다

Mergesort

1. 주어진 배열 반 가르고

2. 각각 정렬 한다 (재귀로)

3. 각각 정렬한 걸 합친다

이걸 디바인 앤 컨펌이란다

한국어로 직역하면 나누고 확인받기?

직관적인 이름이라 볼 수 있겠다

이러한 분할 정복(디바인 앤 컨펌이란 뜻)을 할 때에 중요한건

…

갑자기 교수님이 했던 말을 수차례 반복해서 요약 실패했다

대충 분할 정복 핵심에 대해서 설명한 듯 하다

이건 뭐 인터넷 뒤져도 나오는 거니

강연을 열어나가는 서문정도로 적절한 예시인 듯 하다

그리 어렵지도 않고 우스워보이지도 않는 내용

분할 정복 예시

파이썬 max가 해주는 거 우리가 한다 가정

여러가지 코드들을 가져와

각 알고리즘 별 풀이방식과 시간복잡도의 차이에 대해 설명해주었다

C로 코드를 보여주었는데

강사피셜)

C는 참 좋은데… 참… 흠…

잘 뒤지니 조심하라고 한다 ㅇㅇ

아무튼 N개의 숫자들에서 가장 큰 수를 찾으려면

아무리 효율적으로 짜봐도

N개를 전부 탐색해야 하니

시간 복잡도는 $O(N)$ 보다 못 줄인다 한다

안보고 큰지 작은 지 알려면

사실 컴퓨터가 아니라 무당 불러야 하긴 함 ㅇㅇ;;

그러니 복잡하고 고급 알고리즘이라고 꼭 좋은 건 아니라고 한다

시간 복잡도 점화식

recursion tree라는 키워드로 알아서 공부하란다

뭔가 설명하시긴 했는데

ㄹㅇ 좆도 이해못함;;

나중에 따로 공부하면 관련해서 작성하겠다

이진 탐색

binary search
얜 존나 많이 봐서 이-지 하다

비-전공자는 물론 비-인간도 하루 안에 이해 가능한 수준이다

이진 탐색 할때 가운데 범위보다 작다면

작은 범위에 있는게 아니라

큰 범위에 없다는 식으로 이해하란다

흠…

불필요한 탐색 범위를 제거하는 식으로 이해해야지

필요한 탐색 범위를 얻는 식이 아니란 걸 설명하는 듯 한데

예시로 들고온게 너무 이-지한 바람에

크게 안와닿는 모양이다

다들 그래서 어쩌라고? 라는 식의 반응이라 말이다

호응하고 환호성 지르고 눈물 좀 흘려들 주지 ㅉ

그럼 바로 감동의 도가니에 전미가 울었다 할 수 있었는데 말이다

Multiplication

곱셈이란 뜻이다

엥?

걍 곱하면 되지 ㅄ이세요?

라고 하면 뒤진다

막 4자릿수는 그렇게 되지만

515571233 자릿수 쯤 되면 그게 안된다고 한다

그럼 이것도 D&C로 할 수 있다는데

여기서 중요한 건

어떻게 쪼개고, 쪼갠 값을 어떻게 사용할지다

이런 곱하기를 분할 정복하는 예시로

4자릿수 x 4자릿수에서

결합법칙? 교환법칙? 그런거 응용해서 하는 거 알려줬다

예시)

1472 = 1400 + 72

2569 = 2500 + 69

1472 * 2569
= (1400 + 72) * (2500 + 69)

대강 일반화 하자면

$x = 10^m a + b$

$y = 10^m c + d$

$xy = 10^{2m} ac + 10^m(bc + ad) + bd$

이런 느낌이다

그리고 이의 시간 복잡도를 코드와 함꼐 설명해줬는데…

스킵하고 결과부터 말하자면 $O(n^2)$ 라고 한다

…?

뭐야 ㅅㅂ 하기 전과 시간 복잡도 똑같다

결국 머리써서 쓰레기를 만든 꼴이 되버렸다

쓰레기를 나무로 만들지 못할만정

걍 쓰레기를 만들었다..

$O(n^2)$를 줄이기 위해 노력해 $O(n^2)$를 만들었으니

사실 그것이 곱셈의 한계인가 싶다

여기서 더 못줄이는 거지 ㅇㅇ

하지만,

그러면 이딴 얘기를 안 꺼냈다

$xy = 10^{2m} ac + 10^m(bc + ad) + bd$ 라는 식에서

사실 $bc+ad$만 알면 더 간단히 할 수 있을지도 모른다 라는 생각을 할 수 있다

만약 그렇다면 축하한다

작성자보다 똑똑한거니

블로그 그만보고 나가라

아무튼
$bc+ad$를 구하려면
$ac + bd - (a-b)(c-d)$를 해야 하고

이를 통해

기존 디바이드 방식을 줄여 4번에서 무려

3번!!! 으로 줄일 수 있다

원래 시간 복잡도는

$4T(n/2) + O(n)$이었는데
$3T(n/2) + O(n)$로 줄였으므로

시간 복잡도는

$O(n^{log_23}) = O(n^{1.58496})$으로

$O(n^2)$에서 줄여버렸다..

이것이 최초로 시간 복잡도를 더 줄일 알고리즘이라 한다

학생이 교수 말 반박하고 만든 알고리즘이란다

그리고 최근에는

$O(n*logn)$까지 줄였다고 한다

동적 계획법

이번 주의 키워드 단어다

저번처럼 재귀 끝나고 재귀 설명하지 않은게 다행이라 생각한다

휴, 공부 안해서 이득이다~

미리 공부해서 이해했으면 손해 볼 뻔ㅋㅋ

주요 특징이라곤 ㅈ도 다이나믹하지 않은데

다이나믹이란다

뭐, 지은 사람 마음이니 쩔수 없다

다이나믹 프로그래밍 예제로 피보나치(그 나치 아님) 수열을 들고 왔는데

난 이미 공부했던거라 대충 넘어가겠다

대충 다이나믹 안쓰고 재귀 박으면

존나 느려서 ㅈ된다는 내용

시간 복잡도가 지수함수만큼 나오면

쓰레기니 갖다 버리란다

재귀요정 이 쓰레기 같은 ㅅㄲ

그래서 왜 쓰레기냐?

순수하게 재귀만 쓸 경우

중복계산을 존나게 해서 시간복잡도가 존나게 가파르다

그렇다는 건 중복계산만 쳐내면 된다는 뜻이다

그래서 테이블 기법이란게 있는데

테이블을 만들어 여기에 재귀 값을 저장하는 것이다

그렇다.

재귀요정이 쓰레기 같은 이유는

우리가 쓰레기 같은 방법을 명령해서다

그러니 상수도에 폐수 버리는 짓은 이제 멈추고 클-린한 다이나믹 프로그래밍을 사용하자

대강 이번 강연의 핵심을 예상해보자

분할 정복에 대한 개념,

메모제이션이 뭔가?

그리고 이를 통한 다이나믹 프로그래밍에 대한 이해인 것 같다

위에 적힌 내용을 안다면 큰 도움이 안될수도 있겠다

핵심은 올바른 점화식을 찾고 table을 관리하는 것

그것이 DP : table의 핵심이다

점화식은 그 점화(Ignite)가 아니라
점화식(recurrence relation)이다

사실 점화식 찾는게 어렵다

재귀하고 메모제이션 하는 건 이-지하니

문제 해결하는 점화식 구현이 문제다

그리고 Grid를 통해서

최단경로 갯수 세는 문제를 예시로 들었는데

걍 그건 안적겠다

일종의 점화식을 파악하고

이를 풀어나가는 방식이면 어떤 문제든 상관없으니

궁금하면 알아서 찾아보자

ㅅㅂ 2시간 강연인데 쉬는 시간 없나?

에스프레소 설탕 2포 넣고 텀블러 물 한잔

다 마실때즘 되니

슬슬…

사실 1시간 반 강연이란다

옥게이~

10분 정도는 더 참을 수 있을 것 같다

LCS

롱기스트 꺼먼 섮시ㅅ컨스

딱 어제 마지막으로 정리한 내용이라

여기가서 내가 정리한 거 봐도 된다

🔽🔽🔽🔽🔽🔽🔽🔽🔽🔽🔽

로ㅇ기스thㅡ 커먼ㄴ 섭시ㅣ킨스

🔼🔼🔼🔼🔼🔼🔼🔼🔼🔼🔼

(대충 LCS에 대한 설명)

강의 요약

저번과 달리 재귀가 끝나고 온건 아니라 만족이다

솔찌 저번에는 너무 늦게 강연왔다

아무튼, 이번 강의의 내용은

문제를 작게 쪼개 해결 뒤 합하는 법을

분할 정복으로 설명했다

그리고 재귀를 그냥 하면 병신이 될 수 있다는 내용을 설명했고

이를 해결하기 위해 계산값저장(메모제이션)의 중요성에 대해 알려줬다

최종적으로 다이나믹 프로그래밍의 중요 아이디어인

작게 쪼개고 메모제이션해 답을 내놓는 방식의 흐름을 설명했다

꽤나 훌륭한 빌드업이었다

그외에 다이나믹 프로그래밍의 방식인

LCS등을 설명하려 했으나

시간이 부족해 LCS만 설명했다

대충 LCS는 짝짓기라는 내용이었던 것 같다

짝을 함부로 맺어주지 말고 잘 지어주란다

싯팔 10분이 아니라 20분 참고 있는데 강연이 안끝난다;;

으윽…

뭔 ㅅㅂ 화장실 2분 갔다 왔더니

강연이 끝났다;;

졸지에 2분 못참아 강연 중 화장실 간

싸가지 없는 새끼가 돼버렸다;;

ㅅㅂ