CS/자료구조 (7) 썸네일형 리스트형 해시(Hash) 1. 해시란? 데이터를 효율적으로 관리하기 위해 임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 것 Lee → 해싱함수 → 5 Kim → 해싱함수 → 3 Park → 해싱함수 → 2 ... Chun → 해싱함수 → 5 // Lee와 해싱값 충돌 ① 해당 데이터의 해시값을 해시 함수를 이용하여 계산한다. ② 이 해시값을 주소로 하는 위치에 데이터를 저장한다. ③ 저장 후에 검색할 때 데이터의 해시값을 계산해서 바로 해당 위치로 이동할 수 있다. O(1) 하지만 데이터가 많아지면 다른 데이터임에도 같은 해시값이 나오는 충돌이 발생한다. 그래도 해시 테이블을 쓰는 이유는? 적은 자원으로 많은 데이터를 효율적으로 관리하기 위해 하드디스크나 클라우드에 존재하는 무한한 데이터들을 유한한 개수의 해시값으로 매핑.. 이진탐색트리(BST) 이진탐색+연결리스트 이진탐색: 탐색 시 O(logN) but 삽입, 삭제 불가능 연결리스트: 삽입, 삭제 시 O(1) but 탐색 시 O(N) 두 가지를 합해서 장점을 얻은 것이 이진 탐색 트리이다. 1. 이진탐색트리란? 각 노드의 자식이 2개 이하이다. 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 크다. 중복 허용 X BST는 검색 목적 자료구조인데, 중복이 많은 경우 트리를 사용하면 검색 속도가 더 느려진다. 이 경우에는 노드에 해당 값의 count를 갖게 하여 처리하는 것이 더 효율적이다. 중위순회로 정렬된 순서를 읽을 수 있다. 2. 삭제 ① 리프 노드 삭제 시: 그냥 삭제 ② 자식 1개인 노드 삭제 시: 지워진 위치에 자식 노드 올리기 ③ 자식 2개인 노드 삭제 시: 오른쪽 자식 중 가장.. 트리(Tree) 1. 트리란? 노드와 엣지로 이루어진 자료구조이다. 사이클이 존재하지 않는다. 사이클이 존재한다면, 이는 그래프이다. 모든 노드는 자료형으로 표현이 가능하다. 루트에서 한 노드로 가는 경로는 유일하다. 노드가 N개라면 간선은 N-1개이다. 계층 구조가 확실한 구조에서 사용한다. 2. 트리 순회 방식 ① 전위순회 부모-왼쪽 자식-오른쪽 자식 순으로 방문 void preOrder(int idx){ if(tree[idx]){ cout 힙(Heap) 우선순위 큐를 위해 만들어진 자료구조이다. 우선순위 큐는, 데이터들의 우선순위 차례대로 데이터가 나가는 자료구조를 말한다. 시뮬레이션, 작업 스케줄링, 수치해석 계산 등에 사용된다. 삽입, 삭제 모두 O(logN)이 걸린다. 1. 힙이란? 완전 이진 트리의 일종 최대, 최소값을 빠르게 찾도록 만들어진 자료구조 반정렬 상태(전체 정렬 상태가 아님!) 중복된 값을 허용한다 탐색에 적합하지 않다 특정 노드로 접근이 불가능하다 ① 최대힙(C++) ② 최소힙(Java) 두 종류가 있다. 2. Heap vs BST(이진 탐색 트리) BST 특정 노드 접근 가능 정렬된 상태 유지 중복 허용 X Heap 특정 노드 접근 불가능 전체 정렬 X 중복 허용 부모 노드와 자식 노드 관계 왼쪽 자식 index = (부모 ind.. 스택&큐 1. 스택(Stack) LIFO 후입선출 구조를 갖는다. 함수 콜스택, 문자열 역순 출력, 연산자 후위표기법 등에 사용된다. 삽입, 삭제 시 O(1), 검색 시 O(N) 2. 큐(Queue) FIFO 선입선출 구조를 갖는다. 버퍼, 입력된 것을 처리하지 못하고 있는 상황, BFS 등에 사용된다. 삽입, 삭제 시 O(1), 검색 시 O(N) Array vs ArrayList vs LinkedList 1. Array index로 접근이 가능하다. 검색이 용이하다. 배열 크기가 정해져있고, 연속된 메모리 공간에 저장된다. 중간에 데이터를 저장, 삭제하는 경우 비효율적이다. int arr[10]; string arr[5]; 와 같이, 선언할 때 크기와 데이터타입을 지정해 주어야 한다. 2. ArrayList 선언할 때 크기를 지정해주지 않아도 된다. C++에서는 벡터를 생각하면 된다. array에서는 배열에 접근하기 위해 index가 중요했지만, list에서는 데이터의 순서가 중요하다. 배열 크기가 동적이라는 장점이 있지만, 중간에 데이터를 삽입, 삭제할 경우 여전히 시간이 많이 걸린다. 3. LinkedList 한 노드에 연결될 노드의 포인터 위치를 가리키는 방식으로 구현된다. index로 접근하지 못.. BigO(시간복잡도) 1. 알고리즘이란? 어떤 목적을 달성하거나 결과물을 만들어내기 위해 거쳐야 하는 일련의 과정들 여러가지 상황에 따른 알고리즘은 모두 다르다. 시간 복잡도가 가장 낮은 알고리즘을 선택하여 사용한다. 알고리즘 실행시간은 컴퓨터가 알고리즘 코드를 실행하는 속도에 의존한다. 2. 점근적 표기법 최상의 경우: 오메가 표기법 (Big-Ω Notation) 평균의 경우: 세타 표기법 (Big-θ Notation) 최악의 경우: 빅오 표기법 (Big-O Notation) 보통은 최악의 경우를 기준으로 알고리즘 성능을 판단한다. 3. 빅오 표기법 시간 복잡도와 공간 복잡도가 있다. 시간복잡도는 입력된 N의 크기에 따라 실행되는 조작의 수를 나타낸다. 공간복잡도는 알고리즘이 실행될 때 사용하는 메모리의 양을 나타낸다. 오.. 이전 1 다음
