💿 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) 시간복잡도 안에 검색, 삽입, 삭제를 할 수 있다.(해..

[CS] 오버헤드, 스택 오버 플로우

오버헤드(OverHead) 어떤 처리를 하기 위해 들어가는 간접적인 처리 시간 혹은 메모리 등 A라는 작업을 단순 처리하는 시간이 10초일 때, 안정성을 고려하여 B라는 작업을 추가하여 총 15초가 걸렸다면 이 때의 `overhead = 5초` 작업 B를 개선하여 총 12초가 되었다면 `overhead가 3초 단축되었다`고 한다. 스택 오버 플로우(Stack Overflow) 스택 메모리 : Stack 영역의 메모리로 보통은 지역 변수가 저장되는 메모리(함수에서 선언 후 할당, 함수를 빠져나오면 해제) 스택 메모리를 초과하는 경우 발생하는 에러를 스택오버플로우라고 한다. python에선 기본적으로 1000만큼의 메모리가 할당

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

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