campkim

그래프 특정 사물, 개념 혹은 데이터 간의 연결관게를 정점(vertex)과 간선(edge)로 표현한 것. 정점 = vertex = node 라고 이해하는 것이 간편하다. 수식으로 그래프는 G(V,E)로 표기 가능하며, 이때 V는 정점들의 집합{v1,v2 ... } , E는 간선들의 집합{e1,e2...}이다. 간선(edge)의 경우 시작점과 도착점으로 구성되어 있고, 방향이 있을 수도 있고 없을 수도 있다. 간선의 특징에 따라 그래프의 종류가 나뉜다. 간선방향이 있는경우 (Directed) - 시작점과 도착점이 있다. '시작 → 도착' 단일 방향으로 연결되어 있다. 간선의 방향이 없는 경우 (Undirected) - 두 노드의 시작, 도착노드가 별도 구분되어 있지않다. 즉 쌍방 통행이 가능함. 순환 구조..

위상 정렬(topological) 유향 그래프에서 정점(vertex)를 간선(edge)의방향에 거스르지 않도록 나열하는 것을 의미함. 선후 관계가 정의된 그래프 구조 상에서 선후 관계에 따른 정렬에 사용될 수 있는데, 대표적으로 대학교 수강과목에서 선수과목 구조를 예를 들 수 있다. 선수과목이 있다면 선수과목을 먼저 수강해야하므로, 특정 과목들을 수강해야 할 때 위상 정렬을 이용할 있기 때문이다. 위상 정렬 성립조건 유향 그래프 구조일 것 (directed) 간선들이 방향을 가지고 있어야 한다. 유향 그래프 구조에 따라 2개 이상의 정렬이 나올 수 있다. 싸이클을 형성하지 않을 것 (acyclic graph) 싸이클이 형성된다는 것은 순환구조를 의미한다. 순환하는 구조에서는 위상정렬이 불가능하다. 위상 ..

파이썬을 사용한 자료구조 및 알고리즘 공부중 가끔 부딪히는 문제가 있었다. reference 혹은 대부분 코드를 수정하여 해결하곤 했지만, 파이썬의 구동원리에 대한 이해를 높일 필요가 있을 것 같다. 오늘은 파이썬의 함수 호출방법에 대해 알아본다. 함수의 호출방식 두 가지 먼저 함수의 호출방법은 2가지가 있다. Call by value (값에 의한 호출) - 기본적으로 C언어에서 지원하는 방식, 함수에서 값을 복사해서 전달하는 방식. 인자로 전달되는 변수를 함수의 매개변수에 복사함. 이렇게 복사되면 인자로 전달한 변수와는 별개의 변수가 되며, 매개변수를 변경해도 원래의 변수에는 영향을 미치지 않는다. 원본값에 영향이 없다는 의미이다. 값이 복사되기 때문에, 메모리를 차지한다. 많은 계산이 들어가면 과부하..

객체와 변수 파이썬에서는 데이터, 함수, 모듈, 클래스 모두 객체(object)로 취급한다. 객체는 자료형(data type)을 갖으며, 메모리공간을 차지한다. 파이썬의 변수는 값을 갖지 않는다는 특징이 있다. 변수는 객체가 아니고, 객체에 연결된 이름에 불과하다. 다른 프로그래밍 언어의 경우, 변수란 값을 저장하는 상자와 같다고 비유한다고 하지만, 파이썬에서는 맞는 비유가 아니다. 파이썬에서 변수는 객체를 참조하는 객체에 연결된 이름에 불과하다 ? 모든 객체는 메모리를 차지하고, 자료형 뿐만아니라 식별번호(id)를 갖는다. 식변번호는 다른객체와 구별할 수 있는, 객체 고유의 번호이다. 객체가 저장된 메모리의 주소라고 이해하는 것이 맞는 것 같다. 하기 이미지를 참고하면 이해에 도움이 된다. 위 실행문을..

정렬에 사용되는 다양한 알고리즘이 있다. 각 정렬은 특성과 원리 시간복잡도에 차이가 있다. (시간 복잡도에 관해서는 글 하단의 표 참고) 정렬 알고리즘에 대해 정리하고, 학습 이해에 도움이 되었던 유용한 시각자료를 포스팅하고자 한다. 선택정렬 배열의 가장 작은 요소를 가장 앞의 요소와 반복적으로 바꾸는 방법 선형 정렬이므로 전체 연산 횟수는 'N + (N-1) + (N-2) + ..... + 2' 이므로 전체 시간복잡도는 약 O(N2) 이다. ##선택 정렬 (Python 구현 예시) arr = [17, 25, 49, 10, 23, 41, 6, 72, 4, 18] for i in range(len(arr)): min_index = i #가장 작은 원소의 index - 루프 시작 지점에서는 맨 앞의 원소의 ..

이름에서 직관적으로 어떤 개념인지 알 수 있다. '이분 + 탐색' 정렬되어있는 배열 혹은 특정 범위에서, 값을 찾는 강력한 도구로서 사용 될 수 있음. (선형탐색보다 유리하다!) 주된 목적은 탐색시 시간 복잡도상의 효율성을 높임에 있다. (평균 시간복잡도 NlogN ) *향후 응용범위에 대한 노하우가 깊어지면 글 수정을 통해 보완 예정. 개념 배열 혹은 특정 범위에서 찾고자하는 값이 있는 경우, 두 부분으로 나누어 탐색하고 가능성 없는 부분은 더 이상 탐색하지 않는다. 따라서 한번의 탐색당 탐색범위를 N/2로 줄여나갈 수 있다는 것이 장점이다. 이때, 두 부분으로 나누는 기준은 배열상 중앙에 위치한 값이다. (양 끝값의 평균값이 아님) 이분탐색 사용의 전제조건은 배열이 반드시 미리 '정렬' 되어 있어야 ..