모던 자바 인 액션 내용 정리

JAVA/고급 자바|2020. 4. 12. 16:46

 

포킹 

자바 8에서 추가된 스트림 api에서 데이터를 필터링, 추출, 그룹화 등의 기능을 진행할 수 있다. 이러한 동작들을 병렬화 할 수 있어 여러 cpu에서 작업을 분산해서 처리할 수 있다. 이런 작업을 포킹 단계라고 한다.

 

 

함수형 인터페이스

- 하나의 추상메서드를 가지고 있는 함수형 인터페이스지만 상속을 받은 인터페이스는 추상메서드를 하나만 가지고 있다고 하여도 함수형 인터페이스가 아니다.

- 디폴트 메소드가 아무리 많아도 추상 메소드가 하나이면 함수형 인터페이스이다.

- @FunctionalInterfeace 애노테이션을 붙이면 함수형 인터페이스가 아닌 경우 컴파일 에러를 발생 시킬 수 있다.

 

 

람다에서 지역변수를 final로 제약하는 이유 

람다에서 지역변수가 final로 사용되는지 궁금한데 이는 인터페이스 변수는 힙에 저장되고 지역변수는 스택에 저장되는 이유가 대표적이다. 람다에서 지역변수에 바로 접근할 수 있다는 가정하에 람다가 스레드에서 실행된다면 변수가 할당한 스레드가 사라져서 변수 할당이 해제되었는데도 람다를 실행하는 스레드에서는 해당 변수에 접근하려 할 수 있다. 그렇기 때문에 람다 내부에서 사용하는 값은 복사본으로써 그 값은 변경되면 안된다는 제약이 존재한다. (그래서  무조건 final로 제약하는 것)

 

 

predicate에는 여러 and, or, negete등이 사용이 가능하다.

and와 or로 predicate를 연결 할 수 있고 negete로 반대의 값을 가져올수도 있다.

 

List<String> dish = Arrays.asList("banana", "pizza", "chicken");

Predicate<String> isBanana = new Predicate<String>() {
	@Override
	public boolean test(String s) {
    	return s.equals("banana");
	}
};

Predicate<String> isChicken = new Predicate<String>() {
	@Override
	public boolean test(String s) {
    	return s.equals("chicken");
	}
};

Predicate<String> isNotPizza = new Predicate<String>() {
	@Override
	public boolean test(String s) {
    	return !s.equals("pizza");
	}
};

// predicate or
System.out.println(dish.stream().filter(isBanana.or(isChicken)).collect(Collectors.joining(", ")));

// predicate and
System.out.println(dish.stream().filter(isBanana.and(isChicken)).collect(Collectors.joining(", ")));

// predicate negate
System.out.println(dish.stream().filter(isBanana.negate()).collect(Collectors.joining(", ")));

 

 

Map의 문제 FlatMap으로 해결

- 문제상황

["hello", "world"] 두개의 단어에서 알파벳 중복된 걸 빼고 하나의 알파벳 배열로 합쳐 보자. 구하고자 하는 결과물은 다음과 같다. ["H", "e", "l", "o", "W", "r", "d"]

 

- Map으로 진행

List<String> str = Arrays.asList("hello", "world");

str.stream()
    .map(data -> data.split(""))
    .distinct()
    .collect(Collectors.toList());

이렇게 하면 각 문자열에서 문자로 쪼개고 거기서 distinct작업을 한뒤 합쳐서 성공적으로 하나의 list안에 중복된 문자가 없을 것 같지만 실제로는 ["hello"], ["world"]가 노출 된다. 

 

왜냐하면 실제로 동작하는은 다음과 같이 진행되기 때문이다.

hello → ["h","e","l","l","o"] (split하면 문자열 배열로 반환) 
world → ["w", "o", "r", "l", "d"] (split하면 문자열 배열로 반환) 

최종
→ distinct 대상이 string[] 결국 두개가 합쳐져 Stream<String[]>이 된다.

그럼 이를 해결 하기 위해서 map에서 생성된 배열이 dinstinct로 넘어갈 때 각 값을 다른 스트림으로 만든 다음 모든 스트림을 하나의 스트림으로 연결해야 하는데 이를 flatMap으로 해결이 가능하다.

 

List<String> str = Arrays.asList("hello", "world");
        System.out.println(str.stream()
            .map(data -> data.split(""))
            .flatMap(Arrays::stream)
            .distinct()
            .collect(Collectors.toList()));

map으로 반환된 Stream<String[]>에서 각 String[]을 Stream으로 변형한 후 하나의 stream으로 합쳐서 distinct를 진행하면 정상적인 결과가 도출된다.

 

flatmap은 각 요소를 별도의 스트림으로 만든 후 다시 합쳐준다. 또한 flatMap은 스트림을 받아 다른 스트림으로 변경해주는 역할을 한다.

예를 들어 (1, 2, 3) 배열과 (4, 5) 배열이 있을 때 이 두개를 합쳐서 (1, 4), (1, 5), (2, 4), (2, 5), (3, 4), (3,5) 이렇게 묶고 싶으면 다음과 같이 flatMap을 사용하여 두개를 합칠 수 있다.

List<Integer> data1 = Arrays.asList(1, 2, 3);
List<Integer> data2 = Arrays.asList(4, 5);
data1.stream()
	.flatMap(
		data -> data2.stream().map(j -> new int[] {data, j})
	)
	.collect(Collectors.toList());

만약 map(data → data.2stream().map(j → new int[] {data, })로 사용했으면 결국 최종적으로 Stream<Stream<int[]>>가 만들어지는 아쉬운 결과가 나올 수 있다.

 

 

findFirst와 findAny 차이

findFirst와 findAny는 같은 결과를 가져오지만 병렬 스트림에서는 findFirst로 첫 번째 요소를 가져오는게 어렵기 때문에 그런 경우에는 findAny를 사용한다.

 

 

parallel stream과 fork/join

parallel을 사용하여 fork/join 병렬을 진행 할 수 있다. 병렬 스트림은 기본적으로 ForkJoinPool을 사용하는데 이는 프로세스 수 즉 Runtime.getRuntime().availableProcessor()가 반환하는 값에 상응하는 스레드를 갖는다. 이 fork/join의 스레드 수는 조절이 가능하다.

 

 

Optional Serialize

Optional의 경우에 serialize를 구현하지 않았기 때문에 이는 직렬화 될 수 없다.

 

 

옳지 못한 상속 차단

코드 양이 많고 동작이 변경 되기를 원치 않는 클래스의 경우 final로 선언 또는 private 생성자를 지정한다. 이렇게 되어 있는 클래스의 기능을 이용하기 위해서는 델리게이션 즉 멤버 변수로 이용해서 클래스에서 필요한 메서드를 직접 호출하는 메서드를 작성하는 것이 좋다.

 

 

다중 상속 상황에서 동일한 이름의 메소드 우선순위

1. 클래스가 무조건 이긴다.

2. 서브 인터페이스가 이긴다. 예를 들어 B 클래스가 A 클래스를 상속받는다면 B 클래스가 무조건 A 클래스를 이긴다.

3. 이래도 불명확한 경우에는 여러 인터페이스를 상속받은 클래스에서 명시적으로 받고자 하는 곳을 지정할 수 있다.

 

 

CompletableFuture와 리액티브 프로그래밍 컨셉

값이 있을 때는 onNext, 도중에 에러가 발생했을 때는 onError, 값을 다 소진했거나 에러가 발생해서 더 이상 처리할 데이터가 없을 때 onComplete 등 각각의 콜백이 호출 된다. 이런 이벤트는 보통 순서의 개의치 않는다.

 

CompletableFuture 클래스의 join는 Future 인터페이스의 get 메소드와 동일한 의미로써 작업이 끝날 때 까지 기다린다. 다만 join은 어떠한 예외도 발생시키지 않는다는 차이점이 존재한다.

 

publisher는 subscriber가 자신을 구독하는 경우 최초로 onSubscribe를 호출하여 SubScription 객체를 전달한다. 이 Subscription 인터페이스는 publisher에게 이벤트 요청을 알리는 request 메소드가 있고 더 이상 받지 않겠다고 하는 cancel이 존대한다. 

 

publisher는 반드시 Subscription의 request 메소드에 정의된 개수 이하의 요소만 Subscriber에게 전달 할 수 있다. 해당 요청을 받은 publisher는 subscriber에게 onNext를 통해 여러번에 통해 데이터를 전달 할 수 있고 전달된 값에 따라 onComplete, onError를 통해 publisher에게 데이터 전달 성공 유무를 전달 할 수 있다. 이 대화는 publisher가 subscriber에게 전달한 subscription을 통해서 이루어진다.

 

 

 

 

 

책 전체가 조금 재미없게 구성되어 있다. 그래도 정리할 수 있어 좋았다.

댓글()

Java 메모리 구조 및 GC 알고리즘 정리

JAVA/고급 자바|2019. 9. 23. 22:07

자바 메모리 구조는 1.8 이후로 일부분 바뀌었다.

이 부분에 대한 정리를 다시 하고 싶었고 GC 알고리즘에 대한 종류와 상세 내용을 정리하고 싶었다. 그럼 이 두 가지 사항에 대해 가볍게 정리해보자.

Java 메모리 구조

Method Area

프로그램이 실행되는 도중에 아직 사용되지 않은 클래스들의 코드는 new를 통해 클래스의 인스턴스가 생성되면 JVM Method Area에 인스턴스 변수, 메스드 코드, 클래스 변수등을 저장한다. 해당영역은 모든 쓰레드 사이에서 공유되고 static 키워드로 생성된 변수 또한 저장을 Runtime Constant Pool 영역에 저장한다. 실 데이터를 저장하는 것이 아니라 레퍼런스만 저장하며 실제 데이터는 Heap 영역에 저장한다.

 

JVM Language stack

각 스레드들은 생성과 동시에 각자의 stack을 생성하게 되는데 이 영역에 메소드가 실행될 때 사용된 메스드의 데이터들을 저장한다. 그리고 메서드 실행이 끝나면 해당 stack영역은 사라진다.

 

PC Registers

각 스레드별로 PC Registers가 존재하며 JVM 머신이 가장 최근에 실행한 명령어의 주소를 저장한다.

 

Native Method Area

Native Library에 의존하는 native 코드들을 저장하는 곳이다. (JNI)

 

Permenent (Java8 metaspace 대체)

permenent 영역에 로드된 클래스의 메타 정보와 static한 변수들 정보들이 담겨져 있는데 그 중 static 영역과 상수 영역은 heap으로 옮겨졌다.

-XX:MetaspaceSize : JVM이 사용하는 네이티브 메모리 
-XX:MaxMetaspaceSize : metaspace의 최대 메모리 

 

Heap 영역

GC가 발생되는 대표적인 영역이며 new를 통해 인스턴스가 동적으로 생성된 데이터와 배열정보를 저장하는 공간으로 xms, xmx등의 옵션으로 기본 힙사이즈를 설정할 수 있다. 해당 힙사이즈도 모든 쓰레드 사이에서 공유된다.

-Xms : JVM 시작 시 힙 영역 크기
-Xmx : 최대 힙 영역 크기

힙 영역은 GC가 발생되는 방법에 따라 Young, Old영역으로 나뉘게 된다.

1. Young 영역 

Eden

새롭게 할당된 데이터가 쌓이는 곳으로 일정주기 동안 참조가 유지되면 Survivor로 옮겨진다. Survivor로 옮겨지지 못한 데이터는 GC에 의해 청소된다.

Survivor

Eden영역에서 넘어온 데이터가 1 또는 2영역으로 나눠서 저장된다. 참조가 살아있는 경우 주기에 맞춰서 다른 Survivor영역으로 이동하고 그렇지 못한 데이터들은 GC에 의해서 처리된다. 위와 같은 경우를 Minor GC라고 한다. 

-XX: NewRatio      : New영역과 Old 영역의 비율
-XX: NewSize       : New 영역의 크기
-XX: SurvivorRatio : Eden 영역과 Survivor 영역의 비율

 

2. Old 영역

Survivor 영역에서 오래 살아남은 데이터의 경우 Old 영역으로 넘어가게 된다. Old 영역은 이렇게 넘어온 데이터가 많기 때문에 Young크기 보다 더 크게 설계되며 이부분에서 발생된 GC를 Major GC라고 한다.

 

GC 알고리즘

YOUNG, OLD GC가 발생되는 알고리즘 종류에 대해 정리해보자. 우선 GC의 경우 mark > sweep > compaction 작업이 순서대로 동작한다. 우선 GC 대상을 고르는 mark 작업이 선행되고 실제 제거를 수행하는 sweep가 동작한다. 그리고 메모리의 파편화가 된 부분을 채워 나가는 Compaction 작업으로 마무리한다.

Serial GC

위에서 언급한 3가지 작업이 진행되는 간단한 GC 알고리즘이다. 이 GC의 경우 처리하는 쓰레드가 단 하나이기 때문에 처리하는 과정 동안에 발생하는 STW (Stop the world) pause 시간이 길다.

 

Parallel GC

Serial GC에서 동작하는 스레드가 하나였기 때문에 문제가 자주 발생하였는데, 여기에 작업을 진행하는 스레드를 추가하여 병렬로 작업을 진행한 알고리즘 이다.

왼쪽부터 Serial GC, Parallel SerialGC (https://www.oracle.com/technetwork/java/index.html)

CMS GC

기존에 사용되던 GC 알고리즘 보다 STW pause 시간을 줄이기 위해 고안된 방법으로 없애야 하는 데이터를 정확하게 선별하는 작업이 추가로 진행된다. 그만큼 연산작업이 추가되어 CPU같은 리소스 자원 사용이 증가하였다. 최초 GC 판단하는 initial Mark, initial mark때 선정된 객체를 참조 하는 객체의 GC 대상인지 판단하는  Concurrent Mark, 마지막 검증 작업을 하는 Remark작업을 통해 대상을 선정한 후 Concurrent Sweep 작업을 통해 데이터를 지운다. 그리고 기존 Serial GC와의 차이점은 데이터를 sweep한 후 compaction 작업을 자주 진행하지 않는다. 파편화된 메모리를 자주 매꾸면 그만큼 오버헤드가 많이 발생할 수 있기 때문에 심각한 파편화가 발생했을 때만 매꾼다.

 

G1GC

기존에 GC 알고리즘과는 다른 알고리즘이 나온게 G1GC이다. 기존에는 Eden, Survivor, Old, Permanent영역으로 정확하게 나누어져 있었다. 하지만 G1GC 사용할 경우 heap 영역을 2048개 region 영역으로 쪼개고 이 지역의 크기는 G1HeapRegionSize를 통해 32mb 까지 지정이 가능하다.

또한 새로운 형태의 상태값이 생겼는데 Humongous와 Available/Unused이다. Humongous는 region크기의 50%를 초과하는 큰 데이터를 저장하기 위한 곳이고 Available/Unused는 아직 사용하지 않는 region을 뜻 한다.

각 Region은 Eden, Survivor, Old, Permanent, Humongous, Available/Unused 상태로 지정이 가능하고 데이터가 가장 많이 찬 Region에서 GC가 발생된다. 

G1GC 사용 시 heap 영역 (https://c-guntur.github.io/java-gc/#/6)

 

 

출처

https://www.guru99.com/java-virtual-machine-jvm.html
https://d2.naver.com/helloworld/1329

댓글()

백준 4673번 셀프 넘버

JAVA/알고리즘|2019. 6. 14. 23:45

1 ~ 10000까지의 숫자중에 셀프 넘버가 아닌 데이터를 noSelfNumber에 집어넣고 loop를 순회하면서 selfNumber 여부를 체크하면 된다. 간단한 문제이다.

https://www.acmicpc.net/problem/4673

 

4673번: 셀프 넘버

문제 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, 이 수를 시작해서 n, d(n), d(d(n)), d(d(d(n))), ...과 같은 무한 수열을 만들 수 있다.  예를 들어, 33으로 시작한다면 다음 수는 33 + 3 + 3 = 39이고, 그 다음 수는

www.acmicpc.net

import java.util.ArrayList;
import java.util.List;

public class Main {

    public static void main(String[] args) {
        getNonSelfNumber();
    }

    public static void getNonSelfNumber() {
        List<Integer> nonSelfNumber = new ArrayList<>();

        for (int i = 1; i < 10000; i++) {
            if (!nonSelfNumber.contains(i)) {
                System.out.println(i);
            }

            nonSelfNumber.add(func(i));
        }

    }

    public static int func(int num) {
        int result = num;

        while (num != 0) {
            result += num % 10;
            num /= 10;
        }

        return result;
    }

}

댓글()

DFS로 미로 탈출하기

JAVA/알고리즘|2019. 5. 6. 10:19

최단거리 알고리즘을 공부하면서 예전해 만들었었던 미로 찾기를 다시한번 해봤다.

초년생때 이런문제가 어려웠는데 다시해보니 크게 어렵지는 않은것 같다.

DTO


package dto;

/**
 * Maze 블록의 정보를 보관하는 DTO
 * 
 * @author rokki
 *
 */
public class MazeBlock {
	private int x; // x 좌표
	private int y; // y 좌표
	private int count; // 카운트
	
	public MazeBlock(int x, int y, int count) {
		this.x = x;
		this.y = y;
		this.count = count;
	}

	public int getX() {
		return x;
	}

	public void setX(int x) {
		this.x = x;
	}

	public int getY() {
		return y;
	}

	public void setY(int y) {
		this.y = y;
	}

	public int getCount() {
		return count;
	}

	public void setCount(int count) {
		this.count = count;
	}
}

package dto;

/**
 * 거리와 맵을 저장하고 있는 클래스
 * 
 * @author rokki
 *
 */
public class ResultDto {
	private int resultCount;		// 경로 카운트
	private char[][] result;		// 최단 거리 맵
	
	public ResultDto(int resultCount, char[][] result) {
		this.resultCount = resultCount;
		this.result = result;
	}

	public int getResultCount() {
		return resultCount;
	}

	public void setResultCount(int resultCount) {
		this.resultCount = resultCount;
	}

	public char[][] getResult() {
		return result;
	}

	public void setResult(char[][] result) {
		this.result = result;
	}

}

 

Service


package service;

import java.io.IOException;
import java.nio.ByteBuffer;
import java.nio.channels.FileChannel;
import java.nio.charset.Charset;
import java.nio.file.Paths;
import java.nio.file.StandardOpenOption;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Stream;

import dto.MazeBlock;
import dto.ResultDto;
import serviceI.MazeService;

/**
 * 맵 경로를 찾는 서비스
 *
 * @author wedul
 *
 */
public class MazeServiceImpl implements MazeService {
	
	private char map[][];
	private boolean visited[][];
	private int maxX;
	private int maxY;
	private int currCount;
	private List<ResultDto> result = new ArrayList<>();

	@Override
	public void setMap(String path) throws IOException {
		List<String> mapList = readFile(path);
		this.maxY = mapList.size();
		this.maxX = mapList.get(0).length();
		this.map = new char[maxX][maxY];
		this.visited = new boolean[maxX][maxY];
		
		readFile(path).forEach((data) -> {
			for (int i = 0; i < data.length(); i++) {
				map[i][currCount] = data.charAt(i);
				visited[i][currCount] = false;
			}
			currCount++;
		});
	}

	@Override
	public void printMap() {
		for (int i = 0; i < maxY; i++) {
			for (int j = 0; j < maxX; j++) {
				System.out.print(map[j][i]);
			}
		}
	}
	
	public void printMap(char[][] paramMap) {
		for (int i = 0; i < maxY; i++) {
			for (int j = 0; j < maxX; j++) {
				System.out.print(paramMap[j][i]);
			}
		}
	}

	@Override
	public void findRoute() {
		// dfs 진행 (재귀)
		move(new MazeBlock(0, 1, 0));
	}
	
	/**
	 * map 나가기
	 * 
	 * @param dto
	 */
	private void move(MazeBlock dto) {
		int x = dto.getX();
		int y = dto.getY();
		visited[x][y] = true;
		int count = dto.getCount() + 1;
		
		// 위로 이동
		if (enableGo(new MazeBlock(x , y - 1, count))) {
			move(new MazeBlock(x, y - 1, count));
		}
		
		// 오른쪽으로 이동
		if (enableGo(new MazeBlock(x + 1, y, count))) {
			move(new MazeBlock(x + 1, y, count));
		}
		
		// 아래로 이동
		if (enableGo(new MazeBlock(x, y + 1, count))) {
			move(new MazeBlock(x, y + 1, count));
		}
		
		// 왼쪽으로 이동
		if (enableGo(new MazeBlock(x - 1, y, count))) {
			move(new MazeBlock(x - 1, y, count));
		}
		
		visited[x][y] = false;
	}
	
	/**
	 * 더 나아갈 수 있는지 확인
	 * 
	 * @param x
	 * @param y
	 * @return
	 */
	private boolean enableGo(MazeBlock dto) {
		int x = dto.getX();
		int y = dto.getY();
		
		// 경로 이탈 확인
		if (x < 0 || y < 0 || x > maxX || y > maxY) {
			return false;
		} 
		
		// 종점에 도착할 시 출려
		if (map[x][y] == 'G') {
			setResult(dto.getCount());
		}
		
		return map[x][y] == ' ' && !visited[x][y];
	}
	
	/**
	 * 경로들을 저장
	 * 
	 * @param count
	 */
	private void setResult(int count) {
		// map 복제
		char[][] cloneMap = new char[maxX][maxY];
		
		for (int i = 0 ; i < maxY; i++) {
			for (int j = 0; j < maxX; j++) {
				cloneMap[j][i] = map[j][i];
			}
		}
		
		for (int i = 0 ; i < maxY; i++) {
			for (int j = 0; j < maxX; j++) {
				if (visited[j][i]) {
					cloneMap[j][i] = '*';
				}
			}
		}
		
		result.add(new ResultDto(count, cloneMap));
	}
	
	@Override
	public void printResult() {
		ResultDto shortResult = result.get(0); // 최단경로 객체
		
		for (ResultDto dto : result) {
			System.out.println("GOAL===================" + dto.getResultCount());
			if (shortResult.getResultCount() > dto.getResultCount()) {
				shortResult = dto;
			}
		}
		
		System.out.println();
		System.out.println("short length : " + shortResult.getResultCount());
		printMap(shortResult.getResult());
	}
	
	/**
	 * nio를 사용하여 파일 읽기
	 * 
	 * @throws IOException 
	 */
	private List<String> readFile(String path) throws IOException {
		List<String> datas = new ArrayList<>();
		FileChannel fileChannel = FileChannel.open(Paths.get(path), StandardOpenOption.READ);
		 
        ByteBuffer buffer = ByteBuffer.allocate(1024);

        Charset charset = Charset.defaultCharset();
        String data = "";
 
        int byteCount;
 
        while (true) {
            byteCount = fileChannel.read(buffer);
 
            if (byteCount == -1)
                break;
 
            buffer.flip();
            data += charset.decode(buffer).toString();
            buffer.clear();
        }
 
        fileChannel.close();
        
        Stream<String> stream = Arrays.stream(data.split("\\n"));
        stream.forEach((eachData) -> {
        	datas.add(eachData);
        });
        
        return datas;
	}

}


package serviceI;

import java.io.IOException;

public interface MazeService {
	
	/**
	 * 파일에서 Map을 읽어 출력
	 * 
	 * @param path
	 * @throws IOException
	 */
	void setMap(String path) throws IOException;
	
	/**
	 * 맵 출력
	 */
	void printMap();
	
	/**
	 * 최단거리 찾기
	 */
	void findRoute();
	
	/**
	 * 최단거리 결과 출력
	 */
	void printResult();

}

package main;

public class Main {
	public static void main(String[] args) {
		MazeService service = new MazeServiceImpl();
		try {
			service.setMap("Map/maze.txt");
			service.findRoute();
			service.printResult();
		} catch (Exception e) {
			System.out.println("Fail Find Map");
		}
	}
}

 

결과


GOAL===================33 
GOAL===================31 
GOAL===================41 
GOAL===================39 
GOAL===================27 
GOAL===================25 
GOAL===================35 
GOAL===================33 
GOAL===================25 
GOAL===================23 
GOAL===================25 
GOAL===================23 

short length : 23 
################### 
********                     # 
#######*##### ## ## 
#      ******                 # 
## ##### ###*###### 
 # #  ## # #*# #  # 
   #                ******G 
###################

댓글()

백준 4936 - 섬의개수

JAVA/알고리즘|2018. 10. 6. 01:49

결국은 순회하면서 하는 DFS를 했는데 다음번에는 DP 또는 그래프 문제를 좀 많이 풀어 보고 싶다.


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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
import java.util.*;
 
public class Main {
 
    public static void main(String[] args) {
 
        // 붕어빵 개수
        Scanner sc = new Scanner(System.in);
        List<LandDto> lands = new ArrayList<>();
 
        while (true) {
            int weight = sc.nextInt();
            int height = sc.nextInt();
 
            if (weight == 0 && height == 0) {
                break;
            }
 
            int[][] dataMatrix = new int[height][weight];
            for (int y = 0; y < height; y++) {
                for (int x = 0; x < weight; x++) {
                    dataMatrix[y][x] = sc.nextInt();
                }
            }
 
            lands.add(new LandDto(weight, height, dataMatrix, new boolean[height][weight]));
        }
 
        lands.forEach(land -> {
            calLandCount(land);
        });
 
    }
 
    private static void calLandCount(LandDto landDto) {
        int count = 0;
        for (int y = 0; y < landDto.getHeight(); y++) {
            for (int x = 0; x < landDto.getWeight(); x++) {
                if (!landDto.getVisited()[y][x]) {
                    if (landDto.getDataMatrix()[y][x] == 1) {
                        count++;
                        findLand(x, y, landDto);
                    } else {
                        landDto.getVisited()[y][x] = true;
                    }
                }
            }
        }
        System.out.println(count);
    }
 
    private static void findLand(int x, int y, LandDto landDto) {
        landDto.getVisited()[y][x] = true;
 
        if (checkIsGo(x + 1, y, landDto)) {
            findLand(x + 1, y, landDto);
        }
 
        if (checkIsGo(x + 1, y - 1, landDto)) {
            findLand(x + 1, y - 1, landDto);
        }
 
        if (checkIsGo(x, y - 1, landDto)) {
            findLand(x, y - 1, landDto);
        }
 
        if (checkIsGo(x - 1, y - 1, landDto)) {
            findLand(x - 1, y - 1, landDto);
        }
 
        if (checkIsGo(x - 1, y, landDto)) {
            findLand(x - 1, y, landDto);
        }
 
        if (checkIsGo(x - 1, y + 1, landDto)) {
            findLand(x - 1, y + 1, landDto);
        }
 
        if (checkIsGo(x, y + 1, landDto)) {
            findLand(x, y + 1, landDto);
        }
 
        if (checkIsGo(x + 1, y + 1, landDto)) {
            findLand(x + 1, y + 1, landDto);
        }
 
    }
 
    private static boolean checkIsGo(int x, int y, LandDto landDto) {
        return x >= 0 && y >= 0 && x < landDto.getWeight() && y < landDto.getHeight() && landDto.getDataMatrix()[y][x] == 1 && !landDto.getVisited()[y][x];
    }
 
    static class LandDto {
        private int weight;
        private int height;
 
        private int[][] dataMatrix;
        private boolean[][] visited;
 
        LandDto(int weight, int height, int[][] dataMatrix, boolean[][] visited) {
            this.weight = weight;
            this.height = height;
            this.dataMatrix = dataMatrix;
            this.visited = visited;
        }
 
        public int getWeight() {
            return weight;
        }
 
        public int getHeight() {
            return height;
        }
 
        public int[][] getDataMatrix() {
            return dataMatrix;
        }
 
        public boolean[][] getVisited() {
            return visited;
        }
 
    }
 
}
 
cs

자세한 소스는 git 참고

https://github.com/weduls/algorithm/tree/master/%EA%B7%B8%EB%9E%98%ED%94%84/%EC%84%AC%EC%9D%98%20%EA%B0%9C%EC%88%98

댓글()

백준 알고리즘 2583 - 영역 구하기

JAVA/알고리즘|2018. 10. 6. 01:25

백준 알고리즘 2583번 영역구하기 문제는 DFS를 사용해서 구현해봤다. 문제지를 보자마자 읽기 싫어졌지만 읽어보면 되게 단순하게 많이 접해봤던 문제인거 같다.


https://www.acmicpc.net/problem/2583

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
import java.util.*;
 
public class Main {
 
    private static int M; // 세로
    private static int N; // 가로
    private static List<AreaWeightCntDto> areaWeightCntList = new ArrayList<>(); // 결과를 보관할 리스트
    private static List<Dot> visisted = new ArrayList<>();     // 방문여부를 체크할 리스트
    private static Set<Dot> box = new HashSet<>();             // box의 위치를 부여하는 hashset
 
    public static void main(String[] args) {
 
        Scanner in = new Scanner(System.in);
        M = in.nextInt();
        N = in.nextInt();
        int K = in.nextInt();
 
        // 공간 개수
        int areaCnt = 0;
 
        // 현재 박스의 위치 좌표를 모두 보관
        for (int i = 0; i < K; i++) {
            int x1 = in.nextInt();
            int y1 = in.nextInt();
            int x2 = in.nextInt();
            int y2 = in.nextInt();
 
            for (int tmpX = x1; tmpX < x2; tmpX++) {
                for (int tmpY = y1; tmpY < y2; tmpY++) {
                    box.add(new Dot(tmpX, tmpY));
                }
            }
        }
 
        //
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (enableGo(i, j)) {
                    ++areaCnt;
                    AreaWeightCntDto areaWeightCnt = new AreaWeightCntDto(1);
                    areaWeightCntList.add(areaWeightCnt);
                    visisted.add(new Dot(i, j));
                    getResult(i, j, areaWeightCnt);
                }
            }
        }
 
        // 결과 정렬
        areaWeightCntList.sort((o1, o2) -> {
            return o1.getCnt() > o2.getCnt() ? 1 : -1;
        });
 
        // 개수 출력
        System.out.println(areaCnt);
 
        // 출력
        areaWeightCntList.stream().forEach((e) -> {
            System.out.print(e.getCnt() + " ");
        });
 
    }
 
    /**
     * 공간들의 합을 저장할 Dto
     */
    static class AreaWeightCntDto {
        private int cnt;
 
        public AreaWeightCntDto(int cnt) {
            this.cnt = cnt;
        }
 
        public int getCnt() {
            return cnt;
        }
 
        public void setCnt(int cnt) {
            this.cnt = cnt;
        }
 
        public void increCnt() {
            ++this.cnt;
        }
    }
 
    /**
     * 공간 넓이 구하기
     *
     * @param x
     * @param y
     * @param sum
     */
    private static void getResult(int x, int y, AreaWeightCntDto sum) {
        if (enableGo(x, y + 1)) {
            visisted.add(new Dot(x, y + 1));
            sum.increCnt();
            ;
            getResult(x, y + 1, sum);
        }
 
        if (enableGo(x + 1, y)) {
            visisted.add(new Dot(x + 1, y));
            sum.increCnt();
            getResult(x + 1, y, sum);
        }
 
        if (enableGo(x, y - 1)) {
            visisted.add(new Dot(x, y - 1));
            sum.increCnt();
            getResult(x, y - 1, sum);
        }
 
        if (enableGo(x - 1, y)) {
            visisted.add(new Dot(x - 1, y));
            sum.increCnt();
            getResult(x - 1, y, sum);
        }
    }
 
    /**
     * 해당 좌표가 지나갈 수 있는 좌표인지 여부 확인
     *
     * @param x
     * @param y
     * @return
     */
    private static boolean enableGo(int x, int y) {
        // 경로 이탈 확인
        if (x < 0 || y < 0 || x >= N || y >= M) {
            return false;
        }
 
        // 이미 방문했는지, 박스가 있는 위치인지 여부 확인.
        return (!box.contains(new Dot(x, y)) && !visisted.contains(new Dot(x, y)));
    }
 
    /**
     * 좌표를 담는 Dot 객체
     */
    static class Dot {
 
        public Dot(int x, int y) {
            this.x = x;
            this.y = y;
        }
 
        private int x;
        private int y;
 
        @Override
        public boolean equals(Object obj) {
            if (!(obj instanceof Dot)) {
                return false;
            }
 
            Dot tmp = (Dot) obj;
 
            return Objects.equals(this.x, tmp.x) && Objects.equals(this.y, tmp.y);
        }
 
        @Override
        public int hashCode() {
            return Objects.hash(this.x, this.y);
        }
    }
 
}
cs




댓글()

백준 1929번 소수 구하기 문제

JAVA/알고리즘|2018. 10. 5. 00:25

일반적으로 소수 구하는 방식으로 진행하면 시간이 너무 걸려서 에러가 발생한다. 그래서 고민하던 중에이런 생각이 났다. 모든 수는 자신의 제곱근 이상의 수로 나눠지지 않기 때문에 자신의 제곱근까지 2이상의 자연수로 나눠지는지 판단하면 된다고 생각했다. 

그 결과 된다.
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
52
53
54
55
56
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
 
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
 
        List<Integer> result = new ArrayList<>();
 
        // 순환
        for (int i = n; i <= m; i++) {
            if (isDecimal(i)) {
                result.add(i);
            }
        }
 
        // 결과 출력
        result.stream().forEach((e) -> {
            System.out.println(e);
        });
 
    }
 
    /**
     * 소수 체크
     *
     * @param num
     * @return
     */
    private static boolean isDecimal(int num) {
 
        if (1 == num) {
            return false;
        }
 
        /**
         * 자연수는 자신의 제곱근 이상의 수로 나눠지지 않는다는 조건을 이용해서, 자신의 제곱근 수 까지의 수로 나눠지는지 여부를 판단.
         */
        int sqrpData = new BigDecimal(Math.sqrt(num)).intValue();
 
        for (int i = 2; i <= sqrpData; i++) {
            if (num % i == 0) {
                return false;
            }
        }
 
        return true;
    }
 
}
cs


댓글()

[공유] 자바 유료화 관련 글 공유

JAVA/고급 자바|2018. 10. 4. 01:01

자바 유료화 관련해서 궁금해서 알아보던중 좋은 글을 작성해주신 분들이 있어서 공유합니다.

결론적으로 개인 개발환경에서 Oracle JDK를 사용하는건 상관없고 솔루션같이 상업적으로 사용 되는 부분에서는 OpenJDK를 사용하면 된다는 건가...

아직도 잘 모르겠다. 시간이 지나면 답이 나오겠지.



댓글()