개발소설

순열(permutation) 요소 n개 중에 r개를 선택하여 순서에 상관 있게 뽑는 경우의 수 순서에 상관이 있다는것은 알파벳 3개를 뽑을때 [ A, B, C ]와 [B, A, C] 는 다르다 뽑은 요소가 같아도 순서가 다르면 다른것 요소가 중복되면 안된다. nPr = n! / (n - r)! 5장에서 3장을 뽑는다면 5P3 5 * 4 * 3 * 2 * 1 / 2 * 1 120 / 2 = 60 자바 순열 템플릿 (Template) //뽑을 요소들이 담긴 리스트 n //뽑을 갯수 r //결과를 담을 리스트 ArrayList result = new ArrayList(); boolean[] visited = new boolean[n.size()]; // 요소 사용 여부 체크용 return permtation(..

Grahp 여러 개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조 x축과 y축이 있는 수학에서의 그래프와 달리 거미줄처럼 여러개의 점과 선으로 이루어진 복잡한 네트워크 모양을 하고 있다. Graph의 구조 직접적인 관계가 있는 경우 두점이 직접적인 선으로 이어진다. 간접적인 관계인 경우 몇개의 점과 선에 걸쳐 이어진다, 그래프에서 하나의 점을 정점(vertex), 하나의 선은 간선(edge)라고 합니다. Graph의 표현 방식 인접 행렬 두 정점을 바로 이어주는 간선이 있다면 두 정점은 인접한다 라고 한다. 서로 다른 정점들이 인접한 상태인지를 2차원 배열의 형태로 나타낸다. A라는 정점과 B라는 정점이 이어져 있다면 1(true), 이어져 있지 않다면 0(false)로 표시한다. 가중치 ..

Tree 나무를 거꾸로 뒤집어 놓은 형태를 의미하는 자료 구조 단방향 그래프이고 하나의 뿌리(root)로부터 가지가 사방으로 뻗은 형태 데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조 하나의 데이터 아래 여러개 데이터가 존재하는 비선형 구조 stack과 queue는 데이터를 순차적으로 나열시킨 선형구조 이다. 루트(Root)라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선(edge)으로 연결 각 데이터를 노드(Node)라고 한다. 두 노드가 상하 관계의 계층으로 연결되면 부모/자식 관계가됨 연결된 상층의 노드를 부모 노드(Parent Node), 하층의 노드를 자식 노드(Child Node)라 한다. 자식이 없는 노드를 리프 노드(Reaf Node)라고 한다..

Queue 선입 선출 구조의 자료구조 이다. FIFO(First In First Out) 가장 먼저 입력한 데이터를 가장 먼저 출력한다. 데이터의 입출력 방향이 다르다. front : 출력 rear : 입력 데이터를 하나씩 입력하고 하나씩 빼야 한다. - 여러개의 데이터를 동시에 처리 할 수 없다. 큐에 데이터를 입력하는 것을 'enqueue', 데이터를 출력하는 것을 'dequeue'라고 한다. 현실에서 일반적인 대기줄을 생각하면 된다. 가장 먼저 대기줄에 선 사람이 우선 순위가 가장 높다. 컴퓨터의 장치들 사이에서 데이터를 주고 받을 때, 각 장치 사이에 존재하는 속도, 시간의 차이를 극복하기 위해 임시 기억 장치의 자료 구조로 Queue를 사용한다, 이것을 버퍼(buffer)라고 한다. 프린터로 인..

Stack 데이터를 순서대로 쌓는 자료구조 후입 선출 구조 이다. - LIFO(Last In First Out), FILO(First In Last Out) 가장 먼저 입력한 데이터가 가장 마지막의 출력이 된다. 데이터의 입출력 방향이 같다. 데이터를 하나씩 입력하고 하나씩 빼야 한다. - 여러개의 데이터를 동시에 처리 할 수 없다. 현실에서 프링글스통을 생각하면 된다. - 포장시 가장 먼저 넣었던 과자를 가장 마지막에 뺀다. 스택에 데이터를 입력하는 것을 PUSH, 데이터를 꺼내는것을 POP이라고 한다. JAVA에서 Stack 자바에서 클래스로 제공한다. import java.util.*; // stack 생성 Stack stack = new Stack(); // stack 입력 stack.push("..