SELECT FOOD_TYPE, REST_ID, REST_NAME, MAX(FAVORITES)
FROM REST_INFO
GROUP BY FOOD_TYPE
ORDER BY FOOD_TYPE DESC;
정답
SELECT FOOD_TYPE, REST_ID, REST_NAME, FAVORITES
FROM REST_INFO
WHERE (FOOD_TYPE, FAVORITES) IN
(SELECT FOOD_TYPE, MAX(FAVORITES)
FROM REST_INFO
GROUP BY FOOD_TYPE)
ORDER BY FOOD_TYPE DESC
public class Audience{
public Bag bag;
->
private Bag bag;
public Bag getBag() {
return bag;
}
->
public Long buy(Ticket ticket){
if( bag.hasInvitation()) {
bag.setTicket(ticket);
return 0L;
} else {
bag.setTicket(ticket);
bag.minusAmount(ticket.getFee());
return ticket.getFee();
}
}
변화점 : 각 객체들이 맡은 책임에 맞게 일을 행하도록 구현되었다.
Theater의 경우를 예로 들었을 때 객체는 다른 객체에게 이 일을 행해달라고 전달했을 뿐이다.
캡슐화와 응집도
객체지향의 핵심은 객체 내부의 상태를 캡슐화하고 객체 간에 오직 공용 인터페이스(메시지)를 통해서만 상호작용하도록 만드는 것
객체가 밀접하게 연관된 작업만을 수행하고 연관성이 없는 작업은 다른 객체에게 위임하는 것이 응집도를 높이는 방법이다.
자신의 데이터를 책임지며 자신의 데이터를 가공하는 것이 객체의 응집도를 높이는 핵심
절차지향과 객체지향
절차적 프로그래밍 Step01에서는 Theater가 절차지향적인 코드였으며, Process역할을 했었다. 이렇게 Step01의 Theater처럼 별도 모듈에 위치시키는 방식
객체지향 프로그래밍 Step02에서는 프로세스가 각 객체 안에서 동작하도록 구성했다. ex)class Audience
책임의 이동(shift of responsibility) 두 방식의 근본적인 차이는 기능을 처리할 때 Theater가 직접 처리를 하는 방식과, Theater가 말을하면 Audience와 TicketSeller가 스스로 처리를 하는 방식으로 구분을 할 수 있다.
책임 집중 : Theater
책임 분산 : buy → Audience, SellTo → TicketSeller
Step03. 추가 개선
TicketOffice
기존 : getTicket, getFee를 통해 티켓 자체를 Office에서 꺼내옴
변경 : sellTicketTo를 통해 기존의 티켓을 꺼내오는 방식 변경
class TicketOffice{
...
public Ticket getTicket(){
...
}
public void plusAmount(){
...
}
...
}
->
class TicketOffice{
...
public void sellTicketTo(Audience audience){
plusAmount(audience.buy(getTicket()));
}
private Ticket getTicket(){
...
}
private void plusAmount(){
...
}
...
}
public TicketOffice getTicketOffice() {
return ticketOffice;
}
->
public class TicketSeller{
public void sellTo(Audience audience){
ticketOffice.sellTicketTo(audience);
}
}
인터페이스에만 의존하게하는 형태로 변경됨
but TicketSeller는 audience를 넘겨주며 서로 의존하게 만듦
트레이드오프
인터페이스에만 의존하는 Audience결합도가 중요한지, audience를 넘겨주며 의존성이 생겨난 것이 더 좋을지 개발자는 트레이드 오프를 해야 할 순간이 온다.
두가지 이슈를 통해 (책에서의)개발팀은 TicketOffice의 자율성을 지켜 의존성 제거를 택했다.
의인화
Theater, Bag, TicketOffice는 실세계에서 자율적인 존재가 아니다. 하지만 객체지향 패러다임에서는 생물과 동일하게 객체로 다뤘다. 이렇게 모든 객체는 능동적이고 자율적인 존재로 바뀌도록 설계하는 원칙을 의인화라고 부른다
자바 7 이전의 버전에서는 병렬의 처리가 어려웠다. 분할을 위한 스레드 할당 → 동기화 추가 → 결과 합치기의 과정을 통해 병렬 처리가 실행되는데, 각 병렬처리를 한 후에 스레드를 합칠 때 동기화를 적절히 이뤄줘야 교착 상태를 피할 수 있었다. 7버전 부터 지원하기 시작한 Fork/Join 프레임워크를 활용하면 해당 문제를 쉽고 효율적으로 해결할 수 있다. 이 Fork/Join 프레임워크를 활용한 스트림 API와 병렬 처리에 대해서 배워보자.
병렬 스트림
각각의 스레드에서 처리할 수 있도록 스트림 요소를 여러 청크로 분할한 스트림
멀티코어 프로세서가 각각의 청크를 처리하도록 한다
Collections.parallelStream() or Arrays.stream().parallel()
Pipeline에있는 parallel 상태에 true가 저장된다.
이후 파이프라인 처리할 때 처리할 때 parallel 체크를 통해 해결한다.
병렬 처리를 고려할 때는 성능 벤치마킹을 하는 것을 권장
성능 최적화
기본형(primitive) 타입의 경우 기본형 특화 스트림 권장 - 오토박싱의 이유
일반적으로 순차적인 처리가 필요한 스트림의 경우 병렬 비용이 더욱 비싸 느릴 가능성이 높음
순차 처리가 필요없는 경우 findAny같은 순서에 상관 없는 쇼트 서킷, unordered 같은 메서드 사용
하나의 요소를 처리하는 데 드는 비용이 비싸다면 고려
스트림 자료구조의 특성을 확인 ex) LinkedList vs ArrayList 일반적으로 좋음
병합 과정의 비용을 생각해야 한다
| 소스 | 분해성 |
| --- | --- |
| ArrayList | Excellent |
| LinkedList | Bad |
| IntStream.range | Excellent |
| Stream.iterate | Bad |
| HashSet | Good |
| TreeSet | Good |
| Stream.generate | iterate보단 낫다 |
parallel처리 관련 이미지
포크/조인 프레임워크
병렬 작업할 때 사용
재귀적으로 큰 작업을 작은 작업으로 분할한 후 서브태스크의 결과를 합쳐서 전체 결과를 만듦
스레드 풀(ForkJoinPool)의 작업자 스레드에 분산 할당하는 ExecutorService
ExecutorService를 왜 언급하는가?
RecursiveTask를 실제로 활용했을 때 해당 추상 클래스의 부모인 ForkJoinTask에서 ForkJoinPool을 활용해서 실제 활용하고있기 때문
RecursiveTask → ForkJoinTask에서 사용하는 ForkJoinPool → ExcutorService
분할 정복(divide-and-conquer) 알고리즘의 병렬화
compute() 메서드 오버라이딩 해서 구현
병렬처리 시 주의점
join 호출은 두 서브태스크가 모두 시작된 다음에 해야한다.
ForkJoinPool의 invoke메서드는 병렬 계산 시작하는 시점에서 한번만 사용
한쪽은 fork() 한쪽은 compute() ⇒ 같은 스레드 재사용 피하기 위함
디버깅이 어렵다 ⇒ 스택이 아닌 다른 스레드 이기 때문
병렬 처리가 무조건 빠르지 않다.
작업 훔치기(work stealing) 특성을 갖고있음
ForkJoin을 활용한 RecursiveTask 예시
import java.util.concurrent.ForkJoinTask;
import java.util.concurrent.RecursiveTask;
import java.util.stream.LongStream;
public class ForkJoinSumCalculator extends RecursiveTask<Long> {
//THRESHOLD 이상의 값 까지만 분해
public static final long THRESHOLD = 10_000;
private final long[] numbers;
private final int start;
private final int end;
public ForkJoinSumCalculator(long[] numbers) {
this(numbers, 0, numbers.length);
}
private ForkJoinSumCalculator(long[] numbers, int start, int end) {
this.numbers = numbers;
this.start = start;
this.end = end;
}
@Override
protected Long compute() {
int length = end - start; //해당 태스크에서 더할 배열의 길이
if (length <= THRESHOLD) {
return computeSequentially();
}
//각 태스크 분리 left, right
ForkJoinSumCalculator leftTask =
new ForkJoinSumCalculator(numbers, start, start + length / 2);
//생성한 태스크 비동기 실행
leftTask.fork();
ForkJoinSumCalculator rightTask =
new ForkJoinSumCalculator(numbers, start + length / 2, end);
//두번째 태스크 동기 실행
Long rightResult = rightTask.compute();
//비동기 실행했던 left의 결과를 읽거나 처리완료 후 읽기까지 대기
Long leftResult = leftTask.join();
return leftResult + rightResult;
}
//가장 작은 단위일 때 작은 단위로 쪼갠 태스크의 결과를 계산
private long computeSequentially() {
long sum = 0;
for (int i = start; i < end; i++) {
sum += numbers[i];
}
return sum;
}
public static long forkJoinSum(long n) {
long[] numbers = LongStream.rangeClosed(1, n).toArray();
ForkJoinTask<Long> task = new ForkJoinSumCalculator(numbers);
return FORK_JOIN_POOL.invoke(task);
}
}
//호출 방법
ForkJoinSumCalculator.forkJoinSum(long n));
Spliterator 인터페이스
구성 요소
booleaen tryAdvance(Consumer<? super T> action)
요소를 하나씩 순차적으로 돌며 요소가 남아있는지 확인
Spliterator trySplit()
일부 요소를 분할해서 새로운 Spliterator 생성
long estimateSize()
탐색해야 할 요소 수 정보 제공(RecursiveTask의 THRESHOLD 역할로 보임)
전형적인 투 포인터 형태로 햄스터의 몸집을 구멍을 막았을 때 구멍의 크기m에 최대한 가까운 수를 찾아 출력하는 문제
구현 방법
탐색 했을 때 최대값을 찾을 max값
누적합을 계산해 줄 count
투 포인터에 활용할 left, right
⇒ while문 안에서 count의 값이 m보다 크면 left의 값을 count에서 뺀 후 left++, count의 값이 m보다 작거나 같으면 right의 값을 count에 더한 후 right++ 이 때 max의 값와 카운트의 값을 비교해 최댓값을 갱신
풀이
import java.io.*;
import java.util.*;
public class p25916 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int[] a = new int[n];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
a[i] = Integer.parseInt(st.nextToken());
}
//8 10
//2 2 2 2 11 2 5 2
//9
int left = 0;
int right = 0;
int max = Integer.MIN_VALUE;
int count = 0;
while (right < n) {
if (count +a[right] <= m) {
count += a[right];
max = Integer.max(max, count);
right++;
}else{
count -= a[left];
left++;
}
}
System.out.println(max);
}
}
1000의 범위이기에 Set만 사용해서 처리해도 풀리는 문제 But 공부하기 위해 이분탐색으로 구현! 각 행을 지울 때 마다 바뀌는 세로문자열에 중복값을 있는지 없는지 찾는 문제
구현 방법
세로 문자열 전체를 크게 저장할 StringBuilder[] 배열
중복체크를 위한 Set자료구조
중복에 걸린 것을 확인하기 위한 boolean값 flag
⇒ center는 행의 수라는 ****점을 확실하게 인지하고 진행한다면 할만할 것 행의 수를 center로 잡고 중복 값이 걸렸다면 행이 잘리기 이전 값도 똑같이 중복이란 점을 생각 →
flag 작동 시 right = center - 1;
flag 미작동 시 중복이 걸리지 않았기 때문에 left = center + 1;
풀이
package Baekjoon.gold;
import java.io.*;
import java.util.*;
//행을 지울때 마다 그 때의 세로문자열들 중에 중복값이 있느냐
public class p2866 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int r = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
char[][] a = new char[r][c];
for (int i = 0; i < r; i++) {
a[i] = br.readLine().toCharArray();
}
StringBuilder[] sb = new StringBuilder[c];
for (int i = 0; i < c; i++) {
sb[i] = new StringBuilder();
}
for (int i = 0; i < c; i++) {
for (int j = 0; j < r; j++) {
sb[i].append(a[j][i]);
}
}
if (r == 2) {
System.out.println(0);
return;
}
int left = 0;
int right = r;
int minValue = Integer.MAX_VALUE;
boolean flag;
//center는 행의 수
while (left <= right) {
flag = false;
int center = (left + right) / 2;
Set<String> set = new HashSet<>();
for (int i = 0; i < c; i++) {
String s = sb[i].substring(center, r);
if (!set.add(s)) {
minValue = center;
flag = true;
}
}
if (flag) {
right = center - 1;
} else {
left = center + 1;
}
}
if (minValue == Integer.MAX_VALUE) {
System.out.println(0);
} else {
System.out.println(minValue - 1);
}
}
}
후기
의외로 이분탐색의 아이디어보다 문제 이해하는데 더 힘들었던 문제… 이분탐색인걸 알고 풀어서 그런 것 같긴 하다. 또 Set만을 사용해도 풀리는 것을 확인했는데 효율이 매우 좋지 않았었음
