그래프
그래프 정의 그래프: 정점과 간선으로 이루어진 자료구조 차수(degree): 각 정점에 대해서 간선으로 연결된 이웃한 정점의 개수 무방향 그래프(Undirected Graph): 간선의 방향이 없는 그래프 방향 그래프(Directed Graph): 간선의 방향이 있...
Posts by Tag
Algorithm
우선순위 큐
우선순위 큐 정의와 성질 우선순위 큐: 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)에 해결하는 알고리즘 투 포인터 문제는 이분탐색으로도 풀리는 경우가 자주 있음
이분탐색
이분탐색 알고리즘 설명 이분탐색: 정렬되어 있는 배열에서 특정 데이터를 찾기 위해 모든 데이터를 순차적으로 확인하는 대신 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법 주의사항 이분탐색을 하고자 한다면 주어진 배열은 정렬되어 있어야 함 무한 루프에 빠지지 ...
수학
수학 소수 소수: 1과 자기 자신으로만 나누어지는 수 합성수 N에서 1을 제외한 가장 작은 약수는 √n 이하 범위 내에서의 소수 판정법: 에라토스테네스의 체 소인수분해: 2부터 계속 나누기(더이상 나누어지지 않는다면 1씩 증가시키면서 나누기) // 시간복잡도...
다이나믹 프로그래밍
Dynamic Programming 설명 여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘 DP 푸는 과정 테이블 정의하기 점화식 찾기 초기값 정하기
정렬 2
정렬 2 Counting Sort 수를 세고 난 뒤 정렬 수의 범위가 한정적일 경우 사용 가능 Non-Comparison Sort Radix Sort 기수 정렬 자릿수를 이용하여 정렬을 수행하고 counting sort를 응용한 알고리즘이라고도 생각...
정렬 1
정렬 1 기초 정렬 선택 정렬, 버블 정렬, 삽입 정렬 모두 O(N^2) // 버블 정렬 #include<iostream> using namespace std; int main(void){ int arr[5] = {13,-2,2,4,6}; int n=...
재귀
재귀 알고리즘 설명 재귀: 하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘 재귀 함수의 조건: 특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 함(Base condition) 모든 입력은 base condition으로 수렴해야 함 재귀함...
백트래킹
백트래킹 알고리즘 설명 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘 예제 1부터 N까지의 수 중 중복없이 M개를 고른 경우 // 1부터 N까지의 수 중 중복없이 M개를 고른 경우 #include<iostream> #in...
BFS and DFS
BFS 알고리즘 설명 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김 큐에서 원소를 pop하고 그 칸에 상하좌우로 인접한 칸 확인 방문하지 않고 조건에 만족하면 push 큐가 빌때까지 반복 자주 실수하...
Stack의 활용
Stack의 활용 수식의 괄호 쌍 FIFO 여는 괄호가 나오면 스택에 추가 닫는 괄호가 나왔을 경우 스택이 비어있으면 올바르지 않은 괄호 쌍 스택의 top이 짝이 맞지 않는 괄호일 경우 올바르지 않은 괄호 쌍 스택의 top이 짝...
Stack
Stack 정의와 성질 FILO(Fisrt In Last Out) 자료구조 원소의 추가: O(1) 원소의 제거: O(1) 제일 상단의 원소 확인: O(1) 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 구현 배열 혹은 연결리스트...
Queue
Queue 정의와 성질 FIFO(First In First Out) 원소 추가: O(1) 원소 제거: O(1); 제일 앞/뒤의 원소 확인: O(1) 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 추가되는 곳을 rear, 제거되는 곳을 fr...
Deque
Deque 정의와 성질 양쪽 끝에서 삽입과 삭제가 가능 원소 추가: O(1) 원소 제거: O(1); 제일 앞/뒤의 원소 확인: O(1) 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 STL Deque에서는 인덱스로 원소 접근 가능 ...
Linked List
Linked List 정의와 성질 원소들을 저장할 때 그 다음 원소가 있는 위치를 포함 k번째 원소를 확인/변경하기 위해 O(k)가 필요함 임의의 위치에 원소를 추가/제거는 O(1) 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 쉬...
Array
Array 배열의 성질 O(1)에 k번째 원소를 확인/변경 가능 추가적으로 소모되는 메모리의 양이 거의 없음 cache hit rate가 높음(메모리상 데이터들이 붙어있음) 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림 임의의 위치에 원소를 추가: ...
C++ 주의해야할 점
C++ 주의해야할 점
자료형
자료형
복잡도
복잡도
Python
파이썬 인터프리터
파이썬 인터프리터