전자기기가 많이 보급되면서 동시에 SW도 많이 보급되고 있다. 우리 삶에 있어서 SW를 빼놓으면 정말 불편할 것이다. 우리가 사용하는 SW는 바로바로 우리가 원하는 답을 가져다 준다. 만약에 우리가 사용하는 프로그램이 바로 답을 주지 않고 몇분, 몇시간을 기다려야한다면 과연 사람들이 사용할 것인가? 당연 사용하지 않을 것이다. 그래서 우리는 더 빠르고 효율적인 프로그램을 만들어야하고 이때 좋은 알고리즘이 필요하다.
알고리즘 카테고리에서는 알고리즘을 만드는 기법들에 대해서 포스팅할 예정이다. 우리는 알고리즘을 만드는 기법, 문제에 대한 접근 방법만 알고 있다면 복잡한 문제도 풀 수 있을 것이다.
알고리즘이란 무엇인가? 우리가 구하고자 하는 과제들을 문제(Problem)이라고 한다. 문제란 해답(solution)을 찾으려고 물어보는 질문이다. 이때 문제는 알고리즘으로 푼다(solve)라고 표현한다. 어렵거나 복잡하게 생각할 수 있겠지만 바로 문제를 푸는 방법이다.
그렇다면 이러한 접근 기법만 있으면 모든 문제를 풀 수 있는가? 답은 No다. 많이들 '이건 슈퍼컴퓨터로도 몇십년 계산해야해'라는 등의 말을 들어본적이 있을 것이다. 바로 Time Complexity, 쉽게 말해서 연산이 너무 많아서 물리적으로 구하는 데 오랜 시간이 걸릴 때 Time Complexity가 높다고 표현한다. 실제로도 몇십년은 고사하고 몇일만 걸려 우리는 꺼려할 것이다. 이렇게 어려운 문제들을 NP문제라고 한다. 정확한 정의는 이후 포스팅에서 다루겠다.
위와 같이 어려운 문제는 우리 주변에 정말 많이 있다. 어려운 문제라고 해서, 우리가 풀 수 없다고 해서 안푸는건 아니다. 최대한 빠르게 구해보려고 할것이다. 만약 이것이 아니라면 우리는 정답에 가장 가까운 값을 찾으려고 할 것이다. 바로 그 방법은 approximation시킨다고 말한다. 가능한 빠르게 답을 구하려고 하는 기법도 있고 근사값을 구하는 다양한 알고리즘들이 있다. 근사값을 구하는 방법은 인공지능 카테고리에서 다루도록 하겠다.
알고리즘 카테고리에서 다룰 기법들은 다음과 같다.
- Divide & Conquer
- Dynamic Programming
- Greedy Algorithm
- Back Tracking
- Branch and Bound
- Genetic Algorithm
'컴퓨터공학 > 알고리즘' 카테고리의 다른 글
Time Complexity (시간복잡도) (0) | 2018.12.24 |
---|
댓글