Algorithms
1.[알고리즘] 위상 정렬(Topological Sorting) - 백준 1516번
어떤 일을 하기 위해 일련의 작업을 차례때로 수행해야 하는 알고리즘이다. 즉, B를 하기 위해선 A를 해야하고, C를 하기 위해선 B를 해야하는 상황에서 A-> B-> C 순서로 할 수 있다. 예를 들어, 대학교에서 선수 과목을 들어야 해당 과목을 들을 수 있듯이 순서
2.[알고리즘] 다익스트라(Dijkstra) - 백준 1753번
하나의 시작 정점에서 다르정점까지의 최단 경로를 계산하는 것이다. 최단 경로 알고리즘이라고도 불린다! 다음과 같은 그림에서 최단경로를 계산하려고 한다.각 단계에서 S안에 있지 않은 정점 중에서 가장 distance값이 작은 정점을 S에 추가한다.정점 W를 거쳐서 정점
3.[알고리즘] 우선순위 큐
우선순위 큐란? > 우선순위를 가진 항목들을 저장하는 큐 FIFO 순서가 아니라 우선 순위가 높은 데이터가 먼저 나가게 된다. 우선순위 큐는 2가지로 구분된다. 최소 우선순위 큐 : 가장 우선순위가 낮은 요소부터 삭제 최대 우선순위큐 : 가장 우선순위가 높은 요소부
4.[알고리즘] 다익스트라(Dijkstra) - 백준 1854번
_다익스트라 알고리즘은 https://velog.io/@galong/%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BCDijkstra-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%EC%A4%80-17
5.이것이 코딩이다 - 미로 탈출 (파이썬)
유튜브로 "이것이 코딩이다" DFS&BFS 문제를 풀어보다 "미로 탈출" 문제에서 오류가 발생했다. 인접한 노드에 자신의 노드 값을 +1 함이 부분에서 오류가 났다.범위 확인을 한 뒤에 graphnx를 했는데, list index out of range라고.......
6.[줄 세우기] 위상 정렬 | python 2252번
위상 정렬 (Topological sort) 위상 정렬은 비순환 방향 그래프에서 정점을 선형으로 정렬하는 것이다. 방향 그래프에서 간선 가 있다면, 정점 u는 정점 v를 선행하여 정렬한다. 방향 그래프 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열해야한다.
7.[골드바흐 파티션] 백준 17103 파이썬
골드바흐 파티션 - 백준 17103골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다.짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 두 소수의 순서만 다른 것은 같
8.[유클리드 호제법] - 백준 1934번, 1850번 | python
유클리드 호제법에 대해 알아보자.유클리드 호제법(euclidean-algorithm)은 두 수의 최대 공약수를 구하는 알고리즘이다. 일반적으로 최대 공약수를 구하는 방법은 소인수 분해를 이용한 공통된 소수들의 곱으로 표현할 수 있지만, 유클리드 호제법은 더 간단한 방식
9.[기타 레슨] 백준 2343번 | 이진탐색 | 파이썬
문제를 풀기 앞서 이진탐색에 대해 알아보자.이진 탐색(binary search)은 데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘이다. 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다. 시간 복잡도는 O(log
10.[트리의 지름] 백준 1167 | BFS | 파이썬
백준 - 트리의 지름트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터
11.[에라토스테네스의 체] 소수 구하기 | 파이썬 | 백준 1929번
소수는 약수가 1과 자기자신만 있는 수를 말한다.자연수 n이 소수인지 확인하는 방법은 2부터 n-1만큼 하나라도 나누어 떨어지는 수가 있는지 확인한다.위 코드는 직관적이지만 비효율적이라는 단점이 있다.이 코드의 시간 복잡도는 O(n)으로 n의 범위가 10^9보다 크면
12.[칵테일] DFS | 유클리드 호제법 | 백준 1033번 | python
백준 - 칵테일예제 입력1예제 출력1예제 입력2예제 출력2예제 입력3예제 출력3예제 입력4예제 출력4이 문제는 그래프 관점으로 생각하면 사이클이 없는 트리 구조로 이해할 수 있다.DFS를 사용하여 유클리드 호제법으로 비율의 최소 공배수와 최대 공약수를 구하고, 재료의
13.[집합의 표현] 유니온 파인드 | 백준 1717번 | python
유니온 파인드(union-find)는 일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성되어 있는 알고리즘이다. union 연산각 노드가 속한 집합을 1