인접리스트를 이용해 구현한 방향성 그래프



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Scanner;
 
public class DirectedAdList {
    
    /*
     * 방향성이 있는 그래프를 인접 리스트로 구현
     */
    
    static int nV; //총 vertex 개수
    static int nE; //총 edge 개수
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        nV = scan.nextInt();
        nE = scan.nextInt();
        ArrayList<ArrayList<Integer>> adList = new <ArrayList<Integer>> ArrayList();
        
        for(int i=0;i<nV;i++) adList.add(new<Integer> ArrayList());
        //adList에 담을 리스트(각 vertex마다 인접한 vertext를 표현한 리스트)
        
        for(int i=0;i<nE;i++) {
            int vertex1, vertex2;
            vertex1 = scan.nextInt();
            vertex2 = scan.nextInt();
            
            adList.get(vertex1).add(vertex2);
        }
        
        
        //인접리스트 출력
        for(int i=0;i<nV;i++) {
            Iterator<Integer> iter = adList.get(i).iterator();
            System.out.print(i);
            if(iter.hasNext()) System.out.print("-");
            while(iter.hasNext()) System.out.print(iter.next() + " ");
            System.out.println("");
        }
    }
}
cs



인접리스트를 이용해 구현한 비방향성 그래프


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public class UndirectedAdList {
    /*
     * 비방향 그래프를 인접리스트를 통해 구현
     * 비항향 그래프를 구현하기 위해 방향성 그래프로 변환하여 구현
     * 그렇기에 edge정보를 담기위한 공간이 방향성 그래프에비해 많이듬(2배)
     * 정점과 간선의 개수가 증가하면 증가할수록 공간이 많이 필요하다.
     * 이를 해결하기 위해 인접행렬이 나옴
     */
    
    
    static int nV; //총 vertex 개수
    static int nE; //총 edge 개수
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        nV = scan.nextInt();
        nE = scan.nextInt();
        ArrayList<ArrayList<Integer>> adList = new <ArrayList<Integer>> ArrayList();
        
        for(int i=0;i<nV;i++) adList.add(new<Integer> ArrayList());
        //adList에 담을 리스트(각 vertex마다 인접한 vertext를 표현한 리스트)
        
        for(int i=0;i<nE;i++) {
            int vertex1, vertex2;
            vertex1 = scan.nextInt();
            vertex2 = scan.nextInt();
            
            adList.get(vertex1).add(vertex2);//비방향 그래프이기 때문에 번갈아서 구현
            adList.get(vertex2).add(vertex1);//비방향 그래프를 방향성그래프로 변환하여 구현하기에
                                             //번갈아서 edge를 구현해야한다.
        }
        
        
        //인접리스트 출력
        for(int i=0;i<nV;i++) {
            Iterator<Integer> iter = adList.get(i).iterator();
            System.out.print(i);
            if(iter.hasNext()) System.out.print("-");
            while(iter.hasNext()) System.out.print(iter.next() + " ");
            System.out.println("");
        }
    }
}
cs



인접행렬를 이용해 구현한 방향성 그래프


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import java.util.Scanner;
 
public class DirectedAdMatrix {
    
    /*
     * 인접행렬을 이용해 구현한 방향성 그래프
     */
    
    static int nV; //총 vertex 수
    static int nE; //총 edge 수
    static int[][] adMatrix;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        nV = scan.nextInt();
        nE = scan.nextInt();
        
        adMatrix = new int[nV][nV];
        
        for(int i=0;i<nE;i++) {
            int vertex1, vertex2;
            vertex1 = scan.nextInt();
            vertex2 = scan.nextInt();
            adMatrix[vertex2][vertex1] = 1;
        }
        
    
        for(int i=0;i<nV;i++) {
            System.out.print(i + "-" );
            for(int j=0;j<nV;j++) {
                System.out.print(adMatrix[j][i]+ " ");
            }
            System.out.println();
        }
    }    
}
cs



인접행렬를 이용해 구현한 방향성 그래프


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
public class UndirectedADMatrix {
    
    /*
     * 인접행렬을 이용해 구현한 비방향성 그래프
     */
    
    static int nV; //총 vertex 수
    static int nE; //총 edge 수
    static int[][] adMatrix;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        nV = scan.nextInt();
        nE = scan.nextInt();
        
        adMatrix = new int[nV][nV];
        
        for(int i=0;i<nE;i++) {
            int vertex1, vertex2;
            vertex1 = scan.nextInt();
            vertex2 = scan.nextInt();
            adMatrix[vertex2][vertex1] = 1; //비방향성이기에 같이 표현
            adMatrix[vertex1][vertex2] = 1;
        }
        
    
        for(int i=0;i<nV;i++) {
            System.out.print(i + "-" );
            for(int j=0;j<nV;j++) {
                System.out.print(adMatrix[j][i]+ " ");
            }
            System.out.println();
        }
    }
    
    /*
     * 공간 복잡도가 vertex의 수 * vertex의 수
     * 공간이 항상 미리 정해지기에 edge가 vertex에 비해 적을 경우
     * 공간 낭비가 일어난다.
     * 
     * 그래프가 드문드문이면 인접리스트 E<V*V
     * 촘촘하면 인접행렬 (행렬은 1비트만 사용)
     * 
     * 간선을 찾는데 걸리는 시간
     * 인접행렬 : 1
     * 인접리스트 : V
     * 
     * 모든 간선을 찾거나 방문하는데 걸리는 시간
     * 인접행렬 : V*V
     * 인접리스트 : V+E
     */
}
cs


'자료구조' 카테고리의 다른 글

[Map] HashMap  (0) 2017.03.10
[Set]HashSet의 특징  (1) 2017.03.09
[그래프]넓이 우선 탐색(BFS)  (0) 2017.03.07
ArrayList와 LinkedList  (0) 2017.01.02
Array 배열 for Java  (0) 2016.12.23

클래스 멤버와 로컬변수 사용


클래스 멤버 사용


람다식 실행 블록은 클래스의 멤버인 필드와 메소드를 제약없이 사용가능

하지만 주의할 것은 this 키워드!!

일반적인 익명 객체 내부에서는 this는 익명 객체의 참조이지만

람다식에서는 실행한 객체의 참조임


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public interface MyFunctionInterface {
    public void method();
}
 
 
public class UsingThis {
    public int outterField = 0;
    
    class Inner {
        int innerField = 10;
        
        void method() {
            MyFunctionInterface fi = () -> {
                //outterField를 참조하기 위한 방법
                System.out.println("outerField : " + outterField);
                System.out.println("outerField : " + UsingThis.this.outterField);
                
                //innerField를 참조하기 위한 방법
                System.out.println("innerField : " + innerField);
                System.out.println("innerField : " + this.innerField);
            };
            fi.method();
        }
    }
}
 
 
public class UsingThisExample {
    public static void main(String[] args) {
        UsingThis usingThis = new UsingThis();
        UsingThis.Inner inner = usingThis.new Inner();
        inner.method();
    }
}
cs



로컬변수 사용


로컬변수는 제한 없이 사용가능

그러나 사용 변수는 final 특성을 가지게 되어 변경 불가능하게 된다.

'Java' 카테고리의 다른 글

[Collection] 동기화된 컬렉션  (0) 2017.03.10
[람다식]메소드와 생성자 참조  (0) 2017.03.08
[람다식] 타켓타입과 함수적 인터페이스  (0) 2017.02.24
[람다식] 람다식 기본  (0) 2017.02.24
[제너릭]제너릭 타입의 상속  (0) 2017.02.17

타켓타입과 함수적 인터페이스


자바는 메소드를 단독으로 선언할 수 없고 클래스의 구성 멤버로 선언된다.

그렇기에 람다식은 단순히 메소드를 생성하는 것이 아니라 이 메소드를 가지고 있는 객체를 생성하는 것!!


람다식이 생성하는 객체는 인터페이스의 익명 구현 객체

인터페이스를 구현하는 것이기 때문에 람다식은 인터페이스의 종류에 따라 작성방법이 달라진다.

람다식이 대입될 인터페이스가 람다식의 타겟 타입


함수적 인터페이스


람다식은 하나의 메소드를 정의하기 때문에 두 개 이상의 추상 메소드가 선언된 인터페이스는

람다식의 타겟 타입이 될 수 없다.


하나의 추상 메소드가 선언된 인터페이스만이 람다식의 타겟 타입이 될 수 있고,

이러한 인터페이스를 함수적 인터페이스라고 부름


@FunctionalInterface

함수적 인터페이스를 작성할 때 두개 이상의 추상 메소드가 선언되지 않도록 컴파일러가 체크해주는 기능으로

인터페이스 선언시 @FunctionalInterface 어노테이션을 붙이면 됨


1
2
3
4
5
@FuntionalInterface
public interface MyFunInterface {
    public void method();
    public void method2(); //컴파일 오류
}
cs



매개 변수와 리턴갑이 없는 람다식


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
@FunctionalInterface
public interface MyFuntionalInterface {
    public void method();
}
//함수적 인터페이스
//이 인터페이스의 추상메서드는 매개변수와 리턴값이 없기 때문에
//이 인터페이스를 타겟 타입으로 갖는 람다식은 매겨변수와 리턴값이 없어야 함 
 
 
public class MyFuntionalInterfaceExample {
    public static void main(String[] args) {
        MyFuntionalInterface fi;
        
        fi = () -> {
            String str = "method call_1";
            System.out.println(str);
        };
        fi.method();
        
        fi = () -> System.out.println("method call_2");
        fi.method();    
    }
}
cs




매개 변수와 리턴값이 있는 람다식


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
@FunctionalInterface
public interface MyFuntionalInterface2 {
    public int method(int x, int y);
}
 
//타겟타입이 될 인터페이스
//추상메서드의 리턴값은 int, 매개변수는 두개
//이 인터페이스를 타겟 타입으로 갖는 람다식은
//리턴값 int를 가져야하며 매개변수가 두개여야 한다.
 
public class MyFuntionalInterfaceExample2 {
    public static void main(String[] args) {
        MyFuntionalInterface2 fi;
        
        fi = (x, y) -> {
            int result = x + y;
            return x + y;
        };
        System.out.println(fi.method(2, 3));
        
        fi = (x, y) -> x + y; 
        System.out.println(fi.method(2, 3));
    }
}
 
cs





표준 API 함수적 인터페이스 종류


*자바 8부터 자주 사용되는 함수적 인터페이스를 java.util.funtion에서 제공하고 있음

'Java' 카테고리의 다른 글

[람다식]메소드와 생성자 참조  (0) 2017.03.08
[람다식] 클래스 멤버와 로컬변수의 사용  (0) 2017.02.24
[람다식] 람다식 기본  (0) 2017.02.24
[제너릭]제너릭 타입의 상속  (0) 2017.02.17
[제너릭]와일드카드 타입  (0) 2017.02.17

람다식



람다식이란? 



람다식 등장 배경


람다식은 함수적 프로그래밍을 위해 자바8부터 지원하기 시작


함수적 프로그래밍이 부각되는 이유는 병렬처리와 이벤트 지향 프로그래밍에 적합하기 때문이다.



람다식이란?


람다식은 익명함수를 생성하기 위한 식으로 객체 지향 언어보다는 함수 지향 언어에 가깝다.

람다식을 사용하면 코드가 간결해지고, 컬랙션의 요소를 필터링하거나 매핑해서 원하는 결과를 쉽게 집계 가능



람다식의 형태


매개변수를 가진 코드 블록 --> 런타임 시에는 익명 구현 객체를 생성


1
2
3
4
5
6
7
8
9
Runnable runnable = () -> { ... };
//람다식
 
 
Runnable runnable = new Runnalble() {
    public void run() { ... }
};
// 익명 구현 객체
// 람다식이 런타임시에는 익명 구현 객체로 생성
cs

 



람다식 기본 문법


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
(int a) -> { System.out.println(a); }
//기본 람다식
 
(a) -> { System.out.println(a); }
//매개변수 타입은 런타임시 대입되는 값에 따라 자동으로 인식이 가능
//그렇기에 람다식에서는 매개변수 타입을 일반적으로 언급안함
 
a -> System.out.println(a);
//하나의 매개변수만 있다면 괄호 생략가능
//마찬가디로 하나의 실행문만 있다면 중괄호 생략가능
 
(x, y) -> { return x + y; };
(x, y) -> x + y
//중괄호에 리턴문만 있다면 return을 사용하지 않는게 정석 
cs



'Java' 카테고리의 다른 글

[람다식] 클래스 멤버와 로컬변수의 사용  (0) 2017.02.24
[람다식] 타켓타입과 함수적 인터페이스  (0) 2017.02.24
[제너릭]제너릭 타입의 상속  (0) 2017.02.17
[제너릭]와일드카드 타입  (0) 2017.02.17
[제너릭]제너릭 메소드  (0) 2017.02.16

제너릭 타입도 다른 타입과 마찬가지로 부모클래스가 될 수 있다.


특징

자식 제너릭타입에 타입 파라미터를 추가 가능!



Product라는 제너릭타입이 있다.


1
2
3
public class Product<T, M> {
    //생략
}
cs



Product를 상속받은 ChildProduct는 추가로 타입파라미터를 가질수 있다.

1
2
3
4
public class ChildProduct<T, M, C> extends Product<T, M> {
            //제너릭 타입을 상속받을 때 자식은 추가 타입 파라미터를 가질수 있다.
    //생략..
}
cs


'Java' 카테고리의 다른 글

[람다식] 타켓타입과 함수적 인터페이스  (0) 2017.02.24
[람다식] 람다식 기본  (0) 2017.02.24
[제너릭]와일드카드 타입  (0) 2017.02.17
[제너릭]제너릭 메소드  (0) 2017.02.16
[제너릭] 제너릭과 비제너릭 비교  (0) 2017.02.15

?를 보통 와일드카드라고 부른다.


제너릭타입에서는 구체적인 타입을 명시하는 대신 와일드카드를 이용할 수 있다.


제너릭 타입<?> : Unbounded WildCards  

제너릭 타입<? extends 상위클래스> : Upper Bounded WildCards - 상위타입이나 하위타입만

제너릭 타입<? super 하위클래스> : Lower Bounded WildCards - 하위타입이나 상위타입만


수강생을 예를 들어서 살펴보면

수강생들은 다음과 같은 상속관계를 가지고 있다. 



코드를 통해 와이드카드 타입 매개변수를 살펴보자.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.util.Arrays;
 
public class WildCardExample {
    public static void registerCourse(Course<?> course) { 
                                    //모든 수강생이 들을수 있는 과정
        System.out.println(course.getName() + "수강생: " + Arrays.toString(course.getStudents()));
    }
 
    public static void registerCourseStudents(Course<? extends Student> course) { 
                                                //학생들만 들을 수 있는 과정(Student, HighStudent)
        System.out.println(course.getName() + "수강생: " + Arrays.toString(course.getStudents()));
    }
    
    public static void registerCourseWorker(Course<? super Worker> course) { 
                                            //직장인과 일반인 들을 수 있는 과정(Worker, Person)
        System.out.println(course.getName() + "수강생: " + Arrays.toString(course.getStudents()));
    }
}
cs


'Java' 카테고리의 다른 글

[람다식] 람다식 기본  (0) 2017.02.24
[제너릭]제너릭 타입의 상속  (0) 2017.02.17
[제너릭]제너릭 메소드  (0) 2017.02.16
[제너릭] 제너릭과 비제너릭 비교  (0) 2017.02.15
Thread 상속으로 thread 생성  (0) 2017.01.27

제너릭 메소드


제너릭 메소드란?


매개타입과 리턴타입으로 타입 파리미터를 갖는 메소드



제너릭 메소드 호출 방법


이 제너릭 메소드를 호출하는 방법은 구체적 타입을 명시적으로 지정하는 방법과

컴파일러과 매개값을 보고 구체적인 타입을 추정하게 하는 방법이 있다.


이 방법들을 실제 코드를 통해 살펴보자.



제너릭 메서드 구현


1
2
3
4
5
6
7
8
public class Util {
    public static <T> Box<T> boxing(T t) {  //제너릭 메소드는 <T> 매개변수 타입과
                                            //Box<T> 리턴타입으로 타입 파라미터를 갖는 메서드
        Box<T> box = new Box<T>();
        box.set(t);
        return box;
    }
}
cs



제너릭 메서드 호출


1
2
3
4
5
6
7
8
9
public class BoxingMethodExample {
    public static void main(String[] args) {
        Box<Integer> box1 = Util.<Integer>boxing(100); //구체적 타입을 명시하여 호출
        int intValue = box1.get();
        
        Box<String> box2 = Util.boxing("북스터디"); //컴파일러가 추정하게 하여 호출
        String name = box2.get();
    }
}
cs


'Java' 카테고리의 다른 글

[제너릭]제너릭 타입의 상속  (0) 2017.02.17
[제너릭]와일드카드 타입  (0) 2017.02.17
[제너릭] 제너릭과 비제너릭 비교  (0) 2017.02.15
Thread 상속으로 thread 생성  (0) 2017.01.27
Runnable을 이용한 Thread 생성 방법들  (0) 2017.01.25

제너릭 사용 시 장점


1. 컴파일시 강한 타입체크

2. 타입변환을 제거



장점을 제너릭을 사용하지 않을 때와 제너릭을 사용했을 때

코드가 어떻게 달라지는지 직접 보면서 살펴보자.



제너릭을 사용하지 않고 클래스 정의


1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
public class NoGenericBox {
    
    /*
     * 제너릭을 사용하지 않은 클래스
     * Object는 최상위 클래스로 어떤 타입이라도 담을 수 있다.
     * 하지만 다른 타입의 변수에 담을려면 타입변환이 필요하다.
     */
    
    private Object object;
    public void set(Object object) { this.object = object; }
    public Object get() { return object; }
}
 
cs



제너릭을 사용하지 않은 객체에 String을 넣고 빼보기


1
2
3
4
5
6
7
8
9
10
11
12
public class NoGenericExample {
    public static void main(String[] args) {
        NoGenericBox box = new NoGenericBox();
        
        box.set("배"); 
        //object에 '배'가 담김 --> Object타입
        
        String fruit = (String)box.get(); 
        //'배'를 String으로 형변환이 필요
    }
}
 
cs



제너릭을 사용한 클래스 정의


1
2
3
4
5
6
7
8
9
10
11
public class GenericBox<T> {
    
    /*
     * 제너릭을 이용한 클래스 정의
     * 제너릭타입 T를 클래스 생성시 파라미터로 전달하여 형변환이 필요없다.
     */
    
    private T t;
    public T get() { return t; }
    public void set(T t) { this.t = t; }
}
cs




제너릭을 사용한 객체에 String 넣고 빼기


1
2
3
4
5
6
7
8
9
10
11
12
public class GenericBoxExample {
    public static void main(String[] args) {
        GenericBox<String> box1 = new GenericBox<String>();
        //제너릭을 이용한 객체 생성
        box1.set("수박");
        String fruit = box1.get();//제너릭으로 타입을 제한했기데 형변환이 필요없다.
        
        GenericBox<Integer> box2 = new GenericBox<Integer>();
        box2.set(5);
        int count = box2.get();
    }
}
cs


'Java' 카테고리의 다른 글

[제너릭]와일드카드 타입  (0) 2017.02.17
[제너릭]제너릭 메소드  (0) 2017.02.16
Thread 상속으로 thread 생성  (0) 2017.01.27
Runnable을 이용한 Thread 생성 방법들  (0) 2017.01.25
멀티 스레드 개념  (0) 2017.01.25

Thread 클래스를 상속받아 thread 생성


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class CreateThread2 {
    /*
      Thread클래스를 상속받은 하위 클래스를 통한 thread 생성
     */
    
    public static void main(String[] args) {
        //직접 클래스를 정의해 Thread 생성
        Thread thread = new SubThread();
        thread.start();
        
        //익명 클래스로 Thread 생성
        Thread thread2 = new Thread() {
            public void run() {
                System.out.println("Anonymous thread");
            }
        };
        
        thread2.start();
    }
    public static class SubThread extends Thread {
        public void run() {
            //thread 실행시 실행될 부분
            System.out.println("Thread 하위클래스로 생성");
        }
    }
}
cs


'Java' 카테고리의 다른 글

[제너릭]와일드카드 타입  (0) 2017.02.17
[제너릭]제너릭 메소드  (0) 2017.02.16
[제너릭] 제너릭과 비제너릭 비교  (0) 2017.02.15
Runnable을 이용한 Thread 생성 방법들  (0) 2017.01.25
멀티 스레드 개념  (0) 2017.01.25
Thread를 생성하는 방법 중에서도 Thread 클래스로 부터 직접 생성하는 방법


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class CreateThread {
    
    /*
        Thread 클래스로부터 Thread 직접 생성
    */
 
    // 기본적으로 thread를 생성하기 위해서는 Runnable 타입의 인자가 필요
    
 
    //thread 생성 방법1. Runnble 구현 클래스를 통한 thread 생성 
    static class Task implements Runnable {
        public void run() {
            System.out.println("hello thread");
        }
    }
 
    public static void main(String[] args) {
        Task task = new Task();
        Thread thread1 = new Thread(task);
        thread1.start();
        
        //thread 생성방법2. 익명 구현 객체를 통한 thread 생성
        Thread thread2 = new Thread(new Runnable() {
            public void run() {
                System.out.println("thread2 created by Anonymous class");
            }
        });
        thread2.start();
        
        //thread 생성방법3. 람다식을 이용한 thread 생성
        Thread thread3 = new Thread( () -> {
            System.out.println("thread3 created by lambda");
        });
        thread3.start();
    }
}
cs


'Java' 카테고리의 다른 글

[제너릭]와일드카드 타입  (0) 2017.02.17
[제너릭]제너릭 메소드  (0) 2017.02.16
[제너릭] 제너릭과 비제너릭 비교  (0) 2017.02.15
Thread 상속으로 thread 생성  (0) 2017.01.27
멀티 스레드 개념  (0) 2017.01.25

+ Recent posts

티스토리툴바