(2021.10.08) 알고리즘 수업들으면서 정리하기 6탄 5주차 내용 -1 (4주차는 추석이어서 수업 없었음) Maximum-subarray problem input: sequence of numbers A[1 ... n] output: subarray의 greatest sum(contiguous subarray of A) A[i ... j] Naive approach 교수님께서 어떠한 문제를 풀 때는 naive하게 풀어보는 것부터 시작해보라고 하셨다 (naive 뜻을 몰라서 처음엔 무슨 말인지 이해하지 못했음) Divide-and-conquer approach Subproblem: Find a maximum subarray of A[low..high] (original call low=1, high=..
(2021.10.07) 알고리즘 수업들으면서 정리하기 5탄 3주차 내용 끝!! Divide-and-Conquer algorithms Divide-and-conquer를 이용하여 merge sort의 T(n) 계산 proof by telescoping 은 수업시간에 했음 ↓↓↓↓↓↓↓↓ proof by induction on n 은 과제로 했음 ↓↓↓↓↓↓↓↓ (답이 맞는지는 아직 모름..) Master Method for solving recurrences 과제로 했던 master method 문제들 ↓↓↓↓↓↓↓↓
(2021.10.07) 알고리즘 수업들으면서 정리하기 4탄 3주차 내용 Merge Sort insertion sort가 incremental approach로 정렬하는 반면, (정렬된 배열의 원소개수가 늘어남) merge sort는 divide-and conquer approach로 정렬한다. --> divide-and-conquer approackh는 recursion의 개념을 기반으로 한다. Divide-and-conquer Divide the problem into several su-bproblems Conquer the sub-problems by solving them recursively. Combine the solutions to the sub-problems to get the solu..
(2021.10.06) 알고리즘 수업들으면서 정리하기 3탄 3주차 내용 Asymptotic Notation (점근적 표기) 알고리즘의 런타임을 표기하기 위해서 highest-order term으로 정의하는 것을 점근적 표기라고 한다. 점근적 표기에는 세가지가 있다. Big O: 상한선 제시 - upper bound Big Omega: 하한선 제시 - lower bound Big Theta: 상한선과 하한선 둘다 제시 (Big O는 Big theta로 표기가능하지만, Big theta는 Big O로 표기할 수 없음 - 교수님 왕강조) Big O --> 상한선 제시 : upper bound Big Omega --> 하한선 제시 : lower bound --> BEST case performance를 얘기할 ..
(2021.10.06) 알고리즘 수업들으면서 정리하기 2탄 2주차+3주차 내용 Insertion sort - loop invariants statement: j-1 번째까지는 정렬되어 있음이 계속 보장된다. Initialization(초기조건): first iteration 전에도 참이어야 하는데, j=2부터 시작되는 것을 통해 first iteration 전에는 j=1임을 생각할 수 있다. j=1 일 때, A[1]은 원소가 하나이기 때문에 정렬 상태이므로 참이다. Maintenance(유지조건): 한 iteration이전에 참이었다면, 다음 iteration 이전에도 참을 유지해야 하는데, inner loop에 들어가기 전에는 out of order이고, loop를 나오는 순간에 key값이 order가..
(2021.10.06) 알고리즘 수업들으면서 정리하기 1탄 2주차 내용 insertion sort (삽입정렬) - 작동원리 input: sequence of numbers output: permutation (오름차순) pseudocode Insertion_sort(A,n) for j
(2021.07.19) 자구 7주차 과제랑 연결 깊이 우선 탐색 (Depth First Search) 깊이 우선탐색 (DFS) 은 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색하다가 더 이상 탐색할 수 없을 때, 그 전의 정점으로 돌아가 다른 방향의 간선으로 탐색을 하는 순회방법이다. 탐색 과정에서 후입 선출 구조의 스택을 사용한다. 정점 A에서 탐색할 정점이 없으므로 스택을 pop하면, 스택이 공백이므로 깊이 우선 탐색을 종료한다. 깊이 우선 탐색으로 순회한 경로는 아래와 같다.
(2021.07.19) 자구 재수강하면서 정리했던 것들 DFS, BFS, 최소비용 신장트리, 최단경로 알고리즘은 하나씩 자세하게 정리해서 따로 올릴 계획이다. V(vertex) : 정점 E(Edge) : 간선 차수(degree) : 정점에 부속되어있는 간선의 수 경로(path) : 정점 Vi ~ 정점 Vj 까지 간선으로 연결된 정점을 순서대로 나열한 리스트 - 단순경로 : 모두 다른 정점으로 구성 - cycle : 시작정점과 마지막정점이 같음 순차 자료구조를 이용한 그래프의 구현: 인접행렬 연결 자료구조를 이용한 그래프의 구현: 인접리스트 그래프의 순회 - DFS: 깊이 우선 탐색 (후입 선출 구조의 스택) - BFS: 넓이 우선 탐색 (선입 선출 구조의 큐) 신장트리(Spanning Tree) : 모든..
(2020.12.19) 참고도서 https://book.naver.com/bookdb/book_detail.nhn?bid=10896666 C로 배우는 쉬운 자료구조 단계별 그림과 삽화로 이론을 다지고 C 언어로 구현해 보는 자료구조 입문서 자료를 구조화하는 다양한 방법을 단계별 그림과 삽화를 곁들여 쉽게 설명하고, 자료구조의 핵심 알고리즘을 C 프로 book.naver.com 연결 자료구조 ▶ 연결 자료구조의 개념 각 원소에 저장되어 있는 다음 원소의 주소(링크)에 의해 순서가 연결되는 구현 방식 --> 작은 공간을 여러 개 연결하여 전체를 표현 --> 크기를 유연하게 변경 가능 & 메모리를 좀 더 효율적으로 사용 가능 ▶ 연결 자료구조의 메모리 저장 방식 노드 단위로 메모리가 할당되며, 저장 위치의..
(2020.12.17) 참고 도서 https://book.naver.com/bookdb/book_detail.nhn?bid=10896666 C로 배우는 쉬운 자료구조 단계별 그림과 삽화로 이론을 다지고 C 언어로 구현해 보는 자료구조 입문서 자료를 구조화하는 다양한 방법을 단계별 그림과 삽화를 곁들여 쉽게 설명하고, 자료구조의 핵심 알고리즘을 C 프로 book.naver.com 시험을 앞두고,,, 정리 중,,, (시험 하루 전) 자료구조 재수강을 위해 열심히 정리 중이다... 순차 자료구조 ▶ 순차 자료 구조의 개념 구현할 자료들을 논리적인 순서대로 메모리에 연속하여 저장하는 구현 방식 ▶ 순차 자료 구조의 메모리 저장 방식 메모리의 저장 시작 위치부터 빈자리 없이 자료를 순서대로 연속하여 저장한다. 논..