본문 바로가기

Computer Science

(8)

그래프 이론 - 4. 이분 그래프 정의 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. 판정 그래프의 정점들을 BFS 혹은 DFS로 탐색하면서 판단할 수 있다. 1. 방문하지 않은 정점을 찾는다. 2. 방문하지 않은 정점의 방문여부는 1로 체크한 후, 탐색을 시작한다. 인접한 정점의 방문여부를 체크한다. 인접 정점의 방문여부가 현재 정점의 방문여부와 같을 시, 해당 그래프는 이분그래프가 아니므로 시행을 종료한다. 해당 정점을 방문하지 않았을 시, 현재 정점의 방문여부에 -1을 곱한 값으로 체크한다. 3. 만약 모든 정점의 순회가 중단되지 않았다면 해당 그래프는 이분그래프 이다. 코드 https://..

그래프 이론 - 2. 백트래킹 (Backtracking) 정의 백트래킹이란 문제의 해가 될 수 있는 후보들을 탐색하면서, 각 후보들이 해가 될 가능성이 없다고 판단될 시 해당 후보를 버리는 방식이다. 예시 백트래킹을 활용할 수 있는 대표적인 유형의 문제로 스도쿠가 있다. 스도쿠의 칸이 충분히 많이 채워져 있다면 논리적 추론 만으로 풀 수 있지만, 그렇지 않다면 어느 정도 무작위 대입이 필요하다. 이 문제를 브루트 포스 방식으로 푼 다면, 고려해야 할 경우의 수는 9^n 으로 매우 크다. 효율성 향상을 위해서는, 현재 단계에서 규칙을 만족하지 못할 시, 더 진행하지 않고 이전 단계로 돌아가 현재 사용한 값대신 다음 값을 대입하는 방법을 써야 한다. 백준에 있는 스도쿠 문제를 예시로 들겠다. https://www.acmicpc.net/problem/2239 223..

그래프 이론 - 1. DFS (깊이 우선 탐색) / BFS (너비 우선 탐색) DFS (Depth First Search, 깊이 우선 탐색) / BFS (Breadth First Search, 너비 우선 탐색) DFS, BFS는 그래프 문제에서 가장 기본적인 알고리즘들로, DFS와 BFS는 탐색을 진행할 때 우선시하는 방향에 따라 구분할 수 있다. DFS 원리 먼저 시작하는 정점과 인접한 정점들을 방문 배열에 추가하고, 배열의 끝 부터 탐색을 시작한다. A에서 시작한다고 가정하면 [B,C,D]를 배열에 추가하면 된다. 배열의 끝에 있는 D를 배열에서 꺼낸다. 인접한 정점을 아직 방문하지 않았다면, 해당 정점으로 이동한 후, 해당 정점과 인접한 정점들을 배열에 추가한다. D와 인접한 정점은 [H] 이므로 H를 배열의 끝에 추가하면 된다. 위의 과정을 더 탐색할 정점이 없을 때 까지 ..

그래프 이론 - 0. 소개 알고리즘을 공부하면서 처음 만나는 큰 고비는 어디일까? 난이도에 대한 체감은 사람마다 다르겠지만 대체로 그래프 문제에서 벽을 느끼는 경우가 많다. 내 경험에 비추어봐도 그러했고, 현재 속해있는 알고리즘 스터디의 스터디원들도 그러했고, 현업의 알고리즘 강사님 또한 교육생들이 가장 어려움을 겪는 파트로 그래프를 꼽으셨다. solved.ac의 태그에 따르면 그래프 이론은 백준에서 분류된 문제 유형 중 5번째로 많다. 흔히 출제되지 않는 문제라면 그냥 배제해버릴 수도 있었겠지만, 그래프 문제는 자주 등장하는 유형의 문제이기 때문에 절대로 포기해서는 안 된다. 그렇다면 사람들이 그래프 문제를 처음 접했을 때 어려움을 겪는 이유는 무엇일까? 아마도 평소 코드를 작성할 때 문자열, 배열, 사칙연산 등은 자주 사용되는..

볼록 껍질 (컨벡스 헐, Convex Hull) 알고리즘 정의 주어진 집합의 볼록 껍질은 해당 집합을 포함하는 가장 작은 볼록 다각형을 의미한다. 원리 볼록 껍질을 구하는 알고리즘은 여럿 있는데, 그 중 하나인 그레이엄 스캔(Graham Scan)을 소개한다. CCW 알고리즘(https://monogatary.tistory.com/55)을 응용한 방식이며, $O(n\log{n})$ 의 시간 복잡도를 가진다. 주어진 좌표들을 정렬한 다음, 해당 배열을 순회한다. 스택을 생성하고, 배열을 순회하면서 배열 내의 좌표 c에 대하여 다음 과정을 반복한다. 스택에 원소가 2개 이상 존재할 경우, 스택의 뒤에서 2번째 원소를 a, 마지막 원소를 b라 하자. 좌표 a,b,c의 ccw가 양수거나, 스택의 원소가 2개 미만이 남을 때 까지 스택의 마지막 원소를 제거한다. 만약 ..

CCW (Counter Clock Wise) 알고리즘 정의 CCW는 점 3개를 연결했을 때 직선의 방향을 파악할 수 있는 알고리즘이다. 구체적으로, 점 A, B, C가 있을 때, 세 점을 순서대로 이어서 나오는 선이 시계 방향을 그리는지, 반시계 방향을 그리는지, 혹은 일직선인지 알려준다. 원리 CCW는 벡터의 외적과 연관이 있다. 벡터 $u$,$v$의 외적 $u \times v$ 의 크기 $| u \times v |$ 는 $|u||v| \sin \theta$ 와 같은데, 여기서 $\theta$는 두 벡터 사이의 각도이다. $\sin{\theta}$는 $180 ^\circ < \theta < 360 ^\circ $ 일 때 음수값을 가지므로, $| u \times v |$ 의 부호에 따라 두 벡터의 방향을 파악할 수 있다. 주의할 점 벡터의 외적은 교환법칙이..

Manacher's Algorithm 소개 Manacher's 알고리즘은 문자열 내에서 가장 긴 팰린드롬을 찾는데 특화되어 있는 알고리즘이다. 만약 위 문제를 브루트포스 방식으로 접근한다면 $O(n^2)$의 시간 복잡도를 가질 것이다. 하지만 Manacher 알고리즘을 사용하면 $O(n)$ 시간으로 문제 해결이 가능하다. 원리 0. 주어진 문자열의 문자들 사이에 특수문자를 추가 (예: banana -> #b#a#n#a#n#a#) 아래 방법은 홀수 팰린드롬만 계산할 수 있기 때문에 이를 해결해주기 위해 문자열 사이에 특수 문자를 추가해준다. 1. 주어진 문자열 S와 동일한 길이의 배열 A를 생성, 초기값을 전부 0으로 설정. 2. 팰린드롬의 반지름 r, 중점 p의 초기값을 0으로 설정 3. 문자열의 인덱스 i에 대하여 다음을 수행 i > r ..

비트마스킹 (Bitmasking) 비트마스킹 이진수 표현을 이용한 연산 연산 속도가 빠르고 메모리를 적게 차지하는 장점을 가지고 있다 비트연산자 연산자 연산 예시 a & b and 두 비트가 모두 1일 시 1, 이외 0 1011(2) & 1110(2) -> 1010(2) a | b or 두 비트가 모두 0일 시 0, 이외 1 1011(2) | 1110(2) -> 1111(2) a ^ b xor 두 비트가 같을 시 0, 다를 시 1 1011(2) ^ 1110(2) -> 0101(2) ~ a not 비트가 1일 시 0, 0일 시 1 ~ 1011(2) -> 0100(2) a > b right shift a 비트의를 오른쪽으로 b칸 만큼 이동 1011(2) >> 1 -> 0101(2) * 파이썬에서 양수에 not 연산을 사용하면 음수가 나오는 ..

이전 1 다음

티스토리툴바