알고리즘
-
알고리즘: Boyer-Moore 과반수 투표 알고리즘알고리즘 2024. 6. 11. 14:04
과반수 찾기 알고리즘:n크기의 배열이 주어지고 그 안에는 n/2보다 많이 중복되는 수 x가 존재한다면,그 수를 찾는 알고리즘이다.입력: 정수의 배열 A[n]을 입력으로 받는다ex: {1, 1, 2, 5, 3, 5, 1, 3}출력:A[n]에서 n/2번 이상 나오는 원소가 있다면 그 원소를 출력한다.더보기Brute Force:각 원소마다 자기 뒤에 나오는 횟수를 세어본다.worst case: O(n2)Sorting Method:예시: 3 1 2 2 1 1 1 1 2 1 3 2 1 1 1 2배열을 정렬함 (시간복잡도 = O(n log n))1 1 1 1 1 1 1 1 1 2 2 2 2 2 3 3하나씩 읽고 바로 직전 원소와 같다면 count해서 n/2보다 큰 경우 return. (시간복잡도 = O(n))맨 마..
-
알고리즘: DFS, BFS (너비우선탐색, 깊이우선탐색)알고리즘 2024. 6. 6. 18:04
DFS와 BFS는 그래프를 탐색하는 알고리즘이다.DFS(Depth-First Search)DFS는 그래프를 깊이 우선으로 탐색한다. 즉, 시작 노드에서 시작하여 한 갈래를 끝까지 탐색한 후에 다른 갈래를 탐색한다.구현 방법스택이나 재귀함수로 구현한다.동작 과정시작 노드를 스택에 넣는다.예를 들어, 시작 노드가 A라고 합시다. 처음에는 스택에 A만 들어 있다.스택: [A]스택에서 노드를 하나 꺼내어 방문한다.스택에서 A를 꺼내어 방문한다.방문한 노드: A스택: []방문한 노드의 인접 노드 중 방문하지 않은 노드를 스택에 넣는다.예를 들어, A의 인접 노드가 B와 C라면, 이들을 스택에 넣는다.스택: [B, C]스택이 빌 때까지 2-3 단계를 반복한다.다음으로, 스택에서 C를 꺼내어 방문한다.방문한 노드: ..
-
알고리즘: Knapsack(배낭 알고리즘)알고리즘 2024. 6. 4. 16:34
Knapsack 알고리즘:Knapsack 알고리즘이란 n개의 물건을 배낭에 최대 가치로 넣는 문제이다.배낭에는 무게 수용치가 정해져있다. (ex: 15kg)n개의 물건은 각각 다른 가치와 다른 무게가 정해져있다.위 문제는 물건을 쪼갤 수 있는 경우와 아닌 경우로 나뉜다. (Fraction Knaspack Problem & 0-1 knapSack Problem)0-1 knapSack Problem(쪼갤 수 없는 배낭문제):위 문제는 대표적인 DP 알고리즘 문제이다. (동적계획법)DP 알고리즘이란 큰 하나의 문제를 작은 여러개의 문제로 쪼개어 순차적으로 풀어나가는 방식이다. 위와 같은 경우를 보자.배낭: 최대 15kg물건: ($4, 12kg), ($2, 1kg), ($10, 4kg), ($2, 2kg), (..
-
알고리즘: Convex Hull(컴벡스 헐), Graham Scan, Quick Hull알고리즘 2024. 6. 1. 16:18
Convex Hull:차원 평면에 여러개의 점이 있을 때, 그 점 중 일부를 이어서 나머지 점을 내부에 포함할 수 있는 볼록 다각형을 만드는 알고리즘.볼록 다각형이란 다각형 내부의 두 점을 잇는 어떤 선분도 다각형 외부로 나가지 않는 단순 다각형사전지식:위 문제를 이해하기 위해서는 우선 CCW 알고리즘을 알아야한다.https://qktjwl123.tistory.com/95 알고리즘: CCW(Counter Clock Wise)CCW 알고리즘: 3개의 점 A, B, C가 있을 때 이 점 3개를 이은 직선의 방향을 알고자 할 때 유용한 기하 알고리즘. 세 점 A(x1, y1), B(x2, y2), C(x3, y3)이 주어졌을 때두 벡터 (x2-x1, y2-y1), (x3-x1, y3-y1)의 외qktjwl1..
-
알고리즘: 확장 유클리드 호제법알고리즘 2024. 5. 28. 16:17
우선 유클리드 호제법을 먼저 공부하고 보자!!https://qktjwl123.tistory.com/97 알고리즘: 유클리드 호제법(최대공약수, gcd)유클리드 호제법유클리드 호제법은 두 수 A,B의 최대공약수를 구하는 알고리즘이다. 방법A=0이면 GCD(0,B)=B이므로 GCD(A,B)=B이고 멈춤.B=0이면 GCD(A,0)=A이므로 GCD(A,B)=A이고 멈. A를 A = B⋅Q + R의 형qktjwl123.tistory.com모듈러 역수란?확장 유클리드 알고리즘은 모듈러 역수를 구하는 알고리즘이다.모듈러 역수란 A*B (mod C) = 1이 되게하는 B를 뜻한다. (A와 C는 주어지고 B를 구해야한다.)*모듈러 역수는 A와 C가 서로소일 경우에만 존재한다.*GCD(A, C) = 1인 경우 A (m..
-
알고리즘: 유클리드 호제법(최대공약수, gcd)알고리즘 2024. 5. 28. 10:54
유클리드 호제법유클리드 호제법은 두 수 A,B의 최대공약수를 구하는 알고리즘이다. 방법A=0이면 GCD(0,B)=B이므로 GCD(A,B)=B이고 멈춤.B=0이면 GCD(A,0)=A이므로 GCD(A,B)=A이고 멈. A를 A = B⋅Q + R의 형식으로 씀. (Q는 A를 B로 나눈 몫.)GCD(A,B) = GCD(B,A-B)이므로 유클리드 호제법을 이용하여 GCD(B,A-B)를 찾음. 예시:270과 192의 최대공약수 - GCD(270,192)GCD(270,192) - 270과 192의 최대공약수 찾기A=270, B=192A ≠ 0B ≠ 0270 = 192 * 1 +78GCD(270,192)=GCD(192,78) - 이기 때문에 192와 78의 최대공약수 찾기A=192, B=78A ≠0B ≠0192 =..
-
알고리즘: CCW(Counter Clock Wise)알고리즘 2024. 5. 23. 09:45
CCW 알고리즘: 3개의 점 A, B, C가 있을 때 이 점 3개를 이은 직선의 방향을 알고자 할 때 유용한 기하 알고리즘. 위 알고리즘을 사용하면 선분 AB에 대해 점 C가 선분의 왼쪽에 있는지 오른쪽에 있는지 판단할 수 있다.다른말로 표현하면 시계방향을 그리는지 반시계 방향을 그리는지 알 수 있다. 세 점 A(x1, y1), B(x2, y2), C(x3, y3)이 주어졌을 때두 벡터 (x2-x1, y2-y1), (x3-x1, y3-y1)의 외적의 부호가 방향을 결정한다. 일반화한 외적의 식은 다음과 같다: (x2-x1)*(y3-y1) - (y2-y1)*(x3-x1) 시계, 반시계, 직선 총 3가지 경우가 존재할 수 있음.시계: -1, 직선: 0, 반시계: 1int ccw(int x1, int y1,..
-
알고리즘: (BIT 부분 합, 누적 합)알고리즘 2024. 3. 27. 18:45
부분 합:A[n]배열이 있을 때, a,b (0A[a]~A[b]까지 더하는 문제. 1. Brute-force1. 순회하여 부분 합을 구한다. 전처리: x시간복잡도: O(n) 2. O(n) 전처리, O(sqrt(n)) 질의1. 배열 A를 sqrt(n)개의 원소씩 그룹으로 묶음2. 각각의 합을 구함3. a, b가 주어지면 양 끝부분의 합만 직접 구하고 중간 부분은 미리 구한 합을 더해줌 전처리: O(n)시간복잡도: O(sqrt(n)) 전처리 후 sqrt(n)개의 그룹, worst case: a=1, b=n-1 중간 값을 처리하는 시간복잡도: sqrt(n)-2 (총 그룹의 수-양 끝의 2그룹) 양 끝 값을 처리하는 시간복잡도: 2sqrt(n) (양 그룹의 원소의 수) 총 시간 복잡도..