오늘 포스트는 제곧내, 자료구조와 알고리즘이 도대체 왜 중요한가에 대해 다룬다.

🙋‍♀️ 이 게시물에는 초짜 개발자의 생각을 기반으로 쓴 것이니 참고 바람.

자료구조란?

자, 일단 자료구조라는 것은 뭘까?
위키의 정의에 따르면, 자료구조란 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미한다.

결국 데이터를 어떻게 다룰 것인가, 어떻게 저장하고 어떻게 꺼내올 것인가 하는 데이터 사용방법이다.

그래 자료구조,, 사용방법 그거 뭔데 어떻게 하는건데

걱정하지마라. 이미 우리 고인물 석박사들이 다 만들어 놓으심

하지만 우리는 이미 늘상 자료구조를 쓰고 있다.

대표적으로 배열을 들수 있다.

우리는 배열이 크기를 고정해서 인덱스를 부여하므로, 데이터 읽기가 빠르고 효율적이다! 라는 것을 알고 있다.
"배열"은 마치 일직선으로 데이터를 저장한다고 해서 "선형(직선 모양, linear) 구조"의 자료구조를 가지고 있다.

근데 우리는 이 배열이 추가/삭제에 대해 속도나, 메모리 관리가 비효율적인 것 또한 알고 있다. 그래서 우리는 linkedList를 떠올리게 된다.

이처럼 어떤 기능/상황의 특성에 따라 우린 각각 다른 자료구조를 쓴다. 왜? 효율성을 위해서!

자료구조의 종류

자료 구조를 형태상으로 구분하면,

일단은 크게 선형구조, 비선형구조로 나눌 수 있다.

• 선형 구조(linear structure) : 말 그대로 "선" 모양처럼 순차적으로 데이터를 저장하는 방식이다. 즉, 하나의 데이터 바로 다음에 또 다른 하나의 데이터가 있는 1:1 구조를 가지고 있다.

• 비선형 구조(nonlinear structure): "선"이 아닌 구조처럼 하나의 자료뒤에 여러개의 자료가 있을 수 있는 방식이다. 선형구조와 다르게 하나의 데이터가 여러 개의 데이터를 가리킬 수 있으며 즉, 1:n 구조를 가지고 있다.

그 다음으로는

• 단순 구조 : 정수, 실수, 문자, 문자열 등의 컴퓨터가 기본적으로 제공하는 자료형

• 데이터를 효율적으로 이용할 수 있도록 파일에 저장하는 방법인 파일(file) 구조

이렇게 참고만 하자.

자료구조의 필요성

그럼 다시 우리가 자료구조를 알아야 하는 이유는 정리하자면 다음과 같다.

✅ 데이터를 체계적으로 저장하고, 효율적으로 활용하기 위해
✅ 불필요한 메모리, 성능 낭비를 줄이기 위해

우리가 데이터를 다룰 줄 아는 다양한 방법을 알고 있다면, 어떠한 문제상황에 대해 알맞은 자료구조를 사용해서 문제를 효율적으로 해결 할 수 있을 것이다.
즉, 자료구조는 알고리즘이 데이터를 효율적으로 사용할 수 있게 도와주는 핵심 부품 역할을 한다.!

마치 학부생시절 이동수단은 지하철밖에 몰라서 걸어갈 수 있는 거리도 전철만 탄 필자같이,, 돈낭비 시간낭비 체력낭비를 할 수 있는 것,,

알고리즘

자, 그럼 알고리즘은 무엇인가?

위키에 따르면,

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

간단히 어떤 문제를 풀기 위한 단계적 절차 라고 이해하자.

알고리즘의 필요성

우리가 컴퓨터로, 스마트폰으로 수행하는 많은 작업들이 알고리즘에 의해 수행된다.

예를 들어 만약 인터넷에서 검색을 하는 데에는 검색 알고리즘이 사용된다. 근데 만약 내가 "햄" 을 검색했는데 "햄스터"가 나온다면 일단 빡칠것이다.

결과는 제대로 나왔는데 결과를 내기까지 1시간이 걸린다면? 🤷‍♀️ 일단 한국인은 결과가 나오기 전에 화면을 끌거지만, 내가 햄 검색하는데 1시간이나 기다려야하나 하고 이제 검색에 대한 실용성과 필요성을 못 느끼게 될 것이다.

이처럼 검색 알고리즘은 사용자가 입력한 키워드가 문장에 들어간 문건들을 찾아내고 이 중에서 관련성이 높은 것을 순서대로 정렬해야한다. 당연히 이 연산이 수행되는 속도는 빠를수록 좋고, 정확도가 높을수록 좋을 것이다.

우리는 이 연산을 수행할때 어떤 자료구조를 활용해서 알고리즘을 짜야 효율적인지 고민해야하는 것이다.

더욱 더 효율적이고 성능 좋은 것을 추구하는 것은 소비자로써 당연한 것이다.
그럼 우리는 어떤 문제에 대해 정확하고 효율적으로 결과를 출력하기 위해 다음과 같은 조건을 생각해야 한다.

알고리즘의 조건

• 입력 : 외부에서 제공되는 자료가 0개 이상 존재한다.
• 출력 : 적어도 2개 이상의 서로 다른 결과를 내어야 한다.(즉 모든 입력에 하나의 출력이 나오면 안 됨)
• 명확성 : 수행 과정은 명확하고 모호하지 않은 명령어로 구성되어야 한다.
• 유한성(종결성) : 유한 번의 명령어를 수행 후(유한 시간 내)에 종료한다.
• 효율성 : 모든 과정은 명백하게 실행 가능(검증 가능) 한 것이어야 한다.

알고리즘 분류

알고리즘에도 다양한 종류가 있다. 간단히 분류를 해보자면

• 구현 : 재귀적 알고리즘, 연역적 알고리즘, 결정론적 알고리즘, 근사 알고리즘, 양자 알고리즘 등.
• 설계 : 무차별 대입 공격, 분할 정복 알고리즘, 그래프 순회, 분기 한정법, 확률적 알고리즘, 리덕션, 백트래킹 등.
• 최적화 문제 : 선형 계획법, 동적 계획법, 탐욕 알고리즘, 휴리스틱 함수 등.
• 이론적 분야 : 검색 알고리즘, 정렬 알고리즘, 수치 알고리즘, 그래프 알고리즘, 문자열 알고리즘, 암호학적 알고리즘, 기계 학습, 데이터 압축 등.

좋은 알고리즘?

그럼 좋은 알고리즘 이란 뭘까?🤷‍♀️

우리는 흔히 알고리즘을 판단할 때 공간복잡도 와 시간복잡도를 계산하게 된다.

• 공간복잡도 : 총 저장공간의 양
• 시간복잡도 : 총 소요시간

✅ 시간복잡도가 적다 = 속도가 빠르다
: 속도가 빠르다는 것은 결과값을 가지고 올때까지의 시간이 짧다는 것을 의미한다. 결과의 값이 같다면 짧은 시간안에 올바른 결과를 얻을 수 있는 알고리즘이 더 좋은 알고리즘으로 판단된다.

✅ 효율적이다
: 다른말로 프로그램을 실행할 때 사용하는 메모리 영역이 적어야 한다.
현대에는 대부분 대용량으로 바뀌면서 공간이 부족하지 않기 때문에 시간복잡도가 더 중요시 되는 것 같지만, 그래도 공간복잡도도 중요한 판단 기준이 된다.
대량의 메모리가 필요한것은 프로그램의 효율이 낮다는 것으로, 비용 면에서 메모리 영역이 적은것이 더 좋다고 말할 수 있다.

하지만 고려해야할 것이 더 있다.

✅ 유지보수성을 위한 이해하기 쉬운 코드를 짜는 것도 중요하다.
복잡하고 난해한 알고리즘을 작성하면 나중에는 본인조차 이해하기가 어렵게 되고, 여러 사람들과 협업 시 다른 사람이 곧바로 이해할 수 없게되어 문제가 생길 수 있다.

또한 이러한 알고리즘은 올바른 결과가 나타나는지도 검증하기 어렵기 때문에 틀린 부분을 찾기도 어렵게 되어 작업 능률이 저하된다.

✅ 재이용하기 쉽다
: 과거에 작성한 것을 그대로 사용하거나 부분적으로 이용할 수 있다면 새로운 프로그램을 만드는 데 필요한 시간을 단축시킬 수 있다.