💿 Data/부트캠프

[TIL] 104. [자료구조] 순회

키워드 순회(트리 : 전위/중위/후위, 그래프 : BFS/DFS) 순회(Traversal) 트리, 그래프와 같이 연결된 자료구조에서 모든 노드를 한 번씩 탐색하는 것 순회의 목적 : 모든 혹은 특정 노드를 방문하는 방법을 찾는 것 방향에 따라 순회하는 방법이 달라진다. [순회] 트리구조 트리 구조에서의 순회는 크게 전위, 중위, 후위로 나누어진다. 전위 : 1. Root node -> 2. Left node -> 3. Right node 중위 : 1. Left node -> 2. Root node -> 3. Right node 후위 : 1. Left node -> 2. Right node -> 3. Root node 단순하게 왼쪽에서 오른쪽이면서 Root node의 위치에 따라 나누어진다고 생각하면 쉽다..

[TIL] 103. [자료구조] 그래프

키워드 그래프 인접행렬/인접리스트 그래프 그래프는 기본적으로 vert(노드, 정점)와 edge(간선, 링크)로 구성되어있다. 그래프는 노드간의 관계, 트리는 노드간의 계층을 표현 방향성(단방향, 양방향) 순서가 존재하기 때문에 마지막 노드가 Leaf node가 된다. 양방향 형태의 경우, 그 주목적이 노드간의 상호 교환(서로 노드 정보를 공유) 무방향성 방향이 존재하지 않고 연결된 노드들(이웃 노드들)끼리 서로 인접 순환성 그래프가 가질 수 있는 성질로, 위와 같이 순환을 형성할 수 있다. [그래프] 인접리스트, 인접행렬 그래프 자료구조를 구현하는 두가지 방법 인접리스트 그래프의 형태를 리스트로 표현 전체 노드의 목록을 저장하고 있다. 파이썬의 딕셔너리로 그래프를 구현한 예시) class Graph: d..

[TIL] 102. [자료구조] 해시테이블

키워드 해시 해시함수 해시테이블 해시충돌(체이닝, 오픈 어드레싱) 해시테이블 키(key)를 활용하여 값(value)에 직접 접근이 가능한 구조 해싱의 주된 목적은 검색 데이터의 양과 상관없이 성능이 빠르다.(키를 통해 바로 값을 검색하기때문) 파이썬의 딕셔너리는 내부적으로 해시테이블 구조 해시함수 해시함수를 통해 키를 해시테이블 내의 버킷(=hashes)로 매핑 해시함수의 입력값 형태는 다양하지만, 출력값의 형태는 숫자 입력값과 출력값이 일대일 대응이 되어야 한다. 실제로는 완벽한 일대일 대응은 어려우며, 다른 입력값에 대해 같은 출력이 나오는 경우를 해시충돌이라고 한다. 일반적으로 해시함수는 문자열 입력값을 정수형 출력값으로 반환 해시성능 O(1) 시간복잡도 안에 검색, 삽입, 삭제를 할 수 있다.(해..

[TIL] 101. [분할 정복, 정렬] 퀵 정렬, 병합 정렬

키워드 분할 정복 퀵 정렬 병합 정렬 분할 정복 복잡하거나 큰 문제를 작은 하위 문제로 나누어 푸는 방법 문제를 나누어 병렬적으로 해결 가능(단, 문제해결을 위해 함수가 재귀적으로 호출될 수 있으므로 메모리 사용량 증가) 분할(Divide) : 문제를 작게 작게 나누는 과정 정복(Conquer) : 작게 나눈 문제를 하나씩 return 하여 정복(특정값을 도출) 먼저 Divide를 한 후 그의 역순으로 작은 문제부터 하나하나 정복해서 최종 결과값을 도출 단, 과연 이 문제를 분할 정복으로 해결하는 것이 더 효율적인 것이도 생각해볼 필요가 있다! 아래는 재귀와 분할 정복의 차이(분할 정복은 보통 재귀함수를 활용) [정렬, 분할정복] 퀵 정렬(Quick Sort) 피벗(pivot)이라는 값을 특정지어주고(보..

[TIL] 100. [알고리즘] 탐색

키워드 탐색 선형탐색 이진탐색 [알고리즘] 탐색 자료를 하나씩 탐색하는 알고리즘 문제를 해결하기 위해서는 문제를 탐색해야한다. [탐색] 선형탐색(Linear Search) 기본적인 탐색 알고리즘으로 한번에 하나씩 차근차근 모두 검색하는 것 def linear_search(arr, value): for i in range(len(arr)): if arr[i] == value: return i [탐색] 이진탐색(Binary Search) 탐색을 할 때, 반씩 줄여나가면서 탐색 마치 업다운 게임에서 가운데 값을 말하면 점점 좁혀나가는 방식 단, 데이터가 이미 정렬된 경우에만 작동한다. O(logn)의 시간복잡도를 갖는다.(그룹을 2개씩 나누면서 진행하기 때문) def binary_search(arr, valu..