CSAlgorithm
Graph Algorithms
Graph Algorithms, 그래프 알고리즘 우리가 하는 그 함수 그래프를 말하는 것이 아니고 객체 간의 짝을 이루는 관계를 모델링한 형태가 그래프인 것을 말한다. 그래프의 형태는 여러가지가 있다고 하는데 그중에서 undirected(방향이 없음)…
2025.06.098분#Algorithm
/tags
#Algorithm
9 posts
CSAlgorithm
Greedy Algorithms
Greedy Algorithms, 한국말로 탐욕(?) 탐색법이라고 하면 될 것 같다. 이 기법은 말 그대로 결정의 순간에 모든 경우를 보는게 아니라 당장 코앞의 문제에 최선의 선택을 하는 방식을 말한다. 당연히 전체를 보지 않기 때문에 최선이 아닌 경…
2025.06.083분#Algorithm
CSAlgorithm
알고리즘 문제 풀이(2)
1번 정수 4는 1, 2, 3의 합으로 표현할 때 아래와 같이 7가지의 방법이 있다. 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1 자연수 N을 입력 받아, N을 1, 2, 3의 합으로 표현할 때에, 몇 가지 방법이 있…
2025.06.0813분#Algorithm
CSAlgorithm
Backtracking
Backtracking 기법: recursion을 사용하는 기법으로 문제의 해를 찾다가 아니라는 것을 알면 되돌아가서 다른 해를 찾는 방식. Subset Sum 문제 어떤 정수 집합 X의 부분집합 중에서 합이 T인 값이 있는지 확인하는 문제! T 0이…
2025.06.062분#Algorithm
CSAlgorithm
Divide and Conquer(D&C) 기법을 사용한 알고리즘
Divide and Conquer(D&C)? 분할&정복 기법, 말 그대로 문제를 분할해서 해결하는 기법이다 1. 문제를 분할 해서 smaller instance로 만들기 2. recursion을 사용해서 작은 문제에 대한 답을 얻음 3. 병합해서 원래…
2025.06.062분#Algorithm
CSAlgorithm
Dynamic Programming (동적계획법)
지금까지 recursion을 사용해서 여러 문제를 풀었는데, 과연 recursion이 항상 최선이었을까? 당장 이전에 썼던 곱셈 문제도 더 빠른 방식이 존재했었다. (중복되는 recursion을 줄여서 속도를 올림) 그렇기 때문에 점화식과 이전의 결과…
2025.06.0626분#Algorithm
CSAlgorithm
Recursion(재귀) algorithm 과 D&C(분할과 정복) 시간복잡도 분석
recursion을 알기 전에 reduction에 대해 먼저 알아보자 일단 알고리즘에서 자주 사용하는 (거의) 유일한 기술이라고 수업에서 배웠다. 기술이라고하니 거창해 보이지만 단순하게 표현하면 black box라고 보면 된다. 이게 뭔 말이냐면 어떤…
2025.06.065분#Algorithm
CSAlgorithm
시간 복잡도 분석 연습
Master Theorem 점화식이 T(n) rT(n/c) + O(f(n))의 형태일 때 case1. f(n) Ω($𝑛^{log c r}$) 이면 T(n) O(f(n)) case2. f(n) Θ ($𝑛^{log c r}log^k n$) 이면 T(n…
2025.06.063분#Algorithm
CSAlgorithm
시간 복잡도(Time Complexity)
시간 복잡도? 모든 환경적인 요인(언어, 컴퓨터 스펙 등)은 고려하지 않고 오로지 알고리즘 자체에 대한 수행시간의 개념 시간 복잡도 Algorithm의 수행시간을 이론적으로 분석하기 위한 개념 왜 필요한가? 같은 문제를 푸는 여러 알고리즘 중에 가장 …
2025.06.051분#Algorithm