파이썬 프로그래밍 - 자료구조 및 알고리즘 수업

김태희·2025년 2월 4일

python 알고리즘 자료구조 파이썬

파이썬 프로그래밍 수업

목록 보기

2/2

14. search and sorting

순차탐색

링크 [알고리즘] 순차 탐색(Sequential Search)에 대해 알아보자!(+Python 구현)

코드 세가지

def linear_search_while(L: list, value: Any) -> int:
	i = 0
	while i < len(L) and L[i] != value:
		i = i + 1
	if i == len(L):
		return -1
	else:
		return i

def linear_search_sentinel(L: list, value: Any) -> int:
	L.append(value) # Add the sentinel
	i = 0
	while L[i] != value:
		i = i + 1
	L.pop() # Remove the sentinel
	if i == len(L):
		return -1
	else:
		return i

def linear_search_for(L: list, value: Any) -> int:
	for i in range(len(L)):
		if L[i] == value:
			return i
	return -1

이진탐색

링크 [알고리즘] 이진 탐색(Binary Search)에 대해 알아보자!(+Python 구현)

코드

def binary_search(L: list, v: Any) -> int:
		start, end = 0, len(L) – 1
		while start != end + 1:
			mid = (start+end) // 2
			if L[mid] < v:
				start = mid + 1
			else:
				end = mid - 1
		if start < len(L) and L[start] == v:
			return start
		else:
			return -1

선택 정렬

링크 [Algorithm] 선택정렬 / 버블정렬 / 삽입정렬 선택 정렬(Selection Sort) - C언어/자료구조

코드

def selection_sort(L: list) -> None:
	for i in range(len(L)):
		smallest = find_min(L, i)
		L[i], L[smallest] = L[smallest], L[i] # swap

def find_min(L: list, start_idx: int) -> int:
	smallest = start_idx # (1) Initialize smallest
	for i in range(start_idx+1, len(L)): # (2) Update smallest
		if L[i] < L[smallest]:
			smallest = i
		return smallest # (3) Return the final value

def selection_sort(L: list) -> None:
	for i in range(len(L)):
		smallest = i
		for j in range(i+1, len(L)):
			if L[j] < L[smallest]:
				smallest = j
		L[i], L[smallest] = L[smallest], L[i] # swap

시간복잡도 : O(n^2)

15. sorting and big O

삽입정렬

링크 [알고리즘] 삽입 정렬(insertion sort)이란 - Heee's Development Blog
ex) 카드 게임할 때 카드 정렬

코드

def insertion_sort(L: list) -> None:
	for i in range(1, len(L)):
		insert(L, i)

def insert(L: list, last_idx: int) -> None:
	for i in range(last_idx,0,-1): # (1) Go backwards
		if L[i-1] > L[i]: # (2) Check stopping condition
			L[i-1], L[i] = L[i], L[i-1] # (3) Swap
		else:
			break

def insertion_sort(L: list) -> None:
	for i in range(1, len(L)):
		for j in range(i,0,-1): # (1) Go backwards
			if L[j-1] > L[j]: # (2) Check stopping condition
				L[j-1], L[j] = L[j], L[j-1] # (3) Swap
			else:
				break

시간복잡도 : O(n^2)

16. recursion and mergesort

피보나치 재귀

코드

def fibonacci(n: int) -> int:
	if n == 1 or n == 2:
		return n
	else:
		return fibonacci(n-1) + fibonacci(n-2)

합병정렬

링크 [알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog

코드

def mergeSortHelp(L: list, first: int, last: int) -> None:
	if first == last: # Conditional statements
		return # Base case
	else: 
		mid = first + (last – first) // 2
		mergeSortHelp(L, first, mid) # Recursive call for sublist1
		mergeSortHelp(L, mid+1, last) # Recursive call for sublist2
		merge(L, first, mid, last) # Merge the two (sorted) sublists

def merge(L: list, first: int, mid: int, last: int) -> None:
	k = first
	sub1 = L[first:mid+1]
	sub2 = L[mid+1:last+1]
	i = j = 0
	while i < len(sub1) and j < len(sub2):
		if sub1[i] <= sub2[j]:
			L[k] = sub1[i]
			i = i+1
		else:
			L[k] = sub2[j]
			j = j+1
		k = k+1

시간 복잡도
- O(NlogN)
공간 복잡도
- O(N)

Tim Sort

merge sort + insertion sort

17. arrays and linked lists

Array

장점
- 접근이 쉽다
- 옆집
단점
- resize가 어렵다 (사이즈를 늘리려 할 때 힘들다)
- 유동성이 떨어진다

Linked List

장점
- 데이터 추가가 빠르다
- 유동성이 좋다
단점
- 엑세스 속도가 느리다
- 집 주소 알려면 앞 주소에 가야한다

코드

class SLList():
	def __init__(self) -> None:
		self.first = None
		
	def addFirst(self, x: int) -> None:
		newFirst = LinkedNode(x)
		 newFirst.next = self.first
		self.first = newFist
		
	def getFirst(self) -> int:
		if self.first:
			return self.first.val
		return None

class SLList():
	def __init__(self) -> None:
		self.first = None
		self.size = 0
	def addFirst(self, x: int) -> None:
		newFirst = LinkedNode(x)
		newFirst.next = self.first
		self.first = newFirst
		self.size += 1
	def getFirst(self) -> int:
		if self.first:
			return self.first.val
		return None
	def getSize(self) -> int:
		return self.size
		
	def append(self, x: int) -> None:
		self.size += 1
		curNode = self.first
		while(curNode.next != None):
		curNode = curNode.next
		curNode.next = LinkedNode(x)

class SLList():
	def __init__(self) -> None:
		self.sentinel = LinkedNode(0)
		self.size = 0
	def addFirst(self, x: int) -> None:
		newFirst = LinkedNode(x)
		newFirst.next = self.sentinel.next
		self.sentinel.next = newFirst
		self.size += 1
	def getFirst(self) -> int:
		if self.sentinel.next:
			return self.sentinel.next.val
		return None
	def getSize(self) -> int: # Improved with caching!
		return self.size

def append(self, x: int) -> None: # Improved with sentinel!
	self.size += 1
	curNode = self.sentinel
	while curNode.next != None:
		curNode = curNode.next
curNode.next = LinkedNode(x)

18. queues and stacks

큐 queue
- FIFO
- pop()에 파라미터 필요없다
스택 stack
- LIFO
- pop()에 파라미터 필요없다
- ex)
  - 가장 최근에 열린 괄호랑 매칭

22. binary search trees

이진탐색 트리 [자료구조] 이진 탐색 트리 (BST, Binary Search Tree)
- 삽입
  - 루트보다 크면 오른쪽 작으면 왼쪽에
- 삭제
  - 자식이 없으면
    - 그냥 지우고
  - 자식이 1개 있으면
    - 부모랑 연결해주고 본인 지움
  - 자식이 2개 있으면
    - 왼쪽 중에서 가장 큰 거 or 오른쪽 중에서 가장 작은 거랑 위치 바꿈

코드

class TreeNode():
	def __init__(self, x: int):
		self.val = x
		self.left = None
		self.right = None
		
class BST():
	def __init__(self):
		self.root = None
	def search(self, x: int):
	def insert(self, x: int):
	def delete(self, x: int):

23. trees

BFS & DFS DFS vs BFS (깊이우선탐색 vs 너비우선탐색)

BFS

class Tree():
	def visit(self, node: TreeNode):
		print(node.val)

	def BFT(self):
		if self.root == None:
			return
		q = [self.root]
		while q:
			curNode = q.pop(0)
			self.visit(curNode)
			for childNode in curNode.child:
				if childNode:
					q.append(childNode)

class Tree():
	def visit(self, node: TreeNode):
		print(node.val)

def BFT(self):
	if self.root == None:
		return
	q = deque([self.root])
	while q:
		curNode = q.popleft()
		self.visit(curNode)
		for childNode in curNode.child:
			if childNode:
				q.append(childNode)

Preorder, Inorder, Postorder

자녀 방문하기 전에 오면
- 프리오더
자녀 방문하던 중에 오면
- 인오더
자녀 방문하고 나서 오면
- 포스트오더

코드

preorder

class Tree():
	def visit(self, node: TreeNode):
		print(node.val)

	def __DFT_preorderHelp(self, curNode: TreeNode):
		if curNode == None:
			return
		self.visit(curNode)
			for childNode in curNode.child:
				self.__DFT_preorderHelp(childNode)

def DFT_preorder(self):
	self.__DFT_preorderHelp(self.root)

inorder

class Tree():
		def visit(self, node: TreeNode):
			print(node.val)

		def __DFT_inorderHelp(self, curNode: TreeNode):
			if curNode == None:
				return
			for i in range(len(curNode.child)):
				if i == 1:
					self.visit(curNode)
				self.__DFT_inorderHelp(curNode.child[i])

def DFT_inorder(self):
	self.__DFT_inorderHelp(self.root)

postorder

class Tree():
	def visit(self, node: TreeNode, size: float) -> None:
		node.val += size

	def __DFT_postorderHelp(curNode: TreeNode) -> float:
		if not curNode:
			return 0
		subSize = 0
		for i in range(len(curNode.child)):
			subSize += self.__DFT_postorderHelp(curNode.child[i])
		self.visit(curNode, subSize)
		return curNode.val

def DFT_postorder(self) -> float:
	return self.__DFT_postorderHelp(self.root)

24. graphs

Vertex : 노드
Edge : 노드의 쌍
path : 경로
simple path
- 노드가 겹치지 않는
cyclic
- 사이클이 하나라도 있으면
acyclic
- 사이클이 전혀 없으면
- ex) simple path
undirected vs directed
- 엣지는 방향성이 있을 수도 없을 수도 있음
- Tree는 방향성 있음
  - 부모 → 자식

그래프 설계

class undi_graph():
	def __init__(self, V: list, E: list) -> None:
		self.V = V[:]
		self.neighbor = {}
		for v in V:
			self.neighbor[v] = []
		for (v, w) in E:
			self.neighbor[v].append(w)
			self.neighbor[w].append(v)

preorder 그래프

class undi_graph():
	def __DFTHelp(self, visited: list, v: int) -> None:
	if not visited[v]:
		visited[v] = True
		print(v)
		for w in self.neighbor[v]:
			self.__DFTHelp(visited, w)
			
def DFT(self) -> None:
		if self.V:
			visited = {}
		for v in self.V:
			visited[v] = False
		for v in self.V:
			self.__DFTHelp(visited, v)

김태희

내 벨로그

이전 포스트

파이썬 프로그래밍 - 자료구조 및 알고리즘 수업

파이썬 프로그래밍 수업

14. search and sorting

15. sorting and big O

16. recursion and mergesort

17. arrays and linked lists

18. queues and stacks

22. binary search trees

23. trees

24. graphs

파이썬 프로그래밍 - 파이썬 수업

0개의 댓글