알고리즘
1.[알고리즘] 그리디
현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘해 선택: 현재 상태에서 가장 최선이라고 생각하는 해를 선택한다.적절성 검사: 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다.해 검사: 현재까지 선택한
2.[알고리즘] DFS / BFS
2023. 04. 07. DFS / BFS > DFS, BFS 모두 그래프에 속하는 알고리즘으로, 간선과 정점이 존재하며 현실의 지도를 선형적으로 표현하기 위해 고안된 구조이다. 그리디 알고리즘의 수행과정 > 1. 해 선택: 현재 상태에서 가장 최선이라고 생각하는 해
3.[알고리즘] DP
2023. 04. 14. 동적 계획법 Dynamic Programming 📌 동적계획법은 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법이다. 동적 계획법의 핵심 이론 📢 동적 계획법의 원
4.[알고리즘] 유니온 파인드
일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는 지를 확인하는 find 연산(자신의 대표 노드를 찾아줌)으로 구성되어 있는 알고리즘이다.유니온 파인드를 표현하는 일반적인 방법은 1차원
5.[알고리즘] 위상정렬
2023. 05. 15. 위상정렬 📌 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘으로 항상 유일한 값으로 정렬되지 않는다. 또한 사이클이 존재하면 노드 간의 순서를 명확하게 정의할 수 없으므로 위상 정렬을 적용할 수 없다. 위상정렬의 핵심 이론 📢
6.[알고리즘] 최단 경로 알고리즘 - 벨만 포드
벨만-포드 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘으로, 특정 출발 노드에서 다른 모든 노드까지의 최단 경로를 탐색한다. 다익스트라 알고리즘과 다른 점은 음수 가중치 에지가 있어도 수행할 수 있다는 것이다. 또한 전체 그래프에서 음수 사이클의 존재 여부를 판단
7.[알고리즘] 최단 경로 알고리즘 - 다익스트라
다익스트라 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘으로 에지는 모두 0이상의 양수여야 한다.시간복잡도: O(ElogV) V(노드 수) E(에지 수)그래프를 인접 리스트로 구현한다.최단 거리 리스트를 만들고 출발 노드는 문제에 주어진대로 설정하지만 여기선 출발
8.[알고리즘] 최단 경로 알고리즘 - 플로이드 워셜
플로이드-워셜 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘으로 시작점이 있는 것이 아니라 모든 노드 간의 최단 경로를 탐색한다. 음수 가중치 에지가 있어도 되며(but cycle이 존재하면 안됨) 동적 계획법의 원리를 이용해 알고리즘에 접근한다. 시간복잡도는 O(
9.[알고리즘] 세그먼트 트리
세그먼트 트리는 주어진 데이터의 구간 합과 데이터 업데이트를 빠르게 수행하기 위해 고안해낸 자료구조의 형태이다. 세그먼트 트리의 종류는 구간합, 최대-최소 구하기로 나눌 수 있고, 구현 단계는 트리 초기화하기, 질의값 구하기, 데이터 업데이트하기로 나눌 수 있다.리프
10.[알고리즘] 에라토스테네스의 체
소수(Prime Number) 판별 알고리즘으로 소수란 '양의 약수를 두 개만 가지는 자연수'를 의미하며 2,3,5,7,11, ... 등이 존재합니다. 이러한 소수를 대량으로 빠르고 정확하게 구하는 방법이다.특히, 다수의 자연수에 대하여 소수 여부를 판별할 때 사용하는