그래프에서 Spanning Tree란 그래프의 모든 정점을 잇지만 사이클은 없는 부분 그래프를 의미한다. 즉, 형태와 관계없이 모든 정점을 사이클없이 이을수만 있다면, 그것이 곧 스패닝 트리이다. 스패닝 트리는 이름처럼 트리의 일종으로 V개의 모든 정점을 연결하는 간선의 수는 V-1개가 된다. 이때 최소 Spanning Tree(MST)는 이러한 스패닝 트리 중에서 간선의 가중치 합이 최소가 되는 스패닝 트리를 말한다. 즉, 간선의 가중치가 있을때 최소 스패닝 트리를 만들 수 있다. 그리고 이러한 최소 스패닝 트리를 구하는 알고리즘은 대표적으로 Kruscal과 Prim 알고리즘이 존재한다. 그럼 먼저 Kruscal 알고리즘에 대해서 알아보자. Kruscal Algorithm 크루스칼 알고리즘은 간선들을 ..
최단 거리 알고리즘이란 그래프 상에서 노드 간의 탐색 비용을 최소화하는 알고리즘이다. 일반적으로는 네비게이션과 같은 길찾기에 적용된다. 이러한 최단 거리 알고리즘의 종류에는 크게 3가지가 있다. 다익스트라(Dijkstra) 알고리즘 다익스트라 알고리즘은 그래프 상의 특정 한 노드에서 다른 모든 노드까지의 최단 거리를 구하는 알고리즘이다. 다르게 표현하면 가중 그래프에서 간선 가중치의 합이 최소가 되는 경로를 찾는 알고리즘 중 하나이다. 그래서 다익스트라는 그리디와 동적 계획법이 합쳐진 형태이다. 왜냐하면, 현재 위치한 노드에서 최선의 경로를 반복적으로 찾으면서도 계산해둔 경로를 활용해 중복된 하위 문제를 풀기 때문이다. 또한 다익스트라는 만약 그래프에 음의 가중치가 있다면 사용할 수 없다. 그 이유는 그..
해시 테이블이란 검색하고자 하는 키 값을 입력받아서 해쉬 함수를 돌려서 반환받은 HashCode를 배열의 index로 환산해서 데이터에 접근하는 방식의 자료 구조이다. F(key) -> HashCode -> Index -> Value 이때, 해시 함수는 어떠한 특정한 데이터를 이용해서 입력받은 키 값으로 그 값이 얼마나 큰지에 상관없이 동일한 해시 코드를 만들어준다. 그리고 해시 테이블의 가장 큰 장점은 검색 속도가 매우 빠르다는 점이다. O(1). 왜냐하면, 해시 코드의 값 자체가 배열의 인덱스로 활용되기 때문에 해시 코드로 배열의 위치에 다이렉트로 접근할 수 있기 때문이다. 그러나 해시 테이블도 고민이 있다. 바로 hash algorithm이 좋지 않을 경우, 한 배열의 인덱스에 여러 개의 값이 할당..
다익스트라 알고리즘은 DP를 활용한 대표적인 최단 경로 탐색 알고리즘이다. 흔히 인공위성 GPS 소프트웨어에서 많이 사용되며, 개념적으로는 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 다만 이때 음의 간선을 포함할 수 없다. 물론 현실 세계에서는 음의 간선이 존재하지 않기때문에 다익스트라는 현실 세계에서 사용하기 매우 적합한 알고리즘인 것이다. 여기서 다익스트라 알고리즘이 왜 DP인지 궁금할 것이다. 그 이유는 최단 거리는 여러 개의 최단 거리로 이루어져있기 때문에 작은 문제가 큰 문제의 부분 집합에 속해있기 때문이다. 즉, 다익스트라는 하나의 최단 거리를 구할 때, 그 이전까지의 구했던 최단 거리 정보를 그대로 사용한다는 특징이 있다. 그리고 다익스트라 알고리즘은 정렬 후에 ..
개념 위상 정렬(Topology Sort)는 순서가 정해져있는 작업을 차례대로 수행해야할 때 그 순서를 결정해주기 위해서 사용하는 알고리즘이다. 쉽게 말하면 그래프의 흐름이 있고, 다양한 조건이 얽혀있을 때 정확히 1열로 그래프의 노드를 나열할 수 있도록 하는 알고리즘이 위상 정렬인 것이다. 따라서 다음과 같이 모든 조건을 만족하도록 일직선의 순서를 하나 만들어낼 수 있는 것이다. 대학생 되기 -> 학과 사이트 가입하기 -> 4학년 되기 -> 정보처리기사 합격하기 -> 자격 서류 제출하기 -> 졸업시험 신청하기 -> 졸업하기 이렇게 정렬을 하면 순서대로 작업을 수행했을 때 성공적으로 '졸업하기'까지 갈 수 있다. 또한 위 말고도 다른 답도 존재하게 된다. 그래서 위상 정렬은 여러 개의 답이 존재할 수 있..
tree는 부모-자식 관계를 가지는 구조로 계층이 있고, 그룹이 있다. 이 것을 가능하게 한 것이 노드가 하나 이상의 자식 노드를 가지기 때문이다. 트리의 노드 중에는 부모를 아는 경우도 있고, 자식만 아는 경우도 있고, 데이터가 잘 정렬된 것도 있고, 섞여있는 것도 있다. 그리고 트리중에서 자식 노드가 최대 2개 까지만 붙는 경우를 이진 트리라고 한다. 그리고 그 이상의 3개씩 자식이 붙는 경우를 ternary tree라고 한다. 그럼 이 중에서 가장 중요한 이진 트리를 알아보자. Binary Tree는 이진 트리다. 즉, 자식 노드가 최대 2개인 트리이다. 여기서 Binary Search Tree는 왼쪽 자식에는 현재 루트 값보다 작은 값이 들어가고, 오른쪽 자식에는 현재 루트 값보다 큰 값이 들어가..
그래프란? 그래프는 다음과 같이 연결되어있는 원소간의 관계를 표현한 자료구조이다. 이 그래프라는 것은 연결할 객체를 나타내는 정점(vertex)와 객체를 연결하는 간선(edge)의 집합으로 구성된다. 즉, 그래프 G를 G(V,E)로 정의하고, 여기서 V는 정점의 집합, E는 간선들의 집합을 의미한다. 그래프의 종류에는 그래프에는 크게 무방향 그래프(undirected graph)와 방향 그래프(directed graph)가 있는데, 무방향 그래프는 두 정점을 연결하는 간선에 방향이 없는 그래프이다. 정점 V1, V2를 표현시에 (V1, V2)처럼 표현할 수 있고, 이는 (V2, V1)과 같은 간선을 나타낸다. 방향 그래프는 간선에 방향이 있는 그래프이다. 정점 V1, V2를 연결하는 간선을 로 표현하는데..
정렬이란 이름, 학번, 학점 등의 키를 항목값의 대소 관계에 따라 데이터 집합을 일정한 순서로 바꾸어 늘어놓는 작업을 말한다. 이렇게 데이터를 정렬하면 더 쉽게 검색할 수 있는 장점이 생긴다. 이 데이터들의 정렬 순서에 따라 2가지로 나뉠 수 있는데, 작은 데이터를 앞쪽에 늘어놓는 것을 오름차순 정렬이라고 하고, 그 반대를 내림차순 정렬이라고 한다. 그리고 정렬 알고리즘은 안정적인 알고리즘과 그렇지 않은 알고리즘으로 나눌 수 있다. 그렇다면 안정적인 알고리즘은 무엇일까? 안정적인 알고리즘은 값이 같은 원소의 순서가 정렬 후에도 유지되는 것을 말한다. 또한 내부 정렬과 외부 정렬 2가지로도 나눌 수 있는데, 내부 정렬이란 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우에 사용하는 알고리즘을 뜻하며..
알고리즘이란 알고리즘이란 어떠한 문제를 해결하기 위한 여러 동작들의 모임을 말한다. 알고리즘은 유한성을 가지며, 언젠가는 끝나야하는 속성을 가지고 있다. 좋은 알고리즘을 작성하기 위해서는 항상 효율성을 고려해야 한다. 이때, 알고리즘의 복잡도를 판단하는 척도로 공간복잡도와 시간복잡도를 계산하게 된다. 그 중 시간 복잡도는 알고리즘 내 연산의 횟수와 밀접한 관계가 있다. 시간 복잡도 시간 복잡도는 알고리즘의 수행시간을 말한다. 공간 복잡도 공간 복잡도는 알고리즘 실행에 필요한 메모리의 양을 말한다. 사실 위 2가지 복잡도 중 좀 더 주안점을 두고 보는 것은 시간복잡도인데, 공간에 대한 부분은 하드웨어의 발달로 인해 상대적으로 비중이 줄었기 때문이다. 또한 시간복잡도와 공간복잡도는 일반적으로 반비례하는 성질..
반복문이란 프로그램 내에서 똑같은 명령을 일정 횟수만큼 반복하여 수행하도록 제어하는 명령문이다. 파이썬에서 사용되는 대표적인 반복문으로는 while문, for문 등이 있다. 재귀란 어떠한 이벤트에서 자기 자신을 포함하고, 다시 자기 자신을 사용하여 정의되는 경우를 말한다. 그럼 재귀 함수는 무엇일까? 재귀 함수는 내부적으로 자기 자신을 호출하는 함수를 말한다. 또한 반드시 종료 조건이 필요하다는 특징을 가지고 있다. 단, 재귀 호출을 너무 많이 하게되면 스택 메모리 영역에 너무 많은 공간을 할당하게 되어 Stack Overflow가 발생할 수 있다는 점을 주의해야 한다. 따라서 재귀 함수를 구현할 때는 최악의 경우 얼마나 많은 재귀 호출이 발생하는지를 잘 살펴보아야 한다. 또한 재귀 함수에 대한 이해도가..
