본문 바로가기
반응형

코딩/알고리즘,디자인패턴8

내적 내적 점곱(점들의 곱)이라고 불리기도 하는 내적은 스칼라값을 내는 벡터 곱셈의 일종이다. 결과가 스칼라 값이라 스칼라 곱이라고 부르기도 한다. 벡터 A = (Ax, Ay, Az)일때, 두 벡터의 곱은 AxBx+AyBy+AzBz이다. 이는 A*B = ||A|| ||B|| cosC 가 되며 C를 통하여 AB사이의 각도를 구할 수 있다. (||A|| = A벡터의 크기 = √(x^+y^+^))) 그 증명은 A = (1, 2, 3)이고 B = (-4,0, -1)이라고 할 때, A*B = (1,2,3) * (-4,0,-1) = -4-3 = -7 ||A|| = √(1^+2^+3^) = √14 ||B|| = √17 cosC = A*B/||A||||B|| = -7/√14√17 C = acos(-7/√14√17) = 약1.. 2022. 1. 5.
백트래킹(Backtracking) 알고리즘 설명 DFS를 기반으로 생성된 알고리즘으로, 기존 DFS는 모든 경우의 수를 찾아가기 때문에 불필요한 탐색이 존재하여 이 부분이 문제가 되는 경우가 있었다. 때문에 이를 보완하기 위해서 나온 알고리즘으로, 현재 탐색을 진행하고있는 루트가 이미 실패가 예정된 루트라면 해당 루트를 종료하고 더 이상 그 루트를 통하여 탐색을 진행하지 않고 이전으로 돌아가는 것을 백트래킹이라고 칭한다. 때문에 현재 루트의 가능성을 판단하는 조건이 잘 짜여질수록 효율이 올라가게 된다. 보통 DFS를 사용하는 문제에서, 완전탐색 시 경우의 수가 너무 많아지는 문제에 대하여 조건을 걸어서 루트를 줄이는 역할을 한다. 대표적인 백트래킹 문제인 N-Queen에서의 예시 문제를 요약하자면 퀸이 서로 겹치지 않게 NxN크기의 판에 N개의 .. 2021. 7. 30.
에라토스테네스의 체 알고리즘 진행 과정 순차 탐색 -> 색칠되지 않은 칸 발견 -> 해당 칸을 소수로 분류하고, 해당 숫자의 곱을 모두 색칠. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 #include using namespace std; bool Num[1000001] = {}; int main() { int Start, End; cin >> Start >> End; for (int i = Start ; i 2021. 4. 8.
그리디(Greedy) 알고리즘 Greedy(욕심) 알고리즘이란? 매 선택에서 지금 최선인 답을 선택하는 알고리즘. 다만, 종합적으로 판단하는 것이 아니기 때문에 결과적으로 정답이 아닐 수 있다. 진행 과정 두 숫자를 거쳐서 총 합의 최소를 구하는 과정에서, 정답은 시작->20->30 으로 총합 50이지만, 그리디 알고리즘을 통하여 접근하면 해당 알고리즘은 언제나 "현재 선택지의 상황만"고려하여 답을 찾는 알고리즘이기 때문에 1. 20보다 15가 더 적으니 15로 진행. 2. 100과 200중 100이 더 적으니 100으로 진행. 이런 방식을 통하여 총합 115가 정답으로 도출된다. 2021. 4. 6.
반응형