그래프
그래프 정의 그래프: 정점과 간선으로 이루어진 자료구조 차수(degree): 각 정점에 대해서 간선으로 연결된 이웃한 정점의 개수 무방향 그래프(Undirected Graph): 간선의 방향이 없는 그래프 방향 그래프(Directed Graph): 간선의 방향이 있...
최근 포스트
우선순위 큐
우선순위 큐 정의와 성질 우선순위 큐: pop을 할 때 가장 먼저 들어온 원소가 나오는 대신 우선순위가 가장 높은 원소가 나오는 큐 원소의 추가(Heap): O(lgN) 우선순위가 가장 높은 원소의 확인(Heap): O(1) 우선순위가 가장 높은 원소 제거(Heap...
이진 검색 트리
이진 검색 트리 정의와 성질 정점(Vertex/Node): 트리에서 각 원소 루트(Root): 트리에서 가장 꼭대기의 정점 리프(leaf): 제일 말단에 위치해 자식이 없는 정점 간선(Edge): 정점을 연결하는 선 이진 트리(Binary Tree): 각 노드의...
해시 구현
해시 구현 구현 해시 테이블 크기, 해시 함수를 정해야 함 Load factor: 원소의 개수/테이블의 크기 Load factor를 작게 유지하면 충돌이 덜 생겨서 각 연산이 거의 O(1)에 동작하지만 cache hit rate가 줄어들고 메모리도 많이 차지하는 단점이...
해시
해시 정의와 성질 해시에서는 insert, erase, find, update 모두 O(1) 해시 함수: 임의의 길이의 데이터를 고정된 길이의 데이터로 대응시키는 함수 충돌 서로 다른 키가 같은 해시 값을 가질 경우 충돌이 일어남 충돌이 발생했을 때 회...
투 포인터
투 포인터 알고리즘 설명 투 포인터: 배열에서 원래 이중 for문으로 O(N^2)에 처리되는 작업을 2개 포인터의 움직임으로 O(N)에 해결하는 알고리즘 투 포인터 문제는 이분탐색으로도 풀리는 경우가 자주 있음
이분탐색
이분탐색 알고리즘 설명 이분탐색: 정렬되어 있는 배열에서 특정 데이터를 찾기 위해 모든 데이터를 순차적으로 확인하는 대신 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법 주의사항 이분탐색을 하고자 한다면 주어진 배열은 정렬되어 있어야 함 무한 루프에 빠지지 ...