알고리즘 스터디를 하다가, 스터디원 한 분이 선정하신 문제를 풀다가 알게 된 유형이다.처음에는 union-find 문제인 줄 알았으나, 알고보니 새로운 유형의 문제였다.!! 착각했던 만큼이나 알고리즘의 글로서의 개념은 매우 비슷하다.union-find는 무향 그래프에서의 노드 간의 연결을, 동일한 부모 원소로 두면서 각 집합으로 표현을 한다.SCC는 유향 그래프에서의 노드 간의 명확한 연결만을, 동일한 부모 원소로 두면서 각 컴포넌트(집합)으로 표현을 한다.(그래서 `강한 결합 알고리즘` 알고리즘이라고 부른다.) 여기에서 "명확한 연결"이란 "두 노드 간의 자유로운 이동"을 뜻한다.무향 그래프에서는 간선에 방향성이 없어 자연스럽게 자유로운 이동이 가능했지만,유향 그래프에서는 간선에 방향성이 있어 a → ..

Stack, Queue은 자료구조를 시작했을 때, 가장 처음 만나는 자료구조이다. 하지만.. 알고리즘에서 Stack 유형 알고리즘을 풀 때에는 번번히 어려움을 마주한다..😂먼저 Stack 유형이라는 것을 파악하기에도 힘들고(DP / Greedy로 우선 접근), 파악한다고 하더라도 응용 문제에서는 자체 테스트케이스에서 틀리는 경우가 많다. 물론 지금까지 Stack 문제를 많이 풀지 않아서 그런 것 같기도 하지만..무언가 정답 코드에 테스트 예제를 디버깅하면서 추적하면 이해가 잘 되지만, 그 전에는 확 와닿지 않는 느낌이랄까 그렇지만 Stack 문제를 풀 때마다 새롭고, 재밌다🤩일반 구현에 비해 직관적(눈은 직관적이지만, 머리는 복잡한..)이고, 시간복잡도 측면에서도 대부분 O(N)으로 효율적이게 해결할..

위상 정렬은 그래프 문제를 풀다보면 한 번씩 마주치게 되는 알고리즘이다.처음에는 위상 정렬이라는 이름이 낯설었지만, 개념을 알고 구현을 해 보면 재밌는 알고리즘인 것 같다. 1. 개념위상 정렬은 사이클이 없고 방향이 있는 그래프(DAG, Directed Acyclic Graph)에서 노드들의 선수 관계를 표현하는 알고리즘이다. 그래서 순서가 정해져있는 작업들을 수행할 때 사용하는 알고리즘으로, 프로세스 스케줄링 예시를 생각해보면 이해하기 쉽다.A 프로세스가 실행이 끝나야 B 프로세스를 시작할 수 있다.B 과목을 듣기 위해 A 과목을 먼저 들어야 한다. 위상 정렬 알고리즘 코드를 보기 앞서, 진입차수와 진출차수에 대한 개념을 먼저 이해하면 좋다.진입차수: 특정 노드로 들어오는 간선의 개수진출차수: 특정 노..

알고리즘을 풀다가 분리집합, union-find 관련 문제를 자주 접하여 관련 개념들을 정리하고자 글을 적게 되었다. 1. 개념`Union-Find, Disjoint Set` 두 단어 모두 알고리즘을 풀다 보면 한 번씩 들어보게 되는 용어이다. 처음에는 '2개의 문제 유형이 다른가?' 하고 생각을 했는데 같은 문제로 보면 될 것 같다.정확히 말하면 그래프 탐색에 dfs, bfs 알고리즘을 사용하듯이, 분리집합에는 Union-Find 알고리즘을 사용한다.하지만 분리집합을 관리하기 위한 알고리즘으로 Union-Find 알고리즘이 효율이 매우 좋아 다른 알고리즘이 필요하지 않는다고 보면 될 것 같다. 그럼 간략하게나마 각 용어의 개념을 정리해보자. Disjoint Set: 서로소 집합이라고 하며, 서로 겹치지..

이분탐색 문제를 찾아 풀다가 1450. 냅색문제에서 처음에는 투포인터로 접근해서 풀다가정답을 보니 브루트포스, 분할정복(?), 이분탐색이 한데 어울러진 듯한 느낌을 받아 정리하게 되었다. cf. MITM 기법의 핵심은 브루트포스를 분할하는 것이며, 추가적인 연산에 +a의 알고리즘 기법이 사용되었을 뿐이다. 1. 개념: 브루트포스 알고리즘을 사용해야 할 경우, 브루트포스를 분할해서 복잡도를 최소화하는 알고리즘 기법이다. 분할정복과의 차이점?: 분할정복은 작은 문제들의 해결을 합치면서, 큰 문제의 해결로 이어져 나간다. MITM 문제를 쪼개는 것은 같지만, 중간에서 만나 결합하는 과정에서 +a의 추가적인 연산이 필요하다. 2. 문제 예시*BOJ - 1450. 냅색문제 [코드]# O(2^(N/2))# ..

1. 개념플로이드 워셜 알고리즘은 다익스트라와 같이 최단 경로 알고리즘 중의 하나로,가중치가 있는 그래프에서 모든 노드 쌍 간의 최단 경로를 구하는 알고리즘이다. 다익스트라 같은 경우는 단일 노드에서 다른 모든 노드까지의 최단 경로였지만 여기서는 모든 노드 쌍 간의 최단 경로이다..! 아래에서 구현 코드와 함께 이해해보자. 2. 코드 이해플로이드 알고리즘의 코드 구조를 매우 간단하다. 일단 모든 노드 쌍 간의 최단거리를 구해야 하므로 n^2의 계산이 필요하다.여기에서는 i → j 까지 직행으로 가는 거리를 구할 수 있다.for i in range(n): # 출발지 for j in range(n): # 도착지 dist[i][j] 위 수식에서 i → j 까지 갈 때, 경유지를 고..