Sentio, ergo sum

문제 설명 파일

subset.hwp

샘플 파일

test.inp

test.out

인공지능 과제에서 인덱싱을 하면서 무심코 HashMap을 사용했는데,

다른 조의 시연을 보니 인덱싱에 상당한 시간이 소요되었다.

갑자기 궁금증이 생겨서 세 컬렉션의 속도를 비교하게 되었다.

테스트 엘리먼트는 Integer 인스턴스 5,000,000(5백만개)를 이용하여 수행하였다.

탐색과 삭제에서는 균등하게 떨어진 4990개의 데이터를 이용하였다.

테스트 결과 :

HashMap의 경우는 입력되는 시간을 제외하면 우수한 성능을 보였고,

(탐색과 삭제 시에 인덱스가 아닌 키값으로 하였음)

ArrayList 의 경우에는 내부적으로 배열을 쓰는 컬렉션 답게 탐색에서는 매우 우수한 속도를 보였지만

삭제 시에 배열의 구조가 변경되므로 매우 느린 속도를 보였다.

LinkedList는.. 탐색, 삭제 모두 순차 탐색을 하므로(실제로 이중 연결 링크드리스트로 되어있고, Head, Rear 포인터를 이용해서, 탐색하려고 하는 인덱스와 리스트 크기의 반과 비교해서 인덱스가 작은 경우 앞에서부터 탐색하고, 큰 경우 뒤에서부터 탐색하도록 되어있어 평균적으로 n / 2의 시간 복잡도를 가진다.) 많이 느렸다. -_-

따라서 HashMap은 Key, Value 쌍을 가지는 데이터를 관리할 때 용이하고,

ArrayList는 데이터가 입력 되고 삭제가 빈번하지 않은 경우에 사용하면 되고,

Linkedlist는 Queue와 같이 Head와 Read와 가까이에서 탐색, 삭제가 이뤄지는 경우에 쓰면 좋을 듯 하다.

테스트에 사용한 코드는 아래와 같습니다. 참고 하실 분은 아래의 소스를 사용하시면 됩니다.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

public class TestCode {
	static Integer[] testArray = new Integer[5000000];
	Integer[] values = new Integer[4990];

	public void hashMapTest() {
		long start = System.nanoTime();

		HashMap hashmap = new HashMap();
		for(Integer integer : testArray){
			hashmap.put(integer, integer);
		}
		
		long end = System.nanoTime();
		
		System.out.println("\nHashMap Test");
		System.out.println("\t입력 소요 시간  " + second(start, end) + "초");
		
		start = System.nanoTime();
		for(Integer value : values){
			hashmap.get(value);
		}		
		end = System.nanoTime();
		System.out.println("\t탐색 소요 시간 " + second(start, end) + "초");
		
		start = System.nanoTime();
		for(Integer value : values){
			hashmap.remove(value);
		}
		end = System.nanoTime();
		System.out.println("\t삭제 소요 시간 " + second(start, end) + "초");
	}
	
	public void arrayListTest(){
		long start = System.nanoTime();
		
		ArrayList arrayList = new ArrayList();
		for(Integer integer : testArray){
			arrayList.add(integer);
		}
		
		long end = System.nanoTime();
		
		System.out.println("\nArrayList");
		System.out.println("\t입력 소요 시간  " + second(start, end) + "초");
		
		start = System.nanoTime();
		for(Integer value : values){
			arrayList.get(value);
		}		
		end = System.nanoTime();
		System.out.println("\t탐색 소요 시간 " + second(start, end) + "초");
		
		start = System.nanoTime();
		for(Integer value : values){
			arrayList.remove(value);
		}
		end = System.nanoTime();
		System.out.println("\t삭제 소요 시간 " + second(start, end) + "초");
	}
	
	public void linkedListTest(){
		long start = System.nanoTime();
		
		List linkedList = new LinkedList();
		for(Integer integer : testArray){
			linkedList.add(integer);
		}
		
		long end = System.nanoTime();
		
		System.out.println("\nLinkedList");
		System.out.println("\t입력 소요 시간  " + second(start, end) + "초");
		start = System.nanoTime();
		for(int value : values){
			linkedList.get(value);
		}		
		end = System.nanoTime();
		System.out.println("\t탐색 소요 시간 " + second(start, end) + "초");
		
		start = System.nanoTime();
		for(int value : values){
			linkedList.remove(value);
		}
		end = System.nanoTime();
		System.out.println("\t삭제 소요 시간 " + second(start, end) + "초");
	}


	private void prepare() {
		long start = System.nanoTime();
		for (int i = 0; i < testArray.length; i++) {
			testArray[i] = i;
		}
		long end = System.nanoTime();
		
		ArrayList temp = new ArrayList(1000);
		for(int i = 0 ; i < 4990 ; i++){
			temp.add(i * 1000);
		}
		temp.toArray(values);
		
		
		System.out.println(testArray.length + "개의 인스턴스 생성 시간 " +
				second(start, end) + "초");
		
	}
	
	private double second(long start, long end){
		return (end - start) / Math.pow(10, 9);
	}

	public void start() {
		prepare();
		hashMapTest();
		arrayListTest();
		linkedListTest();
	}

	public static void main(String[] args) {
		TestCode test = new TestCode();
		test.start();
	}
}

네이트온을 사용하면서 네이트온 메인창의 광고와 시작 시

자동으로 뜨는 팝업창을 제거하는 방법입니다.

공짜로 사용하면서 광고정도는 봐줘야 인지상정이지만..! 그래도 걸리적 거리는게 현실 -_ -ㅋ

양심의 가책을 쪼금(;) 느끼면서 팁을 올려봅니다. (윈도우 XP 기준입니다.)

1. 메인창 하단 광고 없애기

시작메뉴 >> 실행에서 위와 같이 입력하고 확인을 눌러줍니다.

연결 프로그램 창이 뜨면 Notepad(메모장)을 선택합니다.

메모장이 뜨면 빨간색으로 쓴 부분과 같이 쓰고 저장해주고 종료하면 됩니다.(아래 복사)

127.0.0.1 adimg.nate.com

127.0.0.1 cyad.nate.com

127.0.0.1 nateonevent.nate.com

127.0.0.1 nateon.nate.com

127.0.0.1 nokw.nate.com

2. 팝업 광고 없애기

네이트온 창 메뉴에서 설정(S) >> 환경 설정(S)를 들어갑니다. 단축키 F11을 누르셔도 됩니다.

보기 탭에서 로그인시 보기 설정을 모두 보지 않기를 하시면 팝업 창이 뜨지 않습니다.

이상입니다. 좀 더 네이트온을 가볍게 써봅시다 :)

※ 윈도우 7 환경 기준으로 설명했습니다.

보통 윈도우에서 기본 값으로 "알려진 확장자를 보이지 않음"으로 되어있어서

연결프로그램이 있는 확장자의 경우에는 확장자가 보이지 않습니다.

가끔씩 확장자를 봐야할 때가 있는데, 아래와 같이 설정하면 확장자를 확인할 수 있습니다.

먼저 아무 폴더나 열고, 왼쪽 상단에서 [구성 ▼] 를 눌러 메뉴가 보이면 [폴더 및 검색 옵션]을 클릭합니다.

[폴더 옵션] 대화상자가 열리면 [보기] 탭으로 이동하신 후 고급 설정란에서 조금 스크롤을 내리면

알려진 파일 형식의 파일 확장명 숨기기 항목이 보일겁니다.

이 항목의 체크를 해제 해 주시고 확인을 누르시면 파일 이름에서 확장자가 보이는 것을 확인할 수 있습니다.

Gmail을 이용해서 데모 프로그램을 보낼 일이 있어서 해당 실행파일을 첨부했더니 이게 뭔가..?

"보안상의 이유로 Gmail에서는 해당 형식의 파일을 보낼 수 없습니다."

다른 메일로 보내려고 했더니 이상하게 계속해서 반송이 되는 바람에 그냥 지메일로 보내기로 했다.

팁이랄 것도 없지만 해결 방법은 확장자를 exe에서 다른 확장자로 바꾸어주면 된다.

단, 완전히 다른 확장자로 변경하는 경우 원래의 확장자를 유추하기 힘들수 있으므로

가장 끝의 글자만 언더바(_)로 바꿔주는 것과 같이 원래의 확장자를 반쯤 유지해주면 좋다.

exe -> ex_ 로 확장자 변경 후 첨부하여 전송

[그림 1] AWT에서 한글이 깨져서 나오는 현상

AWT에서 한글 입력 시에 네모 글자로 나올 때가 있습니다. 정확한 이유는 모르겠지만 프로젝트의 인코딩과

컴파일시의 인코딩이 일치하지 않아서 발생하는 문제인 듯 합니다.

제 경우에는 프로젝트의 기본 인코딩이 UTF-8 인 경우였습니다.

보통은 Inherited Character Encoding 이라고 해서 디폴트 인코딩을 사용해서

문제 없이 사용할 수 있었는데, UTF-8로 지정하니 한글이 깨져버리네요.

이럴 때는 -Dfile.encoding=MS949 라는 VM Arguments를 추가해주면 됩니다.

상세한 설정 방법을 알아보도록 하겠습니다.

먼저 이클립스의 Package Explorer에서 프로젝트를 선택한 후 Alt + Enter 키 또는 마우스 오른쪽 버튼을 눌러

Properties for Project 대화상자를 엽니다. 제 경우의 프로젝트 이름은  GUI_MathML이군요.

[그림 2] Package Explorer에서 프로젝트 선택

[Properties for Project] 대화 상자가 열리면 Run/Debug Settings 탭으로 이동합니다.

그리고 Launch configurations for 'Project name': 항목을 보면 최근에 실행한 메인 클래스가 보이는데,

AWT의 메인이 되는 클래스를 클릭하고 [Edit...] 버튼을 누르시거나 더블클릭 해서 실행 설정 편집창을 엽니다.

※ 만약 아무런 클래스도 보이지 않는다면 [New...] 버튼을 눌러 Java Application을 선택하고 Main class를 선택하고, 이 후에 나오는 내용을 동일하게 적용하면 됩니다.

[그림 3] 프로젝트 속성 대화상자의 Run/Debug Settings 탭

[Edit configuration] 창이 열리면 Arguments 탭으로 이동하여 VM arguments: 란에

-Dfile.encoding=MS949 라고 입력해 준 후 [OK]버튼을 눌러 모든 설정을 완료하고 닫아줍니다.

[그림 4] Edit Configuration 대화상자의 Arguments 탭의 VM arguments 항목 수정

여기까지 설정을 마쳤으면 다시 프로그램을 실행해 봅니다.

[그림 5] 설정 완료 후  AWT 프로그램 재실행

이제 한글이 정상적으로 나옵니다. :D

2학년 자료구조 수업 문제를 낼일이 있어서 우선순위 큐(힙)을 이용해서 내본 문제

문제 파일 :

ds_assignDoc8.hwp

샘플 입력, 출력 파일 :

test.inp

test.out

시뮬레이션 프로그램(Visual C# 2010 환경에서 작성, .Net 4.0 이상 필요)

FreeTaxi.exe

같은 입력 데이터에 세가지의 처리를 해야할 일이 있어서,

처음에 입력 데이터를 입력받아서 배열로 만든 후,

아무런 생각없이 Arrays 클래스의 copyOf 메서드를 이용해서 나머지 두개의 카피 배열을 만들었다.

분명 로직은 샐 틈이 없는데, 알 수 없는 이유로 프로그램의 흐름이 이상해져서

몇시간 째 코드를 뚫어져라 보다가 정말 '아!' 하는 생각이 머릿속을 스치고 지나갔다.

배열 복사는 Shallow Copy..............

같은 레퍼런스를 쓰니 당연히 값이 틀어질 수 밖에..... 악!!

좋은 교훈을 얻었다. 덤으로 continue 단 한줄의 교훈도 

힙을 구현하기는 귀찮아서 '혹시나' 싶어서 찾아보니 '역시나' 고맙게도 자바에 PriorityQueue가 있네요.

먼저 PriortyQueue는 java.util 패키지에 있고, 여러 형태의 생성자가 오버로딩되어 있는데,

주요한 두가지만 알아보면 아래와 같습니다.

• PriortyQueue<E>()
• PriorityQueue<E>(int initialCapacity, Comparator<? super E> comparator)

둘을 비교하자면 전자는 기본 생성자를 이용해서 심플하게 생성하는 방법이고,

후자는 초기 큐 내부의 배열 크기와 Comparator 객체를 전달하면서 객체를 생성하는 방법입니다.

(어째서인지 initialCapacity 없이 Comparator만 전달하는 생성자는 없더군요.)

※ initialCapacity?

큐 내부에서 사용하는 배열의 초기 크기를 결정하는 값입니다.

기본적으로 11의 크기를 사용하고 임의로 전달할 경우에는 그 크기를 사용하는데 1보다 작은 경우

IllegalArgumentException 예외가 발생합니다. 전달 인자가 잘못되었단 얘기죠.

배열의 크기는 initialCapacity로 고정되는 것이 아니라, 요소의 수가 배열의 크기에 도달하면

크기를 늘립니다. 재밌는 것은 배열의 크기가 커질 때 규칙을 보면 배열의 크기가 64 미만일 때는 2씩 커지고,

그 이후로는 이전 크기의 1/2 씩 증가하도록 되어있습니다.

왜 이런 룰이 적용되었는지는 잘 모르겠네요.

큐 내의 배열의 최대크기는 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

이렇게 정의되어 있으니, 값으로 보면 2147483639 까지입니다. 왠만한 경우엔 다 들어갈 수 있겠죠?

다만, 힙 메모리가 부족해서 최대 크기가 되기 전에 OutOfMemoryError가 먼저 발생하겠네요.

큐에서 중요한 두 메서드, 큐에 넣고(add), 큐에서 빼는(poll) 메서드에 대해 간단하게 설명하겠습니다.

덤으로 가장 우선순위가 높은 요소를 확인하는 peek 메서드도요.

• boolean add(E e) : 큐에 요소를 추가합니다. 반환값은 성공 여부입니다.
• E poll() : 큐에서 우선순위가 가장 높은 요소를 빼냅니다. 즉 반환 후에 큐에서 삭제됩니다.
• E peek() : poll과 달리 큐에서 삭제하지 않고 가장 우선순위가 높은 요소를 얻습니다.

1. PriorityQueue()

기본 생성자를 이용하는 경우는 제너릭 타입 E의 compareTo 메서드를 이용하여 정렬에 사용합니다.

compareTo 메서드는 그냥 compareTo메서드를 만들어 쓰는 것이 아니라, 

Comparable 인터페이스를 구현해서 만듭니다.

만약 Comparable 인터페이스를 구현하지 않은 클래스를 큐의 엘리먼트로 사용하는 경우에는

java.lang.ClassCastException을 만나게 될 겁니다. PriorityQueue 내부에서 Comparable 타입으로 캐스팅해서

compareTo 메서드를 호출하기 때문입니다.

기본 생성자를 이용하여 큐의 객체를 생성하는 경우를 소스코드로 작성해볼까요.

먼저 요소로 사용할 Element 클래스를 작성해 보겠습니다.

class Element implements Comparable<Element>{
	private int num; // 정렬의 기준이 될 값
	
	public Element(int num){
		this.num = num;
	}
	
	public int getNum(){
		return num;
	}

	@Override // Comparable 인터페이스의 compareTo 메서드 구현
	public int compareTo(Element o) {
		return num <= o.num ? -1 : 1;
	}
}

compareTo 메서드의 기능은 현재 객체와 다른 Element 객체를 비교하여 우선순위를 판단하는 것입니다.

우선순위의 판단은 반환값으로 하는데 음수인 경우에는 현재 객체가 우선임을 의미하고,

양수인 경우에는 대상 객체(위의 소스코드에서는 Element o)가 우선임을 의미합니다.

간편하게 return num - o.num; 을 해도 됩니다.

다음으로 PriorityQueue를 사용해 볼 클래스 PriorityQueueTest 를 작성해 보겠습니다.

public class PriorityQueueTest {
	public static void main(String[] args) {
		PriorityQueue<Element> q =
				new PriorityQueue<Element>();
		
		Random random = new Random(System.nanoTime());
		
		// 0~49의 난수를 생성하여 큐에 넣습니다.
		for(int i = 0 ; i < 10 ; i++){
			q.add(new Element(random.nextInt(50)));
		}
		
		// 큐에서 값을 빼면서 정렬이 되었는지 출력해봅니다.
		int size = q.size();
		for(int i = 0 ; i<size ; i++){
			System.out.println(q.poll().getNum());
		}
	}
}

[출력결과]

2. PriorityQueue(int initialCapacity, Comparator<? super E> comparator)

복잡해 보이는 생성자지만 간단합니다. 초기 배열 크기와 Comparator를 구현한 객체를 전달해 주면 되는데,

Comparator<? super E> 가 조금 거슬리는 분도 있을 거라고 생각합니다.

Java 5 부터 제너릭 개념이 들어가면서 컬렉션 관련 API에는 제너릭이 들어가도록 모두 바뀌었습니다.

제너릭이라고 말하는게 꺽쇠 괄호 < > 를 이용해 타입을 지정해 주는 것을 말합니다.

제너릭에 관해서는 다른 글에서 얘기하기로 하고, 위의 <? super E>가 의미하는 것만 알아보면

Comparator 선언 시, 혹은 구현시에 Comparator<타입> 의 형태로 적어줘야 합니다.

이때 ? super E 가 의미하는 게 위에 들어가는 타입은 E를 상속받은 하위 클래스여야 한다는 의미가 됩니다.

풀어보면 어떤 타입(?)의 부모(super)가 E여야 한다. 라고 볼 수 있겠네요.

복잡하게 생각할 것 없이 여기서는 "타입"의 위치에 Element를 적어주도록 합시다.

Comparator 인터페이스를 구현하는 방법은 여러가지가 있겠지만 여기서는 그냥 익명 이너 클래스로 구현하여

전달하도록 하겠습니다. Element 클래스는 위의 클래스 그대로 사용합니다.

class PriorityQueueTest {
	public static void main(String[] args) {
		PriorityQueue<Element> q =
			new PriorityQueue<Element>(50, new Comparator<Element>() {
				@Override
				// Comparator 인터페이스의 compare 메서드를 구현합니다.
				// 여기서는 이전과 반대로 내림차순 정렬을 하도록 했습니다.
				public int compare(Element o1, Element o2) {
					return o2.getNum() - o1.getNum(); 
				}
			});
		
		Random random = new Random(System.nanoTime());
		
		// 0~49의 난수를 생성하여 큐에 넣습니다.
		for(int i = 0 ; i < 10 ; i++){
			q.add(new Element(random.nextInt(50)));
		}
		
		// 큐에서 값을 빼면서 정렬이 되었는지 출력해봅니다.
		int size = q.size();
		for(int i = 0 ; i<size ; i++){
			System.out.println(q.poll().getNum());
		}
	}
}

[출력 결과]

내림차순으로 정렬이 되었습니다. 여기서 조금 의아한 점을 찾으신 분도 있을 것 같습니다.

이미 Element는 Comparable 인터페이스를 구현해서 오름차순으로 정렬하도록 되어있는데,

내림차순으로 정렬되었기 때문입니다. 그 의문점의 결과는 위의 출력결과가 말해줍니다.

즉 compareTo 메서드보다 compare 메서드가 우선한다는 말이지요.

(그냥 내부적으로는 if(comparator != null){ ... } 이렇게 되어있어서 문장상에서 우선하게끔 되어있습니다.)

자바의 PriorityQueue 클래스를 사용해 봤습니다.

Comparator나 Comparable인터페이스에 대한 개념이 확실하게 잡힌다면 크게 무리 없이 사용할 수 있을 것 같습니다.

개인적으로 컴퓨터 공학을 전공하면서, 프로그래밍을 위해 필요한 공부가 무엇인지 정리해 보았습니다.

아직 학생이고, 실무경험이 없다보니 현실과는 동떨어진 얘기를 할 수도 있습니다. 언제나 태클 환영입니다.

1. 수학

중학교 때부터 게임에 빠져서 공부는 저만치 뒷전이었습니다.

오죽하면 공부하라고 해줬던 빨간펜도 몇달이나 손도 한번 안대고 잔뜩 쌓여서는 부모님께 죽도록 맞았을까요.

심지어 게임만 한다고 인터넷을 끊거나 컴퓨터를 버린 적도 있습니다.

지금 생각하면 정말 사무칠 정도로 후회됩니다만, 되돌릴 수 없으니 그 후회를 되돌릴 만큼 지금 열심히 해야겠죠.

어쨌거나, 게임으로 인해 고2까지도 공부는 시험 당일치기 밖에 없었는데,

과학은 좋아해서 그나마 수업시간에도 따라갈 수 있었고, 다른 과목도 그럭저럭 해왔는데,

수학만큼은 한번 놓치고 나니 정신을 차렸을 땐 도무지 뒤쫓아 갈 수가 없더군요.

그나마 희한하게도 미분, 적분은 좋아해서 고거 하나는 찔끔 할 줄 알고,

나머진 그냥 경험에 의한 문제 풀이 정도가 다네요.

일단 지금까지 프로그래밍을 하면서 수학적인 개념이 없어도 크게 문제될 것은 없었지만,

탄탄한 수학 이론이 바탕이 된 프로그래밍은 프로그램에 날개를 달아준다고 생각합니다. 

논리적인 사고를 할 수 있게 해주고, 효율적인 알고리즘을 작성하게 해줄 수 있는게 수학 지식에서 비롯되죠.

즉, 본인도 적은 노력으로 프로그래밍을 할 수 있고, 프로그램도 효율적으로 동작할 수 있게하므로

경제성이 올라간다고 생각할 수 있겠네요.

2. 영어

영어공부요? 저도 싫어합니다. 좋은 우리말 두고 영어 공부하긴 정말 싫죠.

잘하고 싶은 욕심은 납니다. 하지는 않고서 말이죠.

객기일지도 모르겠지만 토익, 오픽 이런 스펙보단 제 적성, 제가 하고 싶은 일을 따라가자는 주의입니다.

그런 핑계로 영어 공부를 소홀히 하고 있었는데, 공부를 깊이 하면 할 수록 성적을 위한 영어가 아니라,

지식을 습득하기 위한 영어가 정말로 필요하다고 느껴집니다.

프로그래밍 언어가 한국에서 시작했으면 모를까, 컴퓨터도 그렇고 프로그래밍 언어도 그렇고

영어권 국가에서 시작한게 많다보니 퀄리티 높은 정보나 깊이 있는 정보들은 영어로 되어있는게 많습니다.

그렇다보니 자연스럽게 영어 실력이 절실해지더군요.

헌데 아직도 영어는 뒷전이네요. 말만 필요하다 필요하다. 언제부터 시작할까요?