[Algorithm] 알고리즘이란? 알고리즘 vs 자료구조 차이란?

유튜브 보다가 문득 떠올라서 알고리즘이 뭔지, 알고리즘과 자료구조 차이는 뭔지 확인하고 정리하기로 했다.

알고리즘의 사전적 정의는 아래와 같다.

어떤 문제의 해결을 위하여, 입력된 자료를 토대로 하여 원하는 출력을 유도하여 내는 규칙의 집합. 여러 단계의 유한 집합으로 구성되는데, 각 단계는 하나 또는 그 이상의 연산을 필요로 한다.

뭔가가 입력되면 어떤 처리가 되어 내가 원하는 출력이 나오게 되면 그것이 알고리즘인 것 같다.

어딘지 딥러닝이랑 비슷한 느낌이 들긴 하는데, 일단 알고리즘이라는 단어의 뜻에 집중한다. 이번엔 위키백과의 내용이다.

https://ko.wikipedia.org/wiki/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

알고리즘 - 위키백과, 우리 모두의 백과사전

알고리즘은 어떤 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것, 계산을 실행하기 위한 단계적 절차를 의미한다. 즉, 문제 해결에 필요한 계산 절차 또는 처리 과정의 순서를 뜻한다. 프로그램 명령어의 집합을 의미하기도 한다. 알고리즘은 연산, 데이터 마이닝(기계 학습) 또는 자동화된 추론을 수행한다.

https://en.wikipedia.org/wiki/Algorithm

Algorithm - Wikipedia

알고리즘은 특정 문제를 해결하거나 계산을 수행하기 위해 잘 정의되고 컴퓨터로 구현 가능한 명령어의 유한 시퀀스다. 알고리즘은 항상 모호하지 않으며 계산, 데이터 처리, 자동화된 추론 및 기타 작업을 수행하기 위한 사양으로 사용된다. 대조적으로 휴리스틱은 최적이 아닐 수 있지만 상황에 따라 충분한 솔루션을 생성하기 위해 실용적인 방법 또는 다양한 추정을 사용하는 문제해결에 사용되는 기술이다.
알고리즘은 유한한 공간, 시간 내에서 함수를 계산하기 위한 잘 정의된 형식 언어로 표현될 수 있다. 초기 상태 및 초기 입력(비어있을 수 있다)에서 시작해 명령어는 실행 시 유한의 잘 정의된 연속 상태를 거쳐, 결국 "출력"을 생성하는 계산을 설명하고 최종 종료 상태에서 종료된다. 한 상태에서 다음 상태로의 전환이 반드시 결정적인 것은 아니다.

결국 정리하면 문제 해결방법이란 거다. 하지만 단순한 해결방법이 아닌 항상 명확한 해결방법이란 게 위키백과를 통해 정리한 알고리즘의 정의다.

그럼 라면 끓이는 법도 알고리즘, 수저 차리는 것부터 시작해서 밥 먹고 치우는 것도 하나의 알고리즘이라 볼 수 있다.

 

그럼 이 알고리즘은 왜 필요한 걸까? 그리고 어떤 장점이 있길래 개발자 취업시장과 인터넷 등지에서 그렇게 알고리즘을 말하는 걸까? 가끔 알고리즘으로 사람을 판단하는 광기의 알고리즘무새가 보이기도 한다

https://www.technotification.com/2019/02/importance-of-algorithms-programming.html

What's the Importance of Algorithms in Computer Programming?

1. 컴퓨터 프로그램의 효율성 향상 : 프로그래밍에는 문제를 해결하는 다양한 방법이 있다. 그러나 사용 가능한 방법의 효율성은 다양하다. 어떤 방법은 다른 것들보다 더 정확한 답변을 제공하는 데 적합하다. 알고리즘은 문제를 해결하는 가장 좋은 방법을 찾는 데 사용된다. 그리 함으로써 프로그램의 효율성이 향상된다. 프로그래밍과 관련해서 효율성은 다른 의미로 쓰일 수 있다. 그중 하나는 소프트웨어의 정확성이다. 최상의 알고리즘을 쓰면 컴퓨터 프로그램이 매우 정확한 결과를 만들 수 있다. 또 다른 의미는 속도다. 프로그램이 문제를 실행하는 속도를 향상하기 위해 알고리즘을 쓸 수 있다. 단일 알고리즘은 프로그램이 문제를 해결하는 데 걸리는 시간을 줄일 수 있다.

2. 자원의 적절한 활용
일반적인 컴퓨터에는 다른 자원이 있는데 그 중 하나가 컴퓨터 메모리다. 실행 단계 동안 컴퓨터 프로그램은 약간의 메모리가 필요하다. 일부 프로그램은 다른 프로그램보다 더 많은 메모리 공간을 사용한다. 컴퓨터 메모리의 사용량은 사용된 알고리즘에 따라 다르다. 알고리즘을 올바르게 선택하면 프로그램이 최소한의 메모리를 쓰게 된다. 메모리와 별도로 알고리즘은 프로그램에 필요한 처리 능력의 양을 결정할 수 있다.

https://stackoverflow.com/questions/3962280/whats-the-importance-of-data-structures-and-algorithms-for-programming

Whats the importance of data structures and algorithms for programming?

효율적인 코드를 작성하고 최적 또는 거의 최적의 방법으로 문제를 해결하는 데 도움이 된다. 이것이 없다면 넌 바퀴를 재발명하게 될 것이다. 또한 더 나은 설계, 구현을 장려함으로써 코드를 보다 쉽게 유지 관리할 수 있도록 코드를 구조화하는 데 도움이 된다.

이미 문제를 해결하는 도구가 발명되어 있는데 알고리즘을 쓰지 않으면 쓸데없이 다시 바퀴부터 만들 수 있다는 말 같다. 확실히 이런 경우가 생기면 작업 시간은 늘어나고 아웃풋이 생기지 않으니 효율적으로 일한다고는 볼 수 없겠다.

 

그럼 이 알고리즘의 종류는 어떤 것들이 있을까? 한번 찾아봤더니 종류가 꽤 많아서 다 적기 귀찮으니 링크로 대체한다.

http://dawoonjeong.com/algorithm-categories/

[Algorithm] 알고리즘 분류

그리고 알고리즘의 특성은 아래와 같다고 한다. 꼭 이것들을 모두 만족해야 하는 건 아닌듯하지만 지키면 좋다 정도인 것 같다.

https://arisu1000.tistory.com/27673

알고리즘(algorithm) 개념 정리

유한성 : 알고리즘의 단계들은 반드시 유한한 횟수를 거친 후에 종료돼야 한다.
효율성 : 모든 과정은 명백히 실행(검증) 가능한 것이어야 한다
명확성 : 알고리즘의 각 단계는 명확한 명령어로 정의돼야 한다
입력 : 알고리즘은 0 또는 그 이상의 입력들을 갖는다. 즉 밖에서 들어오는 데이터가 없거나 1개 이상이다.
출력 : 알고리즘은 하나나 그 이상의 출력들을 갖는다. 즉 최소한 출력이 1개라도 있어야 한다.

 

그럼 자료구조란 뭘까? 자료와 구조를 나눠서 검색해보면 이렇게 나온다.

자료 : 연구나 조사 따위의 바탕이 되는 재료, 만들거나 이루는 데 바탕이 되는 물자나 재료
구조 : 부분이나 요소가 어떤 전체를 짜 이룸. 또는 그렇게 이뤄진 얼개, 일정한 설계에 따라 여러 가지 재료를 얽어서 만든 물건

단어 각각을 놓고 보면 자료구조는 어떤 것의 재료가 되는 것(자료)을 엮어서 만들어낸 어떤 것이라는 뉘앙스의 뜻일 것 같다.

이제 자료구조의 사전적 정의를 확인해보자.

자료구조 : 추상적으로 나타낸 자료의 모습과 그것을 다루는 연산에 대한 정의

 

유추한 뜻과는 제법 많이 다르다. 추상적으로 나타낸 자료의 모습이란 뭘까? 그 자료를 다루는 연산에 대한 정의?

다음으로 위키백과에선 뭐라고 말하는지 확인해봤다.

https://ko.wikipedia.org/wiki/%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0

자료 구조 - 위키백과, 우리 모두의 백과사전

자료구조는 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미한다. 더 정확히 말해, 자료구조는 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미한다.

 

하나 이상의 데이터 간의 관계, 그리고 데이터에 적용하는 함수들을 다루는 것이 자료구조인 것 같다. 

다른 사람들은 자료구조의 정의를 어떻게 설명해놓았는지 확인해보자.

https://searchsqlserver.techtarget.com/definition/data-structure

What are Data Structures? - Definition from WhatIs.com

자료구조는 데이터를 구성, 처리, 검색 및 저장하기 위한 특수한 형식이다. 자료구조에는 몇 가지 기본, 고급 유형이 있으며 모두 특정 목적에 맞게 데이터를 배열하도록 설계됐다. 자료구조는 사용자가 적절한 방식으로 필요한 데이터에 쉽게 접근하고 작업할 수 있도록 한다...(중략)... 각 자료구조에는 데이터 값, 데이터 간의 관계 및 (경우에 따라) 데이터에 적용할 수 있는 함수에 대한 정보가 포함된다.

https://www.javatpoint.com/data-structure-tutorial

Data Structures | DS Tutorial - javatpoint

자료구조 이름은 메모리에서 데이터를 구성하는 것을 나타낸다. 이 데이터 구성 방법에는 여러 가지가 있다. 배열은 데이터가 순차적으로 저장되는 메모리 요소의 모음이다. 즉, 배열이 요소를 연속적으로 저장한다고 말할 수 있다. 이 데이터 구성은 자료구조 배열의 도움으로 수행된다. 자료구조는 C, C++, JAVA 등과 같은 프로그래밍 언어가 아니다. 메모리의 데이터를 구조화하기 위해 모든 프로그래밍 언어에서 사용할 수 있는 알고리즘 세트다. 메모리에 데이터를 구조화하기 위해 n개의 알고리즘이 제안됐으며, 이런 모든 알고리즘을 추상 데이터 유형이라고 한다.

https://www.javatpoint.com/data-structure-introduction

DS Introduction - javatpoint

자료구조는 데이터를 효율적으로 사용할 수 있도록 컴퓨터에서 데이터를 효과적으로 저장하고 구성하는 방법을 제공하는 데이터 요소 그룹으로 정의할 수 있다. 자료구조의 몇 가지 예로는 배열, 링크드리스트, 스택, 큐 등이 있다.
자료구조는 컴퓨터 과학의 거의 모든 측면(OS, 컴파일러 설계, 인공지능, 그래픽 등)에서 널리 쓰인다. 자료구조는 개발자가 데이터를 효율적으로 처리할 수 있도록 하므로 많은 컴퓨터 과학 알고리즘의 주요 부분이다. 소프트웨어의 주요 기능은 사용자의 데이터를 가능한 한 빨리 저장하고 검색하는 것이므로 SW 또는 프로그램의 성능 향상에 중요한 역할을 한다.

https://www.integralist.co.uk/posts/data-types-and-data-structures/

Data Types and Data Structures ⋆ Mark McDonnell

자료구조는 효율적인 접근 및 수정을 허용하는 방식으로 저장, 구성되는 데이터 유형 '값'의 모음이다. 어떤 경우에는 자료구조가 특정 데이터 유형의 기본 구현이 될 수 있다. 예를 들어 복합 데이터 유형은 기본 데이터 유형 또는 기타 복합 유형으로 구성된 자료구조인 반면, 추상 데이터 유형은 특정 데이터에 대한 일련의 동작(어떤 의미에서 인터페이스와 거의 유사함)을 정의한다. 구조는 해당 데이터 유형에 대한 구체적인 구현으로 사용될 수 있다.
자료구조는 일반적으로 4가지 형식이 있다.
1. 리니어 : 배열, 리스트
2. 트리 : 바이너리, 힙, 공간 분할(space partitioning) 등
3. 해시 : 분산 해시 테이블(distributed hash table), 해시 트리 등
4. 그래프 : 결정(decision), 지시(directed), 비순환(acyclic) 등

 

다른 글들을 추가로 더 찾아봤지만 결론은 자료구조는 데이터에 효율적으로 접근하고 그 데이터를 수정하기 위해 사용되는 데이터들의 모음이라는 뜻을 갖고 있었다.

여기서 알고리즘과 자료구조의 차이를 알 수 있다.

 

• 알고리즘 : 문제 해결에 필요한 절차들의 순서
• 자료구조 : 데이터에 효율적으로 접근하고 수정할 수 있도록 하는 데이터들의 모음

그런데 이 2가지는 왜 쓰이는 걸까? 옛날 뚱땡이 모니터의 컴퓨터를 쓰던 시절이라면 몰라도 요즘은 SSD가 테라바이트 단위로 나오고, 램 또한 64GB 이상을 장착할 수 있는 메인보드 등 좋은 컴퓨터 부품들이 넘쳐나는 시대다. 자료구조와 알고리즘은 왜 필요한 걸까?

 

카메라를 하나 사려고 한다고 가정한다. 그런 당신의 눈에 마음에 드는 디자인의 카메라가 있어서 봤더니, 내 눈으로 보는 것과 완전 동일한 화질의 사진을 제공하는 카메라다.

그런데 사진을 한번 찍으면 출력하는 데 몇 시간이 걸리고, 뽑은 사진을 컴퓨터에 저장하려고 하니 1장에 몇 기가바이트나 한다. 이 카메라를 구매할 것인가?

대다수의 사람은 사지 않을 것이다. 왜냐면 카메라의 기능은 정말 매력적이다. 내 눈으로 보는 것과 똑같은 화질의 사진을 제공하니까. 그런데 그걸 얻기 위해 수반되는 비용들이 너무 크다. 바꿔 말해 좋은 기능에 반해 실행 시간이 거지같이 길다. 또한 메모리 효율도 거지 같다.

그러나 누구는 이렇게 말할 수 있다. 시스템 설계 부분에서 고려해야 하는 문제인 거 같은데 개발자는 신경 쓰지 않아도 되는 거 아니냐고. 개미 눈물만큼의 일리는 있다.

 

이번엔 어떤 정보 검색 앱이 있다고 가정한다. UI도 세련됐고 UX도 흠잡을 데 없으며, 인공지능도 도입되어 있어서 내가 검색한 내용과 유사한 또는 다른 사람들이 많이 찾아본 내용들을 같이 보여준다. 원하는 내용이 pdf나 txt 파일인 경우 이것의 빠른 다운로드 또한 지원한다. 안드로이드/아이폰을 모두 지원하는 것은 말할 것도 없다.

그런데 앱을 실행하려면 아래와 같은 조건을 만족해야 한다.

 

• 앱 실행까지 걸리는 시간 : 1시간
• 검색 후 결과를 받아보기까지 걸리는 시간 : 3시간

 

위의 예시들은 터무니없이 극단적이다. 세상의 어떤 카메라 생산자도, 앱 개발자도 저런 식으로 만들진 않을 것이다.

하지만 앱 최적화 작업은 왜 할까? 웹 페이지에서 다음 페이지의 로딩을 0.n 초라도 빠르게 하려는 이유는 뭘까? 삼성 등 유명한 회사에서 출시되는 기기들은 이전 세대보다 더 빠른 속도를 가진 게 당연한 걸까?

소비자가 그걸 원하기 때문이다. 소비자는 더 빠르고 눈으로 확실히 보이는 개선된 걸 원한다. 이 소비자의 니즈를 만족시키는 제품을 만들어 팔아야 기업의 매출도 오른다. 그래서 기업과 그곳에 속한 개발자들은 종래의 것보다 더 효율적이고 성능 좋은 방법을 추구한다.

 

이것을 가능하게 해주는 것이 자료구조와 알고리즘이다. 상황에 따라 적절한 자료구조와 알고리즘을 사용하면 더 좋은 프로그램(제품)이 만들어지고, 소비자가 원하는 데이터까지 접근하는 데 걸리는 시간을 획기적으로 줄여준다.

그러나 난 이 글의 결론을 "자료구조와 알고리즘 엄청 중요하니 개발 처음 공부할 때부터 바로 시작하세요!"라고 끝맺으려는 건 아니다. 아직 자전거가 뭔지도 모르고 자전거에 흥미도 붙이지 않았는데 외발자전거 타면서 저글링하는 건 중요한 기술이니 바로 연습하라고 하는 거랑 다를 바가 없다고 생각한다.

일단 개발에 흥미를 붙여야 한다고 생각한다. 그리고 그 언어로 아주 간단한 프로그램이나 웹(텍스트 게임, 아주 간단한 그래픽을 이용한 초간단 키오스크, 회원 가입하면 환영 문구를 보여주는 웹 사이트)을 닥치는 대로 만들어본 뒤, 실행 속도가 내 생각과 달리 획기적으로 거지 같은 경우 자료구조와 알고리즘을 봐야 한다고 생각한다.

알고리즘과 자료구조 물론 중요하긴 하지만, 그 중요함이 개발에 흥미를 붙이고 뭔가를 만들어보는 것보다는 우선순위가 뒤떨어진다고 생각한다.