다익스트라Dijkstra 알고리즘 다익스트라 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 다익스트라 알고리즘은 '음의 간선(0보다 작은 값을 가지는 간선)'이 없을 때 정상적으로 동작한다. 다익스트라 알고리즘은 프림 알고리즘 과 동작방식이 비슷하다. 다만 프림알고리즘은 단순히 간선의 길이를 이용해 어떤 간선을 먼저 연결할지 결정하는데 반해, 다익스트라 알고리즘은 '경로의 길이'를 감안해서 간선을 연결한다.다익스트라의 최단 경로 탐색 알고리즘은 사이클이 없는 방향성 그래프에 한해서만 사용 가능. 1. 다익스트라 알고리즘 수도코드 및 알고리즘 원리 S = r로부터의 거리가 계산되고 최단경로가 계산된 집합이다..

최단경로 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미합니다. 다양한 문제 상황 각 지점은 그래프에서 노드(Vertex)로 표현 지점 간 연결된 도로는 그래프에서 간선(Edge)으로 표현 ※조건 1. 유향 그래프 노드(Vertex)와 노드 사이에는 방향성이 있는 간선(Edge)이 주어져야 하며, 무향 그래프인 경우에는 각 간선에 대해 양쪽으로 유향 간선이 있는 유향 그래프로 생각할 수 있다. 즉, 무향 간선(u, v)는 유향 간선 (u, v)와 (v, u)를 의미한다고 가정한다. 무향인 경우에는 최단 경로를 구할 수 없다. 2. 간선 가중치 노드와 노드 사이의 간선에는 무조건 가중치가 부여되어야 한다. ※두 정점 사이의 최단 경로 1. 두 정점 사이의 경로들 중 간선의 가중치 합이 최소인 ..

트리를 이용한 처리 같은 집합의 원소들은 하나의 트리로 관리한다. - 자식 노드가 부모 노드를 가리킨다. 트리의 루트를 집합의 대표 원소로 삼는다. ※연결 리스트와 차이점 1) 자식 노드가 대표노드가 아닌 부모노드를 가리킨다. 2) Binary 트리가 아니여서 자식도드를 여러개 가질 수 있다. 3) 연결 리스트에서 Find-Set(x)의 수행시간은 O(1)이였지만, 트리에서 수행시간은 트리의 depth(깊이)와 연관이 있다. 4) 연결 리스트는 대표노드를 가리키는 Point, 다음노드를 가리키는 Point 두개의 포인터를 가진다. 트리에서는 부모노드를 가리키는 Point하나만 가지게 된다. 따라서, 공간적 효율성, 포인터 수정에 효율적, Find-Set(x)에서는 비효율적 이게 된다. 1) Make-Se..

상호 배타적 집합의 처리 상호배타적 집합만을 대상으로 한다. 이때 교집합은 제외된다. Union(합집합)을 지원해주는 연산 작업들에는 ■ Make-Set(x) : 원소 x로만 이루어진 집합을 만든다. ■ Find-Set(x) : 원소 x를 가지고 있는 집합을 알아낸다. ■ Union(x,y) : 원소 x를 가진 집합과 원소 y를 가진 집합의 합집합을 만든다. 집합을 처리하는 방법에는 연결리스트를 이용하는 방법과 트리를 이용하는 방법이 있다. 연결 리스트를 이용한 상호 배타적 집합의 처리 방법을 이해한다. 연결 리스트를 이용해 집합을 처리하는 연산들의 수행 시간을 분석한다. 트리를 이용한 상호 배타적 집합의 처리 방법을 이해한다. 트리를 이요해 집합을 처리하는 연산들의 수행 시간을 분석한다. 연결 리스트를..

C 포인터와 동적 메모리 할당 리뷰(1) (Pointers and Dynamic Memory Allocations) • 포인터 – C언어에서는 어떤 타입 T에 대해 T의 포인터 타입이 존재 – 포인터 타입의 실제값은 메모리 주소가 됨 – 포인터 타입에 사용되는 연산자 • & : 주소 연산자 • * : 역참조(dereferencing, 간접 지시) 연산자 Ex) i(정수 변수), pi(정수에 대한 포인터) int i, *pi pi = &i; i에 10을 저장하기 위해서는 다음과 같이 할 수 있다. i = 10; 또는 *pi = 10; – 널(null)포인터 : 어떤 객체나 함수도 가리키지 않는다. • 정수 0값으로 표현 • 널포인터에 대한 검사 int (pi == NULL) 또는 if(!pi) C 포인터와..

#먼저 추상데이터 타입 ADT(Abstract Data Type)에 대해서 알아보자! 추상 데이터 타입(Abstract Data Type, ADT)이란 : 추상적으로 수학적으로 정의된 데이터 타입 : 어떠한 자료와 자료의 연산이 정의되어 있다. 연산은 추상 데이터 유형과 외부 간의 인터페이스 역할을 한다. 실제로 자료와 연산이 어떻게 구현되었는 지는 사용자가 알 필요가 없다. 예를 들어, 자연수를 추상 데이터 타입으로 정의하자면, 자료는 0부터 INT_MAX까지의 정수 연산은 zero(), is_zero(), add(x,y), sub(x,y), equal(x,y), successor(x) 등이 될 수 있다. 일상 생활에서 추상 데이터 타입과 비슷한 사례를 찾아보면 자판기가 있을 수 있다. 자판기 안에서 ..

자료구조의 역할 - 왜 중요한가? Computer : 문제(계산)을 풀기 위한 H/W Algorithm : 문제를 푸는 방법 S/W Data Structure : 문제를 이루는 재료의 구성 알고리즘을 이용해서 문제를 풀 때 이 문제를 구성하는 어떠한 방식이 있는데 이때 이 방식을 자료구조라고 할 수 있다. 즉, 알고리즘은 자료구조에 굉장히 큰 영향을 받게 된다. 예를 들어, 문제를 스택을 쓰는 방식, 큐를 쓰는 방식 같이 자료구조가 달라진다면 알고리즘 또한 당연히 달라지게 된다. Computer는 문제를 풀기위한 장치라고 했는데, 세상을 문제의 세계로 바라본다면... 1. 답이 있는 문제 2. 답이 없는 문제 3. 답이 있는지 없는지 모르는 문제 세개로 구분할 수 있다. 이러한 문제를 자료구조와 알고리즘..

딕셔너리(dictionary) 파이썬에서 딕셔너리(dictionary)란 사전형 데이터를 의미하며, 말그대로 단어와 단어의 뜻이 이뤄져 있는 것처럼, key와 value를 1대1로 짝을 이루고 있는 형태입니다.이때 하나의 key에는 하나의 value만이 대응됩니다. 이 때, key 값은 절대로 변하지 않으며 value 값은 변경할 수 있습니다. 딕셔너리는 튜플과 다르게 key-value 쌍 자체를 수정하거나 삭제할 수 있기 때문에 유용하게 사용할 수 있습니다. 대부분의 언어도 이러한 대응 관계를 나타내는 자료형을 갖고 있는데, 이를 연관 배열(Associative array) 또는 해시(Hash)라고 합니다. 1) 딕셔너리 선언 2) 딕셔너리 관련 함수들 (in, keys, values, items, g..

반복문(Loop) 파이썬의 많은 객체는 반복가능(iterable)입니다. 객체내의 모든 요소, 리스트의 모든 요소, 문자열의 모든 요소 그리고 반복문을 반복하여 코드 구문을 여러번 실행 할 수 있습니다. 반복(iterate)의 의미는 객체를 순회하며 반복할 수 있고, 객체 내의 모든 요소마다 작업을 수행 할 수 있다는 것입니다.예를 들어, 문자열의 모든 문자에 대해, 해당 문자열을 순회하며 모든 문자에 대해 반복적으로 무언가를 수행 할 수있습니다. 우리는 문자열의 모든 단일 글자나 문자를 출력하고 싶을 때, 문자열은 이터러블 객체이므로 작업 가능합니다. 또한 리스트의 각 항목을 이터레이트 할 수 있습니다. 리스트가 이터러블이란 뜻입니다. 1. For문 for문의 기본 구조 my_iterable = [1,..

파이썬 조건문(Python Conditional Satement) 일반적인 흐름 제어에 대해 배워볼 것이며 흐름 제어는 기본적으로 우리가 원할 때만 코드를 실행하기 위해 논리를 사용합니다. 논리 흐름을 제어하기 위해서는 몇가지 키워드를 사용합니다. 파이썬에서 다루는 키워드는 if, elif, else 입니다. 조건문을 이해하기 위해서는 파이썬의 제어 흐름 문법이 공백으로 알려진 콜론과 들여쓰기를 사용한다는 것을 이해해야 합니다. 이 들여쓰기는 파이썬에게 절대적으로 중요하며, 다른 프로그래밍 언어들과 차별되는 요소 입니다. 1. If 문 여기 기본적이 if문의 문법이 있습니다. if some_condition://비교연산(참 또는 거짓) excute some code//해당 조건이 참일 경우 밑의 코드가 ..