Study-Note

Comparable 인터페이스 (java.lang) 객체 간의 일반적인 정렬이 필요할 때, Comparable 인터페이스를 확장한다. 정렬할 객체에 Comparable 인터페이스를 implements 한 후, CompareTo() 메서드를 오버라이드 하여 정렬 CompareTo() - 현재 객체 파라미터로 넘어온 객체 : 양수 리턴 Comparator 인터페이스 (java.util) 객체 간의 특정한 정렬이 필요할 때, Comparator 인터페이스를 확장해서 특정 기준을 정의하는 compare() 메서드를 구현한다. 기본적인 정렬 기준과 다르게 정렬하고 싶을 때 사용 Comparator 인터..

그래프 (Graph) * 그래프 자료구조란 노드와 노드를 연결하는 간선으로 구성된 자료구조이다. 그래프의 순회는 DFS 혹은 BFS로 이루어진다. 노드 사이에 양방향 경로를 가질 수 있으므로, 2개 이상의 경로가 가능하다. 루트 노드, 부모-자식 관계가 존재하지 않는다. 아래와 같이 방향이 존재할 수도 있고, 존재하지 않을 수도 있다. * 관련 용어 정점(vertex, node): 위치의 개념 간선(edge): 위치 간의 관계, 노드를 연결하는 선 (link, branch) 인접 정점(adjacent vertex): 간선에 의해 직접 연결된 정점 경로(path): 어느 한 정점에서 다른 정점 까지의 경로 싸이클(cycle): 단순 경로의 시작 정점과 종료 정점이 동일한 경우 단순 경로(Simple Pat..

Java의 Iterator, ListIterator * Iterator 컬렉션 프레임워크에서 저장된 요소를 읽어오는 방법을 표준화하기 위해 사용한다. Collection 인터페이스에서는 Iterator 인터페이스를 구현한 클래스의 인스턴스를 반환하는 iterator() 메소드를 정의하여 각 요소에 접근하도록 하고 있다. Collection 인터페이스를 상속받는 List와 Set 인터페이스 또한 iterator() 메소드를 사용할 수 있습니다. (Map 제외) - List 데이터를 반복하는 방법 1. for( int i =0; i

LinkedList 자료구조 DFS(깊이 우선 탐색) 구현 시에 LinkedList를 사용한다. 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식의 자료구조이다. 객체를 추가하거나 삭제하면 앞, 뒤 링크만 변경되고 나머지 링크는 변경되지 않는다. 데이터 추가나 삭제 시 인덱스가 밀리거나 당겨지는 일이 없기에 ArrayList에 비해 추가, 삭제가 용이하다. (1) 선언 방법 LinkedList list = new LinkedList(); LinkedList student = new LinkedList(); // 타입 지정 LinkedList members = new LinkedList(); // 타입 지정 (2) 값 추가하기 list.addFirst(1); // 가장 앞에 데이터 추가 li..

BFS, 너비 우선 탐색 * 너비 우선 탐색 임의의 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다. 임의의 루트 노드로부터 가장 가까운 노드를 먼저 탐색하고, 멀리 있는 것을 가장 나중에 탐색한다. 어떤 노드를 탐색했는 지를 반드시 기록해야 하며, 일반적으로 큐를 사용해 선입선출을 원칙으로 탐색한다. 1) 깊이가 1인 노드, 2인 노드, 3인 노드... 를 반복하며 탐색하고, 방문한 노드는 큐에 기록한다. 2) 큐에 들어있는 노드를 하나씩 꺼내고 인접해 있는 노드를 차례로 방문한다. 3) 큐에 있는 노드가 없어질 때까지 반복한다. * 적용 예시 두 노드 사이의 최단 경로를 알고싶을 때 임의의 경로를 찾고자 할 때 * 탐색 과정 - 연습 문제 www.acmicpc.net/problem/126..

DFS, 깊이 우선 탐색 * 그래프 탐색 하나의 정점으로부터 시작하여 모든 정점들을 한 번씩 차례대로 방문하는 것이다. * 깊이 우선 탐색 임의의 루트 노드부터 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다. BFS 보다는 검색 속도가 느리다. 인접한 간선이 없을 경우 이전으로 돌아가야 하므로 한 번 방문한 노드는 방문했다는 것을 반드시 표시해두어야 한다. 이를 위해서는 거쳐온 정점들을 모두 저장해 두어야 하는데, 이는 재귀 호출을 이용하여 구현할 수 있다. 1) 임의의 한 노드와 인접해 있는 모든 노드를 탐색하고, 방문한 노드를 표시한다. 2) 임의의 노드에 더 이상 인접한 노드가 없다면 다른 노드에서 가장 가까운 갈림길로 돌아가(백트래킹) 다시 탐색을 진행한다. 3) 방문..

완전탐색 모든 경우의 수를 고려하는 탐색 알고리즘. 완전탐색의 종류 브루트 포스 : for문을 이용하여 처음부터 끝까지 탐색하는 방법 비트 마스크 : 이진수 표현을 자료구조로 쓰는 기법 (AND, OR, XOR, SHIFT, NOT) 백트래킹 : 분할정복을 이용한 기법, 재귀함수를 이용, 해를 찾아가는 도중에 해가 될 것 같지 않은 경로가 있다면 더 이상 가지 않고 되돌아간다. 재귀함수 : 함수 내에서 함수 자기 자신을 계속해서 호출하는 것 순열 : 서로 다른 n개의 원소에서 r개의 중복을 허용하지 않고 순서대로 늘어 놓은 수 BFS(너비 우선 탐색) DFS(깊이 우선 탐색) 관련 문제 완전탐색(재귀 + 순열) : 프로그래머스 소수 찾기 (programmers.co.kr/learn/courses/30/l..

스택 (Stack) 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 자료 구조 Stack stack = new Stack(); * 스택의 연산 pop(): 스택에서 가장 위에 있는 항목을 제거한다. push(item): item 하나를 스택의 가장 윗 부분에 추가한다. peek(): 스택의 가장 위에 있는 항목을 반환한다. isEmpty(): 스택이 비어 있을 때 true를 반환한다. * 관련 메서드 push(Object item): 해당 item을 Stack의 top에 삽입 pop(): Stack의 top에 있는 item을 삭제하고 해당 item을 반환. 스택이 비어있을 때는 EmptyStackException 발생 peek(): Stack의 top에 있는 i..

그리디(탐욕) 알고리즘 각 단계에서 최선책만을 선택하며 다음 단계로 이동하는 일고리즘 최적의 해를 구하는 알고리즘이 아니다. 최적의 해에 근사 해를 구하는 알고리즘 동적 프로그래밍이 지나치게 많은 일을 한다는 것에서 착안하여 고안된 알고리즘. 동적 프로그래밍을 대체하는 것은 아니며 서로 보완해서 사용할 수 있다. 각 단계에서 최선책만을 선택하기 때문에 현재의 결과에 의해 다음 선택이 변하는 경우 적합한 알고리즘이 아니다. 각 단계에서 최선의 선택만을 하지만 결과는 최선이 아닐 수 있다. * 예제 위의 그림에서 가장 숫자가 큰 요소를 찾는데 있어서 해당 분기점마다 보다 큰 수를 찾는 방식으로 최종 해답을 찾아가고 있다. 순간마다 큰 수를 찾아가면 최종 결과는 12이다. 하지만 실제 전체 숫자 중에서 가장 ..

큰 문제를 풀기위해 작은문제를 풀어 큰문제를 풀어가는 방법 기존 재귀함수를 이용하여 피보나치 수열을 구하기 위해서는 많은 연산이 중복된다. 이러한 중복을 제거 하기 위해서 메모이제이션(Memoization)이라는 테크닉을 사용한다. 계산된 값을 버리지 말고 저장한다는 뜻이다. 계산이 된 fib(2) 값을 저장해 놓고 있다가, 필요한 경우 계산없이 호출하게 된다. 이렇게 저장되는 배열을 캐시라고 한다. 배열 f를 캐싱용으로 하나 만들어 둔다. 이 배열 내부를 -1로 모두 초기화 시키고, 만약 -1이라면 결과값이 저장되어 있지 않으므로 계산을 실행한다. * 기존 재귀함수 사용 재귀함수는 Top-Down 방식이다. int fibo(int n) { if (n == 0) return 0; if (n == 1) r..