Algorithm 썸네일형 리스트형 알고리즘 DP 정리 DP? Dynamic Programming 문제를 해결할 때, 큰 문제를 작은 문제로 분할하여 푸는 방법. 분할 정복 알고리즘과 유사. DP는 계산했던 결과를 저장하여 불필요한 연산 제외. 크게 Top-Down, Button-Up 방법 존재. 메모이제이션 (Memoization) : 계산한 값 저장하는 것 특성 Overlapping Subproblems : 큰 문제 --> 작은 문제 --> ... OPtimal Structure : 작은 문제의 결과값(return) --> 큰 문제의 결과값 --> ... 문제풀이 #include int main(){ int n; int a=0,b=1,result=0; scanf("%d", &n); if(n==1) { printf("1"); return 0; } for(i.. 더보기 기초 자료구조 정리(리스트, 그래프, 트리) 리스트(List) 연결 리스트와 같이 순서가 있는 자료구조 C에선 구조체를 이용해 구현 가능 C++에선 #include 를 통해 사용 가능 상황에 따라 배열보다 효율적으로 문제를 풀 수 있음 std::list std::list::iterator #include #include using namespace std; int main(){ list lt; list::iterator iter = lt.begin(); int n, m; scanf("%d %d", &n, &m); for(int i=1;i 더보기 알고리즘 정렬 정리 선택 정렬 (Selection Sort) 주어진 리스트에서 최소값을 맨 앞으로 옮기며 정렬. 내림차순의 경우 최대값을 맨 앞으로 옮김. 시간 복잡도 : //( O(n^2) //) #include #include using namespace std; int main(){ int n,min=0; int i,j; int num[1001]; scanf("%d", &n); for(int i=0;i 더보기 다익스트라 알고리즘 다익스트라 알고리즘? (Dijkstra Algorithm) 가중치 그래프(weighted graph)에서 두 정점(vertex) 사이의 최단 경로를 구하는 알고리즘 A Shortest Path Algorithm 가중치가 양수일 경우에 사용 의사코드 function Dijkstra(Graph, source): create vertex set Q //방문하지 않은 노드들의 집합 Q 선언 for each vertex v in Graph: // 초기화 dist[v] := INFINITY // 소스에서 v까지의 아직 모르는 길이 prev[v] := UNDEFINED // 소스에서 최적 경로의 이전 꼭짓점 add v to Q // 초기에는 모든 노드를 방문하지 않았기 때문에 Q에 add함. dist[source] .. 더보기 이전 1 다음
