just inside

그래프 (Graph)정점(Vertex)과 이 정점들을 연결하는 간선(Edge)으로 구성된 데이터 구조.가중치 그래프 (Weighted Graph) : 각 간선에 가중치(비용 또는 거리 등)가 할당된 그래프비가중치 그래프 (Unweighted Graph) 신장 트리 (Spanning Tree) 알고리즘그래프 이론에서 최소 비용으로 모든 정점을 연결하는 트리를 찾는 알고리즘네트워크 설계, 도로 건설, 통신 케이블 배치와 같은 문제에서 최소 비용으로 네트워크 구성하기 위해 사용 신장 트리의 특징주어진 그래프의 모든 정점을 포함하는 연결 그래프사이클이 없는 그래프n-1개의 엣지를 가짐. n은 그래프의 정점 수 최소 신장 트리 (Minimum Spanning Tree, MST)주어진 가중치 그래프에서 가능한 모든..

DFS (Depth-First Search)  |  깊이 우선 탐색그래프나 트리에서 한 노드부터 출발하여 최대한 깊게 탐색을 진행한 후, 더 이상 갈 곳이 없으면 이전 단계로 되돌아가서 다른 경로를 탐색하는 방식스택을 이용하여 구현 가능, 재귀적으로도 구현 가능노드의 깊이까지 탐색한 후, 다시 돌아와 다른 경로를 탐색그래프의 모든 노드를 방문하고자 할 때 적합 기본 코드 (재귀 방식)# graph : 탐색할 그래프, start : 탐색 시작 노드, visited : 방문 노드 저장 집합def dfs(graph, start, visited=None): if visited is None: visited = set() # 현재 노드 방문. 집합에 추가 visited.add(start)..

이분 탐색 (Binary Search) 이란?정렬된 리스트에서 특정한 값을 빠르게 찾기 위한 알고리즘반으로 나누는 전략을 사용하여 검색 범위를 좁혀 나감 -> $O(log n)$ 의 시간 복잡도 가짐알고리즘 설명1. 초기화리스트의 시작 인덱스 ('left')와 끝 인덱스('right') 설정'left'는 0, 'right'는 리스트의 마지막 인덱스로 초기화2. 반복'left'가 'right'보다 작거나 같은 동안 다음을 반복중앙 인덱스 ('mid') 계산 : 'mid' = (left + right) // 2리스트의 중앙 값과 찾고자 하는 값 비교중앙 값 == 찾고자 하는 값 : 인덱스 반환중앙 값 > 찾고자 하는 값 : 'right' = 'mid' - 1중앙 값 3. 종료'left'가 'right' 보다..

복잡한 문제를 해결하기 위해 사용되는 최적화 기법큰 문제를 여러 작은 부분 문제로 나누어 해결하고, 그 결과를 저장하여 같은 부분 문제를 반복적으로 해결하지 않도록 하는 방식최적화 문제나 점화식 기반 문제에서 사용됨 주요 개념부분 문제의 중복문제 해결 과정에서 동일한 부분 문제가 반복적으로 나타남ex) 피보나치 수열 - 계산 시 동일한 피보나치 수가 여러 번 계산최적 부분 구조문제의 최적 해결 방법이 부분 문제들의 최적 해결 방법으로 구성되는 경우ex) 최단 경로 문제 - 전체 경로의 최적 경로는 부분 경로의 최적 경로로 구성메모이제이션 (Memoization) 또는 타뷸레이션 (Tabulating)메모이제이션 : 재귀적 접근에서 이미 계산된 부분 문제의 결과를 저장하여 중복 계산 방지타뷸레이션 : 반복..

유클리드 호제법 (Euclidean Algorithm) / 최대공약수 계산두 정수의 최대공약수 (GCD, Greatest Common Divisor)를 효율적으로 계산하는 알고리즘두 수의 최대공약수가 두 수의 차이의 최대공약수와 같다는 것원리두 정수 $a$와 $b$ $(a>b)$의 최대공약수를 구하기 위해 다음 과정을 반복$a$를 $b$로 나눈 나머지 $r$을 구한다.$a$를 $b$로, $b$를 $r$로 대체한다.$r$이 0이 될 때까지 이 과정을 반복한다.$r$이 0이 되었을 때, $b$가 $a$와 $b$의 최대공약수$$ GCD(a,b)=GCD(b,a\bmod b)$$def gcd(a,b): while b != 0: a, b = b, a % b return a시간복잡도는 $O(log\ min(a..

소수 (Prime Number) 란?1과 자기 자신 외에는 다른 약수를 가지지 않는 자연수.1보다 큰 자연수 중에서 오직 두 개의 약수만을 가지는 수 -> 1은 소수가 아님 소수 판별 알고리즘특정 숫자 n이 소수인지 확인하려면 2부터 $\sqrt{n}$ 까지의 모든 숫자로 n을 나누어 본다.$n=a \times b$이 때 a와 b 둘 중 하나는 반드시 n의 제곱근 이하이다. n이 소수가 아니라면, 반드시 두 약수 중 하나는 $\sqrt{n}$ 이하가 되게 된다.따라서 소수인지 판별하기 위해서는 2부터 n-1 까지가 아니라, $\sqrt{n}$ 까지만 확인하면 된다. # 제곱근 계산 위해 math 모듈 사용import mathdef ifPrime(n): # 2부터 n의 제곱근까지 반복 for i in ra..

브루트포스 알고리즘 (Brute Force)가능한 모든 경우의 수를 전부 탐색하여 문제를 해결하는 알고리즘 방법가장 직관적이고 단순한 방식으로 문제에 접근특징단순함이해하기 쉽고 구현하기 쉬움가능한 모든 경우를 시도하므로 특별한 사전 지식이나 복잡한 논리 필요 X완전 탐색가능한 모든 경우 탐색하여 최적의 해답 찾음문제 확실하게 해결 가능비효율성경우의 수가 많아질수록 시간이 많이 걸림입력 크기 작은 경우 유용, 입력 크기 커질수록 비효율적