알고리즘

알고리즘의 수행시간을 정량화하는 것계산일반적으로 1억번의 연산당 1초의 시간이 걸린다고 간주표기법일반적으로 빅-오 표기법 사용(Big-O Notation)worst case의 연산횟수 나타내는 표기법최고차항의 차수만을 표기ex. 3n² + 5n + 10 → O(n²)

효율적으로 접근하고 수정할 수 있도록 데이터를 구성하고 저장하는 방법배열 (Array)동일한 자료형의 데이터를 일렬로 나열하는 구조연결 리스트 (Linked List)각 노드가 데이터와 포인터를 가지고 일렬로 연결되어 있는 방식으로 데이터 저장스택(Stack)삽입, 삭

2개의 자연수의 최대공약수를 구하는 알고리즘a를 b로 나눈 나머지를 r이라 하면, a와 b의 최대공약수는 b와 r의 최대공약수와 같다는 성질 이용https://www.acmicpc.net/problem/29601부터 N까지의 모든 소수를 빠르게 구하는 알고리즘

개념 간의 연결 관계를 수학적 모델로 단순화하여 표현한 것주요 용어무향 간선 : 간선의 방향 존재 X유향 간선 : 간선의 방향 존재인접 : 정점 v1, v2에 대해 간선 존재 → 정점 v1과 v2는 인접부속 : 정점 v1, v2에 대해 간선 e 존재 → 간선 e는 정점

무향 그래프 G가 순환이 없는 연결그래프이면, G는 트리노드가 n개이면 간선은 n-1개무향 연결 그래프 G의 부분그래프이고, G의 모든 정점을 포함하는 트리인 그래프무향 연결 가중 그래프 G에서 간선의 가중치 합이 최소인 신장 트리union-find 이용이미 연결된 노

정점 a와 정점 b가 각각 자신을 포함하여 조상을 따라 거슬러 올라갈 때 처음으로 만나게 되는 공통 정점정점 a의 조상이면서 정점 b의 조상인 정점들 중 가장 깊은 정점트리에서 두 노드의 최단거리는 무조건 LCA를 지남LCA 구하기최상위 조상 정점을 시작으로 BFS를

https://www.acmicpc.net/problem/11266무향 연결 그래프 G에서 하나의 정점과 연결된 간선들을 제거했을 때 두개 이상의 연결 그래프로 나뉘어 진다면 해당 정점은 단절점단절점 찾기어떤 정점 a와 a에 연결된 정점 b에 대해서a가 시작정

가중 그래프에서 간선의 가중치 합이 최소가 되는 경로를 찾는 문제종류음이 아닌 가중 그래프에서 단일 쌍, 단일 출발, 단일 도착 최단 경로 문제V개의 정점과 음수가 아닌 E개의 간선을 가진 그래프 G에서 특정 출발 정점에서부터 다른 모든 정점까지의 최단경로 구하는 알고

정수형 자료형의 이진수 표현을 이용해 특정 상태나 값을 비트 단위로 관리하는 방식메모리를 아끼고, 빠르게 상태를 체크하거나 조작할 수 있음예: 상태값 관리, 플래그 체크, 권한 부여 등효율적인 메모리 사용 (비트 단위로 여러 상태를 한 변수에 저장 가능)한 비트당 0과