Breath everything

이것 저것

IT/자료구조 & 알고리즘

1. 크루스칼 알고리즘 동작 원리...? a) 간선의 가중치를 오름차순으로 sort b) (sort 되었으니까) 간선을 하나씩 확인하며 사이클 발생 O: MST에 포함 X 사이클 발생 X: MST에 포함 O c) 모든 간선에 대해 b) 과정을 해줌 사실 수업을 들을 때도 말로만 설명을 들으니까 확실히 이해가 되지 않아서 코드를 짠 후, 그 코드를 분석해보았다. 2. 크루스칼 알고리즘 코드 분석 graph = { 'vertices':['A','B','C','D','E','F','G'], 'edges':[ (7, 'A', 'B'), (5, 'A', 'D'), (7, 'B', 'A'), (8, 'B', 'C'), (9, 'B', 'D'), (7, 'B', 'E'), (8, 'C', 'B'), (5, 'C', ..

2021. 8. 23.

IT/자료구조 & 알고리즘

1. 신장 트리(Spanning Tree)란...? Original 그래프에서 다음의 조건들을 만족시키는 그래프 -> (모든 노드가 연결 / 트리의 속성 만족(사이클 X)) 신장 트리 조건 사이클 X Original 그래프의 모든 노드 포함 모든 노드 연결 2. 최소 신장 트리(MST)란...? Minimum Spanning Tree 신장 트리 중에서, 간선의 가중치 합이 최소인 것 토목, 통신 등등 다양한 분야에서 활용 가능

2021. 8. 21.

IT/자료구조 & 알고리즘

1. DFS란...? 정점의 자식들을 먼저 탐색 2. 구현 전 생각정리 탐색할 그래프를 딕셔너리와 데크를 활용하여 구현해보자 need_visit 데크의 오른쪽에서 하나씩 node를 뽑아오며 탐색하면 최대 깊이까지 탐색하고 다시 올라오는 느낌으로의 탐색이 가능 3. 코드 구현 from collections import deque graph = dict() graph['A'] = deque(['B', 'C']) graph['B'] = deque(['A', 'D']) graph['C'] = deque(['A', 'G', 'H', 'I']) graph['D'] = deque(['B', 'E', 'F']) graph['E'] = deque(['D']) graph['F'] = deque(['D']) graph['G..

2021. 8. 8.

IT/자료구조 & 알고리즘

1. BFS란...? 한 단계씩 내려가면서 같은 레벨에 있는 노드들을 먼저 순회 2. 구현 전 생각정리 탐색할 그래프를 딕셔너리와 데크를 활용하여 구현해보자 need_visit 데크의 왼쪽에서 하나씩 node를 뽑아오며 탐색, 탐색할 때 그 node와 연결된 노드들을 need_visit 데크의 오른쪽에 추가해줌 3. 코드 구현 from collections import deque graph = dict() graph['A'] = deque(['B', 'C']) graph['B'] = deque(['A', 'D']) graph['C'] = deque(['A', 'G', 'H', 'I']) graph['D'] = deque(['B', 'E', 'F']) graph['E'] = deque(['D']) grap..

2021. 8. 8.

IT/자료구조 & 알고리즘

1. 기본 구조와 용어 그래프(Graph): 노드(Node)와 간선(Edge)로 실제 세계 현상이나 사물을 표현하는 자료구조 노드(Node): 위치 간선(Edge): 위치간의 관계를 표시한 선 2. 그래프(Graph) 종류 [무방향 그래프(Undirected Graph)] 방향 X 간선을 통해 양방향으로 움직일 수 있음 [방향 그래프(Directed Graph)] 방향 O 간선을 통해 정해진 방향으로 움직임 [가중치 그래프(Weighted Graph)] 간선에 가중치가 할당 [사이클(Cycle) & 비순환 그래프(Acyclic Graph)] 사이클(Cycle): 단순 경로의 시작 노드와 종료 노드가 동일 비순환 그래프(Acyclic Graph): 사이클이 없는 그래프 #'단순': 경로나 사이클에서 같은 ..

2021. 8. 8.

IT/자료구조 & 알고리즘

1. 기본 원리 (분할) 리스트를 두 개의 서브 리스트로 나눔 (정복) 검색할 숫자가 중간값보다 크면 뒷 서브 리스트에서 탐색, 반대의 경우에는 앞 서브 리스트에서 탐색 2. 생각 정리 리스트를 반씩 나누면서 찾고자 하는 포인트와 점점 가까워지게 하는 프로세스를 재귀 용법을 통해 구현 3. 코드 구현 기존에 정렬되어 있던 리스트에서 특정 값이 있는지 여부를 이진탐색으로 판별하는 코드 def bs(data, s_point): print(data) medium = len(data) // 2 if s_point == data[medium]: return True else: if s_point > data[medium]: #중간값보다 찾으려는 값이 클 때 return bs(data[medium+1:], s_po..

2021. 8. 8.

IT/자료구조 & 알고리즘

1. 기본 원리 리스트를 절반으로 나누는 함수를 재귀적으로 활용하면서 원소가 하나인 상태까지 잘게 나눠줌 나눠진 부분들을 정렬해나가며 하나씩 붙여나감 2. 생각정리 [2,8,6,5,1]를 병합정렬로 정렬하는 시뮬레이션을 돌려봤습니다. 다 나눠지면 left와 right을 merge 하는 과정을 통해 3. 코드 구현 음... 솔직히 어떤 방식으로 정렬을 진행하는지는 개념적을 쉽게 이해가 되었는데... 재귀적으로 구현하려고 하니까 바로 이해가 안되었던 것 같습니다. 분할하는 프로세스를 '내려간다고' 표현하고 합치는 프로세스를 '올라간다고' 표현하면 가장 밑바닥을 찍은 순간 바로 올라갈 수 있는 함수가 작동하게? 코드를 짰습니다. def merge(left, right): merged = list() left_..

2021. 8. 7.

IT/자료구조 & 알고리즘

1. 기본 원리 기준점(pivot) 기준으로 기준점보다 작은 데이터는 왼쪽으로, 기준점보다 큰 데이터는 오른쪽으로 보내는 함수 작성 보통 기준점(pivot)은 범위에서 맨 앞에 있는 것으로 선택 기준점(pivot) 왼쪽과 오른쪽 범위를 재귀 함수로 다시 정렬해주는 프로세스 반복 모든 데이터가 [기준점(pivot), 왼쪽, 오른쪽] 쌍으로 분리가 될 때까지 반복 분리되어 각각의 범위가 정렬된 것들을 다시 병합 2. 코드 구현 전 생각정리 3 5 1 7 4 (3이 기준점) 1 3 5 7 4 (5가 기준점) 1 3 4 5 7 Python list를 활용해서 재귀함수를 통해 정렬된 list를 이어나가면 어떨까? 3. 코드 구현 def qsort(data): if len(data) 단계가 logn만큼 생성, 각 ..

2021. 8. 4.

IT/자료구조 & 알고리즘

1. 재귀 용법(Recursive Call) 함수 안에서 동일한 함수를 호출하 형태 Python에서는 재귀함수 깊이가 1000회 이하여야 함(Python 자체적으로 고정된 stack공간을 잡아놨기 때문) 2. 일반적인 형태 임의의 입력이 주어진다. 임의의 조건이 주어진다. 입력이 임의의 조건을 충족시킬 때까지 재귀호출이 된다. 3. 코드 구현 팩토리얼 연산은 조금 식상한 면이 있어서 좀 신박한 예제들을 재귀 용법을 통해 구현해봤다. 3.1 회문(palindrome) 판별기 def palindrome(input): if len(input)=4: return func(n-1) + func(n-2) + func(n-3)

2021. 8. 4.