2021-01-27-TIL

2021-01-27-TIL

DFS와 BFS는 언제 쓰는가

DFS/BFS는 각각 어떤 경우에 유용하게 쓰이는가? 케이스 스터디 해놓기

먼저 기본적인 기준만 적어 둔다. BFS는 시작점에서 가까운 정점부터 차례로 방문하므로, 간선 가중치가 모두 같은 그래프에서 최단 거리(최소 이동 횟수)를 구할 때 쓴다. 미로의 최단 경로, 몇 번 만에 목표 상태에 도달하는지 묻는 문제가 대표적이다. DFS는 한 경로를 끝까지 따라간 뒤 되돌아오므로, 모든 경우를 탐색하는 백트래킹, 연결 요소 개수 세기, 사이클 판별, 위상 정렬처럼 경로 전체나 방문 순서가 중요한 문제에 맞는다. 둘 다 시간 복잡도는 인접 리스트 기준 O(V + E)이고, BFS는 큐, DFS는 스택(또는 재귀)을 쓴다.

---

Enum

Java의 enum은 상수 목록이면서 동시에 클래스다. 그래서 상수마다 필드와 메서드를 가질 수 있고, 생성자로 값을 연결하거나 상수별로 다른 동작을 람다로 넣을 수 있다. 링크된 우아한형제들 글은 이 성질을 이용해 흩어진 상수와 분기문(if/switch)을 enum 안으로 모으는 사례를 다룬다. 값과 그 값에 딸린 계산 로직이 한곳에 있으니 새 상수를 추가할 때 고칠 곳이 줄어들고, 문자열 상수와 달리 컴파일러가 타입을 검사해 준다.

• https://woowabros.github.io/tools/2017/07/10/java-enum-uses.html

---

Factory Pattern

팩토리 패턴은 객체 생성 코드를 사용하는 코드에서 떼어 내는 패턴이다. 클라이언트는 new 구체클래스()를 직접 부르지 않고 팩토리에 생성을 맡기므로, 어떤 구체 클래스를 만들지 바뀌어도 클라이언트 코드는 바뀌지 않는다. GoF의 팩토리 메서드 패턴은 객체를 생성하는 인터페이스는 상위 클래스가 정하고, 어떤 클래스의 인스턴스를 만들지는 서브클래스가 결정하게 한다. 링크된 글의 요약도 같은 내용이다.

• https://woovictory.github.io/2019/02/07/Design-Pattern-Factory-Pattern/#:~:text=%EB%AA%A8%EB%93%A0%20%ED%8C%A9%ED%86%A0%EB%A6%AC%20%ED%8C%A8%ED%84%B4%EC%97%90%EC%84%9C%EB%8A%94%20%EA%B0%9D%EC%B2%B4,%EC%84%9C%EB%B8%8C%20%ED%81%B4%EB%9E%98%EC%8A%A4%EC%97%90%EC%84%9C%20%EA%B2%B0%EC%A0%95%ED%95%9C%EB%8B%A4.

---

알고리즘 스터디 자료

알고리즘 공부용으로 저장한 자료다. 책 링크 두 개와, 알고리즘 스터디 저장소, 『Cracking the Coding Interview』 문제 풀이 저장소, 그리고 Google이 운영하던 팀 단위 프로그래밍 대회인 Hash Code 페이지다. Hash Code는 정답이 하나로 정해진 문제가 아니라 점수를 최대화하는 최적화 문제를 팀이 함께 푸는 형식이라, 일반적인 코딩 테스트와는 다른 감각을 연습할 수 있다.

• https://book.naver.com/bookdb/book_detail.nhn?bid=16406247
• https://github.com/VSFe/Algorithm_Study
• https://github.com/ghojeong/CtCI
• https://book.naver.com/bookdb/book_detail.nhn?bid=12327704
• https://codingcompetitions.withgoogle.com/hashcode

---

CompletableFuture

CompletableFuture는 Java 8에 추가된 비동기 작업 클래스로, Future와 CompletionStage를 함께 구현한다. 기존 Future는 결과를 얻으려면 get()으로 블로킹해야 했고 여러 작업을 조합하기 어려웠다. CompletableFuture는 작업이 끝났을 때 이어서 할 일을 콜백 체인으로 연결한다.

• supplyAsync() / runAsync(): 작업을 비동기로 시작한다. 실행기를 지정하지 않으면 ForkJoinPool.commonPool()에서 실행된다.
• thenApply(): 결과를 변환한다. thenCompose()는 결과로 또 다른 비동기 작업을 이어 붙이고, thenCombine()은 두 작업의 결과를 합친다.
• exceptionally(), handle(): 앞 단계에서 난 예외를 처리한다.

CompletableFuture.supplyAsync(() -> fetchPrice("A"))
        .thenCombine(CompletableFuture.supplyAsync(() -> fetchPrice("B")), Integer::sum)
        .thenAccept(System.out::println);

비동기 이벤트를 처리하되 결과는 들어온 순서대로 내보내야 하는 문제(세 번째 링크)는, 각 작업의 CompletableFuture를 입력 순서대로 보관해 두고 앞의 것이 완료된 뒤에 다음 결과를 내보내는 식으로 풀 수 있다.

• https://codechacha.com/ko/java-completable-future/
• https://www.baeldung.com/java-completablefuture
• https://stackoverflow.com/questions/19138553/processing-asynchronous-events-and-publishing-results-in-order

---

Java Concurrent programming

Concurrent sw는 동시에 여러가지 작업을 할 수 있는 소프트웨어 가령, 글을 쓰면서 다른 동작을 백그라운드로 수행할 수 있다. 인텔리제이에서 타이핑을하면 자동완성을 해주는 것도 마찬가지

스레드의 순서는 보장을 못한다. 코드상에서는 start()가 먼저 나왔지만 실제로 동작은 각자 하기 때문이다.

start()는 스레드를 실행 가능한 상태로 만들 뿐이고, 실제로 언제 CPU를 받아 실행될지는 OS의 스레드 스케줄러가 정한다. 그래서 먼저 start()한 스레드가 먼저 출력한다는 보장이 없다. 순서가 필요하면 join()으로 끝나기를 기다리거나, 위의 CompletableFuture 체인처럼 의존 관계를 코드로 명시해야 한다.

참고한 자료외부 출처 3

외부 출처

• Enum Types - The Java TutorialsOracle Docs
• CompletableFuture (Java SE 8 API)Oracle Docs
• Thread (Java SE 8 API)Oracle Docs