Algorithm/Algorithm_Theory
-
선형탐색(LinearSearch) & 이진탐색(BinarySearch)Algorithm/Algorithm_Theory 2023. 1. 12. 23:14
선형탐색(LinearSearch) 리스트의 처음부터 끝까지 순서대로 하나씩 탐색을 진행하는 알고리즘 def linear_search(element, some_list): # 여기에 코드를 작성하세요 for e in some_list: if e == element: return some_list.index(e) return None print(linear_search(2, [2, 3, 5, 7, 11])) print(linear_search(0, [2, 3, 5, 7, 11])) print(linear_search(5, [2, 3, 5, 7, 11])) print(linear_search(3, [2, 3, 5, 7, 11])) print(linear_search(11, [2, 3, 5, 7, 11])) 이..
-
재귀(Recursive)Algorithm/Algorithm_Theory 2022. 12. 11. 20:40
# 재귀적으로 문제를 푼다는 것은 같은 형태의 더 작은 문제로 본 문제를 푼다는 것! ex) 5! = 1 x 2 x 3 x 4 x 5 , 5 factorial을 풀기 위해선 4factorial을 풀어야 한다 4! = 1 x 2 x 3 x 4, 4 factorial을 풀기 위해선 3 factorial을 풀어야 한다 3! = 1 x 2 x 3, 3 facotiral을 풀기 위해선 2factorial을 풀어야 한다 0! = 1 ============= 재귀적으로 문제를 풀때는 base case와 recursive case를 풀어야 한다
-
그래프(Graph)Algorithm/Algorithm_Theory 2022. 11. 30. 23:24
용어정리 - 노드(Node) : 그래프에서 하나의 데이터 단위를 나타내는 객체. 원이 노드를 나타낸다 - 엣지(Edge) : 그래프에서 두 노드의 직접적인 연결 관계 데이터. 화살표가 엣지를 칭한다. 두 노드 사이에 엣지가 있을 때 " 두 노드는 인접해 있다 " 라고 표현한다 - 차수(Dimension) : 하나의 노드에 연결된 엣지들의 수. 노드를 떠나는 엣지의 수=> 출력 차수, 노드에 들어오는 엣지의 수 =>입력 차수 - 경로(route): 한 노드에서 다른 노드까지 가는 길 그래프 노드를 구현해보기 class StationNode: """지하철 역 노드를 나타내는 클래스""" def __init__(self, name, num_exits): self.name= name self.num_exits ..
-
깊이우선탐색(DFS, Depth-First Search)Algorithm/Algorithm_Theory 2022. 11. 23. 23:55
DFS(Depth-First Search) - '깊이'를 우선적으로 탐색하는 알고리즘 - DFS를 구현하는 방식은 재귀(recursive) 방식과 스택(stack) 방식이 있다 # 재귀 dfs는 해당 노드의 주변 노드를 탐색할때 첫번째 노드부터 탐색 # stack dfs는 해당 노드의 주변 노드를 탐색할때 맨 뒤 부터 노드부터 탐색 (1) 시작 노드인 노드 1을 스택에 삽입하고 방문 처리 (2) 스택 내 최상단 노드인 노드 1에 인접한 노드는 2, 3이 있습니다. 번호가 낮은 노드 2를 스택에 삽입하고 방문 처리 (3) 스택 내 최상단 노드인 노드 2에 인접한 노드 8을 스택에 삽입하고 방문 처리 (4) 스택 내 최상단 노드인 노드 8에 인접한 노드는 6과 7이 있으며, 번호가 낮은 노드 6을 스택에 삽..
-
너비우선탐색(BFS, Breadh-Frist Search)Algorithm/Algorithm_Theory 2022. 11. 23. 23:37
BFS(Breadth-First Search) - 너비 우선 탐색이라고도 불리며 그래프에서 시작 노드에 인접한 노드부터 탐색하는 알고리즘 - 선입선출(First-in First-out) 방식의 큐(Queue) 자료를 이용 (1) 시작 노드인 노드 1을 큐에 삽입하고 1를 방문 처리 (2) 큐에서 노드 1을 꺼내고 노드 1과 인접한 노드 2, 3을 큐에 삽입하고 2,3 방문 처리 (3) 큐에서 노드 2를 꺼내고 노드 2와 인접한 노드 8을 큐에 삽입하고 8를 방문 처리 (4) 큐에서 노드 3을 꺼내고 노드 3과 인접한 노드 4, 5를 큐에 삽입하고 4,5을 방문 처리 (5) 큐에서 노드 8을 꺼내고 노드 8과 인접한 노드 6, 7을 큐에 삽입하고 6,7를 방문 처리 (6) 그래프 내 노드에서 방문하지 않은..
-
스택(Stack)Algorithm/Algorithm_Theory 2022. 11. 14. 08:43
후입선출(Last In First Out, LIFO) 구조 => 늦게 들어온 데이터가 먼저 나간다 스택 연산 - 데이터간 순서 관계를 유지해야 한다 - 맨 뒤 데이터 추가 - 맨 뒤 데이터 삭제 - 맨 뒤 데이터 접근 스택 동작 과정 보기 코드로 스택 구현해보기 # deque는 python collections 모듈에서 가지고 온다 from collections import deque stack = deque() # 의 맨 끝에 데이터 삽입 stack.append("연아1") stack.append("연아2") stack.append("연아3") # 스택 출력 print(stack) # deque(['연아1', '연아2', '연아3']) # 맨 끝 데이터 출력 print(stack[-1]) # 연아3 #..