알고리즘
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, ... 등이 존재합니다. 이러한 소수를 대량으로 빠르고 정확하게 구하는 방법이다.특히, 다수의 자연수에 대하여 소수 여부를 판별할 때 사용하는
11.[알고리즘] 조합
12.[알고리즘] 조합 / 순열
조합 순열
13.[알고리즘] DP 문제풀이 방법
어떤 자연수 i를 1,3,4의 합을 통해 만들어야하는 상황1,3,4의 합을 통해 i가 만들어지기 직전의 상황을 생각해보면1을 더해서 i가 되는 숫자 (i-1)3을 더해서 i가 되는 숫자 (i-3)4를 더해서 i가 되는 숫자 (i-4) 등의 후보가 존재한다.i를 만들 때
14.[알고리즘] 그래프 알고리즘 총정리 -1 (DFS / BFS)
\-> 정점과 간선으로 이루어져야됨.\-> 만약 간선, 정점 둘 중 하나라도 존재하지 않으면 그래프 아님어떤 특정 상황에서 대부분 상황을 표현할 수 있으니깐.노드의 개수만큼의 공간을 확보한 뒤에 각 노드를 기준으로 연결된 노드를 저장하는 방식예를 들어 음 노드 4개가
15.[알고리즘] 이분 탐색 알고리즘
브루트 포스, 그리디, DP와 같은 경우에는 쓰이는 상황이 명확하지 않기 때문에 접근 방식에 가까운 알고리즘이라고 할 수 있다. 그래서 알고리즘 문제를 접근할 때 브루트 포스로 해결할 수 있는가, 만약 안된다면 그리디, DP를 생각해볼 수 있다고 언급했었다.위 3 가지
16.[알고리즘] 자료구조 정리
알고리즘 문제 풀이 시 사용 빈도가 높은 자료구조만 정리 예정해시테이블은 키(key) 값(value)으로 이루어진 데이터를 저장하는 자료구조이고 파이썬에선 딕셔너리를 활용한다.선입선출 선형 자료구조이고 파이썬에선 deque 사용
17.[알고리즘] 그래프 알고리즘 총정리 -2 (다익스트라, 벨만-포드, 플로이드-워셜)
가중 그래프가 아닌 경우에는 경로 상에 있는 간선의 수가 적을수록 거리가 짧은 것이고 가중 그래프인 경우에는 경로 상에 있는 간선의 가중치 합이 작을 수록 거리가 짧은 것이다.만약 가중치가 음수이고 사이클이 존재하면 사이클을 돌 때마다 음수가중치가 더해지기 때문에 사이