next permutation이란? 보통 순열과 조합을 구현할 때에는 재귀 함수를 사용하여 구현한다. 하지만 재귀적인 함수의 호출은 구하고자 하는 범위가 넓어질 경우 사용하기 힘들다는 단점이 있다. 이런 단점을 해결할 수 있는 것이 next permutation이라는 알고리즘이다. 단순 일차원 탐색을 통해서 순열, 조합을 구할 수 있다는 장점이 있다. 반복문을 통해서 값을 구하기 때문에 원소의 개수가 N이라 할 때 O(N) 만큼의 시간 복잡도를 가진다. 값을 바꿔주는 swap 과정을 거쳐서 순열을 생성하기 때문에 자연스럽게 순열의 순서도 파악할 수 있다는 장점이 있다. 알고리즘 진행 1. 아래와 같은 배열이 주어졌을 때 배열의 맨 뒤에서부터 탐색을 시작하여 N[index] < N[index+1]인 가장 ..

그래프란? 그래프는 정점(Vertex)들과 간선(Edge)들의 집합으로 구성된 자료구조이다. 정점의 위치나, 간선의 순서들은 그래프를 정의하는 데 사용되지 않는다. 트리도 그래프의 일종이나, 그래프는 트리와 다르게 정점마다 간선을 가지지 않을 수 있다. 그래프는 트리와 다르게 계층 구조의 형태가 아니므로, 역시 노드 간에 부모-자식 계층 관계가 성립하지 않는다. 따라서 루트 노드의 개념도 없다. 그래프의 종류 그래프는 정점이나 간선에 추가적인 속성을 부여하거나, 정점이 존재할 수 있는 방법을 다양하게 함으로써 여러 방식의 그래프로 표현이 가능하다. 방향 그래프( Directed Graph ) 대표적인 그래프의 종류 정점을 잇는 간선들이 방향을 가진다. 위 그림의 첫번째 그래프에서 정점 2와 정점 3을 사..

트리 어떤 계층 구조를 표현하고자 할 때, 트리(Tree)라는 자료구조를 사용할 수 있다. 상위 계층이 아래에 있는 하위 계층들을 포함하며 가지를 치는 모습이 마치 나무와 같다고 하여 트리(Tree)라고 명명되었다 한다. 어떤 데이터로 트리를 구성하느냐, 자료들을 어떻게 배치하느냐에 따라서 다양한 트리를 구성할 수가 있다. 트리의 구성요소 트리는 가질 수 있는 데이터(노드)와 노드들을 연결하는 간선으로 구성된다. 노드가 연결되었을 때, 그 두 노드 간에는 상 하 계층 관계가 성립이 되어야 한다. 트리 용어 부모 노드(parent node) : 연결된 노드 중 상위 노드 하위 노드(child node) : 연결된 노드 중 하위 노드 형제 노드(sibling node) : 부모 노드가 같은 노드 루트 노드(..

알고리즘 공부 시작 알고리즘을 너무 오래 놓고 있는 것 같아서.. 나중에 이직을 위해서라도 공부를 해야겠다는 생각이 들었다. 제로 베이스로 기본부터 새로 시작해보려 한다. 선형 자료구조부터 시작! 선형 자료구조란? - 연속적으로 자료 뒤에 자료가 배치되는 구조 - 배열, 리스트, 스택, 큐가 대표적이다. 배열 - 번호(인덱스)와 해당 인덱스에 대응하는 데이터로 이루어진 자료구조다. - 메모리 상에 같은 종류의 데이터들이 순차적으로 저장되고, 인덱스로 해당 자료의 상대적인 위치를 알아낼 수 있다. 배열의 종류 배열에는 엄밀하게 성질에 따라 정적 배열과 동적 배열로 구분할 수 있다. 크게 자세하게 다루지는 않는다. 배열의 특징 - 말 그대로 크기가 정해져 있는 배열을 의미한다. - 연속된 메모리 경로에 정해..