알고리즘 초간단 정리

최근 알고리즘 문제를 계속해서 풀고 있다. 어떤 자료구조와 알고리즘을 사용하면 되겠다 하는 정도까지는 얼추 보이는데 빌트인 자료구조를 주로 이용하다 보니 직접 구현해야 하는 상황은 버벅이게 된다.

 

간단하게 정의와 파이썬에서 이용하는 법을 키워드로 정리한다.

 

리스트

• 배열. 기본적으로는 같은 타입의 데이터가 연속적으로 위치하는 선형 자료구조.
• 인덱스를 통해 빠른 접근이 가능.
• 파이썬에서는 다양한 타입의 데이터를 저장할 수 있으며, 동적으로 크기가 조절됨.
• 구현은 주로 [] 또는 list() 함수 이용.

연결리스트

• 각 노드가 데이터와 다음 노드를 가리키는 포인터로 구성된 선형 자료구조.
• 삽입 삭제가 효율적.
• 다음 노드는 이전노드를 통해서 접근하기에 n번째 요소 조회는 O(n).
• 구현은 주로 collections.deque 이용.
• 양방향 연결리스트
  • 각 노드가 이전 노드와 다음 노드를 모두 가리키는 포인터를 가진 연결리스트
  • 양방향 탐색이 가능.

스택

• LIFO(Last In First Out) 후입선출을 따르는 자료구조.
• 삽입과 삭제가 스택의 가장 끝, 동일한 방향에서 이루어짐.
• 구현은 주로 리스트 또는 deque 이용.

큐

• FIFO(First In First Out) 선입선출을 따르는 자료구조.
• 삽입과 삭제가 큐의 양 끝, 서로 다른 방향에서 이루어짐.
• 구현은 주로 deque 이용.
• 환형큐
  • 일반 큐의 끝과 시작이 연결된 원형 구조의 큐.
  • 큐의 크기가 고정되어 있음.
  • 구현시 deque의 maxlen 파라미터 이용.
• 우선순위 큐
  • 각 요소에 우선순위 부여, 우선순위 높은 요소가 먼저 나감.
  • 구현시 힙이 일반적.

트리

• 노드가 계층적을 연결된 비선형 자료구조.
• 계층적 데이터 표현에 적합.
• 검색, 삽입, 삭제 효율적
• 빌트인 기능은 없으며 주로 직접 구현

힙

• 완전 이진 트리 기반의 자료구조. 최대값(최대힙) 또는 최소값(최소힙)을 빠르게 찾을 수 있음.
• 부모 자식 간 대소관계가 일정하게 유지
• 구현시 주로 heapq 사용. 최소힙만 지원되며 최대 힙은 값을 음수로 변환하는 방식 사용하여 직접 처리.

해시

• 키-값 쌍으로 데이터를 저장하는 자료구조.
• 해시 함수로 빠른 검색 가능. 평균 O(1) 시간복잡도.
• 동일 해시 값이 생성될경우 해시 충돌 가능성. 해결법은 다양함.
• 구현시 {} 또는 dict() 함수 이용.
• 파이썬 이용시 Python 3.7 부터 순서가 보장됨