수학
수학 소수 소수: 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 큐가 빌때까지 반복 자주 실수하...