kkoon9

문제 민오는 1번부터 N번까지 총 N개의 문제로 되어 있는 문제집을 풀려고 한다. 문제는 난이도 순서로 출제되어 있다. 즉 1번 문제가 가장 쉬운 문제이고 N번 문제가 가장 어려운 문제가 된다. 어떤 문제부터 풀까 고민하면서 문제를 훑어보던 민오는, 몇몇 문제들 사이에는 '먼저 푸는 것이 좋은 문제'가 있다는 것을 알게 되었다. 예를 들어 1번 문제를 풀고 나면 4번 문제가 쉽게 풀린다거나 하는 식이다. 민오는 다음의 세 가지 조건에 따라 문제를 풀 순서를 정하기로 하였다. N개의 문제는 모두 풀어야 한다. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다. 가능하면 쉬운 문제부터 풀어야 한다. 예를 들어서 네 개의 문제가 있다고 하자. 4번 문제는 2번 문..

위상정렬은 순서가 정해져 있는 작업을 차례로 수행해야 할 때, 순서를 결정해주는 그래프 정렬 알고리즘이다. 위상 정렬의 시간 복잡도는 **O(V + E)**로 문제를 해결할 수 있다. 위상 정렬은 DFS를 사용하여 구현하거나 indegree 배열을 사용하여 해결 가능하다. indegree란? 한 정점에서 자신에게 들어오는 방향인 간선의 수를 의미한다. 위 그래프를 예로 들어보자. 1번 정점 : 2 2번 정점 : 0 3번 정점 : 1 4번 정점 : 1 위상 정렬 알고리즘 간선의 정보를 받아 모든 정점의 indegree의 개수를 저장한다. indegree가 0인 정점을 큐에 삽입한다. 큐에서 원소를 꺼내 해당 원소와 간선을 제거한다. 제거 이후에 해당 indegree가 0이 된 정점을 큐에 삽입한다. 큐가 ..

문제 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다. 매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 20)..

문제 널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오. 배열에 자연수 x를 넣는다. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. x는 231보다 작은 자연수 또는 0이고, 음의 정수는 입력으로 주어지지 않는다. 출력 입력에서 0이 주어진 횟수만큼 답을 출력한다. 만약 배열이..

자바 8에는 다양한 기술들을 살펴보려고 하는데, 그 두 번째는 람다 표현식이다. 람다 표현식의 기본 형태는 다음과 같다. 🐻 (인자 리스트) → (바디) 앞에서 봤던 함수형 인터페이스 예시 코드에도 람다 표현식이 등장했다. public class UseDoSomething { public static void main(String[] args) { DoSomething doSomething = () -> System.out.println("eric test"); doSomething.print(); } } 인자 리스트 인자가 없을 때 : () ⇒ 대개 Supplier에 해당한다. 인자가 하나 일 때 : (value) 또는 value 인자가 여러 개 일 때 : (value1, value2) 컴파일러가 추론..

자바 8에는 다양한 기술들을 살펴보려고 하는데, 그 첫 번째는 함수형 인터페이스다. 함수형 인터페이스에 대한 설명 예전부터 사용이 되던 인터페이스 추상 메서드가 딱 하나만 있으면 함수형 인터페이스가 된다. Single Abstract Method(SAM) 인터페이스 abstarct는 생략 가능 인터페이스임에도 불구하고 인터페이스 내부에 static 메서드, default 메서드를 다룰 수 있다. static 메서드나 default 메서드가 있더라도 이 외의 추상 메서드가 단 하나라면 함수형 인터페이스가 된다. 자바가 제공해주는 @FunctionalInterface 애너테이션을 통해 인터페이스를 보다 견고하게 관리할 수 있다. @FunctionalInterface public interface DoSome..

문제 이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오. 예를 들어 위와 같은 이진 트리가 입력되면, 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식) 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식) 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트) 가 된다. 입력 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로..

문제 이진트리를 다음의 규칙에 따라 행과 열에 번호가 붙어있는 격자 모양의 틀 속에 그리려고 한다. 이때 다음의 규칙에 따라 그리려고 한다. 이진트리에서 같은 레벨(level)에 있는 노드는 같은 행에 위치한다. 한 열에는 한 노드만 존재한다. 임의의 노드의 왼쪽 부트리(left subtree)에 있는 노드들은 해당 노드보다 왼쪽의 열에 위치하고, 오른쪽 부트리(right subtree)에 있는 노드들은 해당 노드보다 오른쪽의 열에 위치한다. 노드가 배치된 가장 왼쪽 열과 오른쪽 열 사이엔 아무 노드도 없이 비어있는 열은 없다. 이와 같은 규칙에 따라 이진트리를 그릴 때 각 레벨의 너비는 그 레벨에 할당된 노드 중 가장 오른쪽에 위치한 노드의 열 번호에서 가장 왼쪽에 위치한 노드의 열 번호를 뺀 값 더하..