자바로 알고리즘 시작하기 1 - 알고리즘 왜 하나요?

알고리즘 왜 해야해요?

행간에 이런 말이 있다.

알고리즘 잘 하는거랑 개발 잘 하는건 다른 거라던데요?

(이는 개인에 따라 다른 관점이 있을 수 있는 부분이며, 철저히 제 사견임을 밝힙니다.)

 

어느정도 동의는 한다. 우리는 대부분 코딩테스트를 통과하기 위해 알고리즘을 학습한다. 물론, 알고리즘 구현 능력이 실무 개발 역량에 전혀 영향을 미치지 않는다고 할 순 없겠지만, 어느정도 분명 구분되는 영역이라 생각한다. 비유를 하자면 알고리즘 실력과 개발 실력의 상관관계는 마치 토익 실력과 회화 실력 사이의 관계와 유사하다고 생각한다. 즉, 토익을 잘 하면 회화를 잘 할 확률도 높고, 상대적으로 수월하겠지만, 사실 엄격하게 말해선 회화를 잘 하고 싶으면 회화를 공부하는 게 더 효율적이란 이야기다.

 

그럼에도 불구하고, 현업자들은 이렇게 말한다. "알고리즘 못하면서 개발 잘 하는 사람도 있다. 하지만 알고리즘 잘 하는 사람은 거의 대부분 개발도 잘 한다." 이러한 점을 미루어 보았을 때, 개발자로서 응당 지녀야 하는 '불굴의 의지'와 '집념'과 같은 역량이 알고리즘을 수양하면서 자연스럽게 트레이닝된다고 하는 점에서는 알고리즘의 필요성에 대하여 강력하게 동의하는 바이다.

 

아울러 이런 관점도 있다. 프로그래밍이 어려운 이유는 하드 로직을 사용해야 하기 때문이라는 것. 대체로 프로그래밍의 진입 장벽에 대하여 논할 때 "프로그래밍 언어의 문법이나 기술 학습에 대한 어려움"은 널리 알려져 있어 많이 거론되지만, 프로그래밍을 할 때에는 소프트 로직이 아닌 하드 로직을 사용해야 한다는 점에 대하여는 많이 다뤄지지 않는다고 한다. 쉽게 말해 소프트 로직은 직관의 영역이고, 하드 로직은 엄격함의 영역인데, 프로그래밍은 '느낌'으로만 마무리 되어서는 안되며 엄격하게 관철하여 꼼꼼하게 논리로 무장해야 한다. 어려운 것은, 이게 생각보다 어려운 사람들이 많다는 것이다. 하지만 알고리즘 문제는 이러한 하드 로직을 구현하는 사고력을 길러준다고 생각한다. 따라서 알고리즘을 잘 푸는 것이 프로그래밍에 도움이 된다고 할 수 있다.

알고리즘 문제 접근법

알고리즘을 제대로 학습하기로 마음을 먹었으니, 어떻게 접근할지 차근차근 논리적으로 방법론을 구축하자. 아래 내용은 '코딩테스트 문제'를 접근하는 방법론이며, 다음과 같이 정리할 수 있다.

0. 만약 해당 문제가 잘 아는 유형의 문제라면, 알고 있는 직관적인 해법을 바탕으로 시간복잡도를 계산한다. 그 알고리즘으로 해결 가능하다는 판단이 되면 밀고 나간다.
1. 직관적으로 알지 못하는 유형의 문제라면, 완탐 기준으로 시간복잡도를 계산해 본다.
2. if (time limit 안에 들어올 수 있다면) : bruteforce로 접근한다.
3. else : 그 외 그래프, DP, 그리디 등 적절한 알고리즘을 고려하여 접근한다.

알아야 할 사항

위와 같이 알고리즘 문제에 순탄하게 접근하기 위해서는 다음 내용들을 알아야 한다.

1. 자료구조
2. 시간복잡도
3. 알고리즘

자료 구조는 모든 알고리즘 학습의 근간이 된다. 로직 상에서 기본적으로 적절한 자료구조가 존재한다. 예를 들어, 기본적인 BFS 알고리즘의 경우 먼저 입력된 순으로 차근차근 탐색하고자 Queue를 사용하고, DFS 알고리즘은 일정 edge path를 기준으로 전부 탐색한 뒤 그 다음 edges를 탐색하기 위해 LIFO 구조가 적절하기 때문에 stack 또는 재귀를 사용한다. 이처럼 해당 알고리즘을 이해하기 위해서도, 그리고 스스로 로직을 구성할 때 최적화를 자유롭게 하기 위해서도 자료구조에 대한 이해는 필수적이다.

 

아울러 시간복잡도 또한 알고리즘을 선택할 때 중요한 지표이다. 대개의 경우 최악의 경우를 기준으로 해당 로직이 아무리 오래 걸려도 어느 정도의 시간이 걸릴지를 계산하여 해당 알고리즘이 적절한지를 판단하게 된다. 즉, 시간복잡도를 계산할 수 있다면 알고리즘의 적합성을 판단할 수 있는 중요한 지표가 되므로 이를 잘 아는 것도 필수적이다.

그리고 나서 알아야 하는 것이 알고리즘들이다. 대표적인 유형들로는 다음 항목들이 있다.

• 완전탐색을 비롯한 문자열 빡구현 문제들(?)
• 백트래킹
• 그래프 알고리즘 (DFS/BFS/...)
• DP
• 그리디

위 항목만 나온다고 할 순 없지만, 위 항목들도 제대로 못하면서 다른 알고리즘을 열심히 파는 건 비효율적이란 이야기다. 따라서 위 항목들은 조금은 편안하게 풀 수 있을 때 다른 고급 알고리즘에 대한 욕심을 내 보자. (근데 위 알고리즘들만 제대로 하기에도 난 아직 많이 많이 벅차다ㅎㅎㅎ...)

다음 게시글은

자바에서 다룰 수 있는 자료구조에 대하여 한번 알아보겠다.