프로그래밍을 처음 시작하면 자료구조와 알고리즘부터 접하게 된다.
알고리즘이란 말은 실무에서도 많이 사용하지만 요즘 핫한 인공지능에서도 알고리즘이라는 표현을 참 많이 쓰는데
자료구조는 뭐길래 컴퓨터과학의 시작이 되며 알고리즘은 뭐길래 강조되는지 그 개념을 알아보고자 한다.
자료구조란?
자료구조의 정의
자료구조란 쉽게 말하면 데이터를 담는 틀이다. 음식을 담을 때 어떤 음식이냐, 어떤 용도이냐에 따라 담는 그릇이 달라지듯 자료구조도 자유롭게 선택해서 사용할 수 있지만 주먹만한 음식을 담기 위해 테이블만한 그릇이 필요하지 않듯 컴퓨터가 효율적으로 처리할 수 있는 자료구조를 알고 자료의 형태와 알고리즘에 맞게 사용하는 것이 중요하다.
자료구조의 종류
자료구조는 크게 단순 자료구조(Primitive Data Structure)와 복합 자료구조(Non-Primitive Data Structure)로 나뉜다. 단순 자료구조는 정수, 실수, 문자, 문자열과 같은 컴퓨터가 기본적으로 제공하는 자료형을 의미하며 복합자료구조는 데이터가 순차적으로 연결되어 있는냐에 따라 다시 선형 자료구조(Linear Data Structure)와 비선형 자료구조(Non-Linear Data Structure)로 나뉜다.
선형 자료구조는 데이터가 순차적으로 연결된 자료구조를 의미하며 리스트, 연결 리스트, 스택, 큐, 힙이 있다.
비선형 자료구조는 하나의 데이터에 여러 데이터가 연결될 수도 있고 여러 데이터에 하나가 연결될 수 있는 비순차적인 자료구조를 의미하며 트리와 그래프가 있다.
비선형 자료구조는 데이터가 순차적으로 연결되어 있지 않기 때문에 데이터 탐색을 할 때 탐색했던 데이터도 다시 되돌아가서 탐색할 수 있다. 그래서 개별 요소에 접근할 때는 선형 자료구조가 더 효율적이다. 반대로 소셜 네트워크와 같이 데이터 간 연결이 어떻게 이루어지는 지에 대한 정보는 그래프와 같은 비선형 자료구조가 더 적합하다. 이처럼 자료구조의 특징을 알아야 문제에 따라 효율적으로 처리할 수 있는 자료구조를 선택할 수 있다.
각 자료구조에 대한 자세한 설명과 관련 코딩 테스트 문제는 개별 포스팅으로 다루고자 하며 자료구조에 대한 간단한 개념과 특징은 아래와 같다.
리스트
- 고정된 크기로 인해 삽입과 삭제 시 크기를 더 할당하거나 모든 데이터를 이동해야 하기 때문에 비효율적
- 원소의 순서가 정해져 있어 인덱스를 사용해 데이터 검색을 효율적으로 가능
링크드 리스트
- 노드로 연결된 리스트
- 가변적인 크기이기 때문에 데이터를 삽입, 제거 시 크기 할당이나, 데이터를 이동할 필요 없이 추가 제거 용이
- 검색 시 인덱싱이 어렵기 때문에 전부 탐색이 필요
- 데이터 탐색에는 선형 리스트를 데이터 삽입/제거에는 연결 리스트가 유리
스택
- 한쪽으로만 데이터를 넣고 뺄 수 있는 자료구조
- 나중에 들어온 데이터를 먼저 빼는 후입 선출(LIFO, Last In First Out)
- 가방에 짐을 넣고 빼는 것처럼 먼저 넣은 짐을 빼기 위해서는 나중에 넣은 짐부터 빼야 함
큐
- 양쪽에서 데이터를 넣고 뺄 수 있는 자료구조
- 가장 먼저 들어간 데이터를 먼저 빼는 FIFO(First In First Out) 구조
트리
- 나무를 거꾸로 뒤집은 모습
- 노드가 나무 가지처럼 연결되어 있는 비선형 자료구조
- 트리 내 또 다른 하위 트리가 있고, 그 안에 또 다른 하위 트리가 있는 재귀적인 구조를 가짐
그래프
- 노드와 간선으로 구성된 자료구조
- 그래프의 방향이 있으면 방향 그래프, 없으면 무(방)향 그래프라고 함
- 연결의 강도가 표시되어 있으면 가중치 그래프, 없으면 비가중치 그래프라고 함
선형 자료구조
비선형 자료구조
알고리즘이란?
알고리즘의 정의
알고리즘이란 어떤 문제를 해결하기 위한 절차를 의미한다. 컴퓨터 프로그램은 데이터를 처리해서 결과를 나타내는데 이때 데이터는 자료구조로 표현되고 데이터에 대한 처리 방법은 알고리즘으로 구현된다. 주어진 숫자 중에 가장 큰 수를 뽑아내는 프로그램을 작성한다고 하면 주어진 수를 어떻게 표현할 지가 자료구조이고 주어진 수에서 큰 수를 나타내는 방법이 알고리즘인 것이다.
알고리즘의 조건
문제를 해결하는 절차가 기술되었다고 모두 알고리즘이라고 말할 수는 없다. 알고리즘이라고 말하기 위해서는 아래 5가지의 조건을 충족해야 한다.
- 입력 : 0개 이상의 입력이 존재해야 한다.
- 출력 : 1개 이상의 출력이 존재해야 한다.
- 명백성 : 각 명령어의 의미는 모호하지 않고 명확해야 한다.
- 유한성 : 한정된 수의 단계 후 반드시 종료가 되어야 한다.
- 유효성 : 각 명령어들은 실행 가능한 연산이어야 한다.
알고리즘 선택
주어진 문제를 해결하기 위해 수행할 작업을 단계별로 명확하게 정의한 것으로 같은 문제라도 푸는 방식은 다를 수 있으므로 주어진 문제에 적용 가능한 알고리즘도 다양하다. 하지만 자원은 한정되어 있기 때문에 가능한 한 빨리, 적은 리소스로 문제를 해결하는 게 중요하다. 그렇기에 좋은 성능을 내기 위해 알고리즘에 대한 특징을 알고 최적의 알고리즘을 선택해야 한다. 어떤 알고리즘이 좋은 알고리즘인지 선택할 수 있게 성능을 측정하는 방법도 있는데 이는 추후 따로 다루고자 한다.
'Algorithm' 카테고리의 다른 글
| <백준 13335 : 트럭> 문제풀이 with python (4) | 2024.11.09 |
|---|---|
| [TIL] 99클럽 코테 스터디 13일차 TIL - 이진탐색 : 백준 10561 징검다리 문제 풀이 with python (0) | 2024.11.09 |
| [TIL] 99클럽 코테 스터디 7일차 TIL - <프로그래머스 : 10561 징검다리> 문제 풀이 with python (0) | 2024.11.04 |
| [SQL] 프로그래머스 고득점 KIT GROUP BY 문제 정답 (0) | 2024.02.25 |
| 알고리즘 성능 평가 방법 - 빅오 표기법 (0) | 2024.02.06 |
