알고리즘(24.01.08)

알고리즘이란?

입력된 값이 단계적 절차를 거쳐서 결과값으로 반환되는 것을 알고리즘이라고 한다.

알고리즘이 프로그래밍 능력을 평가하기에 가장 좋다고한다.

알고리즘 문제는 프로그래밍 능력을 정량화할 수 있기때문이다.

 

데이터 분석가들이 왜 프로그래밍을 공부해야할까?

위 이미지 속 예시에서처럼 데이터가 DB에 적재되어있지 않을 경우

적재를 요청해야하는 경우가 있다.

이 때 개발자가 해당 업무를 처리해주길 무한정 기다릴수만은 없다.

평소에 개발 공부를 해놓았다면 데이터와 관련된 작업들은 일정 수준 혼자서 수행 가능할 것이다.

 

물론 SQL을 활용해서 데이터 추출하고 분석하는 것만해도 회사에서 1인분은 할 것이다.

하지만 알고리즘에 대한 이해를 바탕으로 프로그래밍을 할 수 있다면 분석 프로세스에서

내가 할 수 있는 영역이 넓어진다.

 

이는 곧 업무를 효율적으로 개선하여 더 나은 환경에서 업무를 수행할 수 있게됨을 의미한다.

 

자료구조

자료구조란 이름 그대로 자료를 담는 구조를 의미한다.

자료는 각각의 자료형의 특징에 맞는 그릇(=구조)에 담다야한다.

항상 자료에 효율적으로 접근할 수 있고, 수정할 수 있는 구조가 무엇일지에 대해서 고민해야한다.

 

1. 배열(Array)

 

배열은 가장 직관적인 자료형이라고한다.

인덱스의 개념이 존재하며

파이썬에서는 리스트라는 이름으로 구현된다.

 

배열에서

검색 연산과 추가연산이라는 개념이 있는데

검색연산의 경우 찾고자 하는 값을 바로 찾을 수 있으며

빅오표기법에따라 O(1)로 표기한다.

O(1)은 'O에 1의 시간에 찾을 수 있다.'라고 읽을 수 있다.

 ※ 빅오표기법에 대한 설명은 아래에 나온다.

 

반면 추가연산의 경우 위치에따라 시간이 달라진다.

만약 [1, 2, 3, 4, 5]라는 리스트(배열)이 있는데

3과 4 사이에 6이라는 숫자를 넣고싶다고 가정해보자

3과 4 사이에 6을 넣으면 4, 5는 한 칸씩 뒤로 밀려나게된다.

밀려나는만큼 연산의 시간이 늘어나는 것이다.

 

위에서 언급한 빅오표기법의 개념은 알고리즘의 효율성을 표현하는 방법으로, 특히 탐색 또는 분류 알고리즘의 수행 능력을 평가하는 척도이다.

빅오표기법은 알고리즘의 실행시간이 최악일 때를 표기하는 방법이며 오메가 표기법, 세타 표기법과 같은 다른 표기법에 비해 성능을 예측하기 용이하여 주로 사용된다고 한다.

 

검색연산을 할 때는 O(1)로 입력 값의 크기에 상관없이 항상 같은 시간이 소요되며

추가연산을 할 때는 O(n)으로 자료형의 길이만큼 반복된다.

 

앞에서 빅오표기법으로 시간이 얼마만큼 소요되는지를 확인했는데

소요되는 시간이 많을수록 시간복잡도가 높다고 볼 수 있다.

 

코딩을 잘 구현했는지(=알고리즘이 효율적인지)를 확인하기위해서는

시간을 얼마나 단축시켰는지, 메모리 사용량을 얼마나 줄였는지 두 가지가 기준이 된다.

두 가지 기준을 가지고서 현재의 자료형이 얼마나 비효율적인지 측정해보고,

효율적인 메소드, 함수를 구현하는 것을 목표로 해야한다.

 

위 이미지에서 store, retrieve, disk space는 각각

• store : 저장
• retrieve : 검색
• disk space : 메모리

을 의미하는데 자료형만 잘 선정해도 자료를 처리하는 속도가 엄청 빨라진다.

python의 경우 pickle이라는 자료형을 많이 사용하는데 저장과 검색이 굉장히 빠르다고한다.

 

2. 연결리스트(Linked List)

두번째 자료형은 연결리스트다.

연결리스트도 배열과 마찬가지로 연속된 데이터를 저장하기위한 자료구조다.

앞서 배열은 추가연산을 할 때 위치에따라 시간이 달라진다고했는데

연결리스트는 이같은 배열의 단점을 해결하기위해 고안된 자료구조다.

추가연산을 할 때는 배열보다 빠르지만 검색을 할 때는 반대로 배열보다 느리다.

그렇기 때문에 연결리스트가 배열보다 더 좋다고 볼 수는 없다.

 

대표적인 연결리스트 자료구조의 예시는 음악 플레이리스트의 이전곡, 다음곡이다.

 

3&4. 큐와 스택

 

세번째 자료구조는 '큐'와 '스택'이다.

큐는 FIFO(First In First Out)이라고 보면 된다.

다시 말해 먼저 들어온 값이 먼저 나가는 것이다.

 

반대로 스택의 경우 먼저 들어온 값 순서대로 차곡차곡 적재되며

가장 나중에 들어온 값이 가장 먼저 나간다.

 

스택의 예시를 한 번 살펴보자.

위 예시를 보면 종류별 괄호들이 들어왔다 나가는걸 확인할 수 있는데

가장 최근에 들어온 괄호와 그 다음에 들어오는 괄호가 같은 종류라면 두 괄호 모두 빠져 나간다.

그렇지 않다면 차례대로 적재된다.

 

5. 해시 테이블

해시 테이블은 key, value 형태인 데이터를 검색이 쉬운 형태로 저장하는 자료구조다.

파이썬에서는 딕셔너리라는 이름으로 해시 테이블 자료구조가 구현된다.

 

자료구조별로 시간복잡도가 다 다르다.

그렇다고해서 우리가 항상 시간복잡도를 고려해서 코드를 작성해야하는 것은 아니다.

우리가 코딩을 할 때는

먼저 관련 라이브러리가 있는지 검색해보고,

있다면 어떤 함수(or 어떤 자료형의 메소드)를 사용해야 하는지 찾아본다.

찾아봤는데 없지만 앞으로 자주 사용할 것 같다면 사용자 정의 함수로 만들어둔다.

만약 대용량 데이터에 자주 사용할 것 같으면 그제서야 성능을 고려하여 코드를 작성하면 되는 것이다.

보통 이 단계는 개발자에게 요청하게되는데

그들에게 툭 던지듯이 요청하는 것은 좋지 않고,

나 스스로 컨셉과 로직을 생각한 상태에서 개발자에게 최적화를 요청할 필요가 있다.

 

6. 트리

 

트리는 이름에서도 알 수 있는것처럼

나무 모양으로 데이터들이 계층적 구조를 갖는 자료구조라고 할 수 있다.

컴퓨터의 디렉토리 구조, 가족 구성도, 만다라트 모두 트리 구조라고 할 수 있다.

 

7. 그래프

 

연결 관계를 표현하는 자료구조를 모두 그래프라고 한다.

도로 정보, 소셜 네트워크 관계망, 인터넷 네트워크망 등이 그래프에 해당한다.

 

 

알고리즘

1. 그리디 알고리즘

 

알고리즘을 푸는 방법은 대표적으로 네가지 정도가 있다.

먼저 그리디 알고리즘은 매 선택의 순간에서 가장 최적의 답을 선택하여 적합한 결과를 도출하는 방법이다.

네이버 또는 카카오 지도에서 최적경로를 찾는 것이 여기에 해당한다.

 

2. 완전 탐색

 

두 번째 방법은 완전탐색으로

모든 경우의 수를 확인해보는 것이다.

자물쇠 따기가 그 예시인데 단순하고 확실하지만 시간복잡도가 높아질 가능성이 높다.

 

3. 이분 탐색

 

세번째 방법은 이분 탐색으로 up & down 게임을 생각하면 쉽게 이해될 것이다.

어떤 값을 얘기하고, 정답이 그 값보다 작은지 큰지를 판별해서 해당사항이 없는 부분은 제거하여 다음 판단을 진행한다.

이 경우 완전탐색처럼 모든 경우를 따져보는 것이 아니기때문에

시간 효율성을 극대화시킬 수 있다.

 

4. 재귀

 

마지막 방법은 재귀다.

재귀란 머리 두, 돌아갈 귀 자로

머리로, 그러니까 처음으로 다시 돌아간다는 말이다.

여기서 '처음'은 프로그래밍에서 '나 자신'을 의미한다고 볼 수 있다.

이 재귀 방법으로 알고리즘을 푼다는건

주어진 문제를 해결하기 위하여 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 방식을 의미한다.