mojo's Blog

영어 단어 테스트 프로그램 만들기 import java.util.*; class Word{ private String eng,han; Word(String eng, String han){ this.eng=eng; this.han=han; } String getEng() { return this.eng; } String getHan() { return this.han; } } public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner scanner=new Scanner(System.in); System.out.println("\"명품영어\"의 단어 테스트를 시작합니다. -1을 입력..

문제 링크 => 1761번: 정점들의 거리 (acmicpc.net) 1761번: 정점들의 거리 첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에 M이 주어지고, 다음 M개의 줄에 거리를 알고 싶은 노드 쌍이 한 줄에 한 쌍씩 www.acmicpc.net 정점과 정점사이의 거리를 구하는 문제이다. 이 문제 역시 LCA 문제인데 다음과 같은 그림을 통해 해당 수식을 이해하기 전에 간단하게 배열들에 대한 설명을 하자면 다음과 같다. parent[x][y] => x 노드의 2^y 의 부모 depth[x] => x 노드의 깊이, 보통 1을 0으로 잡는다. path[x] => 1부터 x까지 연결된 노드의 길이 그렇다면 두 노드를 LCA를 통해 어..

문제 링크 => 11438번: LCA 2 (acmicpc.net) 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 트리를 이용한 최소 공통 조상을 찾는 문제이다. 이문제는 LCA 11437번: LCA (acmicpc.net) 이 문제와 다르게 N 값이 100,000으로 주어졌다. 따라서 1차원 배열로 해결할 경우 시간 초과가 발생한다. 따라서 부모배열을 1차원 배열이 아닌 2차원 배열로 변경하여 parent[x][y] 로 수정해준다. parent[x][y] => x의 노드에서 2^y 위에 존재하는 부모..

문제 링크 => 11437번: LCA (acmicpc.net) 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 트리에서 최소 공통 조상을 구하는 문제이다. 아이디어는 1을 최상단 노드로 잡아서 각 노드들의 부모 노드, 깊이등을 설정한 후, 임의의 두 노드의 가장 가까운 공통 조상을 찾도록 하는 것이다. 부모 노드를 표현하기 위한 배열 parent[x] 와 깊이 배열 depth[x] 을 먼저 살펴보면 다음과 같다. parent[x] : x의 부모 노드 depth[x] : x의 깊이 (0, 1, 2, 3, ...

Generic class : 기존의 클래스 작성 방법과 유사한데, 클래스 이름 다음에 일반화된 타입(generic type)의 매개변수를 사이에 추가한다는 차이가 있다. ex) public class MyClass { ... } Create Generic Object - Specialization 제네릭 클래스에 구체적인 타입을 대입하여 구체적인 객체를 생성하는 과정을 Specialization 이라 부르며, 이 과정은 자바 Compiler에 의해 이루어진다. Type Parameter 제네릭 클래스 내에서 제네릭 타입을 가진 객체의 생성은 허용되지 않는다. ex) public class MyVector{ E create(){ E a = new E(); return a; } } 제네릭 클래스 내에서 제네..

import java.util.*; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner scanner=new Scanner(System.in); Vector v=new Vector(); v.add(5); v.add(4); v.add(-1); v.add(2,100); System.out.println("size : "+v.size()+" capacity : "+v.capacity()); for(int i=0;i