Algorithm

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

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

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

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

https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net 1. Preview 시간 복잡도: O(N) 공간 복잡도: O(N) 참고 : https://velog.io/@waoderboy/BOJ-%EB%B0%B1%EC%A4%80-2138-%EC%A0%84%EA%B5%AC%EC%99%80-%EC%8A%A4%EC%9C%84%EC%B9%98-%ED%8C%8C%EC%9D%B4%EC%8D%AC 유형: 그리디 2. 초기 접근 방법 중앙점이 ..

https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 1. Preview 시간 복잡도: O(M*a(N)) M : 연산 갯수 a(N) : 경로 압축한 find()의 시간 복잡도 공간 복잡도: O(N) 참고 : https://dheldh77.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9C%A0%EB%8B%88%EC%98%A8%ED%8C%8C%EC%9D%B..