알고리즘과 자료구조

알고리즘: 데이터를 어떻게 처리할지에 대한 절차나 방법.
자료구조: 데이터를 어떻게 저장하고 관리할지에 대한 구조.

알고리즘 (Algorithm)

알고리즘은 특정 문제를 해결하기 위해 설계된 단계적인 절차나 방법이다. 데이터를 어떻게 처리하고, 어떤 방식으로 연산을 수행할지에 대한 일련의 명령어를 정의한다. 알고리즘은 얼마나 빠르게 실행되는지(시간 복잡도)와 얼마나 많은 메모리를 사용하는지(공간 복잡도)를 고려해야 한다. 효율적인 알고리즘일수록 빠르고 적은 자원을 사용한다.

알고리즘 예시: 텐텐오락실 비번을 맞혀라

텐텐오락실 비번을 맞혀라

텐텐 모바일게임의 비번을 맞혀라 게임이다. 0 ~ 9까지 각 칸에 들어갈 숫자를 맞춰야 한다. 첫 번째 칸의 정답이 7이라고 가정했을 때, 이걸 두 가지 방식으로 풀 수 있다.

1. 0부터 차례대로 입력하기

제일 단순한 방법은 0부터 9까지 차례대로 입력하여 정답을 찾는 방법이다. 운 좋으면 0을 입력하자마자 정답일 수 있지만 최악의 경우 정답인 7까지 다 한 번씩 눌러봐야 한다.

• 입력 순서: 0  →  1  →  2  → 3 → 4 → 5 → 6 →  7

2. 중간값 입력하기

게임에서 만약 입력한 숫자가 정답보다 높다면 UP, 낮다면 DOWN이라고 알려주는데 이걸 이용할 수 있다. 처음에 0~9 중간 정도인 5를 입력한다. 정답 7은 입력한 5보다 높으니 UP이다. 그럼 6~9 중간값인 8을 입력해 본다. 8은 7보다 높으니, 이번엔 DOWN이다. 그럼 6 아니면 7이 정답이니 한 번씩 다 눌러보는 방식보다 더 빠르게 정답을 찾을 수 있다.

• 입력 순서: 5 (UP) → 8 (DOWN) → 6 → 7

이렇듯 동일한 문제라도 푸는 방법에 따라 해결하는 속도가 달라진다. 1번 방식은 0부터 정답인 7까지 8번 만에 맞혔고, 2번 방식은 4번 만에 정답을 찾았으니 2번이 더 효율적이라고 볼 수 있다.

참고로, 1번 방식은 선형 탐색(linear search)에 해당하며 시간 복잡도는 O(n)이다. 2번 방식은 이진 탐색(binary search)으로 시간 복잡도가 O(log n)이다.

알고리즘 종류

• 정렬 알고리즘: 버블 정렬, 퀵 정렬, 병합 정렬 등
• 탐색 알고리즘: 선형 탐색, 이진 탐색
• 최적화 알고리즘: 그리디 알고리즘, 동적 프로그래밍

이것 외에도 많은 알고리즘이 존재한다.

자료구조 (Data Structure)

자료구조는 데이터를 효율적으로 저장하고 관리하는 구조이다. 어떤 방식으로 데이터를 저장하고, 삽입, 삭제, 탐색 등을 할 것인지에 대한 구체적인 설계를 제공한다. 적절한 자료구조는 알고리즘의 성능을 극대화한다.

자료구조 예시

• 배열(Array): 연속된 메모리 위치에 데이터를 저장
• 스택(Stack): 후입선출(LIFO) 방식
• 큐(Queue): 선입선출(FIFO) 방식
• 트리(Tree): 계층적 데이터 구조

결론

알고리즘과 자료구조는 함께 사용된다. 문제를 해결할 때는 데이터를 어떻게 저장할지(자료구조)와 데이터를 어떻게 처리할지(알고리즘)를 모두 고려해야 한다. 자료구조를 잘 이해하면 알고리즘의 성능을 더 높일 수 있다.