알고리즘과 문제풀이법
알고리즘 개요
알고리즘이란?
알고리즘이란 무엇일까요?
알고리즘이라고 하면 막 엄청난 수학적 공식이 떠오르고, 복잡한 문제풀이 방법이 떠오르시나요?
적어도 저는 그랬습니다.. ㅎㅎ.. 그래서 꽤나 오랫동안 알고리즘을 멀리하면서 살아왔었죠.
근데 사실 알고리즘은 따지고 보면 별거 없습니다.
알고리즘은 "문제를 해결하는 방법", 다르게 말하면 문제 푸는 법입니다.
알고리즘(영어: algorithm)은 수학과 컴퓨터과학에서 사용되는, 문제 해결 방법을 정의한 '일련의 단계적 절차'이자 어떠한 문제를 해결하기 위한 '동작들의 모임'이다. 계산을 실행하기 위한 단계적 규칙과 절차를 의미하기도 한다. 즉, 문제 풀이에 필요한 계산 절차 또는 처리 과정의 순서를 뜻한다. 프로그램명령어의 집합을 의미하기도 한다.
위키피디아에서는 위처럼 정의하긴 하는데, 걍 멋있게 표현한 것일 뿐 문제푸는 방법들을 가리키는 멋진 단어일 뿐입니다.
우리가 앞서서 빅오와 복잡도라는 멋드러진 표현으로 성능을 표현했듯이요!
한번 다음과 같은 문제를 풀어보시겠어요?
누굴 무시하는건가? 하는 생각이 드시나요? ㅎㅎ...
답은 무엇일까요? 6입니다.
그러면 이걸 어떻게 구하셨나요?
곱셈의 정의가 앞에 있는 수를 뒤에 나오는 수만큼 더하는 것이지 않나요?
그래서 2를 3번 더하니까 6이라는 결과가 나왔죠.
이처럼 문제를 푸는 방법이 알고리즘입니다.
여러분은 인지는 하지 못하였지만 곱셈이라는 알고리즘을 통해서 무의식중에 문제를 풀고 계셨던거에요!
이처럼 알고리즘은 문제푸는 방법을 지칭하는 단어 그 이상도 이하도 아닙니다. ㅎㅎ
수학적 표현이나 여러가지 요소들은 결국 이 문제 풀이 방법을 엄격하게 설명하고, 전달하기 위해 사용한 용어들일 뿐인 것이지요.
어디서 들은 이야기인데, 세상에는 자기를 뽐내는 걸 좋아하는 사람들이 많다고 합니다.
하지만 뽐낼때 좀 멋있게 뽐내고 싶고, 자기를 시기 질투하면서 깎아내리는 사람들의 입을 꽉 닫게 하고 싶잖아요?
그래서 내가 찾아낸 문제풀이 방식을 자랑할 때, 엄청 논리적으로 표현할 수 있는 수단인 수학을 써서 표현하는 것 뿐입니다.
어때요? 이렇게 놓고 보니 막연한 두려움들이 좀 사라지셨나요?
알고리즘은 왜 배우는가?
그러면 알고리즘은 왜 배울까요? 왜 중요하기에 전공 과목에서 따로 수업까지 열려가면서 집중적으로 배우게 되는 것일까요?
사실 알고리즘을 배우는 이유는 수학을 배우는 이유와 같습니다.
어떤 문제를 푸는데 보다 효율적으로, 그리고 논리적으로 접근하기 위해서 입니다!
당장 위의 곱셈 문제만 하더라도, 곱셈을 배우지 않았다면 여러분들은 매번 덧셈을 반복하면서 문제를 풀고 있어야 할 거에요!
알고리즘을 배우는 이유도 같습니다!
컴퓨터 상에서 보다 효율적으로 문제를 푸는 프로그램을 만들기 위해 알고리즘을 배운다고 할 수 있습니다.
같은 문제를 푸는데 무식하게 하드코딩해서 짜면 답을 내기까지 1시간이 걸린다고 해봅시다. (이를 naive coding 이라고 합니다.)
그런데 조금 복잡하지만 5분만에 푸는 방법이 있다고 합시다.
혼자서 5분만에 푸는 방법을 고안하기 힘드니까, 똑똑한 사람이 발견한 방법들을 우리가 낼름 배워서 써먹는 것입니다.
속된 말로 날먹이죠.
날먹하기 위해서 배운다고 보시면 됩니다.
똑똑한 사람들이 밤새워가면서 알아낸 방법을 낼름 배우는 것. 그게 곧 알고리즘을 공부하는 것이죠!
프로그래밍은 곧 어떤 문제가 주어졌을때 이를 컴퓨터를 통해 해결하는 방법을 찾는 것입니다.
이를 보다 효율적으로 진행하기 위해서, 옆에 컨닝페이퍼를 두고 문제를 푼다고 생각하시면 됩니다!
기본적인 문제 풀이 방법
알고리즘은 문제를 푸는 방법이라고 했습니다.
그리고, 우리의 스터디 목표는 코딩 테스트를 뿌수고, 실전적 코딩을 해보는 것입니다.
또한 알고리즘을 배우는 이유는 날먹하기 위해, 일종의 문제 풀이 공식이자 치트키를 익히고 써먹는 것입니다.
그럼 이제부터 제일 간단한 날먹부터 하나씩 배워봅시다.
제가 경험한 몇 가지 테크닉들이 있습니다. 이에 대해서 하나씩 설명을 해보고자 합니다.
- 문제를 읽고 분석하라 (문제를 잘 읽어라)
- 특히 입력과 출력을 명확히 하라
- 문제의 조건을 잘 따지고 히든케이스를 고려하자
- 쪼개서 생각해라
- Divide and conquer
- 의사코드를 반드시 작성하라
- 문자열 처리 -> 정규 표현식을 사용할 수 있으면 이를 활용하라
- 기본 내장 함수가 있으면 그것을 사용하라. (예: 객체, 딕셔너리, 힙, 스택 등)
뭔가 뒤죽박죽 섞여있는데, 처음 3개는 문제풀이의 태도에 대한 부분이고, 뒤의 2개는 진짜 문제풀이와 관련된 부분입니다.
차근차근 하나씩 알아봅시다.
문제를 읽고 분석하라 (문제를 잘 읽어라)
학창 시절로 돌아갑시다. 대학생 시절 말고, 초등학교, 중학교, 고등학교 때로요.
여러분들은 지금 수학 수업에 들어와있다고 상상을 해봅시다.
이러저러 원리들을 배우면서, 문제풀이를 들어갔을때 항상 선생님들이 하시는 말씀이 있죠.
문제속에 답이 있다. 그러니 문제를 잘 읽어라.
누가 그걸 몰라서 못하나? 싶은 말이고, 누가 그걸 몰라? 하는 말이지만,
잘 읽는 것 이것은 진리입니다.
정확히는 잘 읽고 잘 파악하는 것이긴 합니다.
알고보니 우리는 삶의 진리를 계속 들으면서 자라왔던 것이지요.
이는 코딩테스트나 알고리즘 문제풀이에도 적용되는 진리입니다.
다만 이렇게 이야기를 하면 진부하죠? 그래서 약간의 체크리스트를 제안해보려고 합니다.
굳이 외울필요는 없고, 그냥 이런 순서로 몸에 익히면 좋다는 의미에서 작성된거니 편하게 보시면 될 듯 해요.
문제를 읽는 방법의 핵심
문제를 읽는 방법의 핵심은 문제 상황을 읽고 이해해서 자신만의 표현 방식으로 재구성 하는 것입니다.
즉, 나의 방식으로 코드로 작성해서 컴퓨터가 작업을 수행할 수 있도록 문제 상황을 재구성하는 것입니다.
이렇게 말하면 크게 와닿지 않으시죠? 그래서 아래와 같은 예시를 준비해봤습니다.
사과 개와 배 개가 주어질 때, 과일은 총 몇 개인가?
이를 어떻게 자신만의 표현으로 바꿀 수 있을까?
사과와 배를 그냥 하나의 대상으로 보고, 과일도 그냥 결과라고 이해하면 되지 않을까?
그리고, 좀 더 기계적으로 이해하면 저는 다음과 같이 이해할 수 있을 것 같습니다.
과 이라는 숫자가 주어진다.
그때, 이 둘의 합을 반환하라.
이렇게 하면 저 문장이 입력과 결과가 주어진 문장이 되었네요.
그러면 우리가 할 일은 입력을 통해 결과를 도출하는 코드를 작성하면 됩니다.
복잡한 생각 필요없이 위에는 단순하니까 이라는 것을 알겠죠?
그러면 이대로 코드로 바꾸면 됩니다.
function calculateFruit(n, m) {
const result = n + m;
return result;
}
그냥 단순하게 n + m 으로 표현해도 되겠지만, 위와 같이 함수로도 표현할 수 있을 것입니다.
다시한번 살펴봅시다.
과 이라는 숫자가 주어진다. -> 함수의 입력값 (파라미터)
이 둘의 합을 반환하라 -> 합수의 리턴값
이렇게 이해되지 않나요?
제가 함수로 표현한 이유도 바로 위와 같습니다.
이처럼 자신만의 표현 방식으로 재구성해서 최종적으로 코드로 작성하기 위한 게 문제를 잘 읽어야 하는 이유입니다.
문제 읽기 체크리스트
위에 과정을 좀 더 세분화해서 작성하면 아래와 같이 표현할 수 있을 것 같아요.
- 문제의 입력과 출력이 무엇인지를 파악한다.
이는 곧input,output이 되므로, 함수를 기준으로 생각하든, I/O 관점에서 생각하든 컴퓨터로 표현할 수 있는 수준으로 표현할 줄 알아야 합니다. - 입력값이 출력값을 결정할 수 있는가? 있다면 어떻게 결정할 수 있는가?
이는 위에서 덧셈을 도출한 것과 같습니다.input을output의 형태로 바꾸는게 우리가 하는 프로그래밍 작업의 전부입니다.
그렇기에input으로output을 만들 수 있는지를 먼저 확인해야 합니다.
만약 만들 수 있다면, 어떻게 만들 수 있는지를 생각해보면 됩니다. - 세부 분석
- 해결 또는 단순화
- 되돌아보기와 리팩터(refactor)
그런데 이게 쉬웠다면 세상에 못푸는 문제는 없었겠죠?
사실 문제푸는 과정은 이를 명확히 해서 글로 써내려가는 과정과 같습니다. 이제부터 이에 대해서 하나씩 살펴볼 예정입니다.
세부 분석 : 문제 쪼개기
앞서서 덧셈을 예로 든 거 기억하시나요?
사실 지금 이 글을 읽는 사람이라면 사칙연산(더하기, 빼기, 곱하기, 나누기) 정도는 하실 수 있으리라 생각이 되어요.
문제 쪼개기란 이런 사칙연산 처럼 자기가 풀 수 있는 영역들로 나누는 과정을 말해요!
단순한 생각이 아니라 무려 Divide and Conquer라는 이름이 붙을 정도로 유명한 알고리즘이기도 하답니다.
알고리즘이 문제 푸는 방법을 칭한다는 것을 생각해보면 당연한 이야기이지만요!
문제 쪼개기를 예시로 하나 들어서 살펴볼까요?
Q. 를 구하시오.
제일 처음에 예시로 들었던 곱셈 예시입니다. 이를 쪼개면 어떻게 쪼갤 수 있을까요?
그 전에, 입력이 과 이고 이에 대한 곱셈 결과가 출력인건 파악되셨죠?
돌아가서, 쪼개는 방법은 이 경우는 정의를 살펴보는 것입니다.
곱하기의 정의가 뭐였죠? 앞에 나온 숫자를 뒤에 나온 숫자번 만큼 반복해서 더하는 표시였죠?
그러면 으로, 덧셈 문제로 변화한 것을 볼 수 있습니다.
그러면 여기서 한가지만 더, 여기서 한번 더 쪼갤 수 있는게 보이시나요?
처음 덧셈 부분인 으로 쪼개지는 게 보이시나요?
그러면 답은
로 표현이 되어요!
쪼개고 보니 또 뭐가 보이시나요?
글씨가 조금 이상하긴 하지만 위와 같은 결과가 보이지 않나요?
는 그저 인 단계의 결과에 불과 합니다.
그러면 코딩도 가능하지 않을까요?
function multiply(a, b) {
let result = 0;
for (let i = 0; i < b; i++) {
result += 3;
}
return result;
}
위와 같이 표현할 수 있지 않을까요?
앞선 과정이 되게 단순해보이지만, 쪼개다보니 규칙이 보였고, 그를 통해서 코드를 만든 모습입니다.
이것보다 복잡한 문제를 푸는 방법도 동일합니다.
자기가 이해할 수 있는 부분으로 어떻게든 쪼개는 겁니다.
그리고 그 쪼갤때 좀 더 잘 쪼개기 위해서 배우는 것들이 이후에 설명할 알고리즘과 자료구조입니다.
당장 이 문제만 놓고 보더라도, 곱셈으로 표현하면 아래와 같이 보다 쉽게 단순화해서 표현할 수 있지 않나요?
function multiply(a, b) {
return a * b;
}
그리고 이런 과정 필요 없이 어느정도 단계는 건너 뛸 수 있지 않나요?
그러면 문제를 하나 내볼테니 연습해봅시다!
Q. 계산기를 구현하시오.
앞서 배운 방법을 통해서 한번 자기가 구현할 수 있는 영역으로 분리해보시곘어요?
단순화하기
이제 다음 스탭인 단순화하기에 대해서 알아봅시다.
사실 우리는 이미 보았습니다.
과일 문제를 확인하였을 때, 저희가 했던 과정이기도 해요.
주어진 문제를 저희가 컴퓨터로 표현할 수 있도록 단순화 시키는 과정이 바로 이것이죠.
문제를 분할하였을 때 이를 컴퓨터로 표현하기 위해서는 단순화를 시켜야하니까요.
사과 문제처럼 우리가 다루기 쉬운 형태로 문제를 바꾸는 것을 단순화하기라고 합니다.
또 하나 예를 들어 볼까요?
Q. 연필 한다스는 12자루이다. 연필 3다스는 총 몇개인가?
어떻게 단순화할 수 있을까요?
연필을 빼버리고, 그냥 12개가 단위구나로 생각한 다음, 그 단위가 3개 있다고 이해하면 되지 않을까요?
좀 더 단순화하면 로 바꿀 수 있지 않을까요?
이런게 바로 단순화하기입니다.
참고로 의외로 단순화하기의 끝판왕이 수학이랍니다!
엄청 단순하게 표현하기 위해서 등의 기호를 사용해서 단순화한게 바로 수학인 것이지요.
이렇게 단순화하여 우리의 표현으로 바꾸었으면 어떻게 하는게 좋을까요?
코드로 옮기기만 하면 끝입니다.
어때요? 참 쉽죠?
되돌아보기와 리팩터(refactor)
마지막은 되돌아보기와 리펙터입니다.
코드 작성 이후에 일어나는 일들인데, 자기가 작성한 코드를 살펴보면서 피드백을 하는 과정입니다.
코드를 더 간결하게 쓸 수는 없었는지, 다른 문제풀이 방법은 없었는지 등을 살펴보는 것이지요.
이는 혼자서 해도 되고, 친구나 동료가 있다면 같이 서로 코드를 돌려보면서 진행해도 됩니다.
앞서서 본, 아래와 같은 코드를 볼까요?
function multiply(a, b) {
let result = 0;
for (let i = 0; i < b; i++) {
result += 3;
}
return result;
}
이를 되돌아보는 것 입니다. 아.. 어떻게 해야 단순화할 수 있을까? 어떻게 해야 코드를 줄일 수 있을까? 다른 풀이는 없었을까?
있었죠!
function multiply(a, b) {
return a * b;
}
위와 같은 코드가요!
이처럼 다 끝난 다음 살펴보는 과정이 되돌아보기와 리팩터입니다.
그거아세요? 문제를 푸는 과정도 중요하지만, 사실 진짜 실력은 이때 많이 발전한답니다.
자기가 풀 당시 못봤던 것들을 보게 되는 과정이 이 과정이거든요.
자기가 몰랐거나 간과했던 것을 배우고, 자신의 머릿속에 데이터베이스를 쌓아가는 과정이 바로 이 과정인 것이지요.
이는 효율적으로 푸는 과정이지만, 사실 개발에서 엄청 중요한 리팩토링 과정이기도 합니다.
다만, 여기는 알고리즘과 자료구조에 대해서만 다루고자 하니.. 깊은 설명은 하지 않을게요!
마무리
어때요? 이제 문제를 어떻게 접근해야할 지 감이 잡히시나요?
제일 중요한 것은 쪼개기(Divide and Conquer)입니다. 문제가 주어지면 어떻게든 내가 풀 수 있는 것들로 쪼개고 배치만 잘 하기만 해도 문제를 잘 풀 수 있을 거에요!
이제 다음은 진짜로 문제를 어떻게 풀어야하는지 와 문제풀이에 활용할 수 있는 알고리즘과 자료구조를 배워봅시다.