[edx] 알고리즘 기초

Hyeon Soo·2022년 5월 22일

1. 들어가기전에

알고리즘은 특정한 문제를 해결하기위한 절차를 의미한다.
비유를 들자면 일종의 자동차 길찾기와 비슷하다. 특정 장소에서 다른 장소로 자동차를 이용하여 가는 방법은 하나가 아니라 매우 여럿일 수 있다. 즉, 특정 문제를 해결하는 알고리즘은 하나가 아니다.
그렇기때문에, 알고리즘은 '최대한 효율적인' 해결을 목표로 한다.
자동차 길찾기에서의 효율은 최단일수도 있고, 최속일수도 있다. 알고리즘 또한, 시간효율을 최대화하는 방법이 있을 수 있고, 메모리효율을 최대화한 방법도 있을 수 있다.
이후로는 정렬/패턴일치/그래프순회에 있어서 유명한 일부 알고리즘들을 소개할 예정이다.

컴퓨터공학에서 재귀란 프로그래밍을 하는 방법으로, 함수나 메서드가 도중에 자기자신을 호출하도록 만드는 것을 말한다.
이러한 자기참조는 원래로는 루프를 돌게된다. 그렇기에 재귀를 이용할 때는, 루프에서 벗어날 수 있는 조건을 반드시 만들어주어야 하며, 그 조건에 반드시 진입할 수 있어야한다.
프로그램을 구동하면, 항상 위에서부터 아래로 코드를 실행하기 때문에, 재귀함수에 진입하면, 진입하는 재귀코드에서 멈추고 새로운 재귀함수를 쌓는다. 계속 새로운 재귀함수를 쌓다가, 조건을 만족하면 값을 그 이전의 재귀함수코드에 반환하고, 이후의 코드를 실행하여 다시 그 이전에 재귀함수코드에 반환하는 방식으로 모든 함수가 실행을 마칠때까지 반복한다. Stack에 재귀함수가 계속 쌓이다가 점차 맨 위부터 하나씩 뽑혀나간다고 생각하면 된다.
재귀함수를 이용하면, 코드를 훨씬 간결하게 작성할 수 있다. 예시로 tree에서 pointer reinforcement를 사용해 node의 변동을 더 단순하게 작성할 수 있었던 것을 들 수 있다.

Brute-Force는 암호학에서 무차별대입을 의미하는데, 예를들면 숫자로 이루어진 4자리수 비밀번호를 찾는다면, 0000부터 9999까지 가능한 모든 숫자를 다 대입해보는 것을 말한다.
항상 적용할 수 있는 것은 아닐지 몰라도, 다른 문제를 해결하기 위한 알고리즘을 구축하는 일에도 brute-force의 발상을 적용하는 것은 가능하다. 단순히, 있을 수 있는 모든 경우를 하나하나 확인하며 해결법을 찾는다면, 거의 모든 문제를 해결할 수는 있다.
Brute-Force의 방법은, 시간과 메모리가 무한히 주어진다면, 100%원하는 결과를 도출할 수 있다는 장점을 가지고 있다. 단점으로는, 대부분의 문제는 경우의 수가 아주 많고 복잡하기 때문에, brute-force의 방법으로는 원하는 시간 내에 목적을 달성하기 어려운 경우가 많다.
그래도, 실제 코드 구축의 복잡함은 차치한다 했을 때, brute-force는 문제의 해결방법 자체는 도출해준다.

이상의 내용은 edx 플랫폼을 통해 GTx에서 제공하는 Data Structures & Algorithms 강의의 내용을 개인적으로 정리한 것입니다. 그렇기 때문에, 부정확한 내용 혹은 잘못 이해하고 있는 내용이 있을 수 있으니 양해 부탁드립니다.