[이코테] 자료구조 기초

📗 자료구조 기초 📗

📍 탐색이란?

• 많은양의 데이터 중에서 원하는 데이터를 찾는과정이며 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룬다. 대표적인 탐색 알고리즘으로 DFS/BFS를 말할 수 있다.

📍 자료구조란?

• 데이터를 표현하고 관리하며 처리하기 위한 구조이며 이중 스택과 큐는 자료구조의 기초 개념으로 다음의 두 핵심적인 함수로 구성된다.
  • 삽입(push) : 데이터를 삽입한다.
  • 삭제(pop) : 데이터를 삭제한다.

📍 스택(stack)이란?

• 스택은 박스 쌓기에 비유할 수 있으며 선입후출 또는 후입선출 구조이다.

• 파이썬은 기본리스트에서 append()와 pop() 메서드를 사용하면 스택 자료구조와 동일하게 동작한다. append()는 리스트의 가장 뒤쪽에 데이터를 삽입하고, pop()은 리스트의 가장 뒤쪽에서 데이터를 꺼내기 때문이다.

🎈 구현 문제 예시

stack=[]

stack.append(5)
stack.append(2)
stack.append(3)
stack.pop()
stack.append(4)

print(stack)

[5,2,4]

📍 큐(queue)이란?

• 큐는 대기 줄에 비유할 수 있다. 선입선출 구조이기 때문에 공정한 자료구조라고 비유된다.
• 파이썬으로 큐를 구현할 때는 collections 모듈에서 제공하는 deque 자료구조를 활용하자. 속도가 효율적이며 queue 라이브러리를 사용하는것보다 더 간단하다.

🎈 큐 문제 예시

from collections import duque

#큐 구현을 위해 deque 라이브러리 사용
queue=deque()

queue.append(5)
queue.append(2)
queue.append(3)
queue.popleft()
queue.append(4)

print(queue)

[2,3,4]

📍 재귀함수란?

• 자기자신을 다시 호출하는 함수를 의미한다.
• 재귀함수를 문제풀이에 사용할 때에는 종료조건을 꼭 명시해야한다.
• 보통 반복문과 재귀함수의 코드를 비교해보면 점화식을 그대로 옮긴 재귀함수의 코드가 더 간결한 것을 확인할 수 있다. 이 개념은 다이나믹 프로그래밍으로 이어지기 때문에 중요하므로 기억!

📌 팩토리얼 재귀함수 예제

def factorial_recursive(n):
	if n <= 1:
    	return 1
    return n* factorial_recursive(n-1)

📌 팩토리얼 반복문 예제

def factorial_iterative(n):
	result = 1
    
    for i in range(1,n+1):
    	result*=i
    return result

Reference

이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈 저