이분 매칭 A 집단이 B 집단을 선탁하는 방법에 대한 알고리즘 즉, 2개의 정점 그룹이 있을 때, 그룹에서 그룹으로 정점의 최대 매칭을 찾는 알고리즘이다. 위와 같은 두 그룹의 정점이 있을 때 각 그룹을 연결할 수 있는 간선의 정보는 아래와 같다. A : 2, 5 B : 2, 3, 4 C : 1, 5 D: 1, 2, 5 E : 2 이 정보를 가지고 정점을 한 번만 사용해서 최대한 많은 정점이 매칭되게 해보자. DFS와 visted 배열을 활용하여 구해준다. 우선 A가 매칭가능한 번호 중 빠른 번호인 2를 매칭 시켜준다. 이후 B를 매칭 시켜주는데 B가 연결할 수 있는 가장 빠른 번호도 2이므로 A로 돌아가 매칭 시킬 수 있는 다른 정점이 있는지 살펴본 후 존재한다면 A가 양보해준다. 따라서, A - 5,..

목차 Segment Tree? 구현 query 응답하기 업데이트 1. Segment Tree? 어떤 데이터가 존재할 때, 특정 구간의 결과값을 구하는데 사용하는 자료구조이다. 단순한 구간합 뿐만 아니라주어진 쿼리에 대해 빠르게 응답하기 위한 자료구조!! 여기서는 이해하기 쉽게 구간합을 예시로 세그먼트 트리를 알아볼 예정 아래와 같은 배열이 존재할 때, 구간합을 구해보자. 배열을 돌면서 원하는 구간의 합을 더해주면 된다! 배열의 크기가 커진다면, 시간이 더 많이 걸릴 것이다. 따라서, 구간별 합을 구해 저장해둔다면 빠르게 찾을 수 있을 것이다!! 세그먼트 트리는 Binary Tree(이진 트리) 구조를 가지고 있다. 배열의 크기 Full Binary Tree 일 경우 높이는 logN 노드의 개수 2 * (..

CCW(Counter Clock Wise) 알고리즘은 벡터의 외적을 통해 세 점의 위치 관계가 시계방향인지 아닌지 판별하는 알고리즘이다. 선분 교차 판별 ccw 알고리즘을 이용하여 선분 교차를 판별할 수 있다. 한 선분을 기준으로 같은 방향에 위치할 경우 선분은 교차되지 않고 그렇지 않은 경우 교차한다. 즉, ccw 함수의 수행 결과로 반시계 방향이 1, 시계 방향의 -1을 갖는다면 CCW(A, B, C)의 결과와 CCW(A, B, D) 결과의 곱이 -1 이 되는 경우 서로 다른 방향에 위치하게 된다. 다만, 아래와 같이 다른 방향이어도 교차하지 않는 경우가 있다. 이 경우는 선분 CD 에 대해서도 CCW 알고리즘을 수행하여 판별한다. 또한, 평행인 경우도 존재하므로, 조건을 잘 분기해주어야 한다. 신발..

연속 행렬이 주어질 때, 행렬의 곱셈 중 가장 효율적인 방법을 찾는 이론 어떤 순서로 곱셈을 할지 결정 하는 것 만약, A - B - C - D 행렬이 있을 때 아래와 같은 형태로 구성될 수 있다. - 결합 법칙이 성립 (ABC)D = (AB)(CD) = A(BCD) = ... 곱셈 순서를 어떻게 정하는 같은 결과이므로, 가장 연산 횟수가 적은 것이 효율적일 것이다. 만약 A가 10 x 30, B가 30 x 5, C가 5 x 60 이면 (AB)C = (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 A(BC) = (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 따라서 아래의 점화식을 바탕으로 최적화 시킬 수 있다. 위의 식을 토대로 ABC의 최..

배낭문제(Knapsack) - 냅색 알고리즘의 경우 짐을 쪼갤 수 있냐 없냐로 나뉜다. 짐을 쪼갤 수 있는 경우를 Fractional Knapsack Algorithm 그 반대의 경우를 0-1 Kanpsack Algorithm이라고 한다. 1. Fractional Knapsack 물건의 가격을 무게로 나누어 무게 대비 가격이 비싼 순서로 정렬 남은 배낭이 감당할 수 있는 무게보다 < 물건의 무게가 많이 나가면 잘라서 넣으면 된다. Greedy로 해결 가능!! 사용하기 쉬운 알고리즘이라 따로 코드는 없고 개념만 보자면 각각 부피가 1 2 3, 단가가 3, 2, 1 인 금반지, 은반지, 동반지가 있을 때 여유공간이 4인 배낭이 존재한다. 이 때, 각 반지의 단가 / 부피를 해준 후 값이 높은 순으로 정렬해준..

1. 위상 정렬? 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미한다. 시간 복잡도는 O(V+E) 예시 -> 학교 커리큘럼과 같이 선수과목을 고려하여 학습 순서 결정 아래 그림에서 세 과목을 모두 듣기 위해 적절한 학습 순서는 자료구조 -> 알고리즘 -> 고급 알고리즘 2. 차수 진입차수(Indegree) 특정한 노드로 들어오는 간선의 개수 진출차수(Outdegree) 특정한 노드에서 나가는 간선의 개수 위 그림에서 자료구조 -> 진입차수 0, 진출차수 2 알고리즘 -> 진입차수 1, 진출 차수 1 고급알고리즘 -> 진입차수 2, 진출차수 0 3. 구현 큐를 이용하여 위상 정렬 알고리즘을 구현할 수 있다. 입력을 받으며 각 노드별로 진입차수를 + 해준다. 진..

알고리즘 기법이라고 볼 수는 없지만 비트마스크 기법을 이용하여 풀 수 있는 문제가 꽤 보여서 알아보기로 하였다. 개념 컴퓨터의 최소 연산 단위 bit 이진수를 나타내기 위해 0과 1로만 이루어져 있는데, 비트 연산을 통하여 빠르게 해결 할 수 있다. 예를 들면 -> bfs나 dfs를 하며 visited를 체크 해줄 때, 크기가 10인 배열을 만드는 경우가 있는데 0b0000000000 와 같이 비트마스킹으로 똑같은 표현을 할 수 있다. 즉 더 작은 메모리를 사용하여 표현 가능하다. 장점 비트 연산은 삽입, 삭제, 조회가 빠르다. 코드가 간결해지며 정수 표현으로 dp문제 해결 가능 비트 연산 2022.08.10 - [ALGORITHM/알고리즘 알아보기] - 알고리즘 - 부분 집합 알고리즘 - 부분 집합 완..

이전 포스팅에서는 dp를 이용하여 회문을 판별하는 알고리즘을 알아보았다. 2023.01.21 - [ALGORITHM/알고리즘 알아보기] - [Algorithm] 팰린드롬 판별 알고리즘 [Algorithm] 팰린드롬 판별 알고리즘 회문이란 반대로 읽어도 원본과 같은 단어를 말한다. 3개의 for 문을 사용하여 모든 회문을 찾을 수 있지만, 이 경우 시간 복잡도가 O(N^3)이 되므로, 이미 반복한 부분인 하위 문제의 결과를 DP table cheon2308.tistory.com 이 경우 시간복잡도가 O(N^2)이 되어 10000이상의 길이를 가진다면 시간이 오래걸린다. 이번엔 O(N)의 시간복잡도를 가지는 Manacher 알고리즘을 알아보자. 동작 원리 우선 문자열 S에 대해 배열 A를 구할 수 있다. 배..

회문이란 반대로 읽어도 원본과 같은 단어를 말한다. 3개의 for 문을 사용하여 모든 회문을 찾을 수 있지만, 이 경우 시간 복잡도가 O(N^3)이 되므로, 이미 반복한 부분인 하위 문제의 결과를 DP table에 저장하여 시간 복잡도를 줄이는 알고리즘 이 경우 2개의 for문을 이용하므로 O(N^2)의 시간 복잡도를 가지게 된다. N = int(input()) nums = [*map(int, input().split())] M = int(input()) dp = [[0] * (N) for _ in range(N)] # 각 한 단어씩은 팰린드롬 이므로 True 체크 for i in range(1,N): dp[i][i] = True # 11, 22와 같이 연속된 값인 경우 팰린드롬이므로 True for j..