728x90

CompletableFuture 클래스

우선 주요 메서드 먼저 살펴보고 가도록 하자.

public class CompletableFuture<T> implements Future<T>, CompletionStage<T>{
    public static <U> CompletableFuture<U> supplyAsync(Supplier<U> supplier) {
        return asyncSupplyStage(ASYNC_POOL, supplier);
    }

	public static CompletableFuture<Void> runAsync(Runnable runnable) {
        return asyncRunStage(ASYNC_POOL, runnable);
    }
    
    public boolean complete(T value) {
        boolean triggered = completeValue(value);
        postComplete();
        return triggered;
    }
    
    public boolean isCompletedExceptionally() {
        Object r;
        return ((r = result) instanceof AltResult) && r != NIL;
    }
    
    public static CompletableFuture<Void> allOf(CompletableFuture<?>... cfs) {
        return andTree(cfs, 0, cfs.length - 1);
    }
    
    public static CompletableFuture<Object> anyOf(CompletableFuture<?>... cfs) {
        int n; Object r;
        if ((n = cfs.length) <= 1)
            return (n == 0)
                ? new CompletableFuture<Object>()
                : uniCopyStage(cfs[0]);
        for (CompletableFuture<?> cf : cfs)
            if ((r = cf.result) != null)
                return new CompletableFuture<Object>(encodeRelay(r));
        cfs = cfs.clone();
        CompletableFuture<Object> d = new CompletableFuture<>();
        for (CompletableFuture<?> cf : cfs)
            cf.unipush(new AnyOf(d, cf, cfs));
        // If d was completed while we were adding completions, we should
        // clean the stack of any sources that may have had completions
        // pushed on their stack after d was completed.
        if (d.result != null)
            for (int i = 0, len = cfs.length; i < len; i++)
                if (cfs[i].result != null)
                    for (i++; i < len; i++)
                        if (cfs[i].result == null)
                            cfs[i].cleanStack();
        return d;
    }
}

 

 

supplyAsync

 

    public static <U> CompletableFuture<U> supplyAsync(Supplier<U> supplier) {
        return asyncSupplyStage(ASYNC_POOL, supplier);
    }

 

이렇게 구성이 되어 있었다.

 

보면 알 수 있듯이, 파라미터를 받지 않고도 결과를 만들어서 다음 task에 전달해준다.

 

runAsync

 

	public static CompletableFuture<Void> runAsync(Runnable runnable) {
        return asyncRunStage(ASYNC_POOL, runnable);
    }

 

Runnable과 비슷하다.

값을 받지도, 값을 리턴하지도 않고 수행만 하게 된다.

 

complete

 

CompletableFuture가 완료되지 않았다면 주어진 값으로 채운다.

리턴되는 Boolean은 complete에 의해 상태가 바뀌었다면 true, 아니라면 false를 반환한다.

    public boolean complete(T value) {
        boolean triggered = completeValue(value);
        postComplete();
        return triggered;
    }

 

isCompletedExceptionally

 

CompletableFuture가 에러로 인해 중지가 되었는지 Boolean으로 반환하는 메서드이다.

var futureWithException = CompletableFuture.supplyAsync(() -> 1 / 0);

Thread.sleep(1000);

assert futureWithException.isDone();
assert futureWithException.isCompletedExceptionally();

 

이런식의 코드를 작성하여 확인 할 수 있다.

 

allOf

 

여러개의 CompletableFuture를 모아서 하나의 CompletableFuture로 변환할 수 있다.

모든 CompletableFuture가 완료되면 상태가 done으로 변경된다.

반환하는 값은 없기 때문에 각각의 값에 다시 접근하여 get으로 값을 가져와야 한다.

 

allOf를 테스트 해보기 위해 코드를 작성해서 확인해보자.

@Slf4j
public class A {

    @SneakyThrows
    public static void main(String[] args) {

        var startTime = System.currentTimeMillis();

        var firstFuture = waitAndReturn(100, 1);
        var secondFuture = waitAndReturn(500, 2);
        var thirdFuture = waitAndReturn(1000, 3);

        CompletableFuture.allOf(firstFuture, secondFuture, thirdFuture)
                .thenAcceptAsync(v -> {
                    try{
                        log.info("first: {}", firstFuture.get());
                        log.info("second: {}", secondFuture.get());
                        log.info("third: {}", thirdFuture.get());
                    }catch (Exception e){
                        throw new RuntimeException(e);
                    }
                }).join();

        var endTime = System.currentTimeMillis();

        log.info("time: {}", endTime - startTime);
    }

    public static CompletableFuture<Integer> waitAndReturn(int time, int value) {
        return CompletableFuture.supplyAsync(() -> {
            try {
                Thread.sleep(time);
            } catch (InterruptedException e) {
                throw new RuntimeException(e);
            }
            return value;
        });
    }
}

 

해당 코드를 실행하면 다음과 같이 나온다.

 

차례차례 실행이 된 100 + 500 + 1000이 아닌 1000에 가까운 값이 나오는 것을 볼 수 있다.

 

anyOf

 

allOf와는 다르게 가장 먼저 끝난 Future의 값을 제공해준다.

 

방금과 비슷한 코드를 실행해보면

@Slf4j
public class A {

    @SneakyThrows
    public static void main(String[] args) {

        var startTime = System.currentTimeMillis();

        var firstFuture = waitAndReturn(100, 1);
        var secondFuture = waitAndReturn(500, 2);
        var thirdFuture = waitAndReturn(1000, 3);

        CompletableFuture.anyOf(firstFuture, secondFuture, thirdFuture)
                .thenAcceptAsync(v -> {
                    try{
                        log.info("Hi FirstValue");
                        log.info("value: {}", v);
                    }catch (Exception e){
                        throw new RuntimeException(e);
                    }
                }).join();

        var endTime = System.currentTimeMillis();

        log.info("time: {}", endTime - startTime);
    }

    public static CompletableFuture<Integer> waitAndReturn(int time, int value) {
        return CompletableFuture.supplyAsync(() -> {
            try {
                Thread.sleep(time);
            } catch (InterruptedException e) {
                throw new RuntimeException(e);
            }
            return value;
        });
    }
}

 

 

가장 빨리 실행이 되는 Future만 가져오는 것을 볼 수 있다.

 

 

728x90

https://seungkyu-han.tistory.com/111

 

Future 인터페이스

자바에서 비동기 프로그래밍을 하기 위해 알아야 하는 Future 인터페이스에 대해 알아보자. Method reference :: 연산자를 이용해서 함수에 대한 참조를 간결하게 포현한 것이다. package org.example; import j

seungkyu-han.tistory.com

저번 내용을 읽어보면 도움이 될 것이다.

 

CompletionStage

public interface CompletionStage<T> {

    public <U> CompletionStage<U> thenApply(Function<? super T,? extends U> fn);

    public <U> CompletionStage<U> thenApplyAsync(Function<? super T,? extends U> fn);

    public CompletionStage<Void> thenAccept(Consumer<? super T> action);

    public CompletionStage<Void> thenAcceptAsync(Consumer<? super T> action);

    public CompletionStage<Void> thenRun(Runnable action);

    public CompletionStage<Void> thenRunAsync(Runnable action);

    public <U> CompletionStage<U> thenCompose(Function<? super T, ? extends CompletionStage<U>> fn);

    public <U> CompletionStage<U> thenComposeAsync(Function<? super T, ? extends CompletionStage<U>> fn);

    public CompletionStage<T> exceptionally(Function<Throwable, ? extends T> fn);
}

CompletionStage 인터페이스는 이렇게 구성이 되어 있다.

 

차례로 내려가면서 실행하기 때문에 각각 파이프 하나의 단계라고 생각하면 될 것이다.

저번 내용과 다르게, 결과를 직접적으로 가져올 수 없기 때문에 비동기 프로그래밍이 가능하게 된다.

또한 Non-blocking으로 프로그래밍하기 위해서는 별도의 쓰레드가 필요하다.

Completable은 내부적으로 FokJoinPool을 사용한다.

할당된 CPU 코어 - 1 에 해당하는 쓰레드를 관리하는 것이다.

이렇게 다른 쓰레드에서 실행이 되기 때문에 Non-blocking 프로그래밍도 가능하게 해준다.

 

CompletionStage와 함수형 인터페이스

저번에 배웠던 함수형 인터페이스와 관련하여 각각 CompletionStage와 연결된다.

Consumer - accept -> thenAccept(Consumer action) void 반환
Function - apply -> thenApply(Function fn) 다른 타입 반환
Function - compose -> thenCompose(Function fn) Completion의 결과값
Runnable - run -> thenRun(Runnable action) void 반환

 

thenAccept[Async]

  • Consumer를 파라미터로 받는다.
  • 이전 task로부터 값을 받지만, 값을 넘기지는 않는다.
  • 다음 task에게 null이 전달된다.
  • 값을 받아서 action만 하는 경우에 사용한다.
@FunctionalInterface
public interface Consumer<T> {
    void accept(T t);
}

 

해당 Consumer를 파라미터로 받는다.

 

    public CompletionStage<Void> thenAccept(Consumer<? super T> action);
    public CompletionStage<Void> thenAcceptAsync(Consumer<? super T> action);
    public CompletionStage<Void> thenAcceptAsync(Consumer<? super T> action,
                                                 Executor executor);

 

thenAccept도 하나만 있는 것이 아니라, 3개가 존재한다.

일단 [Async]에 대해서만 확인해보자.

 

@Slf4j
public class A {

    //future 종료된 후에 반환
    public static CompletionStage<Integer> finishedStage() throws InterruptedException {
        var future = CompletableFuture.supplyAsync(() -> {
            log.info("supplyAsync");
            return 1;
        });
        Thread.sleep(100);
        return future;
    }

    //future 종료되기 전에 반환
    public static CompletionStage<Integer> runningStage(){
        return CompletableFuture.supplyAsync(() -> {
            try{
                Thread.sleep(1000);
                log.info("I'm Running!");
            } catch (InterruptedException e){
                throw new RuntimeException(e);
            }
            return 1;
        });
    }

    public static void main(String[] args) throws InterruptedException {

        System.out.println("thenAccept");

        log.info("start thenAccept");
        CompletionStage<Integer> acceptStage = finishedStage();
        acceptStage.thenAccept(i -> {
            log.info("{} in thenAccept", i);
        }).thenAccept(i -> {
            log.info("{} in thenAccept2", i);
        });
        log.info("after thenAccept");

        System.out.println("thenAcceptAsync");

        log.info("start thenAcceptAsync");
        CompletionStage<Integer> acceptAsyncStage = finishedStage();
        acceptAsyncStage.thenAcceptAsync(i -> {
            log.info("{} in thenAcceptAsync", i);
        }).thenAcceptAsync(i -> {
            log.info("{} in thenAcceptAsync2", i);
        });
        log.info("after thenAccept");
    }
}

 

해당코드를 통해 알아보겠다.

종료된 Stage를 사용하여 thenAccept, thenAcceptAsync 2개를 확인해보았다.

 

일단 thenAccept는 반환값이 없기 때문에 2부터는 null이 찍히는 것을 볼 수 있다.

 

그리고 이 두개의 차이는 다음과 같다.

thenAccept는 Future가 완료된 상태라면, caller와 같은 쓰레드에서 실행이 된다.

그렇기 때문에 동기적으로 차례대로 시작된 것을 볼 수 있다.

thenAcceptAsync는 그냥 상태에 상관없이, 그냥 남는 쓰레드에서 실행이 된다.

 

해당 코드로 바꾸어 실행해보자.

        System.out.println("thenAccept Running");

        log.info("start thenAccept Running");
        CompletionStage<Integer> acceptRunningStage = runningStage();
        acceptRunningStage.thenAccept(i -> {
            log.info("{} in thenAccept Running", i);
        }).thenAccept(i -> {
            log.info("{} in thenAccept2 Running", i);
        });
        log.info("after thenAccept");

        Thread.sleep(2000);

        System.out.println("thenAcceptAsync");

        log.info("start thenAcceptAsync Running");
        CompletionStage<Integer> acceptAsyncRunningStage = runningStage();
        acceptAsyncRunningStage.thenAcceptAsync(i -> {
            log.info("{} in thenAcceptAsync Running", i);
        }).thenAcceptAsync(i -> {
            log.info("{} in thenAcceptAsync2 Running", i);
        });
        log.info("after thenAccept");

        Thread.sleep(2000);

 

해당 코드를 실행하면 다음과 같은 결과가 나온다.

 

위와는 다르게 Future가 종료되지 않았다면, thenAccept는 callee에서 실행이 되게 된다.

 

이를 통해, Async는 그냥 thread pool에서 가져와서 실행이 되며 Async가 아니면 stage의 상태에 따라 나뉘는 것을 볼 수 있다.

stage가 실행중이라면, 호출한 caller 쓰레드에서 실행이 된다.

stage가 실행중이 아니라면, 호출된 caller 쓰레드에서 실행이 되게 된다.

 

위에서 마지막에 있던 메서드 중에 파라미터가 하나 더 있던 메서드가 있었다.

executor를 넘겨주는 것인데, 해당 action이 실행될 쓰레드를 지정해주는 것이다.

@Slf4j
public class B {

    @SneakyThrows
    public static void main(String[] args) {
        var single = Executors.newSingleThreadExecutor();
        var fixed = Executors.newFixedThreadPool(10);

        log.info("start main");
        CompletionStage<Integer> stage = CompletableFuture.supplyAsync(() -> {
            log.info("supplyAsync");
            return 1;
        });

        stage
                .thenAcceptAsync(i -> {
                    log.info("{} in thenAcceptAsync", i);
                }, fixed).thenAcceptAsync(i -> {
                    log.info("{} in thenAcceptAsync", i);
                }, single);

        log.info("after thenAccept");
        Thread.sleep(2000);

        single.shutdown();
        fixed.shutdown();
    }
}

 

해당 코드를 실행해보면

이렇게 지정된 쓰레드에서 실행이 되는 것을 볼 수 있다.

 

thenApply[Async]

  • Function를 파라미터로 받는다.
  • 이전 task로부터 T 타입의 값을 받아서 가공하고 U 타입의 값을 반환한다.
  • 다음 task에게 반환했던 값이 전달된다.
  • 값을 변형해서 전달해야 하는 경우 유용하다.
@FunctionalInterface
public interface Function<T, R> {
    R apply(T t);
}

 

해당 Function을 파라미터로 받는다.

 

    public <U> CompletionStage<U> thenApply(Function<? super T,? extends U> fn);

    public <U> CompletionStage<U> thenApplyAsync
        (Function<? super T,? extends U> fn);

    public <U> CompletionStage<U> thenApplyAsync
        (Function<? super T,? extends U> fn,
         Executor executor);

 

메서드가 다음과 같이 있다.

 

해당 메서드들을 하면서 확인해보자.

@Slf4j
public class C {
    public static void main(String[] args) throws InterruptedException {
        CompletionStage<Integer> stage = CompletableFuture.supplyAsync(() -> 1);

        stage.thenApplyAsync(value -> {
            var next = value + 1;
            log.info("in thenApplyAsync : {}", next);
            return next;
        }).thenApplyAsync(value -> {
            var next = "result: " + value;
            log.info("in thenApplyAsync2 : {}", next);
            return next;
        }).thenApplyAsync(value -> {
            var next = value.equals("result: 2");
            log.info("in thenApplyAsync3 : {}", next);
            return next;
        }).thenAcceptAsync(value -> {
            log.info("final: {}", value);
        });

        Thread.sleep(2000);
    }
}

 

해당 코드를 실행하면 다음과 같다.

 

thenApply는 다른 타입을 주고 받는 것이 가능한 것을 볼 수 있다.

 

thenCompose[Async]

  • Function를 파라미터로 받는다.
  • 이전 task로부터 T 타입의 값을 받아서 가공하고 U 타입의 CompletionStage를 반환한다.
  • 반환한 CompletionStage가 done 상태가 되면 값을 다음 task에 전달한다.
  • 다른 future를 반환해야 하는 경우 유용하다.
    public <U> CompletionStage<U> thenCompose
        (Function<? super T, ? extends CompletionStage<U>> fn);

    public <U> CompletionStage<U> thenComposeAsync
        (Function<? super T, ? extends CompletionStage<U>> fn);

    public <U> CompletionStage<U> thenComposeAsync
        (Function<? super T, ? extends CompletionStage<U>> fn,
         Executor executor);

 

그냥 Future를 반환하며, 해당 Future가 끝날 때까지 기다렸다가 준다는 것이다.

 

@Slf4j
public class D {

    public static CompletionStage<Integer> addValue(int number, int value){
        return CompletableFuture.supplyAsync(() -> {
            try{
                Thread.sleep(100);
            } catch (InterruptedException e) {
                throw new RuntimeException(e);
            }
            return number + value;
        });
    }

    public static void main(String[] args) throws InterruptedException {
        CompletionStage<Integer> stage = CompletableFuture.supplyAsync(() -> 1);

        stage.thenComposeAsync(value -> {
            var next = addValue(value, 1);
            log.info("in thenComposeAsync: {}", next);
            return next;
        }).thenComposeAsync(value -> {
            var next = CompletableFuture.supplyAsync(() -> {
                try{
                    Thread.sleep(100);
                } catch (InterruptedException e) {
                    throw new RuntimeException(e);
                }
                return "result: " + value;
            });
            log.info("in thenComposeAsync: {}", next);
            return next;
        }).thenAcceptAsync(value -> log.info("{} in then AcceptAsync", value));

        Thread.sleep(2000);
    }
}

 

해당 코드를 실행해보면

 

다음과 같이 출력이 되는데, 마지막에 result: 2로 Future가 완료된 후의 값을 가져온 것을 볼 수 있다.

 

thenRun[Async]

  • Runnable을 파라미터로 받는다.
  • 이전 task로부터 값을 받지 않고 값을 반환하지 않는다.
  • 다음 task에게 null이 전달된다.
  • future가 완료되었다는 이벤트를 기록할 때 유용하다.

Runnable 인터페이스이다.

@FunctionalInterface
public interface Runnable {
    public abstract void run();
}

 

받는 것도 주는 것도 없는 것을 볼 수 있다.

 

당연히 큰 역할을 하기보다, 그냥 로그? 이벤트 기록 용으로 사용한다고 한다.

 

@Slf4j
public class E {

    public static void main(String[] args) throws InterruptedException {
        CompletionStage<Integer> stage = CompletableFuture.supplyAsync(() -> 1);

        stage.thenRunAsync(() -> log.info("in thenRunAsync"))
                .thenRunAsync(() -> log.info("in thenRunAsync2"))
                .thenAcceptAsync(value -> log.info("{} in thenAcceptAsync", value));

        Thread.sleep(2000);
    }
}

 

해당 코드를 실행해보면

 

그냥 주지도, 받지도 않는 것을 볼 수 있다.

 

exceptionally

  • Function을 파라미터로 받는다.
  • 이전 task에서 발생한 exception을 받아서 처리하고 값을 반환한다.
  • 다음 task에게 반환된 값을 전달한다.
  • future 파이프에서 발생한 에러를 처리할 때 유용하다.
    public CompletionStage<T> exceptionally
        (Function<Throwable, ? extends T> fn);

 

간단하게 해당 에러를 발생하는 코드를 만들어보면

@Slf4j
public class F {

    public static void main(String[] args) throws InterruptedException {
        CompletionStage<Integer> stage = CompletableFuture.supplyAsync(() -> 1);

        stage.thenApplyAsync(i -> {
            log.info("in then ApplyAsync");
            return i / 0;
        }).exceptionally(e -> {
            log.info("{} in exceptionally", e.getMessage());
            return 0;
        }).thenAcceptAsync(value -> {
            log.info("{} in thenAcceptAsync", value);
        });

        Thread.sleep(2000);
    }
}

 

이러한 결과가 나오는 것을 볼 수 있다.

728x90

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

 

2023번: 신기한 소수

수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수

www.acmicpc.net

뻗어 나가는 느낌으로 풀었다.

다양한 길이를 가져야 하기 때문에 함수를 이용해서 풀 수 있도록 하였다.

 

소수를 판정 할 때, 어차피 계산 한 부분은 안 할 거 같아서 굳이 에라토스테네스의 체를 쓰지는 않았다.

 

함수를 이용해서, 만약 길이가 N이라면 해당 수를 바로 출력하고 아니라면 뒤에 수를 계속 붙여주는 방법으로 풀었다.

어차피 앞 부분은 이미 소수일 테니까, 해당 수가 소수인지만 판별을 진행했다.

 

import sys

N = int(sys.stdin.readline().strip())

prime = [2, 3, 5, 7]


def is_prime(number):
    for i in range(2, int(number ** 0.5) + 1):
        if number % i == 0:
            return False
    return True


def wow_prime(cur_number):
    if len(str(cur_number)) == N:
        print(cur_number)
    else:
        for t in range(1, 10):
            if t % 2 != 0 and is_prime(cur_number * 10 + t):
                wow_prime(cur_number * 10 + t)


for i in prime:
    wow_prime(i)
728x90

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

 

9020번: 골드바흐의 추측

1보다 큰 자연수 중에서  1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아

www.acmicpc.net

소수 문제이기 때문에 당연하게 에라토스테네스의 체를 사용해서 소수를 먼저 구한 후 시작하였다.

 

그 후 입력마다, 해당 수를 반으로 나누고 반으로 나눈 값들에 1부터 더하거나 빼가며 둘 다 소수라면 반복문을 멈추고 출력하도록 했다.

import sys

T = int(sys.stdin.readline().strip())

prime = [True for _ in range(10001)]

for i in range(2, int(10001 ** 0.5) + 1):
    if prime[i]:
        for t in range(i + 1, 10001):
            if t % i == 0:
                prime[t] = False

for _ in range(T):
    n = int(sys.stdin.readline().strip())

    for i in range(n // 2 + 1):
        if prime[n // 2 - i] and prime[n // 2 + i]:
            print(n // 2 - i, n // 2 + i)
            break

'알고리즘 > 정수론' 카테고리의 다른 글

백준 2023 신기한 소수 (Python)  (0) 2024.03.02
백준 4948 베르트랑 공준 (Python)  (0) 2024.03.02
백준 1476 날짜 계산 (Python)  (0) 2024.03.02
728x90

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

 

4948번: 베르트랑 공준

베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼

www.acmicpc.net

 

일단 당연히 소수와 관련된 문제이기에 에라토스테네스의 체를 사용해서 풀었다.

https://namu.wiki/w/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98%20%EC%B2%B4

 

에라토스테네스의 체

Sieve of Eratosthenes 고대 그리스의 수학자 에라토스테네스 가 만들어 낸 소수 를 찾는 방법.

namu.wiki

 

그렇게 풀었어도 시간 문제가 발생했었는데, 입력이 있을 때마다 계산을 해서 출력을 했기 때문이었다.

import sys

while True:
    n = int(sys.stdin.readline().strip())

    if n == 0:
        break

    number = [True for i in range(2 * n + 1)]

    for i in range(2, int((2 * n + 1) ** 0.5) + 1):
        if number[i]:
            for t in range(i + 1, 2 * n + 1):
                if t % i == 0:
                    number[t] = False

    print(number[n + 1: 2 * n + 1].count(True))

 

이렇게 풀었는 데, 시간 문제가 발생해서

입력을 받기 전에 계산을 모두 해두고, 출력만 바로바로 할 수 있도록 하였다,

 

import sys

number = [True for i in range(123456 * 2 + 1)]

for i in range(2, int((2 * 123456 + 1) ** 0.5) + 1):
    if number[i]:
        for t in range(i + 1, 2 * 123456 + 1):
            if t % i == 0:
                number[t] = False


while True:
    n = int(sys.stdin.readline().strip())

    if n == 0:
        break

    print(number[n + 1: 2 * n + 1].count(True))

 

이렇게 풀었더니 시간 문제가 발생하지 않았다.

'알고리즘 > 정수론' 카테고리의 다른 글

백준 2023 신기한 소수 (Python)  (0) 2024.03.02
백준 9020 골드바흐의 추측 (Python)  (0) 2024.03.02
백준 1476 날짜 계산 (Python)  (0) 2024.03.02
728x90

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

 

1476번: 날짜 계산

준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타

www.acmicpc.net

 

별 다른 방법 없다.

그냥 1씩 더해가면서 해당 수를 찾고 출력하는 것이다.

 

import sys

E, S, M = map(int, sys.stdin.readline().split())

cur_year = 1

while True:
    if (cur_year - E) % 15 == 0 and (cur_year - S) % 28 == 0 and (cur_year - M) % 19 == 0:
        break
    cur_year += 1

print(cur_year)
728x90

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

 

2583번: 영역 구하기

첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오

www.acmicpc.net

이 문제는 단순한 그래프 탐색이다.

 

하나 다른 문제들과 다른 점이 있다면, 아마 처음에 직사각형들을 색칠한다는 것?

 

그 후에는 그냥 단순히 넓이를 하나씩 입력해주고 그거를 그대로 출력해주면 끝난다.

from collections import deque
import sys
import heapq

dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]

result_list = list()

M, N, K = map(int, sys.stdin.readline().split())

paper = [[0 for _ in range(M)] for _ in range(N)]

for _ in range(K):
    start_x, start_y, end_x, end_y = map(int, sys.stdin.readline().split())

    for x in range(start_x, end_x):
        for y in range(start_y, end_y):
            paper[x][y] = 1

for x in range(N):
    for y in range(M):
        if paper[x][y] == 0:
            need_visit = deque()

            paper[x][y] = -1
            need_visit.append([x, y])

            result = 0

            while need_visit:

                cur_x, cur_y = need_visit.popleft()

                result += 1

                for i in range(4):
                    next_x, next_y = cur_x + dx[i], cur_y + dy[i]
                    if 0 <= next_x < N and 0 <= next_y < M and paper[next_x][next_y] == 0:
                        paper[next_x][next_y] = -1
                        need_visit.append([next_x, next_y])

            heapq.heappush(result_list, result)

print(len(result_list))

while result_list:
    print(heapq.heappop(result_list), end=' ')
728x90

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

 

1976번: 여행 가자

동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인

www.acmicpc.net

BFS, DFS의 문제는 아니고 find와 union을 사용해서 해결하는 문제이다.

 

find 함수

def find(node):
    if parent[node] != node:
        parent[node] = find(parent[node])
    return parent[node]

해당 그래프에서 최상위 노드를 구해주는 함수이다.

만약 find로 구한 노드가 같으면, 같은 그래프에 속하는 노드인 것이다.

 

union 함수이다.

같은 그래프에 속하지 않는 노드들을 연결해주는 함수이다.

def union(node1, node2):
    root1 = find(node1)
    root2 = find(node2)

    if rank[root1] > rank[root2]:
        parent[root2] = root1
    else:
        parent[root1] = root2
        if rank[root1] == rank[root2]:
            rank[root2] += 1

 

이 함수들을 이용해서 같은 그래프에 속하는 노드끼리 묶어주고, 마지막에 여행을 가려는 노드들이 같은 그래프에 있는 지 확인을 해주면 된다.

import sys

N = int(sys.stdin.readline().strip())
M = int(sys.stdin.readline().strip())

parent = [i for i in range(N)]
rank = [0 for _ in range(N)]

city = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

trip = []

if M > 0:
    trip = list(map(int, sys.stdin.readline().split()))


def find(node):
    if parent[node] != node:
        parent[node] = find(parent[node])
    return parent[node]


def union(node1, node2):
    root1 = find(node1)
    root2 = find(node2)

    if rank[root1] > rank[root2]:
        parent[root2] = root1
    else:
        parent[root1] = root2
        if rank[root1] == rank[root2]:
            rank[root2] += 1


for i in range(N):
    for t in range(i):
        if city[i][t] == 1:
            if find(i) != find(t):
                union(i, t)

standard = find(trip[0] - 1)
flag = True

for i in range(1, M):
    if standard != find(trip[i] - 1):
        flag = False

print('YES' if flag else 'NO')

+ Recent posts