Zzong's Notes

알고리즘 스터디

1 min read

함께 보면 좋은 글

General Problems

문자열 압축 굳이 String 을 만들 필요 없이 개수만 계산하면 된다. 숫자 카드2 (백준) lower bound 또는 upper bound 구현 python 으로 시도했는데 TLE 로 실패함. bisect library 를 이용해서 풀음.

string

두 String 이 주어질 경우 문제 (anagram) 인지 확인하기 예시) cat, tac 가 주어질 때, tac 를 잘 나열하면 cat 이 되므로 True 이 문제는 두 가지 방법으로 풀 수 있었음 Counter 사용 두 개의 Counter 가 서로 동일하면 True 만약 하나의 Counter 만 사용할 수...

linear regression

Linear Regression 는 다음과 같은 형태의 모델을 의미한다 p(y\mid\boldsymbol{x},\boldsymbol{\theta})=\mathcal{N}\left(y\mid w {0}+\boldsymbol{w}^{\top}\boldsymbol{x},\sigma^{2}\right) 여기서...

stack

스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조 (LIFO - Last In First Out) 으로 되어 있다.

Insertion Sort

삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

greedy algorithm

매 단계에서 그 순간 가장 좋아 보이는 선택을 하고, 한 번 고른 것은 되돌리지 않는 방식이다. 전체를 내다보지 않으므로 계산이 싸지만, 그 대가로 최종 답이 최적이라는 보장이 사라진다.

sorting

Insertion Sort Selection Sort Merge Sort Bubble Sort quick Sort Heap Sort .

NP-complete

P 는 다항 시간 (polynomial time) 에 결정론적 (deterministically) 으로 해결 가능한 (solvable) 문제들의 집합, 주어지는 입력 (input) 이 참인지 거짓인지를 다항 시간에 결정론적으로 해결하는 알고리즘이 존재하면 X∈P 입니다.

Selection Sort

선택 정렬은 다음과 같은 순서로 이루어진다. 주어진 리스트 중에 최소값을 찾는다. 그 값을 맨 앞에 위치한 값과 교체한다. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. 하나의 원소만 남을 때까지 위의 과정을 반복한다.

페이지 교체 알고리즘

swap out 을 위한 Page 를 선정하기 위한 알고리즘 Memory 에서 앞으로 사용할 가능성이 적은 페이지를 대상 Page 로 선정하여 Page Fault 를 줄이고, 시스템의 성능을 향상한다.