알고리즘과 코딩테스트
CodeState의 SEB 과정에서 언급하기를, 개발자 채용 과정에서 알고리즘과 코딩테스트는 일종의 시험 이라고 표현한다.
채용을 원하는 기업에서 지원자에게 문제를 제출하고 지원자는 '코딩'이라는 도구를 통해 시험을 치르는 과정.
특히, 이런 코딩테스트에서 주요 쟁점은 기초 알고리즘을 활용하여 주어진 상황을 얼마나 코드로 잘 표현할 수 있는가 라고 한다.
즉, 개발자 채용 프로세스에서 문제를 해결하기 위한 최선의 방법(Algorithm)과 그것을 표현할 프로그래밍 언어의 기초(필자의 경우 ..JavaScript)는 필수불가결하다.
알고리즘, 문제를 해결하는 최선의 방법
알고리즘(Algorithm)은 수학과 컴퓨터과학, 언어학 또는 엮인 분야에서 어떠한 문제를 해결하기 위한 정해진 일련의 절차를 의미한다. 또는 계산을 실행하기 위한 단계적 절차를 의미한다. - Wiki
이때, 결과를 얻기 위한 일련의 절차를 정의한다고 그것을 모두 알고리즘으로 볼 수는 없다. 어떠한 문제 해결 방법이 알고리즘이 되기 위해서는 일정한 조건들을 만족 해야 한다.
-
입력(Input) : 알고리즘은 출력에 필요한 자료를 입력 받을 수 있어야 한다. 그러나 입력을 받지 않아도 되는 알고리즘도 존재한다. ex) 일정한 시간마다 점등하는 신호등 <-> 원주율의 N번째 자리 수를 구하는 경우
-
출력(Output) : 알고리즘은 절차 이후, 한가지 이상의 결과를 출력 해야 한다. 출력이 없다면 해당 알고리즘의 종료 여부를 알 수 없고 이는 유한성과도 관련이 있다. 즉, 알고리즘은 그 종료를 알리는 결과 반환이 필요하다.
-
유한성(Finiteness) : 알고리즘은 유한한 명령어를 실행한 뒤 유한한 시간 안에 종료해야 한다. 이는 알고리즘이 실행된 뒤 반드시 종료되어야 함 을 의미한다. 무한히 실행하는 알고리즘은 그 결과를 알 수 없기에 불가하다.
-
명확성(Definiteness) : 알고리즘의 각 단계는 명확해야한다. 각 절차의 실행에 모호한 표현으로 된 지시는 불가하다. ex) 신호등이 몇 분 뒤에 켜진다. <-> 신호등이 5분 뒤에 켜진다.
-
효율성(Efficiency) 알고리즘은 가능한 효율적이어야 한다. 모든 과정은 명백하게 실행 가능하고 시간 복잡도와 공간 복잡도가 종합적으로 낮을수록 좋은 알고리즘으로 평가받는다.
알고리즘, 왜 중요할까?
절차가 명확하고 효율이 좋은 알고리즘은 문제 해결 과정에서 불필요한 작업들을 줄여줄 수 있다.
다양한 알고리즘에 대한 이해와 활용 경험은 프로그래밍 과정에서 문제에 봉착했을 때 보다 효율적으로 문제를 해결하는데 도움이 된다.
이때, 알고리즘을 활용하는 과정에서 알고리즘의 절차가 변경될 경우 Output이 상이할 수 있음을 인지해야 한다.
예를 들어, 다음과 같은 수학 문제를 풀이한다고 가정해보자.
8 / 2 ( 2 + 2 ) = ?
해당 수식의 올바른 풀이 결과는 16이다.
이는 수학을 계산하는 방식(알고리즘)에서 괄호 내부의 수식은 우선 순위를 가지게 되고, 이후 "*,/" 연산자 "-,+" 순으로 우선 순위를 가지게 된다.
만약, 동일한 우선 순위의 연산자인 경우 수식의 좌측부터 계산한다.
하지만, 해당 수식에서 괄호의 함정에 빠진 경우2(2+2)에서 괄호 내부를 계산한 후 생략된 곱셈을 먼저 실행해야 한다고 오해하는 경우 정답은 1이 된다.
이처럼 같은 문제에 대해서 정확하지 않은 알고리즘은 정확하지 않은 결과를 반환하게 된다.
이는 프로그래밍 자체에 큰 문제를 야기할 수 있으므로, 문제 해결에 있어서 정확하고 명확한 알고리즘을 짜는 것이 중요한 것이다.
알고리즘을 잘 짜기 위한 방법?
알고리즘을 잘 짜기 위해서 혹은 코딩 테스트를 잘 풀이하기 위해서는 다음과 같은 논리적인 절차 를 통해 접근하는 것이 중요하다.
1) 문제를 이해하자.
어떤 문제를 해결하기 위한 절차를 정립하기 전에 문제를 명확하게 이해하는 것이 중요하다.
해당 문제의 입출력이 어떻게 되는지, 어떤 제한 조건이 있는지, 여러가지 부가사항들을 포함해 어떤 문제를 해결하고자 하는지를 명확히 아는 것이 첫번째이다.
2) 문제를 해결하기 위한 전략을 세우자.
아이디어를 구체화하는 과정이 필요하다.
필자가 코딩테스트를 접하는 과정에서 가장 어려움을 느끼는 부분은 내 생각을 언어로 표현하는 것이다.
번뜩이는 아이디어가 존재하더라도 그것을 도수코드로 표현하고 다시 프로그래밍 언어로 구현하는 것은 어려운 과정이다.
설계와 기반공사가 탄탄한 건물이 안전한 것 처럼, 충분한 시간을 투자해서 아이디어를 구체화시키고 프로그래밍 언어로 구현하기 전에 도수 코드 혹은 사람이 이해할 수 있는 형태로 바꿔보는 과정이 필요하다.
3) 문제를 코드로 구현하자.
사람이 이해할 수 있는 형태로 구현한 전략을 토대로 해당 절차를 실행할 수 있는 코드를 구현해야 한다.
이때, 가장 중요한 것은 프로그래밍 언어에 대한 이해와 숙련도이다.
한국말로 술술 나오는 문장을 영어로 말하기는 어렵듯이, 머릿 속의 전략을 구체화시켰더라도 프로그래밍 언어에 대한 기초가 부족할 경우 코드로 구현하는 과정이 막연할 수 있다.
전략을 토대로 코드로 구현할 수 있어야 한다.
4) 리팩토링, 최적화하자!
단지, 문제를 풀이하고 공책을 덮어버리지 말자.
효율적인 개발자가 되고자 노력해보자.
물론, 모든 코드가 극한의 효율을 추구할 순 없지만(가독성, 확장성 측면이 중요한 경우) 효율성을 추구하지 않는 경우에는 제각각 이유가 존재한다.
문제를 풀이한 전략에서 보다 최적화할 요소는 없는지, 더 나은 코드는 없는지 고민해 보는 시간을 충분히 갖자.
