코딩 일기장

메모이제이션 컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행속도를 빠르게 하는 기술, 동적 계획법의 핵심 추가적인 메모리 공간이 필요. 재귀 함수 호출로 인한 시스템 호출 스택을 사용, 실행 속도 저하 또는 오버플로우 발생 1. 중복 부분문제 구조 DP는 큰 문제를 이루는 작은 문제들을 먼저 해결하고 작은 문제들의 최적 해를 이용하여 순환적으로 큰 문제를 해결한다. 순환적인 관계를 명시적으로 표현하기 위해서 동적 계획법에서는 일반적으로 수학적 도구인 점화식을 사용한다. DP는 문제의 순환적인 성질 때문에 이전에 계산되어졌던 작은 문제의 해가 다른 어딘가에 필요하게 되는데 이를 위해 DP에서는 이미 해결된 작은 문제들의 해들을 어떤 저장 공간..

개념 다익스트라 알고리즘은 그래프에서 한 정점에서 다른 정점까지의 최단 경로를 구하는 알고리즘. 이 과정에서 도착 정점 뿐만 아니라 모든 다른 정점까지 최단 경로로 방문하여 각 정점까지의 최단 경로로 모두 찾는다. 동작 인접 행렬로 구현하는 방법 출발 노드와 도착 노드를 설정한다. 최단 거리 테이블을 초기화 한다. 현재 위치한 노드의 인접 노드 중 방문하지 않은 노드를 구별하고, 방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택한다. 그 노드를 방문 처리한다. 해당 노드를 거쳐 다른 노드로 넘어가는 간선 비용을 계산해 최단 거리 테이블을 갱신한다. 1 ~ 4 과정을 반복한다. // N: 정점 개수, V: 간선 개수, start: 출발 정점, end: 도착 정점, weight: 비용 // map: 인접..

그래프에서 최소 비용 문제 모든 정점을 연결하는 간선들의 가중치 합이 최소가 되는 트리 두 정점 사이의 최소 비용의 경로 찾기 신장 트리 n개의 정점으로 이루어진 무향 그래프에서 n개의 정점와 n-1개의 간선으로 이루어진 트리 최소 신장 트리 (Minimum Spanning Tree) 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장트리 1. KRUSKAL Algorithm 최초, 모든 간선을 가중치에 따라 오름차순으로 정렬 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킴 → 사이클이 존재하면 다음으로 가중치가 낮은 간선 선택 n-1 개의 간선이 선택될 때까지 2번 반복 MST_KRUSKAL(G, w) for vertex v in G.V // G.V : 그래프의 정점..

1. 순열 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것 nPr nPr = n * (n-1) * (n-2) * ... * (n-r+1) nPn = n! n! = n * (n-1) * (n-2) * ... * 2 * 1 다수의 알고리즘 문제들은 순서화된 요소들의 집합에서 최선의 방법을 찾는 것과 관련 N개의 요소들에 대해서 n! 개의 순열들이 존재한다. n>12 인 경우, 시간 복잡도 폭발적으로 증가 반복문을 통한 순열 생성 for i from 1 to 3 for j from 1 to 3 if j != i then for k from 1 to 3 if k != i and k != j then print i, j ,k end if end for end if end for end for public..