[CS]백엔드에서 자주 쓰이는 자료구조와 알고리즘

✅ 자료구조와 알고리즘

 

자료구조

• 정의 : 데이터의 논리적인 구성방식, 데이터를 저장하고 조직화하는 방법이나 데이터 구조
• 자료구조는 보다 효율적인 알고리즘을 사용할 수 있게 한다

 

 

알고리즘

• 정의 : 주어진 문제를 해결하기 위한 절차나 규칙의 집합, 어떤 방식으로 풀어나갈지를 설명하는 방법
• 데이터를 처리하고 조작하는 방법을 결정하고 , 자료구조를 활용하여 문제를 해결하는 방법을 정의한다

 

알고리즘의 4단계

1. 문제 정의 : 해결하고자 하는 바를 Input/Output으로 나눠 정의한다
2. 알고리즘 설명 : 해결하기 위해 할 일들을 단계적으로 정의한다.
3. 정확성 증명 : 알고리즘이 맞는지 수학적으로 증명
4. 성능 분석 : 시간, 공간복잡도 *알고리즘은 반드시 끝이 있다. 시간이 얼마나 걸리든 작업단계의 횟수는 정해져있고, 여기서 시간, 공간복잡도가 나온다.

 

 

효율적인 프로그램 개발과 문제해결을 위해 다양한 자료구조와 적절한 알고리즘을 선택해서 프로그램을 설계하고 구현한다.

✅ 자주 사용되는 자료구조

• 배열(Array) : 요소들이 인덱스를 가지고 순차적으로 저장되는 자료구조
• 연결 리스트(Linked List) : 노드들이 포인터로 연결되어 있는 자료구조, 데이터의 추가/삭제가 빈번한 경우
• 스택(Stack) : 후입선출(LIFO) 원칙을 따르는 자료구조로, 함수 호출과 관련된 작업에 많이 사용됌
• 큐(Queue) : 선입선출(FIFO) 원칙을 따르는 자료구조로, 작업처리의 순서를 관리하는데 사용됌
• 해시테이블(Hash Table) : 키와 값으로 데이터를 저장하는 자료구조, 검색과 삽입에 빠른 접근
• 트리(Tree) : 계층적인 구조를 가지며, 이진트리, AVL트리, B-트리 등 다양한 형태

 

*배열과 연결리스트의 차이, 장단점

검색에는 배열이 유리하지만 추가/삭제에는 연결리스트가 더 유리하다. 이유는?

 

 

*Stack과 Queue 의 개념

1. Stack

스택(stack) 말 그대로 쌓아 올린다는 것을 의미한다.

책을 쌓는 것 처럼 차곡 차곡 쌓아올린 형태의 자료구조를 말한다.

후입선출, LIFO 구조

• 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있다
• Top으로 정한 곳을 통해서만 접근할 수 있다
• Top을 통해 삽입하는 연산 'push', Top을 통해 삭제하는 연산 'pop'
• Stack이 넘치는 경우를 stack overflow
• Stack이 비어있는 상태에서 원소를 추출하려고 할 때 stack underflow 
• ex) 웹브라우저 방문기록(뒤로가기), 역순 문자열 만들기, 실행취소(undo)

 

 

  2. Queue

Queue 줄, 혹은 줄 서서 기다리는 것을 의미한다. 

은행에서 먼저 온 사람의 업무를 창구에서 처리, 먼저 온 사람이 먼저 놀이기구에 타는 것. 

선입선출, FIFO 구조

 

• 삽입 연산만 이루어지는 곳을 리어(rear) ,삭제 연산만 수행되는 곳을 프론트(front)
• 가장 먼저 들어온 프론트 원소가 가장 먼저 삭제
• ex) 데이터가 입력된 시간 순서대로 처리할 필요가 있을때, 프린터의 인쇄 대기열, 콜센터 고객 대기시간, 프로세스 관리, 캐시구현

 

✅ 자주 사용되는 알고리즘

• 정렬 알고리즘 : 데이터를 정해진 순서대로 재배열 하는 알고리즘
• 검색 알고리즘 : 특정 값을 찾는 알고리즘
• 그래프 알고리즘 : 그래프 자료 구조를 다루는 알고리즘
• 문자열 매칭 알고리즘 : 문자열에서 특정 패턴을 찾는 알고리즘
• 재귀 알고리즘 : 자기 자신을 호출하여 문제를 해결하는 알고리즘

 

재귀알고리즘 예시 

팩토리얼 계산 :

팩토리얼은 양의 정수 n에 대해 1부터 n까지의 모든 정수를 곱한 값을 말한다. 

팩토리얼은 수학적으로 n! 로 표현된다.

def factorial(n):
    if n == 0 or n == 1:
        return 1
    else:
        return n * factorial(n - 1)

# 예시
result = factorial(5)
print(result)  # 출력: 120 (5! = 5 * 4 * 3 * 2 * 1 = 120)