'👩‍💻 프로그래밍/🎐 알고리즘' 카테고리의 글 목록

2024.05.05· 👩‍💻 프로그래밍/🎐 알고리즘

1. KMP 알고리즘패턴을 문장 안에서 좌에서 우로 비교하는 것. 브루트-포스 알고리즘과 다르게 패턴의 위치를 좀더 효율적으로 이동시킨다. 패턴과 문장의 불일치가 발생했을 때 중복연산을 최대한 피하면서 패턴을 우측으로 이동시킨다. 이를 위해서는 문장의 불일치 발생 시, 얼마만큼 건너 뚜니 후에 비교연산을 할 것인가를 판단하여야 한다. 2. 실패함수(파이 배열)KMP 알고리즘에서 탐색 문자열의 접두사와 접미사의 일치 부분을 계산하여 배열의 형태로 저장하는 함수i는 접미사 가리키는 인덱스, len은 접두사 가리키는 인덱스7번째 : 6번째에 len=2, i=5일 때, A가 이미 일치했던 사실을 알기 때문에 이를 이용하기 위해 len은 lps[len-1]로 이동하는 것. 이는 KMP 알고리즘 원리와 동일하다.노..

라빈-카프 알고리즘

2024.05.05· 👩‍💻 프로그래밍/🎐 알고리즘

1. 라빈-카프 알고리즘라빈-카프 알고리즘은 문자열에 해싱 기법을 사용하여 해시 값으로 비교하는 알고리즘 해시 값이 다르다면 두 문자열이 다르다는 것을 보장한다. 하지만 문자열이 달라도 해시 값이 같을 수 있다.👉 우리는 이것을 Spurious Hit이라 한다.Spurious Hit 때문에 해시 값이 같을 경우 추가로 문자열이 같은지 비교하는 작업이 필요하다. 이 특징을 이용하여 라빈-카프 알고리즘은 패턴의 해시값을 텍스트의 부분 문자열의 해시값과 일치하는지 비교하는 작업을 한다. 따라서 라빈-카프 알고리즘은 다음 문자열에 대한 해시 값을 계산해야 한다.길이가 m인 패턴 자체길이가 m인 텍스트의 모든 부분 문자열 2. 해시 함수사용 예시🟩 rolling hash각 위치에서 해시 함수를 처음부터 다시 ..

브루트-포스 알고리즘

2024.05.05· 👩‍💻 프로그래밍/🎐 알고리즘

1. 완전탐색 알고리즘즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다.이 알고리즘의 강력한 점은 예외 없이 100% 확률로 정답만을 출력한다. BUT 그만큼 높은 시간 복잡도를 갖는다.너비 우선 탐색(BFS)와 관련이 깊다. 🌟 완전 탐색 알고리즘과의 차이점완전 탐색 알고리즘 : 모든 경우의 수를 전부 탐색하는 알고리즘, 그 결과를 찾는 것보다 탐색한다는 과정에 중점브루트포스 알고리즘 : 문제를 해결하기 위해, 모든 경우를 탐색하고 답을 도출하는 알고리즘, 결과를 찾는 것에 중점 2. 문제 해결 방법주어진 문제를 선형 구조로 구조화한다.구조화된 문제 공간을 적절한 방법으로 해를 구성할 때까지 탐색한다.구성된 해를 정리한다. 3. 사용 조건 및 예제문제에서 달성하고자 ..

최장 공통 부분 수열(LCS) cf. 최장 공통 문자열

2024.04.29· 👩‍💻 프로그래밍/🎐 알고리즘

🟩 LCS, 최장 공통 부분 수열 Longest Common Subsequence (cf. Longest Common Substring 최장 공통 문자열) 최장 공통 부분 수열의 경우, 부분수열이기 때문에 문자 사이를 건너뛰어 공통되면서 가장 긴 부분 문자열을 찾으면 된다.최장 공통 문자열의 경우, 부분 문자열이 아니기 때문에, 한 번에 이어져 있는 문자열만 가능하다. 🟩 최장 공통 문자열if i == 0 or j == 0: # 마진 설정 LCS[i][j] = 0elif string_A[i] == string_B[j]: LCS[i][j] = LCS[i - 1][j - 1] + 1else: LCS[i][j] = 0 LCS라는 2차원 배열을 이용하여 두 문자열을 행, 열에 매칭한다. 편의상 i, j가..

행렬의 연쇄적 곱셈

2024.04.29· 👩‍💻 프로그래밍/🎐 알고리즘

🟩 n개의 행렬을 연쇄적으로 곱할 때 최소의 기본 곱셈 횟수를 갖는 행렬의 곱셈 순서를 구하는 문제i x j 행렬과 j x k 행렬을 곱하기 위해서는 i x j x k 번 만큼의 곱셈이 필요하다.연쇄적으로 행렬을 곱할 때 어떤 행렬을 먼저 수행하느냐에 따라서 필요한 총 곱셈의 횟수가 달라진다.🟩 연쇄행렬행렬의 곱셈은 아래와 같이 결합법칙이 성립한다.A x (B x C) = (A x B) x C그러나, 행렬을 곱하는 순서에 따라 곱하는 횟수가 달라진다. 👉 즉, 연쇄행렬 최소곱셈 알고리즘은 행렬곱셈에서 곱하는 순서에 따라 곱셉의 횟수가 달라지는데 이러한 법칙을 이용하여 최소로 곱하는 횟수를 구하는 것이다. 연쇄행렬 최소곱셈 알고리즘 재귀관계식 ✨ 예제로 이해하면 쉽게 이해 가능!EX) A(20x1),..

포드-풀커슨 알고리즘(최대 유량 문제)

2024.04.19· 👩‍💻 프로그래밍/🎐 알고리즘

🌟 최대 유량 문제(=네트워크 플로우) 특정한 지점에서 다른 지점으로, 얼마나 많은 유량을 동시에 보낼 수 있는지 계산하는 문제 ✏️ 용어 정리 용량 : c(u,v) 정점 u에서 v로 전송할 수 있는 최대 용량 유량 : f(u,v) 정점 u에서 v로 실제 흐르고 있는 유량 잔여 용량 : r(u,v) = c(u,v) - f(u,v) 간선의 용량과 실제로 흐르는 유량의 차이 소스 s 모든 유량이 시작되는 정점 싱크 t 모든 유량이 도착하는 정점 증가 경로 소스에서 싱크로 유량을 보낼 수 있는 경로 ✏️ 기본 속성 용량 제한 속성 f(u,v)

플로이드 알고리즘(최단 경로)

2024.04.19· 👩‍💻 프로그래밍/🎐 알고리즘

🟩 모든 정점쌍에 대해서 둘 사이의 최단거리를 구할 수 있다. cf. 다익스트라 : 한 시작점에서 다른 정점까지의 최단 거리 단, 플로이드 알고리즘은 음수 가중치가 없는 무조건 양수의 그래프에서 동작 a 👉 b로 이동할 때, 경유점은 c 플로이드 알고리즘은 두 정점 사이의 어떤 경유점이 존재한다면 경유점을 거쳐가는 것을 확인하면서 더 짧은 것을 선택 🟩 구현 1. 위의 그래프를 우선 배열로 구현해야 한다. 초기값은 아주 큰 값으로 설정해야 한다. 그리고 자기 자신까지의 비용은 0으로 설정한다. 2. 시작점을 i, 끝점을 j, 경유점을 k라 할 때, 구하는 식은 다음과 같다. adj[i][j] = MIN(adj[i][j], adj[i][k] + adj[k][j]) 항상 작은 값만을 갖게 되므로 직접적으로 ..

벨만-포드 알고리즘(최단 경로)

2024.04.19· 👩‍💻 프로그래밍/🎐 알고리즘

🟩 한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘 간선의 가중치가 음수일 때도 최단 거리를 구할 수 있다. 🌟 다익스트라 vs 벨만-포드 1번 노드에서 3번 노드로 가는 최단 거리를 구한다고 할 때, 경로1. 1번 👉 3번 (비용 : 10) 👉 다익스트라 알고리즘 경로2. 1번 👉 2번 👉 3번 (비용 : 5) 👉 벨만-포드 알고리즘 ✏️ 다익스트라 알고리즘 매번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하여 한 단계씩 최단 거리를 구해나간다. 음수 간선이 없다면 최적의 해를 구할 수 있다. 시간 복잡도가 빠르다 (O ElogV) ✏️ 벨만-포드 알고리즘 (정점-1)번의 매 단계마다 모든 간선을 전부 확인하면서 모든 노드간의 최단 거리를 구해나간다. cf. 다익스트라와의 차..

다익스트라 알고리즘(최단 경로)

2024.04.19· 👩‍💻 프로그래밍/🎐 알고리즘

🟩음의 가중치(음의 간선, 음의 값)가 없는 그래프의 한 노드에서 각 모든 노드까지의 최단 거리를 구하는 알고리즘 두 꼭짓점 간의 가장 짧은 경로를 찾는 알고리즘이지만 한 꼭짓점을 "소스" 꼭짓점으로 고정하고, 그래프의 다른 모든 꼭짓점까지의 최단경로를 찾는 알고리즘으로 최단 경로 트리를 만드는 것으로도 사용 🟩 그리디이자 동적계획법 그리디 : 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택 다이나믹 프로그래밍 : 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신 👉 가능한 적은 비용으로 가장 빠르게 해답을 도달하는 경로를 찾아내는 대부분의 문제에 응용된다. 🟩 예제 A노드에서 출발하여 F노드로 가는 최단경로를 구하는 문제 S = 방문한 노드들의 집합 d[N] = A -> N까지 계산된 최단 거..

프림 알고리즘 (최소 신장 트리)

2024.04.19· 👩‍💻 프로그래밍/🎐 알고리즘

🟩 시작 정점에서 정점을 추가해가며 단계적으로 트리를 확장하는 기법 즉, 탐색 정점에 대해 연결된 인접 정점들 중 비용이 가장 적은 간선으로 연결된 정점을 선택 🟩 동작 1. 시작 단계는 시작 노드만이 최소 신장 트리 집합에 속한다. 2. 트리 집합에 속한 정점들과 인접한 정점들 중 가장 낮은 가중치의 간선과 연결된 정점에 대해 간선과 정점을 최소 신장 트리 집합에 넣는다 (사이클을 막기 위해 연결된 정점이 이미 트리에 속한다면 그 다음 순서를 넣는다) 3. 2번 과정을 MST 집합의 원소 개수가 그래프의 정점의 개수가 될 때까지 반복한다. 시작 정점 A A와 인접한 노드 B, C 중 C가 가장 가중치가 낮은 간선으로 연결되어 있으니, C를 집합에 넣고 비용에 AC 가중치를 더한다. AC와 인접한 노드들..

크루스칼 알고리즘 (최소 신장 트리)

2024.04.19· 👩‍💻 프로그래밍/🎐 알고리즘

🟩 최소 신장 트리 신장 트리 중 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘 👉 크루스칼 알고리즘 : 가장 적은 비용으로 모든 노드 연결 가능 🌟 신장 트리 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 🌟 최소 신장 트리 신장 트리 중에서도 최소한의 비용으로 만들 수 있는 신장 트리 왼쪽 그래프에서 최소 신장 트리를 찾으면 25를 제외한 2개의 간선 (23+13)으로 이루어진 신장트리 즉, 신장 트리의 조건을 만족하면서 최소 비용으로 만들 수 있는 신장 트리 🟩 크루스칼 알고리즘 동작과정 1. 간선 데이터를 비용에 따라 오름차순으로 정렬한다. 2. 간선을 하나씩 확인하면서 현재의 간선이 사이클을 발생시키는지 확인 👉 사이클 발생 여부에 따라, 최소 신장..

B-트리

2024.04.16· 👩‍💻 프로그래밍/🎐 알고리즘

🟩 균형 탐색 트리 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조 키의 개수 (t-1)~(2t-1) 개 자식 노드의 개수 t~2t 개 🟩 성질 1. 노드에는 2개 이상의 데이터가 들어갈 수 있으며, 항상 정렬된 상태로 저장된다. 2. 내부 노드는 ceil(m/2) ~ m 개의 자식을 가질 수 있다. 최대 m개의 자식을 가질 수 있는 B트리를 m차 B트리라 한다. ceil() 함수는 올림 함수이다. 즉, ceil(3/2) = 2이다. 즉, 3차 B트리의 리프 노드와 루트노드를 제외한 내부 노드는 2-3개의 자식을 가질 수 있다. 3. 특정 노드의 데이터(key)가 K개라면, 자식 노드의 개수는 K+1개여야 한다. 특정 노드의 데이터가 2개라면, 자식 노드는 ..

티스토리툴바