'전체 글'에 해당되는 글 203건

  1. 2015.12.04 허프만 코드 알고리즘 5
  2. 2015.11.27 mutable vs immutable
  3. 2015.11.23 자바 스레드 프로그래밍
  4. 2015.11.21 자바 예외 처리
  5. 2015.11.20 최소 비용 스패닝 트리 - kruskal 알고리즘

허프만 코드 알고리즘

알고리즘 2015. 12. 4. 00:08

허프만 코드 알고리즘은 압축 알고리즘 중의 하나이다.

알집 역시 허프만 코드 알고리즘으로 한 번 압축하고 난 후에, 

Lempel이라는 알고리즘으로 한 번 더 압축한다고 한다. 

그만큼 실제로도 허프만 코드 알고리즘은 압축 알고리즘에서 중요하다는 말!


허프만 코드 알고리즘에 대해서 소개

자주 쓰이는 문자에 작은 bit를 비교적 덜 쓰이는 문자에 큰 bit를 할당해서 문자열을 전체적으로 압축하는 

개념이다.

예를 들어, AABBAC에서 

A => 3번

B => 2번

C => 1번

출현한다. 

가장 많이 사용하는 A에는 0을,

그 다음 B에는 01, C에는 11을 부여해

A(0)A(0)B(01)B(01)A(0)C(11)로 만든다.

=> 000101011

영문자 하나는 1byte이기 때문에 6byte가 사용되었다. (6 * 8 =  48 bit)

압축된 허프만 코드는 9bit가 된다. 

9/48 = 0.18     => 20%로 압축된다!


허프만 코드의 작동 방법?

예를 들어, CDDCACBCBCCCBBCDA라는 문자열이 있다.(총 17byte)

1) 빈도수 검사


2) 빈도수 대로 정렬(Repeat 1/2)


3) 가장 낮은 두 그룹을 묶어서 하나의 그룹으로 만듦(Repeat 2/2)


4) 빈도수 대로 정렬(Repeat 1/2)


5) 가장 낮은 두 그룹을 묶어서 하나의 그룹으로 만듦(Repeat 2/2)


6) 빈도수 대로 정렬(Repeat 1/2)


7) 가장 낮은 두 그룹을 묶어서 하나의 그룹으로 만듦(Repeat 2/2)


8) 트리 완성!



허프만코드 작성

가장 윗 트리에서 빈도수가 큰 트리에 0을 작은 트리에 1을 부여

위(최상위) 트리 노드를 기준으로 비트를 참조한다.

부모노드에서 출발하여 문자열에 다다를때까지 비트를 더하여 참조한다. 즉, 

D => 000

A => 001

B => 01

C => 1 


디코드 하는 방법?

호프만 트리를 타고 내려가면서 문자를 만나면 치환을 한다.(복호화 과정)

1000000100110110111101011000001

최상위 노드를 기준으로 비트의 수를 따라가며 알파벳을 만날 때까지 따라간다.

1(C)/000(D)/000(D) ..........

=> CDDCACBCBCCCBBCDA 가 된다!


참조 http://wooyaggo.tistory.com/95


'알고리즘' 카테고리의 다른 글

최소 비용 스패닝 트리 - kruskal 알고리즘  (0) 2015.11.20
최소 비용 스패닝 트리 - Prim알고리즘  (0) 2015.11.20
이진탐색(Binary Search)  (0) 2015.10.16
쉘 정렬  (0) 2015.09.26
퀵정렬  (0) 2015.09.26
Posted by slender ankles
,

mutable vs immutable

JAVA 2015. 11. 27. 00:33

StringBuffer, StringBuilder vs String

스트링버퍼와 스트링빌더와 스트링 객체와의 가장 큰 차이는 

mutable 인지, immutable인지입니다. 


다음과 같은 코드의 결과값은 어떻게 될까요?

public class Test{
    
    public static void changeMutable(StringBuilder target){
        target.append('d');
    }
    
    public static void changeImmutable(String target){
        target += "d";
    }
    
    public static void main(String[] args) {
        StringBuilder test1 = new StringBuilder("abc");
        String test2 = "abc";
        
        System.out.println(test1);
        System.out.println(test2);
        
        changeMutable(test1);
        changeImmutable(test2);
        
        System.out.println(test1);
        System.out.println(test2);
    }
}
cs

<출력화면>

abc

abc

abcd

abc


와 같이 출력됩니다. 

우선 String클래스는 append와 같이 객체를 변화시킬 메서드를 제공하지 않습니다. 

반면에 StringBuildler와 StringBuffer는 append와 같은 set메서드를 제공합니다. 



그렇다면 immutable, 즉 변할 수 없는 불변의 객체를 제공하는 이유는 무엇이며 어떻한 경우에 필요한 걸까요?

멀티 스레드 환경에서 객체가 변화되는 상황에서는 immutable한 데이터를 통해 정보가 보여져야 합니다. 

그렇지 않은 경우 의도치 않은 데이터가 발생하게 됩니다. 

자바의 문제였던 시간 API가 자바 8에서 개선된 점에도 Date객체를 immutable한 속성으로 fix시켜 놓은 것과 

마찬가지 이유입니다. 




'JAVA' 카테고리의 다른 글

자바 스레드 프로그래밍  (0) 2015.11.23
자바 예외 처리  (0) 2015.11.21
GC(Garbage Collection)의 대상은 누구인가?  (0) 2015.11.10
LinkedHashMap, TreeMap, HashMap  (0) 2015.11.07
Comparable 인터페이스에 대한 이해  (0) 2015.11.07
Posted by slender ankles
,

자바 스레드 프로그래밍

JAVA 2015. 11. 23. 00:33

참조 : http://blog.eairship.kr/126(금지된 엑시노아의 비공정 블로그)

스레드란 무엇인가?

"프로그램의 실행 흐름, 프로그램을 구성하고 있는 실행 단위"라 말할 수 있다. 보통 메인 문에서 순차적으로 실행되는 루틴을 많이 다뤄왔는데 이 것은 싱글 스레드이다. 만약에 하나의 프로그램에서 여러 개의 작업을 동시에 수행하고 싶을 경우에는 멀티 쓰레드(Multi Thread)를 사용하면 된다.


스레드를 어떻게 사용하는지?, 어떻게 동작하는지?

(1) Thread 클래스 상속하는 방법

public class ThreadTest {
    
    public static class MultiThread extends Thread{
        private String name;
        
        public MultiThread(String name){
            System.out.println(getName() + "스레드가 생성되었습니다.");
            this.name = name;
        }
 
        @Override
        public void run() {
            for(int i = 0;i<10;i++){
                System.out.println(getName() + "(" + this.name + ")");
                try {
                    sleep(100);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }
    }
    
    public static void main(String[] args) {
        MultiThread mt1 = new MultiThread("Thread1");
        MultiThread mt2 = new MultiThread("Thread2");
        MultiThread mt3 = new MultiThread("Thread3");
        
        mt1.start();
        mt2.start();
        mt3.start();
    }
}
cs
위의 코드는 Thread 클래스를 extends(상속)한 클래스에서 run()메소드를 정의하고 실행하는 코드입니다.

보통의 싱글 스레드에서 mt1.start(); 코드가 끝나고 mt2.start()코드가 실행되고, 그 다음 mt3.start()가 실행되지만 멀티 스레드에서는 위의 코드들이 동시에 수행됩니다. 그래서 아래의 결과 값처럼 순서에 상관없이 동시에 수행되는 것입니다.

Thread-0스레드가 생성되었습니다.
Thread-1스레드가 생성되었습니다.
Thread-2스레드가 생성되었습니다.
Thread-1(Thread2)
Thread-2(Thread3)
Thread-0(Thread1)
Thread-0(Thread1)
Thread-2(Thread3)
Thread-1(Thread2)
Thread-2(Thread3)
Thread-1(Thread2)
Thread-0(Thread1)
Thread-0(Thread1)
Thread-1(Thread2)
Thread-2(Thread3)
Thread-1(Thread2)
Thread-2(Thread3)
Thread-0(Thread1)
Thread-1(Thread2)
Thread-2(Thread3)
Thread-0(Thread1)
Thread-1(Thread2)
Thread-0(Thread1)
Thread-2(Thread3)
Thread-2(Thread3)
Thread-0(Thread1)
Thread-1(Thread2)
Thread-2(Thread3)
Thread-1(Thread2)
Thread-0(Thread1)
Thread-0(Thread1)
Thread-2(Thread3)
Thread-1(Thread2)
cs


Thread State

스레드의 상태는 다음의 형태로 변화됩니다.

Thread.State 값 

  설명 

NEW

 시작되지 않은 상태

RUNNABLE

 실행 가능 상태

WAITING 

 대기 상태

TIMED_WAITING

 스레드가 특정 시간동안 대기 상태

BLOCKED 

 스레드가 잠겨 있어 풀리기를 기다리는 상태

TERMINATED 

 스레드가 종료된 상태


(2) Runnable Interface를 이용하는 방법

public class ThreadTest {
    
    public static class MultiThread implements Runnable{
        private String name;
        
        public MultiThread(String name){
            System.out.println(name + "스레드가 생성되었습니다.");
            this.name = name;
        }
 
        @Override
        public void run() {
            for(int i = 0;i<10;i++){
                System.out.println(Thread.currentThread().getName() + "(" + this.name + ")");
                try {
                    Thread.sleep(100);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }
    }
    
    public static void main(String[] args) {
        MultiThread mt1 = new MultiThread("Thread1");
        MultiThread mt2 = new MultiThread("Thread2");
        MultiThread mt3 = new MultiThread("Thread3");
        Thread tr1 = new Thread(mt1);
        Thread tr2 = new Thread(mt2);
        Thread tr3 = new Thread(mt3);
        
        tr1.start();
        tr2.start();
        tr3.start();
    }
}
cs

결과값은 동일!!
Runnable Interface를 사용하여 스레드를 구현하는 이유는 무엇일까? 
Java라는 언어의 특성 상 다중 상속이 되지 않는다. 하지만 인터페이스는 다중 상속이 된다. Thread클래스를 상속 받으면 다른 클래스를 상속받지 못하게 된다.
그래서 실제로 쓰레드를 사용할 때는 Runnable Interface를 주로 사용한다.


Thread의 우선순위

public class ThreadTest {
    
    public static class MultiThread implements Runnable{
        private String name;
        
        public MultiThread(String name){
            System.out.println(name + "스레드가 생성되었습니다.");
            this.name = name;
        }
 
        @Override
        public void run() {
            for(int i = 0;i<10;i++){
                System.out.println(Thread.currentThread().getName() + "(우선순위 : " + Thread.currentThread().getPriority() + ")");
            }
        }
    }
    
    public static void main(String[] args) {
        MultiThread mt1 = new MultiThread("Thread1");
        MultiThread mt2 = new MultiThread("Thread2");
        MultiThread mt3 = new MultiThread("Thread3");
        Thread tr1 = new Thread(mt1);
        Thread tr2 = new Thread(mt2);
        Thread tr3 = new Thread(mt3);
        
        tr1.setPriority(Thread.MIN_PRIORITY);
        tr2.setPriority(Thread.NORM_PRIORITY);
        tr3.setPriority(Thread.MAX_PRIORITY);
        
        tr1.start();
        tr2.start();
        tr3.start();
    }
}
cs

쓰레드는 우선 순위에 따라 실행을 우선시 합니다. 물론 출력해보면 꼭 예상되로 되지는 않더라구요.

즉, 우선 순위가 높은 스레드는 우선 순위가 자기보다 낮은 스레드보다 더 많이 실행되는 것입니다.

만약 동일한 우선순위의 스레드가 둘 이상 존재할 경우 CPU의 할당시간을 분배후 실행합니다. 가장 높은 우선 순위는 10, 

기본 우선 순위는 5, 가장 낮은 우선 순위는 1로 , 보통 스레드의 우선 순위는 5입니다. 스레드의 우선 순위를 변경하고 싶다면

setPriority()메소드를 사용하면 됩니다. 위의 코드가 그 예제입니다. 


Thread의 동기화

public class ThreadTest {
    
    public static class clsNumber{
        int num = 0;
        public void addNum(){
            num++;
        }
        public int getNum(){
            return num;
        }
    }
    
    public static class MultiThread implements Runnable{
        clsNumber number;
        
        public MultiThread(clsNumber cn){
            number = cn;
        }
 
        @Override
        public void run() {
            for(int i = 0;i<10000;i++){
                number.addNum();
            }
        }
    }
    
    public static void main(String[] args) {
        
        clsNumber number = new clsNumber();
        
        MultiThread mt1 = new MultiThread(number);
        MultiThread mt2 = new MultiThread(number);
        MultiThread mt3 = new MultiThread(number);
        Thread tr1 = new Thread(mt1);
        Thread tr2 = new Thread(mt2);
        Thread tr3 = new Thread(mt3);
        
        tr1.start();
        tr2.start();
        tr3.start();
        
        try {
            // join()메소드는 스레드가 끝날 때까지 기다린다.
            tr1.join();
            tr2.join();
            tr3.join();
        } catch (Exception e) {
            e.printStackTrace();
        }
        
        System.out.println(number.getNum());
    }
}
cs

결과는??

15380


결과는 30000이 나와야 되는데 15380이 나옵니다. 물론 매번 값도 다르고요. 이유는 무엇일까요?

동기화가 되지 않기 때문에 수행 도중 실행 권한이 다른 스레드로 넘어가서 제대로 된 결과값을 도출해 낼 수 없게 되는 것입니다. 동기화를 해주어야 합니다. 자바에서는 synchronized키워드를 통해 동기화를 가능하게 해줍니다.


동기화를 해준 코드

다음과 같이 synchronized 키워드를 addNum()메소드에 붙여주면 동기화를 지원해주게 됩니다.

public class ThreadTest {
    
    public static class clsNumber{
        int num = 0;
        public synchronized void addNum(){
            num++;
        }
        public int getNum(){
            return num;
        }
    }
    
    public static class MultiThread implements Runnable{
        clsNumber number;
        
        public MultiThread(clsNumber cn){
            number = cn;
        }
 
        @Override
        public void run() {
            for(int i = 0;i<10000;i++){
                number.addNum();
            }
        }
    }
    
    public static void main(String[] args) {
        
        clsNumber number = new clsNumber();
        
        MultiThread mt1 = new MultiThread(number);
        MultiThread mt2 = new MultiThread(number);
        MultiThread mt3 = new MultiThread(number);
        Thread tr1 = new Thread(mt1);
        Thread tr2 = new Thread(mt2);
        Thread tr3 = new Thread(mt3);
        
        tr1.start();
        tr2.start();
        tr3.start();
        
        try {
            // join()메소드는 스레드가 끝날 때까지 기다린다.
            tr1.join();
            tr2.join();
            tr3.join();
        } catch (Exception e) {
            e.printStackTrace();
        }
        
        System.out.println(number.getNum());
    }
}
cs
결과는??
30000




'JAVA' 카테고리의 다른 글

mutable vs immutable  (0) 2015.11.27
자바 예외 처리  (0) 2015.11.21
GC(Garbage Collection)의 대상은 누구인가?  (0) 2015.11.10
LinkedHashMap, TreeMap, HashMap  (0) 2015.11.07
Comparable 인터페이스에 대한 이해  (0) 2015.11.07
Posted by slender ankles
,

자바 예외 처리

JAVA 2015. 11. 21. 19:40


자바 예외 처리하기



예외 처리가 필요한 이유?

예를 들어 4/0이라는 연산을 컴파일러에서 수행했을 때 ArithmeticException이 발생한다. 

예외 처리를 해주지 않았을 때는 에러가 발생하고 프로그램이 그대로 종료된다. 

우리는 예기치 못하게 예외가 발생하더라도(예를들어, JDBC를 사용한 코드는 정확하더라도, 실제 데이터베이스에 데이터가 없어서 에러를 만들어 낼 수도 있다.) 프로그램이 죽지 않고 이를 처리하게 하기 위해서 예외 처리가 필요한 것이다.

<예외처리가 필요한 이유>

// int c = 4 / 0;        => 예외처리 하지 않아 프로그램 죽음 
int c = 4;
try {
   c = c / 0;
} catch (Exception e) {
   System.out.println(e);    // => 예외처리  catch문이 실행되고 프로그램은 죽지 않는다.
}
cs

예외를 고의로 발생시키는 방법?
예외를 고의로 발생시키는 것이 왜 필요한 것일까? 필요할 때가 있다. 
다소 억지스러운 상황이지만 다음과 같은 경우의 로직이 만들어 질 수 있다.

    public static class compareException extends RuntimeException{
    }
    public static void compareTest(String s1, String s2){
        try {
            if(!s1.equals(s2)){
                throw new compareException();
            }
            System.out.println(s1 + " - " + s2 + "는 같습니다.");
        } catch (Exception e) {
            System.out.println(s1 + " - " + s2 + "는 같지 않습니다.");
        }
    }
    
    public static void main(String[] args) {
        String a = "hello";
        String b = "hell";
        compareTest(a, b);
    }
cs
위의 예는 조금 더 쉬운 예로 교체해야 될 것 같다.

try - catch문에서 정상적으로 실행되기 위해 필요한 로직이 try블록 안에 위치할 것이다.

하지만, 예외가 발생한다면? try문 안의 다음 문장은 수행되지 않아야하며, catch문으로 넘어가줘야 합니다.

이럴 때를 위하여 Throw를 통해 고의적으로 예외를 발생시키는 것이 필요합니다. 





'JAVA' 카테고리의 다른 글

mutable vs immutable  (0) 2015.11.27
자바 스레드 프로그래밍  (0) 2015.11.23
GC(Garbage Collection)의 대상은 누구인가?  (0) 2015.11.10
LinkedHashMap, TreeMap, HashMap  (0) 2015.11.07
Comparable 인터페이스에 대한 이해  (0) 2015.11.07
Posted by slender ankles
,

최소 비용 스패닝 트리 - kruskal 알고리즘

알고리즘 2015. 11. 20. 13:29

앞써 설명했던 최소 비용 스패닝 트리를 구하는 알고리즘 2번째, 크루스칼 알고리즘이다.

크루스칼 알고리즘 역시 Greedy 알고리즘의 방법으로 구한다. 


크루스칼(Kruskal) 알고리즘

로직은 다음과 같습니다.

1. 비용을 기준으로 간선을 적은 것부터 큰 것 순으로 정렬한다.

2. 적은 비용의 간선부터 하나씩 그린다.(사이클을 만들게 되는 간선은 그리지 않는다)

3. 모든 정점이 선으로 연결될 때까지 2의 과정을 계속한다.



1) 그래프가 주어집니다.


2) 가중치가 낮은 엣지들 순으로 정렬합니다.


3 - 1) 가중치가 낮은 엣지들을 순으로 엣지를 선택해줍니다.




3 - 2) 사이클이 발생하면 사이클 중에 가장 가중치가 높은 선을 선택하지 않고 넘어갑니다.


4) 모든 노드들이 엣지로 연결되면 최소 비용 스패닝 트리가 완성됩니다. 


엣지의 개수는 (노드의 개수 - 1)입니다.




'알고리즘' 카테고리의 다른 글

허프만 코드 알고리즘  (5) 2015.12.04
최소 비용 스패닝 트리 - Prim알고리즘  (0) 2015.11.20
이진탐색(Binary Search)  (0) 2015.10.16
쉘 정렬  (0) 2015.09.26
퀵정렬  (0) 2015.09.26
Posted by slender ankles
,

티스토리툴바