알고리즘 3대 통곡의 벽 파헤치기

알고리즘엔 3대 통곡의 벽이 있다는 걸 알고 계신가요?

제가 알고리즘 공부 한참 했을 때, 이 3대 통곡의 벽에 부딪힐 때마다 너무 힘들었었는데요.

지금은 알고리즘이라든지, 개발 일을 하지 않고 있어서 쓸데도 없고, 여기다가 그냥 조금씩 풀어보려고 합니다.

 

가볍게 봐 주세요~

 

 

 

 

목차

• 알고리즘 3대 통곡의 벽 1 : 반복문(loop)
• 알고리즘 3대 통곡의 벽 2 : 재귀(recursion)
• 알고리즘 3대 통곡의 벽 3 : 다이내믹 프로그래밍

• 함께 보면 좋은 글

 

 

알고리즘 3대 통곡의 벽 1 : 반복문(loop)

알고리즘 3대 통곡의 벽 첫 번째 관문은 바로 반복문입니다.

 

엥?

반복문이 왜?

쉬운데?

 

...라고 생각하실 수 있겠습니다만, 우리는 태초를 알아야 합니다.

우선 반복문을 봅시다.

 

 

for(let i = 0; i < n; i++) {
	// 여기에 코드 삽입
}

흔한 반복문입니다.

그렇지만 for이 뭔지, let은 왜 저 사이에 껴 있는 건지, i에 n은 뭔지, 마지막은 왜 i++인지, ++i는 안 되는지...

이런 걸 고민했던 시간이 있었을 것입니다.

 

제가 그랬으니까요.

 

반복문은 컴퓨터가 어떻게 행동하는지 알 수 있는 가장 쉽고, 좋은 코드입니다.

나중에 나올 통곡의 벽 2, 3이 모두 반복문이라는 기본 틀에서 뻗어져 나간다는 걸 알고 계실 겁니다.

 

반복문은 단순하게, 정말 단순하게 반복해 준다고 하여 반복문입니다.

 

for이라는 키워드 (괄호 안에 들어간 코드가 끝날) 때까지, {이 안의 코드를 반복} 한다는 겁니다.

let이 선언한다는 것은 알고 계실 거라고 생각할게요.

 

괄호 안 설명해 드릴게요.

 

괄호 안에 i라는 변수를 선언하고, 0으로 초기화를 합니다.

그리고, 이 i가 n보다 크기 전까지,

한 번 반복할 때마다 i를 1씩 올려달라는 뜻입니다.

 

즉, i가 0이고 n이 3이라면, i는 0부터 시작해서 한 번 반복할 때마다 1씩 올라가니까, 0, 1, 2, 3 총 4 번 반복하고 끝납니다.

 

 

 

알고리즘 3대 통곡의 벽 2 : 재귀(recursion)

 

두 번째는 재귀인데요, 재귀도 마찬가지로 반복을 합니다.

단, 함수의 개념을 알아야 합니다.

 

재귀는 자기 자신을 호출합니다. 그러니까, A라는 함수 안에서 A 함수를 부를 수가 있습니다.

 

이런 식으로 쓸 수 있습니다.

function a (n) {
	if(n === 5) return n;
	return a(n + 1);
}

 

말 그대로의 코드입니다. a라는 함수에 n이라는 변수를 받고, 만약에 n이 5라면 5를 반환을 해 주는 코드입니다.

그런데 마지막에도 리턴이 달려 있죠? 그것도 a 함수를 호출해서요.

 

이 코드의 해석은, 결국 if문은 n이 5일 때만 실행된다는 걸 이용합니다.

함수는 함수 안에서 함수를 호출할 수 있습니다. 

 

재귀는 그 함수가 나일 뿐입니다. ^^;

함수가 호출이 됐으니 우선 실행한 함수를 멈추고 호출한 함수를 실행시켜야 하는데,

똑같은 코드의 반복일 뿐이겠죠? 결국에는 빠져나오지 못할 겁니다.

 

빠져나오기 위해서 if문을 두는 거고, 재귀를 호출할 때의 변화를 두는 겁니다.

 

재귀는 인간친화적이기보다 컴퓨터에게 더 친화적이기 때문에, 사람들이 많이들 헷갈려합니다.

재귀 들어가는 건 잘해도, 나가는 게 힘들어서 많이 절절매기도 합니다.

 

이 재귀를 자유자재로 다룰 수만 있다면 웬만한 기초 알고리즘은 다 뗐다고 봐도 무방합니다.

 

 

 

알고리즘 3대 통곡의 벽 3 : 다이내믹 프로그래밍

마지막으로... 다이내믹 프로그래밍, DP입니다.

알고리즘은 당연히 깊은 학문이기 때문에 통곡의 벽 3에서 끝나지 않습니다.

 

또한 유형도 엄청 많고, 또 알아야 할 것도 굉장히 많죠. 

그렇지만 그냥 여기에서 많이들 막힌다~ 정도로만 생각해 주시면 됩니다.

 

DP 같은 경우엔, 재귀의 업데이트라고 제가 많이 말하고는 다닙니다. (비약적인 내용이니까 그냥 그런가 보다 해 주세요)

재귀를 사용하다 보면 결국 같은 코드의 반복이기 때문에 메모리 누수도 엄청나고, 몇 번 하다가 멈추는 경우도 대다수입니다.

 

그래서 DP는 이미 계산한 것을 다시 계산하지 않도록 합니다.

이전에 계산한 것들을 기억하고 있다는 뜻이 되겠죠. ^^;

 

DP 같은 경우엔 대표적인 코드를 올려 드릴 수가 없네요.

알고리즘 문제 유형 같은 것들 뿐이라, 그냥 그 개념만 익힌 뒤에 유형 풀이를 많이 해 보면 감이 잡힙니다.

 

 

이 알고리즘 3대 통곡의 벽을 다 깨면, 웬만한 기초~중하위권 알고리즘은 다 깼다고 봐도 무방합니다.

여기에서 얻은 지식 정보 + 공부법을 토대로 상위로 쭉쭉 가는 일만 남은 거죠!

 

 

알고리즘이 재미있어서 무지성으로 풀었던 날들이 생각이 나네요.

머리 복잡할 때 한 번씩 하면 재미있으니, 종종 여러분들도 해 보세요.

 

글 이만 줄입니다!

 

 

함께 보면 좋은 글