꼭 필요한 자료구조 기초

• 탐색(search) : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
• 자료구조(Data Structure) : 데이터를 표현하고 관리하고 처리하기 위한 구조
  • 삽입(push) : 데이터 삽입
  • 삭제(pop) : 데이터 삭제

 

• 스택(Stack)
  • 선입선출(First In Last Out), 후입선출(Last In First Out)
  • 입구와 출구가 동일한 형태로 스택을 시각화

  stack = []
  stack.append(5)
  stack.append(2)
  stack.append(3)
  stack.append(7)
  stack.pop() # 7 삭제
  stack.append(1)
  stack.append(4)
  stack.pop() # 4 삭제
  print(stack)       # [5,2,3,1]
  print(stack[::-1]) # [1,3,2,5]
  

 

 

• 큐(Queue)
  • 선입선출(First In First Out)

  from collections import deque
  # 시간적으로 우수?함
  queue = deque()
  queue.append(5)
  queue.append(2)
  queue.append(3)
  queue.append(7)
  queue.popleft()
  queue.append(1)
  queue.append(4)
  queue.popleft()
  print(queue) # deque([3,7,1,4]) 먼저 들어온 순서대로 출력
  queue.reverse()   # 다음 출력을 위해 역순으로 바꾸기
  print(queue) # deque([4,1,7.3]) 나중에 들어온 원소부터 출력
  

 

 

• 재귀 함수
  • 자기자신을 다시 호출하는 함수
  • 재귀함수는 종료 조건을 꼭 명시해야 한다
  • 컴퓨터 내부에서 재귀함수의 수행은 스택 구조를 이용한다 → 함수를 계속 호출했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료된다
  • 재귀함수가 수학의 점화식을 그대로 소스코드로 옮겼기 때문에 코드가 더 간결해 보인다

  # 팩토리얼
  # 반복적으로 구현한 n!
  def factorial_iterative(n):
  	result = 1
  	for i in range(1, n+1):
  		result *= i
  	return result
  
  # 재귀적으로 구현한 n!
  def factorial_iterative(n):
  	if n<1:
  		return 1
  	return n*factorial_iterative(n-1)