알고리즘 (26) 썸네일형 리스트형 4-2강 - Euler Cycle(Path) 2 (구현) 2. Euler Cycle(Path) Problem Solution 구현 1) Doubly Linked List Management 1> DBL Structure 아래 구조는 vertex에 대한 adjacent list이며 d에는 edge array의 index를 가지고 있다. (즉, 어떤 edge인지를 나타내는 것이다.) typedef struct _DBL { int d; // store edge array index struct _DBL *twin; // the other DBL pointer struct _DBL *lp , *rp; // reverse & forward ptr } DBL; 2> DBList class class DBList { private: DBL *DBL_pool; public:.. 4-1강 - Euler's path(cycle) 1 (개념 정리 및 구현 아이디어) 0. Review walk : vertex와 edge가 교대로 나타나는 sequence (sequence 내의 edge는 앞 뒤의 vertex를 이어야 한다.) walk edge 중복 불가 vertex 중복 불가 v_0 = v_n walk O X X X trail O O X X path O O O X cycle O O O O closed walk O X X O closed trail O O X O 1. Euler Cycle(Path) Problem 1) 문제 소개 1> 크게 아래 3가지 경우로 나눌 수 있다. - [1] Euler cycle이 존재하거나 - [2] Euler path만 존재하거나 - [3] 아무것도 존재하지 않거나 2> 이들을 판단하는 조건 vertex degree (d(v)) : 각 v.. 3-2강 - 자료구조 & C, C++ programming 2 (Linked List management, Stack & Queue) 3. Linked List Management 구현은 크게 2가지입니다. (array로 구현, dynamic memory allocation) 0) Singly Linked List 기본 구조 typedef struct _SLL { int i; struct _SLL *p; } SLL 1> 필요한 field가 더 있다면 더 추가해도 된다. (양방향성을 구현할 수도 있다.) 2> 위 구조를 이용해서 stack, queue 등을 구현할 수 있다. 3> 단점 : 탐색에 O(n)의 시간 복잡도가 발생한다. 1) Linked List Management의 필요성 allocation/deallocation 함수인 malloc과 free는 속도가 빠른 함수가 아니다. (new와 delete도) 또한, 이를 호출하는데도.. 3-1강 - 자료구조 & C, C++ programming 1 (call by reference, dynamic allocation) 1. Swapping Function swap1 과 swap2는 동일한 기능을 합니다. (속도와 같은 세세한 사항은 다를 수 있어도 기능 자체는 동일합니다.) 2. Dynamic Memory Allocation 0) static memory int staticArr[10]; 프로그램이 종료될 때까지 메모리가 유지된다. 1) malloc의 기본형 int *dynamicArr = (int *)malloc(10 * sizeof(int)); - 위의 코드로 인해 10개의 int를 위한 memory가 할당된다. (그리고 이 array를 가리킬 pointer variable도 할당된다.) - 중간에 메모리를 free로 해제할 수 있다. cf> 심각한 오류가 있을 경우를 대비하는 법 if/else문으로 오류인 경우 .. 2-1강 - Algorithm & Complexity 1 (알고리즘의 정의) 1. Algorithms 1) Algorithms 1> Problem : Instance들의 모임 2> Parameter : 문제에 variable들 (아직 specific value를 할당 받지 못한 상태) 3> Instance : parameter에 specific value를 할당 받은 상태 4> Solution : 주어진 instance에 대한 answer 5> Algorithm : 문제를 해결하기 위한 step-by-step 단계 2) algorithm에 대한 정확한 정의 1> algorithm a finite set of instructions that, if followed, accomplishes a particular task. (particular task를 할 수 있는 집합) 2> a.. 1-2강 - Introduction (Graph Problem) cf> incident, adjacent v_1과 v_3는 adjacent e_1은 v_1(v_3)와 incident 2. Graph Problem 1 1) Minimum Vertex Cover Problem 0> vertex cover = S_VC ∀ e ∈ E and ∀ v ∈ S_VC ⊂ V, v is incident to e (vertex cover : 모든 e와 incident할 수 있는 v들의 조합) 1> 문제 크기가 최소인 vertex cover 구하기 (즉, 모든 e와 incident하는 v를 최소한의 개수로 고르는 문제) 2) Maximum Independent Set Problem 0> independent set = S_IND ∀ v_1, v_2 ∈ S_IND ⊂ V, v_1 is n.. 1-1강 - Introduction (Euler' Graph) 1. Euler's Graph Modeling 9Seven Bridges of Konisberg) cf> path & cycle walk : vertex와 edge가 교대로 나타나는 sequence (sequence 내의 edge는 앞 뒤의 vertex를 이어야 한다.) trail : [1] edge가 중복되지 않으며 [2] walk : vertex와 edge가 교대로 나타나는 sequence path : [1] vertex가 중복되지 않으며 [2] edge가 중복되지 않으며 [3] walk : vertex와 edge가 교대로 나타나는 sequence cycle : [1] 시작점과 끝점이 같은 [2] walk : vertex와 edge가 교대로 나타나는 sequence(사실상 trail과 path는 거의.. 13강 - 너비 우선 탐색 (BFS) 1. 만들 것 1) 큐: 탐색 중인 노드들 저장 / q 2) bfs_visited: 방문 여부 표시 3) node: 현재 탐색할 노드 4) 벡터(bfs_vector): 탐색을 마치고 탐색 순서 저장 (나중에 출력할 것) 2. 코드 1) 시작점 설정 1> 시작 노드를 큐에 삽입 / q.push(시작 노드) 2> 해당 노드를 방문했다고 표시 / bfs_visited[시작 노드] = true 2) 반복문 1> node에 큐의 맨 앞 요소를 저장 / int node = q.front() 2> node를 벡터에 삽입 / bfs_vector.push_back(node) 3> 벡터에 삽입하면 큐에서 node를 뺀다. / q.pop() 4> 반복문 (연결된 노드 탐색) - 새로운 노드가 이 node와 연결된 것 && .. 이전 1 2 3 4 다음
