728x90 반응형 algorithm9 Back Tracking 백트래킹 알고리즘 백트래킹 알고리즘여러 다양한 방법을 순서대로 탑색하면서조건을 만족시키는 솔루션을 찾을 때 까지 되돌아가서 찾는 방법이다마치 미로를 탐색하는 것을 생각하면 되고탐색하다가 Promising 하지 않은 길이면 (미로같은 경우 dead end) back track해서 마지막 갈림길로 돌아가 다른 길로 탐색하는 알고리즘이다탐색 Tree를 전체 탐색하지 않는 버젼의 DFS라고 할 수도 있다 이 알고리즘을 활용한 문제들이 여러개 있는데 N-Queens 문제N-Queens 문제는 N x N 체스보드에 N개의 퀸을 서로 위협하지 않도록 배치하는 방법을 찾는 문제이다. 각 퀸은 자신의 행, 열, 대각선 상에 있는 다른 퀸을 위협하지 않는 배치를 찾는 문제이다 백트래킹을 사용하여 N-Queens 문제를 해결할 때, 상태 공.. 2024. 6. 3. k-Nearest Neighbors (k-NN) 모델 KNN k-NN(k-Nearest Neighbors)는 지연 학습 알고리즘이다.정의k-NN은 함수가 Locally (가깝게) 근사되고, 모든 계산이 함수 평가 시점까지 미뤄지는 지연 학습 알고리즘이다. 분류와 회귀 모두에서 알고리즘은 Feature 공간에서 가장 가까운 k개의 훈련 예제를 기반으로 출력을 예측한다. 작동 방식학습 단계:k-NN의 학습 단계는 없다! Lazy Learning Algorithm학습 데이터는 단순히 저장되고, 명시적인 모델은 학습되지 않는다.예측 단계:분류:주어진 테스트 인스턴스에 대해, 알고리즘은 테스트 인스턴스와 모든 훈련 인스턴스 간의 거리를 계산한다.가장 가까운 k개의 훈련 인스턴스(이웃, neighbor)를 식별한다.테스트 인스턴스의 클래스 레이블은 k개 이웃 중 다수결 투표.. 2024. 5. 26. Strassen Algorithm (스트라센 알고리즘) 행렬의 곱 위와같은 두 행렬들이 있다하자 그러면 행렬 A와B의 곲 C는 다음과 같이 표현된다 그러면 아래와같이 이해될 수 있다 이 행렬의 곱 알고리즘의 시간 복잡도는 O(n^3)의 복잡도를 가진다 그래서 매우 큰 행렬들의 곱을 계산할 때는 매우 버거워진다 그의 결과로 분할정복의 한 방법인 Strassen 알고리즘이 나왔다 각 행렬들을 이렇게 4분할을 해보자 그러면 이렇게 계산해도 결과가 나온다 하지만 이건 또 결국 계산을 하다보면 O(n^3)의 복잡도를 가진다 그럼 Strassen 알고리즘은 어떻게 분할하냐? 위의 행렬들을 정의 해준다 그럼 아래와 같은 곱이 성립 한다 행렬의 곱셈을 한번 줄이고! 덧셈을 늘렸다! 그래서 O(n^3)->O(n^2) 로 수렴하게 된다 왜냐 행렬의 곱셈은 for문 골치거리이기 때문에 그.. 2024. 3. 2. 이전 1 2 다음 728x90 반응형
