이리저리 특강을 듣던 도중, 프론트엔드 코딩테스트 역량에 대한 이야기를 들을 수 있었습니다.
지금껏 프로그래머스를 조금 풀긴했지만, 정말 레벨 1단계에서 머물러있는게 다였습니다.
조금씩 문제를 풀어도 레벨 2는 커녕 코딩테스트에 비비지도 못할 수준이겠다 싶었습니다.
문제를 풀때 어떤 걸 고려해야하는지, 어떤 방법을 사용해야하는지 전혀 감을 잡지도 못한체
남들이 풀어둔 해답을 복사 붙여넣기 하는건 아닌지 고민도 많았습니다.
그런데 이번에 특강을 들으며, 연사님이 말씀하시길
프론트엔드 코딩테스트는 for loop나 DP정도만 사용할 줄 알면 다 할 수 있어요
DP요,,?
저는 드라마 DP말고는 잘 모르겠는걸요,,?
아무튼 이 DP라는 개념을 알면 뭔가 프로그래밍 할 때 큰 도움이 되지 않을까? 라는 생각과 함께 그 동안 밀려 있었던 알고리즘 공부를 다시 시작하기 좋은 시작점이 되지 않을까 싶었습니다.
떨어진 코딩테스트만 하더라도 4곳이 넘기에, 그 동안 기능 구현에만 집중했었던 과거를 떨쳐버리고, 효율적으로 개선해나갈 필요성이 있었습니다.
이번 포스팅에서는 DP가 무엇인지에 대해 자세히 알아보도록 하겠습니다.
Dynamic Programming
DP는 다이나믹 프로그래밍의 약자입니다.
동적 프로그래밍, 또는 동적 계획법이라고 불리는데요.
구체적인 알고리즘을 말하는 것이라기 보단, 문제를 해결하는 일종의 패러다임에 가깝습니다.
이 패러다임의 핵심은 문제를 잘게 쪼갠다는 것입니다.
- "어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는" 방식의 알고리즘을 총칭한다. - 위키백과
- 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법이다. - 나무위키
이게 무슨 소린지 잘 모르겠다면 정상입니다. 저도 그렇거든요.
아무튼 이 개념을 쉽게 풀어말하자면, 기존에 구해뒀던 답을 재활용해서 메모리 효율을 끌어올리는 그런 방법입니다. 메모이제이션을 통해 연산 속도를 끌어올릴 수 있는 셈이죠.
문제를 아주 잘개 쪼개고, 가장 작은 문제를 해결한 방법을 토대로 점차 상위 문제를 푸는데 사용하는 방식입니다. 일종의 바텀업 프로그래밍이라고 생각하면 좋습니다.
바텀업이요?
바텀업에 대한 이해가 잘 안된다구요? 간단한 예시를 들어드릴게요.
여러분은 지금부터 집을 지어야합니다.
집을 지을줄도 모르고, 어떠한 방법으로 만들어 본적도 없습니다.
그럼 지금부터 일주일을 드릴테니 집을 한채 지어주세요.
탑다운
1. 먼저 설계도를 그리자!
2. 쓰리룸이 좋겠어!
3. 화장실을 만들고, 거실도 만들어야겠어
4. 아 주방도 만들자!
5. 이제 이 방의 세부적인 재료들을 정해볼까?
6. 벽돌, 시트지, 보일러 ....탑다운 방식의 장점은, 인력이 많으면 빠르고 효율적으로 끝낼 수 있는 장점이 있어요.
하지만 단점은 구조를 중간에 변경해야 하거나, 계획 자체를 변경해야 할때 치명적이예요.
네? 쓰리룸이 아니라 투룸이라구요,,?
바텀업
1. 일단, 내 방 부터 만들어 볼까?
(뚝딱뚝딱....)
2. 음... 이제 내방도 만들었으니 안방도 만들까?
(뚝딱뚝딱....)
3. 아! 거실하고 화장실도 만들어야 겠네!
(뚝딱뚝딱....)
4. 아! 부엌을 깜빡했네! 부엌도 만들자!
(뚝딱뚝딱....)
5. 이제 다 만들어졌으니 이어 붙이자!
바텀업 방식은 일반적으로 각각의 모듈(module)을 만듭니다.
모듈이란, 전체를 이루기 위한 하나의 단위를 의미합니다.
즉, 바텀업이란 모듈 모듈을 하나씩 만들고 조합하며 만들어갑니다.
마치 프로젝트의 컴포넌트 쪼개기, 또는 컴포넌트별 개발과도 비슷해 보이네요!
이런 바텀업 방식은 변화에 유연하게 대처할 수 있는 장점이 있습니다.
중간에 설계가 바뀌어도 전체를 갈아 엎어야 하는 일을 덜 수 있습니다.
하지만 바텀업 방식은 하나의 치명적인 문제가 있는데요.
기본적으로 모듈화를 할 수 없는 구조,
예를 들면 하나의 구성요소를 만들려면 꼭 다른 요소가 있어야 하는경우가 있죠.
예를 들면, 순차적으로 일을 진행해야 하는 경우가 대표적이예요.
그래서 DP 어떻게 하는건데요
바텀업과 탑다운에 대한 설명이 길었네요. 오랜만에 비유해서 설명하자니 제가 더 신나서 많이 샌 것 같습니다.
DP를 활용하기 위해선 조건이 필요한데요.
다음과 같습니다.
- 작은 문제가 반복해서 나타날 것
- 같은 문제는 구할때마다 정답이 같을 것
이런 조건이 갖춰진다면 다이나믹 프로그래밍을 사용할 수 있습니다.
작은 문제들의 정답이 모두 같다면 상위 문제를 쪼갰을때도 작은 해결법으로 풀어나갈 수 있습니다.
DP를 활용하려면 다음과 같은 방법을 적용해야합니다.
- 쪼개진 작은 문제를 한번만 풉니다.
- 정답을 구한 작은 문제들을 메모해둡니다.
- 이후에 상위 문제를 마주하거나 똑같은 작은 문제가 나타나면 메모해둔 결과값을 이용합니다.
피보나치 수열
DP를 대표적으로 이용할 수 있는 곳이 바로 피보나치 수열 문제입니다.
피보나치는 1,1,2,3,5,8... 이런 수를 이루게 됩니다.
피보나치 수열은 이전의 수와 두단계 전의 수열을 합쳐서 다음 수열을 뽑아냅니다.
식으로 나타내면 다음과 같습니다.
다음수 = 이전 수 + 두단계 전 수
이전의 수를 바탕으로 새로운 수열을 계속해서 만들어갑니다.
여기서 다이나믹 프로그래밍을 사용하기 좋습니다.
먼저 첫 번째 방법입니다.
function fibo_noMemo(n) {
if (n > 2) {
return fibo_noMemo(n - 2) + fibo_noMemo(n - 1);
} else return 1;
}재귀 함수로 만들었는데, 작동은 하지만 효율적이라곤 할 수 없습니다.
첫 번째 두번째 피보나치 수열은 1이 들어옵니다.
예외 처리로 1을 해주시고 처음부터 올라가게 됩니다.
만약 5가 들어왔을 때를 가정해보자면
5번째 수열을 구하기 위해선 4번째 수열이 필요합니다.
4번째 수열을 구하기 위해선 3번째가 필요하구요.
이런식으로 진행되다 보면 하위 계산식까지 찾아 내려갑니다.
전혀 다이나믹 프로그래밍스럽지 못합니다.
그렇다면 다이나믹 프로그래밍스럽게 코드를 변경해봅시다.
중요한 점은, 작은 문제를 해결했던 결과를 재사용한다는 것입니다.
function fibo(n) {
let arr = [0, 1];
if (n < 3) {
arr[n] = 1;
} else if (!arr[n]) {
arr[n] = fibo(n - 1) + fibo(n - 2);
}
return arr[n];
}arr에 수열들을 계속해서 담아두고, 몇번째 수열이 들어오는지 체크가 되고
만약 n번째의 수열이 없다면 n-2, n-1번째의 숫자를 합쳐서 그 수를 n번째 arr에 집어넣는 방식입니다.
이 같은 연산 방식은 시간 복잡도에 있어서 상당히 유리하게 작용합니다.
만약 30번째 수열을 구하려고 할때
재귀 함수를 사용하면 4356586번의 함수 호출이 필요합니다.
그러나 메모이제이션 방식을 적용했을 경우엔 86번만 이뤄집니다.
중복되는 부분 문제를 재사용함으로써, 높은 계산 효율을 챙길 수 있습니다.
사실 어떤 방법이든 상관은 없지만 효율적으로 풀기 위해선 DP라는 패러다임을 알고 있는 것은 매우 중요하다고 생각합니다.
앞으로 있을 코딩테스트에 반드시 써먹을 날을 기약하며, 이만 글 마칩니다.
감사합니다 :)
