응파카 성장일지

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..

https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static Node rootNode = new Node('A', null, null); static class Node{ c..

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

https://programmers-story.tistory.com/10 [백준 알고리즘] 메모리 초과 발생 이유 및 해결 방안 문제를 푸시다보면 다양한 에러를 만나실텐데요. 오늘은 백준알고리즘 1697번을 풀면서 발생한 메모리 초과에 대해서 글을 써보려고 합니다. 메모리 초과가 발생하는 이유를 간단히 말씀드리자 programmers-story.tistory.com 단순한 탐색 문제로 생각하고 인접행렬을 사용해 다음과 같이 풀었더니 메모리 초과가 나왔다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack; import java.util.StringT..

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..

자바의 모든 코드는 클래스 내에 존재한다. 클래스 작성 방법은 다음과 같다. class ClassName { } class ClassName{ public static void main(String[] args){ } } 위 코드의 public static void main(String[] args) 는 프로그램 실행 시 java.exe에 의해 호출되는 프로그램의 시작점이다. Java 애플리케이션에는 main메서드를 포함한 클래스가 반드시 하나 있어야 한다. Java 애플리케이션을 실행할 때는 java.exe 다음 main 메서드가 포함된 클래스 이름을 적어준다. (시작점 역할) 하나의 소스파일에 둘 이상의 클래스를 정의하는 것은 가능하다. 소스파일의 이름은 public class의 이름과 같아야 한다...

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

HashMap은 Map interface를 구현한 대표적인 Map Collection(데이터의 집합)이다. Map은 Key와 Value로 구성된 Entry 객체를 저장하는 구조의 자료구조이고, 이 때 Key와 Value는 둘 다 객체이다. Value는 중복저장이 가능하지만 Key는 중복저장이 불가능하다. 동일한 키로 저장 시 기존값을 삭제하고 해당 Key를 갖는 새로운 값으로 저장된다. HashMap 생성 HashMap 생성 HashMap map = new HashMap(); HashMap 생성 시, 타입 파라미터 생략 HashMap map = new HashMap(); HashMap 생성 시, HashMap map_1의 모든 값을 가진 HashMap 생성 HashMap map = new HashMap(..

자연수 N을 입력받고, 1부터 N까지의 소수의개수를 출력해야 할 경우 편입했을 당시 학교 온라인저지에서 풀었던 코드를 발견했는데 각각 숫자에 대해 2부터 x-1까지 반복문을 돌려 나머지==0 인 경우가 있으면 소수가 아님을 판별하는 brute force 방식, 전체 탐색 방식의 코드였다. O(N)의 시간복잡도를 갖는 비효율적인 방법이지만 1학년 초반의 수업이었음을 감안하여 Time Limit Exceeded가 발생하지 않는 테스트케이스들을 주셨던게 아닐까 한다.. 다음 방법은 N의 약수들이 대칭을 이루고 있다는 성질을 이용한 방법으로, N=20일 때 약수는 1, 2, 4, 5, 10, 20 이고 1과 N을 제외하고, 4와 5는 4*5=20 으로 대칭 관계이기 때문에 굳이 5까지 판별할 필요가 없다는 점을..