[PYTHON] 코딩테스트에 필요한 파이썬 알고리즘/자료구조 - 1

카카오 인턴십 코딩테스트(솔직히 붙을자신 없다)에 앞서 필요한 알고리즘과 자료구조 지식을 정리해보고자한다.

---

1. 배열(Array)

 

• list() 또는 []으로 생성가능 ()은 튜플이다.
• 장점 : 빠른 접근 가능
• 단점 : 추가/삭제가 어려움, 미리 최대길이 지정필요

numbers = [1,2,3,4,5] # 1차원 리스트
numbers2 = [[1,2],[3,4]] # 2차원 리스트

    2. 큐 (Queue) FIFO or LILO 방식

• 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조
• 알아야할 것
  • Enqueue : 큐에 데이터를 넣는것
  • Dequeue : 큐에서 데이터를 꺼내는것
  • 파이썬에는 queue 라이브러리가 있다
    • Queue(), LifoQueue(), PriorityQueue()
      • Queue() : 일반적인 큐
      • LifoQueue(): 나중에 입력된 데이터가 먼저 출력되는 구조
      • PriorityQueue(): 데이터마다 우선순위를 넣어서, 우선순위가 높은 순으로 데이터 출력
• 어디에 쓰이나?
  • 멀티태스킹의 프로세스 스케쥴링방식 구현을 위해 쓰임

  3. 스택 (Stack)

>>> stack = [3, 4, 5]
>>> stack.append(6)
>>> stack.append(7)
>>> stack
[3, 4, 5, 6, 7]
>>> stack.pop()
7
>>> stack
[3, 4, 5, 6]
>>> stack.pop()
6
>>> stack.pop()
5
>>> stack
[3, 4]

• 데이터를 제한적으로 접근하는 구조 (한쪽에서만 자료를 넣거나 빼는 것이 가능)
• 가장 나중에 쌓은 데이터를 가장 먼저 빼내는 데이터 구조
• Queue vs Stack => FIFO vs LIFO and FILO
• LIFO(Last In, First Out)이란
  • 마지막에 넣은 데이터를 가장 먼저 추출
• FILO(First In, Last Out)이란
  • 처음에 넣은 데이터를 가장 마지막에 추출하는 방식
• 주요함수
  • push() : 데이터를 스택이 넣기
  • pop(): 데이터를 스택에서 꺼내기

4.  링크드 리스트 (Linked List)

 

 

 

• 장점: 미리 데이터공간 할당필요 없다
• 단점: 저장공간 효율 x
• 요새는 저장공간 효율 별로 안따지니 넘어가자

 

5. 해쉬 테이블

• 딕셔너리(Dictionary)타입이 파이썬의 해쉬 테이블

 

 

상기 이미지 출처: wikipedia.org