[ALGORITHM]12 [AIGORITHM THEORY] GREEDY(탐욕법) 개념정리 개념 컨셉 탐욕법 이라고 불린다. 현재 상황에서 지금 당장 좋은것만을 고르는 방법 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않음 보통 코딩테스트에 출제되는 그리디 알고리즘의 문제는, 문제를 풀기위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구 그리디 알고리즘을 이용한 해결은 정당성 분석이 중요! 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토 문제에서 가장 큰 순서, 가장 작은 순서와 같이 기준을 암시적으로 제시해준다. 문제 해결 방법 선택 절차 현재 상태에서의 최적 해답을 선택한다. 적절성 검사 선택된 해가 문제의 조건을 만족 하는지 검사한다. 해답 검사 원래의 문제가 해결되었는지 검사, 해결되지 않았다면 선택.. 2023. 5. 15. [AIGORITHM THEORY] DP (Dynamic Programing) 개념정리 개념 컨셉 다이나믹 프로그래밍, DP, 동적 계획법 모두 같은걸 의미함 최적해를 구하기위한 시간, 또는 메모리공간이 많이 필요한 경우 사용하게 된다. 컴퓨터는 연산속도에 한계가 있고, 메모리 공간도 한정적이기 때문 연산속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘이 필요하다. 메모리를 적절히 사용해, 수행시간 효율성을 비약적으로 향상시킨다. 한번계산한 문제는 다시 계산하지 않는다. 이미 계산된 결과는 별도의 영역(dp 테이블) 에 저장, 다시 계산하지 않도록 한다. // Memoization 구현방식은 크게 두가지로 나뉜다. top-down bottom-up 일반적으로 프로그래밍에서 dynamic의 의미는, ‘프로그램이 실행되는 도중에’ 이다. 자료구조 에서의 동적할당 (Dynamic.. 2023. 5. 15. [AIGORITHM THEORY] FLOYD WARSHALL (플로이드 워셜) 개념정리 개념 특징 모든 정점의 쌍 u와 v간의 최단경로를 구하는 알고리즘 Ak[i][j] 0부터 k까지의 정점만을 이용한 정점 i에서 정점 j까지의 최단 경로 정점 0부터 정점 k-1까지의 정점을 고려한 최단 거리 Ak-1을 구한 상태에서 다음 정점k를 고려할 때, 중간에 정점 k를 통과하지 않는 경로와 정점 k를 통과하는 경로 중 경로의 길이가 작은 것을 최단 경로로 택함 A-1[i][j] = cost[i][j] : 초기 상태, 가중치 인접 행렬의 가중치 값 A-1→A0→A1→... 순서로 경로에 정점을 늘려가면서 최단 경로를 구하다가 최종적으로An-1을 구하면 n개의 모든 정점 사이의 최단 경로를 구하게 됨 원리 모든 노드간의 최단거리를 구해야하기에, 2차원 인접 행렬을 구성한다. 알고리즘은 여러 라운드로 .. 2023. 5. 15. [AIGORITHM THEORY] KRUSKAL (크루스칼) 개념정리 개념 MST (최소 비용 신장 트리) 무방향 가중치 그래프에서 최저의 비용을 갖는 신장 트리 간선들의 가중치 합이 최소인 신장 트리를 의미한다. 최소 비용 신장 트리를 만드는 알고리즘 KRUSKAL PRIM 신장 트리를 만드는 제한 조건 그래프 내에 있는 간선들만 사용해야한다. 총 n-1개의 간선만을 사용해야 한다. 사이클을 생성하는 간선은 사용이 금지된다. 원리 그래프 G의 모든 간선을 가중치에 따라 오름차순으로 정리한다. 그래프 G에 가중치가 가장 낮은 간선을 삽입한다. 사이클을 형성하는 간섭 불가능 → 다음으로 가중치가 낮은 간선 삽입 그래프 G에 간선이 n-1개가 삽이될때까지 2. 과정을 반복한다. 크루스칼 알고리즘을 활용해 만들어넨 최소 비용 신장 트리 알고리즘 아래에 적힌 코드를 직접 해석하는.. 2023. 5. 15. 이전 1 2 3 다음
