DFS 알고리즘으로 트리 탐색 트리 : 사이클이 없는 부모와 자식관계가 있는 1: N의 관계 1. Stack 사용하기 * 슈도 코드 DFS(v){ // v: 루트노드 stack.push(v) while(not stack.isEmpty){ curr = stack.pop for w in (curr의 모든 자식) stack.push(w) } } 2. 재귀 사용하기 * 슈도 코드 DFS(v){ v방문; for(w in (v의 모든 자식) { DFS(v); } } DFS 알고리즘으로 그래프 탐색 트리처럼 재귀를 하면 stackoverflow 발생 => 방문했는지 안했는지를 check하는 것이 필요하다. 1. 재귀함수 * 슈도코드 // G: 그래프, visited : 방문 배열 DFS(v) { visited[v]
Algorithm/Theory
그래프 표현 간선의 정보를 저장하는 방식, 메모리나 성능을 고려해서 결정해야 한다. 그래프를 표현하는 방법에는 3가지가 있다. 1) 인접행렬 2) 인접리스트 3) 간선의 배열1. 인접행렬 2차원 배열을 사용. 차수 계산에 용이. 장점: 구현이 간단하다. 조회가 쉽다. 단점 : o(n^2)의 시간복잡도, 공간 낭비. public class 그래프_인접행렬 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); //정점의 개수(V)와 간선의 수(E)가 주어진다. int V = sc.nextInt(); int E = sc.nextInt(); //인접행렬 int[][] adjArr = new int..
정렬을 하려면 기준이 필요하다. Comparator와 Comparable은 모두 인터페이스로 객체를 비교할 수 있도록 만들게 하고, 이것을 사용하려고하면 인터페이스니 선언된 메소드를 반드시 구현을 해야한다. public interface Comparator { int compare(T o1, T o2);}public interface Comparable { public int compareTo(T o);} 위 코드를 보면 매개변수의 개수가 다르다.Comparator는 두 매개변수의 객체를 비교하는 것이고, Comparable은 자기 자신과 매개변수 객체를 비교한다. Compare()은 객체를 비교해서 음수,0,양수 중 하나를 반환하도록 구현해야 한다. (오른쪽이 크면 음수, 작으면 양수)CompareT..
Streamstream : byte 형태로 데이터를 운반하는데 사용되는연결 통로.물이 한쪽 방향으로만 흐르는 것과 같이 스트림은 단방향 통신만 가능하기 때문에 하나의 스트림으로 입력과 출력을 동시에 처리 할 수 없다. 스트림은 먼저 보낸 데이터를 먼저 받게 되어있으며 연속적으로 데이터를 주고 받는다는 점에서 큐(queue)의 FIFO(First in Frist Out) 구조로 되어 있다. Stream 활용 : InputStream / OutputStream입력 스트림 inputStream 은 스트림을 한 줄 씩 읽고, 출력스트림 outputStream 으로 데이터를 내보내며 해당 공간을 비운다. InputStream 은 System.in을 사용하며, OutputStream 은 System.out 을 사..
Deque은 Double-Ended Queue의 줄임말로 큐의 양쪽으로 엘리먼트의 삽입과 삭제를 수행할 수 있는 자료구조를 의미한다.덱(Deque)은 어떤 쪽으로 입력하고 어떤 쪽으로 출력하느냐에 따라서 스택(Stack)으로 사용할 수도 있고, 큐(Queue)로도 사용할 수 있다. 특히 한쪽으로만 입력 가능하도록 설정한 덱을 스크롤(scroll)이라고 하며, 한쪽으로만 출력 가능하도록 설정한 덱을 셸프(shelf)라고 한다. [ Deque 선언 ]Deque deque1 = new ArrayDeque();Deque deque2 = new LinkedBlockingDeque();Deque deque3 = new ConcurrentLinkedDeque();Deque linkedList = new Linked..
스택(Stack)은 "쌓다"라는 의미로, 데이터를 차곡차곡 쌓아 올린 형태의 자료구조.데이터가 순서대로 쌓이며 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 구조.스택은 정해진 방향으로만 쌓을 수 있으며, top으로 정한 곳을 통해서만 접근할 수 있다. 새로 삽입되는 자료는 top이 가리키는 가장 맨 위에 쌓이게 되며, 자료를 삭제할 때도 top을 통해서 삭제가 가능하다.스택의 구조를 후입 선출의 구조라고 하며, 줄여서 LIFO(Last In First Out)라고 부른다. [ 스택의 특징 ]재귀 함수의 동작 흐름과 같은 구조를 가진다.깊이 우선 탐색에 사용된다. 단방향 입출력 구조이다. 데이터를 하나씩만 넣고 뺄 수 있다. [ 스택 연산 ]* push() : 저장소에 자료를 저장한다. * pop()..
