자료 구조

11/23 (자료 구조와 탐색, 수) TIL

(어제에 이은) 자료 구조:트리 : 완전 이진 트리의 경우 잎 노드에서 뿌리 노드까지 도달하는 데 O(logN)O(logN)O(logN) 단계가 필요함.힙 : 최대힙과 최소힙이 있음. 완전 이진 트리의 일종이므로 원소 추가와 삭제시 시간 복잡도는 최대 O(logN)O(logN)O(logN)이 된다.그래프 : 노드와 노드 사이의 연결 관계를 강조하여 나타낸 자료 구조. 인접 행렬과 인접 리스트로 표현할 수 있음. 트리와 그래프를 탐색하기:DFS(깊이 우선 탐색)과 BFS(너비 우선 탐색) 모두 인접 리스트를 데이터 삼아 구현을 연습했다. 인접 행렬로 표현한 버전이 연결 관계를 찾을 때 O(1)의 시간만으로 빠르게 찾는다던데, 정작 탐색을 할 때는 어떻게 활용해야 할지 모르겠다. 다이나믹 프로그래밍과 메..

11/22 (정렬과 자료 구조, 화) TIL

2022/11/22 화 정렬 방법: 버블 정렬 : 꽉 막힌 O(N2)O(N^2)O(N2) “둘 둘을 끝까지 비교 비교하는 모양이 버블 버블해서”선택 정렬: 꽉 막힌 O(N2)O(N^2)O(N2) “최솟값 널 선택한다! 이리 앞으로 와!”삽입 정렬: O(N2)O(N^2)O(N2)인데 잘하면 Ω(N)Ω(N)Ω(N)만에도 끝남. “저 신입인데… 어디로 가면 되나요?” 병합 정렬: O(NlogN)O(NlogN)O(NlogN) “원자 단위로 해체했다 다시 되돌아오는 이것은… ‘원상 복구’를 장담하지 않는 텔레포트” 자료 구조:스택 stack큐 queue해시 hash table → 충돌 해결 방법에 체이닝(Chaining)과 개방 주소법(Open addressing)이 있다. 푼 문제: 너무 많아 일일이 ..