응파카 성장일지

https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 최근 이 문제를 풀었고, 코드가 분명 이클립스 IDE에서는 잘 돌아갔는데 제출만 하면 RuntimeError - NullPointerException이 떴다. 죽어라 봐도 모르겠어서 결국 다른 분 블로그의 답을 확인했는데, 다른 부분은 전부 같고 //내 코드 if (temp.equals("") || temp == null) { // temp가 null이거나 빈 문자열인 경우 실행될 코..

트리 (Tree) Tree 구조는 계층적인 구조를 표현할 수 있는 자료구조이다. Tree 구조는 루트 노드에서 시작하여 여러개의 하위 노드들이 연결된 형태로 구성되며, 각 노드는 각자의 하위 노드들을 가질 수 있다. Java에서는 Tree 구조를 구현하기 위해 다음의 인터페이스와 클래스들을 사용한다. 아래 인터페이스와 클래스들은 중복값을 허용하지 않는다. 사용 인터페이스 java.util.Set Tree 구조를 구현하기 위한 인터페이스로, 이 인터페이스를 implements 하는 클래스들은 모두 Tree 구조를 갖는다. java.util.SortedSet Set 인터페이스를 상속받으며, 정렬된 Tree 구조를 표현하기 위한 인터페이스이다. 사용 클래스 java.util.TreeSet SortedSet 인..

PriorityQueue (우선순위 큐)는 우선순위에 따라 정리되어 있으며, 우선순위가 가장 높은 요소에 먼저 접근할 수 있는 자료구조이다. PriorityQueue 의 구현을 위해서는 Heap 이 사용된다. PriorityQueue는 기본적으로 Min Heap을 사용한다. 가장 높은 우선순위를 갖는 요소는 root 노드에 위치하게 된다. 이에 따른 요소의 추가와 삭제 과정은 다음과 같다. 추가 과정 새로운 요소를 Heap의 마지막 노드에 위치시킨다. 부모노드와 비교하며 적절한 위치에 배치한다. 삭제 과정 우선순위가 제일 높은 요소를 뽑는다. (root 노드) 이후 Heap의 마지막 노드를 root 노드의 위치로 이동시킨다. 자식노드와 비교하며 적절한 위치에 배치한다. PriorityQueue 클래스 메..

[백준 1991] 트리순회 [백준 1991] 트리순회 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 eggmomo.tistory.com 저번에 풀었던 [백준 1991] 트리순회 문제를 풀면서 궁금증이 생겼다. BufferedReader로 받아온 String을 char 자료형으로 변환하는 것이 귀찮아서 Node 클래스의 name 필드 자료형을 String으로 지정하여 풀었는데, static void addNode(Node node, String head, String left, String right) { ..

StringTokenizer는 공백, 탭, 새 줄 등의 구분자( \n, \t, \r, \f )를 기준으로 String을 나눌 때 사용하는 클래스이다. nextToken() nextToken()은 StringTokenizer 에서 다음 토큰을 불러오는 메서드이다. BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer stk = new StringTokenizer(br.readLine()); System.out.print(stk.nextToken()); System.out.print(stk.nextToken()); System.out.print(stk.nextToken()); input output A..

Primitive Type (기본 자료형)은 부등호를 사용하면 간단하게 비교할 수 있었다. 하지만 어떤 기준에 따라 객체를 비교하게 된다면 부등호를 사용할 수는 없다. 아래 문제와 같이 좌표상의 점의 x, y좌표를 기준으로 정렬해야하는 경우가 그렇다. x좌표를 기준으로 오름차순 정렬하되 x좌표가 동일하다면 y좌표를 기준으로 오름차순 정렬하고자 한다. 이럴 때 사용하는 것이 Comparable Interface이다. 사용 방법은 다음과 같다. List 정렬 위한 Collections.sort(List)를 사용한다. 여러 필드를 가진 객체를 비교하기 위해 Comparable 를 implements 한다. 이후 compareTo를 Override 해 return 값으로 sort할 수 있도록 한다. import..

Heap Heap은 완전 이진트리를 기반으로 한다. 최대 힙(Max Heap)은 루트 노드로 올라갈수록 저장된 값이 커지는 구조이다. 최소 힙(Min Heap)은 루트 노드로 올라갈수록 저장된 값이 작아지는 구조이다. 최대 힙이든 최소 힙이든 모든 부모 노드의 우선순위는 자식 노드보다 크거나 같다. 구현의 용이함을 위해 root index는 1부터 시작한다. 위 조건을 만족하며 완전이진트리 형태로 채워나가면 된다. 즉, 형제노드간 우선순위는 고려하지 않아도 된다. Heap의 부모 노드와 자식 노드간 관계 부모 노드의 index = (왼쪽 자식 index) / 2 왼쪽 자식 index = (부모 index) * 2 오른쪽 자식 index = (부모 index) * 2 + 1 새로운 노드 추가 시 새로운 노..

Stack LIFO(Last In, First Out) 원칙을 따르는 선형 데이터 구조. 새로운 요소는 항상 최상위에 삽입되고, 삭제 역시 최상위에서만 이루어 진다. Stack의 주요 메서드 push( {value} ) : Stack의 맨 위에 element를 삽입한다. pop() : Stack의 맨 위에 있는 element를 삭제하고 반환한다. peek() : Stack의 맨 위에 있는 요소를 삭제하지 않고 반환한다. isEmpty() : Stack이 비어있는지 여부를 반환한다. empty() : Stack이 비어있는지 여부를 반환한다. search() : Stack에서 element가 몇 번째 위치에 있는지 반환한다. 1부터 시작한다. clear() : Stack의 모든 값들을 삭제한다. 이 때 em..

동아리 동기들과 스터디 그룹을 만들어 숙제 중 하나인 백준문제 풀이를 진행하던 도중 간단하게 생각했던 Stack 문제에서 시간초과가 발생했다. 옛날에도 비슷한 경험을 했던 적이 있어서 입력방법을 다르게 했더니 해결이 되었던 경험이 있었는데.. 싶어 찾아보니 Scanner 클래스보다 속도면에서 훨씬 우수한 BufferedReader 라는 것이 있다는 것을 알았다. Scanner BufferReader 패키지 java.util java.io 데이터 전송 타이밍 입력 받음과 동시에 즉시 전송. 개행문자 만날 때, Buffer 가득 찰 때 버퍼내용 한 번에 보냄. 속도 비교적 느림. 비교적 빠름. 데이터 파싱 별도의 형변환이 필요 없다. 모든 입력을 String으로 받으므로 별도의 형변환이 필요할 수 있다. 버..

Set interface를 구현한 클래스. BinarySearchTree(이진탐색트리) 구조로 이루어져 있으며, 그 중에서도 성능을 향상시킨 Red-Black Tree로 구현되어있다. 일반적인 이진탐색트리의 경우, 입력값이 분산되어 들어오지 않고 한 쪽에 치우쳐서, 편향되어서 들어온다면 효율적이지 못하게 된다. 이 문제를 보완한 방식이 레드-블랙 트리이다. 레드-블랙 트리는 부모노드를 기준으로 왼쪽 오른쪽으로 배치해 편향되지 않은 구조가 되도록 한다. TreeSet 생성 TreeSet 생성 TreeSet treeSet = new TreeSet(); TreeSet 생성, 타입 파라미터 생략 TreeSet treeSet = new TreeSet(); treeSet_1의 값을 갖는 TreeSet 생성 Tree..