그래프의 개념그래프의 유래쾨니히스베르크(Konigsberg) 다리 문제오일러가 그래프 개념을 도입해서 해결땅과 섬 → Node (Vertex)다리 → Edge (Link)다리 문제 → 한 붓 그리기한 붓 그리기 문제홀수 개의 Edge에 연결된 Vertex의 수가 4개 이상이면 한 붓 그리기가 불가능한 도형그래프의 정의개체들 사이의 일대일 관계를 시각적으로 표현하는 수학적 모델Vertex: 꼭짓점, 정점, 노드Vertex는 대체를 나타냄Edge: 간선1:1 관계, 노드의 쌍으로 표현그래프의 표현그래프를 Vertex와 Edge의 쌍으로 표현G = (V, E)수학적 표현 Vertex: 모든 Vertex들의 집합, V = {0, 1, 2, 3}Edge: Vertex 쌍들의 집합, E = {(0, 2), (0,..
Study/알고리즘
// 1. 라이브러리#include #include #include // 2. 자료 구조// 3. solve() --> 문제 풀이// 분할 정복: N --> N-1// T(N) = T(N-1) + O(1) ==> T(2^N) = T(2^(N-1)) + O(1)int solve(int N, int x, int y) { // 0) 예외 처리: N == 1일 때 if (N == 1) { if (x == 0 && y == 0) return 0; else if (x == 1 && y == 0) return 1; else if (x == 0 && y == 1) return 2; else if (x..
합병정렬합병 (Merging): 정렬된 2개의 리스트(L&R)를 하나의 정렬된 리스트(M)로 결합하는 연산합병 연산의 시간 복잡도: O(n)합병정렬의 과정분할: n개의 원소를 가진 배열을 2개로 분할, 더 이상 분할할 수 없을 때까지 반복정복: 더 이상 분할할 수 없는 배열은 정렬된 것으로 간주결합: 정렬된 배열을 합병해서 더 큰 정렬된 배열 생성, n개의 원소를 가진 정렬된 배열까지 합병을 반복합병정렬 알고리즘int n;int *arr;void merge_sort(int s, int e){ if (s == e) return; mid = (s + e) / 2; merge_sort(s, mid); merge_sort(mid + 1, e); merge(s, mid, m..
분할정복n개의 입력을 가진 문제를 k개의 부분 문제로 쪼개서 문제를 해결하는 전략재귀적으로 정의된 문제에 적합분할정복의 3단계분할: 주어진 문제(problem)를 부분 문제(subproblem)로 쪼개는 것정복: 부분 문제의 해를 구하는 것 (재귀적 과정)결합: 부분 문제의 해를 결합해 원래 문제의 해를 구하는 것결합을 요구하지 않는 경우도 있음 (쾌속 정렬)분할정복의 예시: 쾌속정렬, 합병정렬, 정수 곱하기, 행렬 곱하기, 이진탐색, 중간값 찾기 등기본 구조대부분의 분할정복 알고리즘은 재귀호출을 통해서 구현됨지나친 Recursive Call(재귀호출)의 문제 → 메모리 낭비, Stack Overflow기본 코드 구조 예시global n, A (1:n);DnC (int p, int q) { int ..
개념점근적 분석법: 자원을 얼마나 사용하는지 측정하는 방법좋은 알고리즘 = 정확한 문제 해결 + 좋은 성능좋은 성능의 알고리즘 → 효율적인 알고리즘 → 자원을 적게 사용하는 알고리즘효율의 정의효율(Efficiency): Performance = Solution(fix) / Cost효과(Effective): Performance = Solutuin / Cost(fix)알고리즘은 Solution을 fix하고 효율을 중요시Cost: Resource = temporal + spatialtemporal resource = CPUspatial resource = memory효율의 측면Three Aspects of PerformanceBest Case: 최선의 측면만 고려하는 효율(여러 번 시도 중에 가장 좋은 것만..
정의an Efficient method for solving a problem using a finite sequence of instructionsa list of well-defined instructions for completing a task컴퓨터를 이용한 효율적인 문제 해결 기법요구 조건입력(Input)모든 알고리즘은 주어진 문제(Input)을 해결해야 함입력 없이는 문제 해결을 시작할 수 없음입력은 미리 정의된 양식을 준수해야 함출력(Output)모든 알고리즘은 문제를 해결한 결과(Output)를 보고해야 함결과를 보고하지 않는 알고리즘은 의미 없음출력은 미리 정의된 양식을 준수해야 함명확성(Definiteness)알고리즘의 단계는 다른 해석이 존재하지 않아야 함2가지 이상의 해석이 가능한 ..
