✔️알고리즘 브루트포스 ✔️접근방법 1. 주어진 체스판의 모든 8x8 형태의 부분집합 경우의 수를 다 검사한다. 2. 8x8 체스판은 BWBWBWBW 이나 WBWBWBWB가 반복되면서 이루어져 있다. 어떤 배열이 먼저 시작하는 것이 효율적인지는 알 수 없기 때문에 각각의 경우를 모두 검사한다. mini=64 #8x8 체스판 모두 바꾸는 경우가 최대 str1 = 'BWBWBWBWWBWBWBWBBWBWBWBWWBWBWBWBBWBWBWBWWBWBWBWBBWBWBWBWWBWBWBWB' str2 = 'WBWBWBWBBWBWBWBWWBWBWBWBBWBWBWBWWBWBWBWBBWBWBWBWWBWBWBWBBWBWBWBW' def compare_str(chass, str): global mini #전역변수 사용 위해 g..
알고리즘
💡Floyd - Warshall - 모든 노드 ~ 모든 노드 사이의 최단거리를 구하기 위해 사용하는 알고리즘 (다익스트라 알고리즘: 한 노드~ 모든 다른 노드 사이의 최단거리 구함) - D(a,b) = min(D(a,b), D(a,k)+D(k,b)) - step1. 어떤 경유지도 거치지 않고 출반~도착 최단거리 기본 테이블에서 시작 step2. 각 출발~도착 경로에서 다른 노드(경유지)를 들른다고 생각하고 최단거리 구함 만약 경유지를 들르지 않는 것이 더 최단거리면 D(a,b)를 선택해 그대로 유지, 경유지를 들리는 것이 더 최단거리면 D(a,k)+D(k,b) 선택 => 경유지(k) = 1부터 시작해서 4까지 업데이트 step3. 가장 마지막 테이블이 최종 결과 (배열에도 최종 결과가 저장) void f..
💡동적 계획(Dynamic Programming) - 작은 문제부터 해결하여 그 결과를 큰 문제를 푸는데 사용하는 bottom-top 방식의 알고리즘 (분할정복과 반대) 💡이항계수 ✔️ 재귀호출을 사용한 하향식 접근 방식 int bin(int n,k){ if(k==0||k==n) return 1; else bin(n-1,k) + bin(n-1,k-1) - 항의 개수 = 2(n, k) - 1 - bin(n-1,k) 값 => bin(n-2,k-1), bin(n-2, k) 필요 (재귀호출에 의해서) bin(n-1,k-1)값 => bin(n-2,k-1), bin(n-2,k-2)필요 - 위에서 아래로 , 큰문제를 작은문제로 분할하여 계산하는데 위 예시처럼 분할되어 독립적으로 수행되는 특성 때문에 같은 계산을 여러..
💡그래프 - 경로 : 두 노드 사이에 이음선으로 연결된 노드의 나열 - 연결 그래프 - 부분그래프 - 방향성/비방향성 그래프 : - 경로 : - 순환경로 : 💡신장트리 - 연결된 비방향성 그래프에서 순환경로가 없어지도록 이음선을 제거해 구성한 그래프 - 모든 정점을 다 포함하되 순환경로가 존재하지 않는 연결 그래프 💡MST (최소비용 신장 트리) - 신장 트리가 되는 부분그래프 중에서 가중치의 합이 최소가 되는 그래프 - 순환경로X ex) 도로건설, 통신, 배관 - MST를 찾기 위한 알고리즘으로는 무작정 알고리즘, 탐욕적 알고리즘, 프림 알고리즘, 크루스칼 알고리즘 등 존재 무작정 알고리즘 : 모든 경우 다 고려 탐욕적 알고리즘 : 적절한 최적해 선정절차 따라 하나의 이음선 선정(선정) -> 순환경로 ..
