오늘 뭐했지

질문

답변

Q) 프로세스와 쓰레드의 차이점은?

Q) 메모리 영역 중 힙영역과 스택영역의 차의점은?

Q) 쓰레드에서 stack을 분리한 이유는?

Q) 멀티 프로세싱과 멀티 쓰레딩의 장단점 및 차이점은?

Q) 멀티 쓰레드 환경에서의 주의점

Q) CPU 스케쥴링이 발생하는 시점은?

Q) 선점형 스케쥴링과 비선점형 스케쥴링이란?

Q) 동시성이란?

Q) 병렬성이란?

Q) 데드락이란?

Q) 데드락의 4가지 조건은?

Q) 데드락의 해결방법은?

Q) 임계 영역이란?

Q) 운영체제에서의 기아란?

Q) 세마포어와 뮤텍스의 차이점은?

Q) 페이징과 세그먼트의 차이점은?

Q) 내부 단편화와 외부 단편화란?

Q) 페이지 교체 알고리즘이란?

Q) 컨텍스트 스위칭이란?

Q) 동기와 비동기의 차이점은?

질문모음

답변

1) 객체지향(OOP)이란?

2) 객체지향 설계 원칙인 SOLID란?

3) 관점지향(AOP)이란?

4) 추상화란?

5) 추상 클래스와 인터페이스의 특징과 차이를 설명하시오

6) 캡슐화란?

7) Spring Boot의 어노테이션 중 @Getter와 @Setter의 무분별한 사용을 지양해야하는 이유는 무엇인가?

8) 상속이란?

9) IS-A 관계와 HAS-A 관계의 차이점이란 무엇인가?

10) 다형성이란?

11) 자바의 컴파일 과정을 설명하시오

12) JVM (Java Virtual Machine) 의 역할은 무엇인가?

13) JVM의 내부 구조는?

14) 자바의 메모리 영역의 종류와 그 특성은?

15) 가비지 컬렉션을 위해 만들어진 heap 영역의 구조와 가비지 컬렉션의 동작방식은?

16) Java 7의 특징은?

17) Java 8의 특징은?

18) Java 11의 특징은?

19) 많은 기업이 아직 Java 8을 사용하는 이유는?

20) 제네릭이란?

21) String, StringBuilder, StringBuffer의 차이점은?

22) String을 선언할 때 따옴표를 사용하는 것과 new를 사용하는 것의 차이점은?

Oracle을 이용해 프로그래머스 레벨1 문제를 모두 풀며 잊지 않기 위한 내용을 정리합니다. 문제링크는 생략합니다.

1. 상위 N개 행 조회하기

ROWNUM을 이용하는 방법.

SELECT NAME
FROM (SELECT NAME FROM ANIMAL_INS ORDER BY DATETIME)
WHERE ROWNUM <= 1;

2. NULL 처리

NVL : NULL값이 있으면 다른 NULL이 아닌 지정값으로 조회되도록 하는 함수

SELECT warehouse_id, warehouse_name, address, NVL(freezer_yn, 'N')
from food_warehouse
where address like '경기도%';

-- 코드를 입력하세요
SELECT PT_NAME, PT_NO, GEND_CD, AGE, NVL(TLNO, 'NONE')
FROM PATIENT
WHERE AGE <= 12 AND GEND_CD = 'W'
ORDER BY AGE DESC, PT_NAME;

3. 날짜처리

TO_CHAR : 날짜 데이터와 형식을 인자로 넘기면 형식에 맞추어 출력해주는 함수

SELECT COUNT(*) AS USERS
FROM USER_INFO
WHERE TO_CHAR(JOINED, 'YYYY') = '2021' AND AGE >=20 AND AGE <= 29;

-- 코드를 입력하세요
SELECT dr_name, dr_id, mcdp_cd, to_char(hire_ymd, 'yyyy-mm-dd')
from doctor
where mcdp_cd IN ('CS', 'GS')
order by hire_ymd desc, dr_name asc;

4. 기본 JOIN

아직 JOIN에 대해 깊이있게 이해를 못해서 추가적으로 공부가 필요합니다.

SELECT H.FLAVOR
FROM FIRST_HALF H
INNER JOIN ICECREAM_INFO I ON H.FLAVOR = I.FLAVOR
WHERE H.TOTAL_ORDER > 3000 AND I.INGREDIENT_TYPE = 'fruit_based';

SELECT B.TITLE,
       B.BOARD_ID,
       R.REPLY_ID,
       R.WRITER_ID,
       R.CONTENTS,
       TO_CHAR(R.CREATED_DATE, 'YYYY-MM-DD') AS CREATED_DATE
FROM USED_GOODS_BOARD B
INNER JOIN USED_GOODS_REPLY R ON B.BOARD_ID = R.BOARD_ID
WHERE TO_CHAR(B.CREATED_DATE, 'YYYYMM') = '202210'
ORDER BY R.CREATED_DATE, B.TITLE;

5. 평균, 반올림

AVG는 평균을 구해주며

ROUND는 반올림한 값을 줍니다. ROUND의 두번째 인자값에 따라 반올림 위치를 지정할 수 있습니다.

두번째 인자를 적지 않는다면 0으로 인식하며 소수점 첫째짜리에서 반올림한 값을 리턴합니다.

SELECT ROUND(AVG(DAILY_FEE)) AS AVERAGE_FEE
FROM CAR_RENTAL_COMPANY_CAR
WHERE CAR_TYPE = 'SUV';

6. CASE-WHEN-THEN

주어진 테이블의 정보를 통해 새로운 컬럼을 만들고 싶을때 사용하는 것으로 이해했습니다.

조건이 여러개라면 WHEN-THEN-WHEN-THEN...형태로 이어붙이면 되는것 같습니다.

-- 코드를 입력하세요
SELECT HISTORY_ID, CAR_ID, TO_CHAR(START_DATE, 'YYYY-MM-DD') AS START_DATE, TO_CHAR(END_DATE, 'YYYY-MM-DD') AS END_DATE,
CASE WHEN(END_DATE - START_DATE + 1) >= 30 THEN '장기 대여' ELSE '단기 대여' END AS RENT_TYPE
FROM CAR_RENTAL_COMPANY_RENTAL_HISTORY
WHERE TO_CHAR(START_DATE, 'YYYY-MM') = '2022-09'
ORDER BY HISTORY_ID DESC;

옵저버 패턴

​

정의

옵저버 패턴은 객체의 상태 변화를 관찰하는 관찰자 객체들이 관찰하는 객체에 변화가 있을 때마다 변경 정보를 받고 갱신되도록 하는 디자인 패턴입니다.

옵저버 패턴은 1:1혹은 1:N 의존성을 가지는데, 주로 분산 이벤트 처리 시스템에서 많이 사용됩니다.

발행/구독 모델로 알려져 있기도 합니다.

객체 사이의 의존성을 줄이고 유연하게 상호작용하도록

즉, Coupling을 느슨하게 유지하는 것을 도와주는 패턴입니다.

​

이해하기 가장 쉬운 예시는 유튜브 혹은 인스타그램을 생각하면 됩니다.

유튜브에서 내가 구독한 채널이 새로운 영상을 올리면 새 영상 업로드 알림을 받습니다.

나 뿐만아니라 같은 채널을 구독한 다른 모든 구독자들도 알림을 받을것입니다.

​

옵저버 패턴에서 유튜브 채널이 Subject가 되고, 구독자들이 Observer가 됩니다

관찰자(Observer)라고 해서 관찰자 객체들이 Subject를 스스로 관찰하는 것처럼 느껴지지만
직접 관찰한다는 느낌 보다는 Subject의 변화를 통한 정보 갱신을 하기 위해 변경사항을 전달받길 기다리는 수동적인 상태에 더 가깝습니다.

옵저버 패턴 흐름

1. 한개의 주체(Subject)와 여러개의 관찰자(Observer)로 구성되어습니다.

2. Observer 패턴에서는 Subject의 상태가 바뀌면 변경사항을 Obsever들에게 전달합니다.

3. Subject로부터 받은 정보로 Observer의 정보를 바꿀 수 있습니다.

4. Observer들은 Subject의 Collection에서 삭제/추가 될 수 있습니다.

​

​

유튜브 채널이 있고, 영상을 게시했을때 구독자에게 알림을 보내는 상황을 가정하여 코드를 작성해봤습니다.

public interface Observer {
    void update(String title);
}

관찰자/구독자 역할을 하게될 Observer 인터페이스입니다.

public class ObserverImpl implements Observer{
    String name;
    public ObserverImpl(String name){
        this.name = name;
    }
    @Override
    public void update(String title) {
        System.out.println(this.name + "님, [" + title + "] 영상이 게시되었습니다.");
    }
}

Observer를 구현한 클래스입니다.

Subject.java

public interface Subject {
    void registerObserver(Observer o);
    void removeObserver(Observer o);
    void notifyObserver(String title);
}

SubjectImpl.java

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

public class SubjectImpl implements Subject{

    private final List<Observer> observerList;
    public SubjectImpl(){
        observerList = new ArrayList<>();
    }

    // Observer 추가
    @Override
    public void registerObserver(Observer o) {
        observerList.add(o);
    }

    // Observer 삭제
    @Override
    public void removeObserver(Observer o) {
        observerList.remove(o);
    }

    // Observer들에게 이벤트 알림
    @Override
    public void notifyObserver(String title) {
        for (Observer o : observerList)
            o.update(title);
    }
}

public class youtube {
    public static void main(String[] args) {
        // 유튜브 채널 생성
        Subject channel = new SubjectImpl();
        
        // 구독자 생성
        Observer subscriber1 = new ObserverImpl("철수");
        Observer subscriber2 = new ObserverImpl("영희");
        
        // 구독자 등록
        channel.registerObserver(subscriber1);
        channel.registerObserver(subscriber2);
        
        // 영상 업로드 알림
        channel.notifyObserver("웃긴 짤");
        channel.notifyObserver("무서운 짤");
        
        // 영희가 구독 취소
        channel.removeObserver(subscriber2);
        
        // 영상 업로드 알림
        channel.notifyObserver("슬픈 짤");
    }
}

실행 결과는 아래와 같습니다.

영희가 구독을 취소한 이후로는 영희에게 알림이 가지 않습니다.

장점

​

1. 옵저버 패턴을 사용하면 Subject의 상태 변경을 매번 일일히 확인하지 않고도 자동으로 감지가 가능합니다.

2. Subject의 코드를 변경하지 않아도 새 구독자 클래스를 도입이 가능해 OCP를 준수합니다.

3. 런타임 시점에서 Subject와 Observer가 구독 알림 관계를 맺을 수 있습니다.

4. Subject와 Observer의 관계를 느슨하게 유지할 수 있습니다.

​

단점

​

1. 알림의 순서를 제어할 수 없으며, 무작위 순서로 알림을 받게됩니다.

2. 무분별한 사용은 코드의 복잡도가 증가합니다.

3. 옵저버 객체 등록 이후 해지하지 않으면 메모리 누수가 발생할 수 있습니다.

​

출처 및 참고

https://shan0325.tistory.com/33

https://gsbang.tistory.com/entry/Design-Pattern-Observer-Pattern%EC%98%B5%EC%A0%80%EB%B2%84-%ED%8C%A8%ED%84%B4

https://velog.io/@te-ing/%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%EB%94%94%EC%9E%90%EC%9D%B8%ED%8C%A8%ED%84%B4

https://inpa.tistory.com/entry/GOF-%F0%9F%92%A0-%EC%98%B5%EC%A0%80%EB%B2%84Observer-%ED%8C%A8%ED%84%B4-%EC%A0%9C%EB%8C%80%EB%A1%9C-%EB%B0%B0%EC%9B%8C%EB%B3%B4%EC%9E%90

https://xzio.tistory.com/289

https://refactoring.guru/design-patterns/observer

https://ssdragon.tistory.com/144

https://boj.ma/17943/t

${N}$과 ${Q}$, 그리고 ${N-1}$개의 수가 주어집니다.

${N - 1}$개의 수는

${a_0}$ ${\oplus}$ ${a_1}$, ${a_1}$ ${\oplus}$ ${a_2}$, .... , ${a_{n-1}}$  ${\oplus}$ ${a_n}$ 으로, 입력으로 주어진 i번째 숫자는 원본배열의 i번째 수와 i+1번째 수를 xor한 값입니다.

이후 ${Q}$개의 쿼리가 주어지는데, 쿼리의 종류가 두 가지 있습니다.

0 x y 는 x번째 수와 y번째 수를 xor한 값을 출력하는 쿼리이고,

1 x y d는 x번째 수가 d일때, y번째 수를 출력하라는 쿼리입니다.

xor문제에서는 항상 xor의 중요한 특성 두 가지를 떠올리면 풀리는 경우가 많습니다.

${0}$ ${\oplus}$ ${X}$ = ${X}$

${X}$ ${\oplus}$ ${X}$ = ${0}$

이 두가지 xor연산의 특징을 바탕으로 생각을 해봅니다.

0번 쿼리인 x번째 수와 y번째 수를 xor한 값의 결과는

주어진 배열에서

${A_x}$ ${\oplus}$ ${A_{x+1}}$ ${\oplus}$ ${A_{x+1}}$ ${\oplus}$ ${A_{x+2}}$  ${\oplus}$ ${...}$ ${\oplus}$ ${A_{y-2}}$ ${\oplus}$ ${A_{y-1}}$ ${\oplus}$  ${A_{y-1}}$ ${\oplus}$ ${A_y}$ 를 해주면 중간 항이 모두 소거되기 때문에

${A_x}$ ${\oplus}$ ${A_y}$ 와 같습니다.

따라서 입력으로 주어진 배열에서 x번째 수부터 y - 1번째 수까지 xor한 값을 출력해주면 됩니다.

1번 쿼리는

${X}$번째 수가 ${d}$일때 ${Y}$번째 수를 출력하는 것인데, ${A_X}$ ${\oplus}$ ${A_Y}$ ${\oplus}$ ${A_X}$ ${=}$ ${A_Y}$ 이므로

0번 쿼리를 그대로 갖고온 결과에 ${d}$ 를 xor 해주면 됩니다.

당연히 쿼리마다 일일히 xor해주면 시간초과이므로, 누적합 배열을 이용해 전처리 해주면 쿼리마다 ${O(1)}$ 에 값을 구할 수 있습니다.

코드(python)

import sys
input = sys.stdin.readline


n, q = map(int, input().split())
ls = [0] + list(map(int, input().split()))
k = len(ls)
pxor = [0] * (k)
for i in range(1, k):
    pxor[i] = pxor[i- 1] ^ ls[i]
for _ in range(q):
    oper, *a = map(int, input().split())
    if oper:
        x, y, d = a
        print(pxor[y - 1] ^ pxor[x - 1] ^ d)
    else:
        x, y = a
        print(pxor[y - 1] ^ pxor[x - 1])

제가 안까먹으려고 하나의 글에 모두 정리해둡니다.

아래 justicehui님의 splay tree글을 많이 참고하여 작성합니다.(사실상 정리)

https://justicehui.github.io/hard-algorithm/2018/11/12/SplayTree1/

https://justicehui.github.io/hard-algorithm/2018/11/13/SplayTree2/ 

https://justicehui.github.io/hard-algorithm/2019/10/22/SplayTree3/

https://justicehui.github.io/hard-algorithm/2019/10/23/SplayTree4/

Splay Tree?

스플레이 트리는 BBST의 한 종류로 삽입/삭제/검색 모두 amortized O(logN)에 해주는 자료구조이며 다른 BBST에 비해 구현이 쉽다는 특징이 있습니다. 또한 구간 뒤집기 연산도 가능합니다.

스플레이  트리 노드 구조체

struct node {
    node* l;
    node* r;
    node* p;
    int key;
}

왼쪽 자식, 오른쪽 자식, 부모 노드, key값을 갖도록 합니다.

Rotate

rotate 함수를 통해 특정 노드를 자신의 부모 노드와 자리를 바꾸도록 합니다.

위 그림처럼 X노드를 P노드와 자리를 바꾸고 트리의 형태에 따라 옮긴 후 노드간의 관계를 재설정 하도록하는 함수를 만들것입니다.

void rotate(node* x){ // 위로 올릴 노드
    node* p = x -> p; // x의 부모 노드
    node* b = NULL; // b노드
    if(!p) return; // x가 루트라면 리턴
    if (x == p->l){ // x가 p의 왼쪽 자식
        p -> l = b = x -> r; // p의 왼쪽을 b노드로 
        x -> r = p; // x의 오른쪽 자식을 p노드로
    }else{ // x가 p의 오른쪽 자식
        p -> r = b = x -> l; // p의 오른쪽을 b노드로
        x -> l = p; // x의 왼쪽 자식을 p노드로
    }
    // 부모노드 재설정
    x -> p = p -> p; // x의 부모는 p의 부모
    p -> p = x; // p의 부모는 x
    if (b) b -> p = p; // b노드가 존재한다면 b의 부모는 p
    
    // x가 루트노드가 아닐경우
    // p노드가 p노드의 부모노드의 왼쪽이었다면 x를 왼쪽으로, 오른쪽이었다면 오른쪽으로
    (x -> p ? p == x -> p -> l ?  x -> p -> l : x -> p -> r : tree) = x;
}

node* b 는 위 그림에서의 B노드입니다.

Splay

이제 Splay 함수를 구현할것입니다. Splay 함수는 특정 노드를 루트노드까지 올리는 작업을 하게 될것입니다.

함수는 다음과 같은 순서로 진행됩니다.

1. x가 루트라면 종료합니다.

2. x의 부모가 루트라면 rotate(x)를 하고 종료합니다. (Zig step)

3. x의 조부모(부모의 부모)를 g라고 할 때 상황에 따라 나누어집니다.

3- 1. g-p 방향과 p-x 방향이 같다면, rotate(p) -> rotate(x)를 수행합니다. (Zig-Zig step)

3 - 2. 방향이 다르다면, rotate(x)를 두 번 수행합니다. (Zig-Zag step)

이걸 x가 루트가 될 때까지 반복합니다.

zig, zig-zig, zig-zeg 과정은 아래 사진과 같이 진행됩니다.

1. zig step

2. zig-zig step

x와 p가 둘 다 왼쪽 자식이거나 둘 다 오른쪽 자식일 경우

rotate(p) 후에 rotate(x)를 해줍니다.

3. zig-zag step

함수로 구현하면 다음과 같습니다.

void splay(node* x){
    while(x->p){  // x가 루트가 될때까지 반복
        node* p = x -> p;
        node* g = p -> p;
        if (g){
            if ((x == p -> l) == (p == g -> l)) rotate(p); // zig-zig
            else rotate(x); // zig-zag;
        }
        rotate(x);
    }
}

이제 insert, find, delete 함수를 차례차례 보겠습니다.

Insert

삽입 방식은 일반적인 BST와 같고 마지막에 splay를 해서 루트로 올려줍니다.

void insert(int key){
    node* p =tree;
    node** pp; // 넣을 위치
    if(!p){ // 빈 트리인 경우
        node* x = new node;
        tree = x;
        x -> l = x -> r = x -> p = NULL;
        x -> key = key;
        return;
    }
    while(true){ // 삽입할 위치를 찾을때까지 반복
        if (key == p -> key) return; // 중복값이 있을 경우 종료
        if (key < p -> key){ // 현재 노드의 값보다 작을경우
            if (!p -> l){ // 왼쪽이 비어있으면 왼쪽에 삽입
                pp = &p->l;
                break;
            }
            p = p->l; // 비어있지 않으면 왼쪽 자식으로 이동
        }else{ // 현재 노드의 값보다 크다
            if (!p->r){
                pp = &p->r;
                break;
            }
            p = p->r;
        }
    }
    // 위에서 삽입할 위치를 찾음
    node* x = new node;
    *pp = x;
    x -> l = x -> r = NULL;
    x-> p = p;
    x-> key = key;
    // splay
    splay(x);
}

find

find도 또한 비슷하게 진행되며

마지막에 splay를 해주어 다른 연산을 쉽게 해주도록 합니다.

bool find(int key){
    node* p = tree;
    if(!p) return false; // 비어있는 트리
    while(p){
        if (key == p -> key) break; // 찾았다
        if (key < p -> key){ // 찾으려는게 현재 값보다 작음
            if (!p -> l) break; // 왼쪽이 없다 -> 탐색 실패
            p = p -> l; // 왼쪽으로 이동
        }else{ // 찾으려는게 현재 값보다 큼
            if (!p -> r) break; // 오른쪽이 없다 -> 탐색 실패
            p = p -> r; // 오른쪽으로 이동
        }
    }
    splay(p); // 마지막에 탐색한 노드를 루트로 올림
    return key == p->key; // 탐색한 노드의 값이 찾는값이랑 같은지 return
}

Delete

삭제연산입니다.

void del(int key){
    if (!find(key)) return; // 삭제할 값이 없으면 루트로 이동 후 종료
    node* p = tree;
    if (p -> l && p -> r){ // 자식이 두개
        tree = p->l; // 왼쪽 자식이 새로운 루트
        tree->p = NULL;

        // 오른쪽 서브트리를 왼쪽 서브트리 아래에 삽입
        node* x = tree;
        while(x -> r) x = x -> r;
        x -> r = p -> r;
        p -> r -> p = x;
        delete p;
        return;
    }

    if(p->l){ //자식이 왼쪽만 있는 경우
        tree = p->l;
        tree->p = NULL; //왼쪽 자식이 새로운 루트
        delete p; //노드 삭제
        return;
    }
    if(p->r){ //자식이 오른쪽만 있는 경우
        tree = p->r;
        tree->p = NULL; //오른쪽 자식이 새로운 루트
        delete p; //노드 삭제
        return;
    }

    // 노드가 자신 하나인경우
    delete p;
    tree = NULL;
}

K-th element

k번째 원소를 찾는 함수도 구현해봅시다

k번째 원소를 찾으려면 각 노드를 루트로하는 서브트리의 크기를 알아야 합니다.

구조체에 변수 하나를 추가해줍니다.

struct node{
    node* l;
    node* r;
    node* p;
    int key, cnt;
}

cnt변수의 값은 rotate가 될 때마다 계속 바뀔 것입니다.

cnt변수의 갱신을 담당할 update 함수를 만들어 줍니다.

void update(node* x){
    x -> cnt = 1;
    if (x -> l) x->cnt += x->l->cnt;
    if (x -> r) x->cnt += x->r->cnt;
}

rotate 할 때마다 cnt값이 바뀐다고 했으니 rotate의 마지막 부분에 update함수를 추가해주면 됩니다.

void rotate(node* x){ // 위로 올릴 노드
    node* p = x -> p; // x의 부모 노드
    node* b = NULL; // b노드
    if(!p) return; // x가 루트라면 리턴
    if (x == p->l){ // x가 p의 왼쪽 자식
        p -> l = b = x -> r; // p의 왼쪽을 b노드로
        x -> r = p; // x의 오른쪽 자식을 p노드로
    }else{ // x가 p의 오른쪽 자식
        p -> r = b = x -> l; // p의 오른쪽을 b노드로
        x -> l = p; // x의 왼쪽 자식을 p노드로
    }
    // 부모노드 재설정
    x -> p = p -> p; // x의 부모는 p의 부모
    p -> p = x; // p의 부모는 x
    if (b) b -> p = p; // b노드가 존재한다면 b의 부모는 p

    // x가 루트노드가 아닐경우
    // p노드가 p노드의 부모노드의 왼쪽이었다면 x를 왼쪽으로, 오른쪽이었다면 오른쪽으로
    (x -> p ? p == x -> p -> l ?  x -> p -> l : x -> p -> r : tree) = x;
    update(p), update(x);
}

roatate가 끝난 시점에서, p노드는 x노드의 자식노드이기 때문에

p노드에 대해 먼저 update후에 x노드를 update 해줘야 합니다.

이제 모든 노드의 서브트리의 크기를 cnt에 저장해 뒀으니 k-th element를 구할 수 있습니다.

void kth(int k){
    node* x = tree;
    while(1){
        while(x->l && x->l->cnt > k) x = x->l;
        if (x -> l) x -= x->l->cnt;
        if(!k--)break;
        x = x->r;
    }
    splay(x);
}

여기까지가 기본연산들에 대해 알아봤습니다.

이제 문제에 어떻게 적용할 수 있는지 알아보겠습니다.

대부분 배열에서의 쿼리 문제를 다룰 것입니다.

BBST이기 때문에 중위순회를 하면 항상 같은 순서로 탐색한다는 점을 이용합니다.

따라서 배열의 인덱스를 노드의 key로 생각해주면 배열의 원소를 스플레이트리로 관리할 수 있습니다.

간단한 구간합과 RMQ, 그리고 구간을 뒤집는 flip연산을 살펴보겠습니다.

splay연산을 통해 어떤 구간 [s, e]를 하나의 노드로 모으는 것에 집중해봅니다.

구간 [s, e]를 하나의 노드에 모으는 방법을 알아봅시다

s - 1번째 노드를 splay 해주면

s-1번째 노드가 루트가 되고 왼쪽 자식은 s - 2까지, 오른쪽 자식은 s부터의 구간에 대한 정보를 담고 있을것입니다.

그런 다음에 e + 1번 노드를 s - 1번 노드 오른쪽에 붙여주면

이렇게 될 것이고

루트의 오른쪽 자식의 왼쪽 자식에 [s, e] 구간에 대한 정보가 있을것입니다.

이것을 위해 splay 함수를 수정해서 루트로 올리는 함수에서 특정 노드를 다른 노드의 자식으로 가도록 수정합니다.

void splay(node* x, node* g = nullptr){
    node* y;
    while(x -> p != g){
        node* p = x -> p;
        if (p -> p == g){ // zig step
            rotate(x);
            break;
        }
        auto pp = p -> p;
        if ((p -> l == x) == (pp -> l == p)){ // zig-zig step
            rotate(p);
            rotate(x);
        }else{  // zig-zag step
            rotate(x);
            rotate(x);
        }
    }
    if(!g) tree = x;
}

구간 [s, e] 를 모으는 gather 함수는 다음과 같습니다.

node* gather(int s, int e){ // [s, e]구간을 관리하는 노드를 리턴
    kth(e + 1);
    auto tmp = tree;
    kth(s - 1);
    splay(tmp, tree);
    return tree->r->l;
}

이제 구간을 뒤집는 flip 함수를 보겠습니다.

구간을 뒤집는 연산은 왼쪽 서브트리와 오른쪽 서브트리를 swap하는 것을 재귀적으로 해주면 됩니다.

재귀적으로 처리하면 느리기 때문에 flip됐는지 여부를 lazy하게 처리해줍니다.

구조체에 변수를 추가합니다.

struct node{
	// 다른 변수들
    bool flip;
}

그리고 flip됐는지 여부를 전파할 함수를 만듭니다

void push(node *x){
    if (!x -> flip) return;
    swap(x->l, x->r);
    if (x -> l) x->l->flip = !x->l->flip;
    if (x->r) x->r->flip = !x->r->flip;
    x->flip = false;
}

flip함수는 다음과 같이 간단하게 구현이 가능합니다.

void flip(int s, int e){
    node* x = gather(s, e);
    x->flip = !x->flip;
}

실제 문제에 적용하면 또 코드가 구현하기 편하도록 수정이 됩니다.

이것은 문제 풀이 카테고리에 문제를 직접 풀며 올려보겠습니다.

전체 소스

struct node{
    node* l;
    node* r;
    node* p;
    int key, cnt;
    bool flip;
}*tree;

void update(node* x);

void rotate(node* x){ // 위로 올릴 노드
    node* p = x -> p; // x의 부모 노드
    node* b = NULL; // b노드
    if(!p) return; // x가 루트라면 리턴
    if (x == p->l){ // x가 p의 왼쪽 자식
        p -> l = b = x -> r; // p의 왼쪽을 b노드로
        x -> r = p; // x의 오른쪽 자식을 p노드로
    }else{ // x가 p의 오른쪽 자식
        p -> r = b = x -> l; // p의 오른쪽을 b노드로
        x -> l = p; // x의 왼쪽 자식을 p노드로
    }
    // 부모노드 재설정
    x -> p = p -> p; // x의 부모는 p의 부모
    p -> p = x; // p의 부모는 x
    if (b) b -> p = p; // b노드가 존재한다면 b의 부모는 p

    // x가 루트노드가 아닐경우
    // p노드가 p노드의 부모노드의 왼쪽이었다면 x를 왼쪽으로, 오른쪽이었다면 오른쪽으로
    (x -> p ? p == x -> p -> l ?  x -> p -> l : x -> p -> r : tree) = x;
    update(p), update(x);
}



void splay(node* x, node* g = nullptr){
    node* y;
    while(x -> p != g){
        node* p = x -> p;
        if (p -> p == g){
            rotate(x);
            break;
        }
        auto pp = p -> p;
        if ((p -> l == x) == (pp -> l == p)){
            rotate(p);
            rotate(x);
        }else{
            rotate(x);
            rotate(x);
        }
    }
    if(!g) tree = x;
}

void insert(int key){
    node* p =tree;
    node** pp; // 넣을 위치
    if(!p){ // 빈 트리인 경우
        node* x = new node;
        tree = x;
        x -> l = x -> r = x -> p = NULL;
        x -> key = key;
        return;
    }
    while(true){ // 삽입할 위치를 찾을때까지 반복
        if (key == p -> key) return; // 중복값이 있을 경우 종료
        if (key < p -> key){ // 현재 노드의 값보다 작을경우
            if (!p -> l){ // 왼쪽이 비어있으면 왼쪽에 삽입
                pp = &p->l;
                break;
            }
            p = p->l; // 비어있지 않으면 왼쪽 자식으로 이동
        }else{ // 현재 노드의 값보다 크다
            if (!p->r){
                pp = &p->r;
                break;
            }
            p = p->r;
        }
    }
    // 위에서 삽입할 위치를 찾음
    node* x = new node;
    *pp = x;
    x -> l = x -> r = NULL;
    x-> p = p;
    x-> key = key;
    // splay
    splay(x);
}

bool find(int key){
    node* p = tree;
    if(!p) return false; // 비어있는 트리
    while(p){
        if (key == p -> key) break; // 찾았다
        if (key < p -> key){
            if (!p -> l) break;
            p = p -> l;
        }else{
            if (!p -> r) break;
            p = p -> r;
        }
    }
    splay(p);
    return key == p->key;
}

void del(int key){
    if (!find(key)) return; // 삭제할 값이 없으면 루트로 이동 후 종료
    node* p = tree;
    if (p -> l && p -> r){ // 자식이 두개
        tree = p->l; // 왼쪽 자식이 새로운 루트
        tree->p = NULL;

        // 오른쪽 서브트리를 왼쪽 서브트리 아래에 삽입
        node* x = tree;
        while(x -> r) x = x -> r;
        x -> r = p -> r;
        p -> r -> p = x;
        delete p;
        return;
    }

    if(p->l){ //자식이 왼쪽만 있는 경우
        tree = p->l;
        tree->p = NULL; //왼쪽 자식이 새로운 루트
        delete p; //노드 삭제
        return;
    }
    if(p->r){ //자식이 오른쪽만 있는 경우
        tree = p->r;
        tree->p = NULL; //오른쪽 자식이 새로운 루트
        delete p; //노드 삭제
        return;
    }

    // 노드가 자신 하나인경우
    delete p;
    tree = NULL;
}

void update(node* x){
    x -> cnt = 1;
    if (x -> l) x->cnt += x->l->cnt;
    if (x -> r) x->cnt += x->r->cnt;
}

void kth(int k){
    node* x = tree;
    while(1){
        while(x->l && x->l->cnt > k) x = x->l;
        if (x -> l) x -= x->l->cnt;
        if(!k--)break;
        x = x->r;
    }
    splay(x);
}

node* gather(int s, int e){ // [s, e]구간을 관리하는 노드를 리턴
    kth(e + 1);
    auto tmp = tree;
    kth(s - 1);
    splay(tmp, tree);
    return tree->r->l;
}

void push(node *x){
    if (!x -> flip) return;
    swap(x->l, x->r);
    if (x -> l) x->l->flip = !x->l->flip;
    if (x->r) x->r->flip = !x->r->flip;
    x->flip = false;
}

void flip(int s, int e){
    node* x = gather(s, e);
    x->flip = !x->flip;
}

사진 출처 :

https://justicehui.github.io/hard-algorithm/2019/10/23/SplayTree4/

https://blog.chodaeho.com/posts/2021/splay-tree-1/

https://boj.ma/7346/t

주어지는 두 유전자 문자열의 길이를 같게 적절히 공백을 추가했을 때 얻어지는 결괏값의 최대치를 알고 싶습니다.

또한 같은 위치에 두 문자열 모두에 공백이 있으면 안 됩니다.

주어지는 문자열의 길이는 100을 넘지 않습니다.

완전탐색부터 생각해 보면

문자열 두 개를 만들건대 문자열 각각의 인덱스를 n, m이라고 하면 첫 번째 문자열의 n번째 위치에 공백을 넣거나, 두 번째 문자열의 m번째 위치에 공백을 넣거나, 두 문자열 모두에 공백을 넣지 않거나

3가지 경우에 대해 분기를 나누어 진행하면 답을 찾을 수 있을 것 같습니다.

하지만 모든 경우에 대해 해 본다면 시간초과입니다.

예제의 문자열을 그대로 들고 왔습니다.

AGTGATG
GTTAG

첫 번째 문자열의 3번 인덱스까지 만들었고,  두 번째 문자열의 2번 인덱스까지 만들었을 때 그 이후에 공백을 적절히 채워 최댓값을 찾는 것은 이전에 어떤 방식으로 공백을 채웠든 항상 일정할 것입니다.

따라서 dp로 최적화가 가능합니다.

코드(c++)

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define NM 101010
#define MAX 1010100
#define BIAS 1048576
#define MOD 1000000007
#define X first
#define Y second
#define INF 100000000
#define FOR(i) for(int _=0;_<(i);_++)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
using namespace std;


int main() {
    fastio
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    vector<vector<int>> arr = {
            {5, -1, -2, -1, -3},
            {-1, 5, -3, -2, -4},
            {-2, -3, 5, -2, -2},
            {-1, -2, -2, 5, -1},
            {-3, -4, -2, -1, 0}
    };
    string s = "ACGT*";
    map<char, map<char, int>> mp;

    for(int i = 0; i < 5 ;i ++){
        for (int j = 0 ; j < 5; j++){
            mp[s[i]][s[j]] = arr[i][j];
        }
    }

    int t;
    cin >> t;
    while(t--){
        int n, m;
        string s1, s2;
        cin >> n >> s1 >> m >> s2;
        if (n < m) swap(n, m), swap(s1, s2);
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, -1));
        auto recur = [&](const auto&self, int a, int b) -> int{
            if (a == n){
                int total = 0;
                for (int i = b ;i < m; i++){
                    total += mp['*'][s2[i]];
                }
                return total;
            }
            if (b == m){
                int total = 0;
                for (int i = a ;i < n; i++){
                    total += mp[s1[i]]['*'];
                }
                return total;
            }
            int&ret = dp[a][b];
            if (ret != -1) return ret;
            ret = -INF;
            // 두개를 직접 비교
            ret = max(ret, self(self, a + 1, b + 1) + mp[s1[a]][s2[b]]);
            // s1을 공백으로 채운다
            ret = max(ret, self(self, a, b + 1) + mp['*'][s2[b]]);
            // s2를 공백으로 채운다
            ret = max(ret, self(self, a + 1, b) + mp[s1[a]]['*']);
            return ret;
        };

        cout << recur(recur, 0,0 ) << endl;

    }


    return 0;
}

약간 귀찮은 전처리만 해주면 됩니다

https://boj.ma/23889/t

돌이 굴러가는 위치들이 주어지고, 세울 수 있는 벽의 개수가 주어질 때 벽을 적절한 위치에 세워 파괴되는 모래성의 개수를 최소로 하고 싶습니다.

완전탐색부터 생각해 보면

주어지는 N개의 위치에 대해 M개의 벽을 놓는 모든 경우의 수에 대해 해 보는 것입니다.

$_{N} C_{M}$ 가지의 경우에 대해 돌을 놔보고, 그때마다 계산을 해주면? 당연히 시간초과입니다.

최적화를 생각해 봅시다

모든 위치에 벽을 놔보는 것이 오래 걸리니 벽을 놓지 않아도 되는 위치에 대해 생각해 봅시다.

저는 처음에 주어지는 돌이 굴러가기 시작하는 위치에만 벽을 놓으면 된다고 생각했습니다.

당연하게도 돌이 굴러가다가 막는 것보다 애초에 돌이 구르지 못하게 하는 것이 더 이득이기 때문입니다.

하지만 돌의 개수 K 또한 최대 N까지 가능하므로 돌의 위치에만 벽을 세워본다 하더라도 시간초과가 날 것입니다.

이제, 벽을 놓지 않아도 되는 돌의 위치에 대해 생각해 봅시다.

예를 들어 입력 예제가 다음과 같이

10 1 2
1 2 3 4 5 6 7 8 9 10
1 10

이런 형태라면

벽은 하나만 놓을 수 있고 돌이 굴러가기 시작하는 위치는 1, 10이므로

1번 위치에 벽을 세우면 10만큼의 모래성이 파괴되지만 10에 설치하게 되면 45만큼의 모래성이 파괴됩니다.

이것을 통해

각 돌마다 벽이 없을 때 파괴하는 모래성의 개수를 알고 있다면, 가장 많이 파괴하는 돌부터 막는 게 최적일 것이라고 생각했습니다.

따라서 돌마다 파괴하는 모래성의 개수를 전처리하여 구하고, 정렬하여 낮은 인덱스 순서대로 출력하면 됩니다.

코드 (c++)

#include <bits/stdc++.h>

#define endl "\n"
#define NM 100101
#define MAX 1010100
#define BIAS 1048576
#define MOD 1000000007
#define X first
#define Y second
#define INF 1000000000
#define FOR(i) for(int _=0;_<(i);_++)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
//typedef __int128 i128;
using namespace std;


int main() {
    fastio
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int n, m, k;
    cin >> n >> m >> k;
    vector<int> arr(n + 1), stone(k + 1), psum(n + 1, 0);
    for (int i = 1; i <= n; i++) cin >> arr[i];
    for (int i = 1 ;i <= k; i++) cin >> stone[i];
    for (int i = 1; i <= n; i++) psum[i] = psum[i - 1] + arr[i];
    vector<pii> v;
    for (int i = 1 ; i < k; i++){
        v.push_back({psum[stone[i + 1] - 1] - psum[stone[i] - 1], stone[i]});
    }
    v.push_back({psum[n] - psum[stone.back() - 1], stone.back()});

    auto comp = [&](pii a, pii b) -> bool{
        if (a.X == b.X) return a.Y < b.Y;
        return a.X > b.X;
    };

    sort(all(v), comp);

    vector<int> ans;

    int cnt = min(m, k);
    for (int i = 0 ; i < cnt; i++){
        ans.push_back(v[i].Y);
    }
    sort(all(ans));

    for (auto i : ans) cout << i << endl;

    return 0;
}

https://boj.ma/31786/t 

2가지 쿼리가 주어집니다.

1번 쿼리 : $(x, 0), (-x, 0)$ 에 위치할때 통신 가능한 기지국의 개수 출력

2번 쿼리 : $(x, y)$ 에 기지국이 있었으면 삭제, 없었으면 추가

$(x, 0)$ 와 $(-x, 0)$ 이 통신하기 위해서는 어떤 기지국 $(a, b)$ 에 대해 세 점이 이루는 삼각형이 예각 삼각형이어야 합니다.

1번 쿼리를 보고 예각 삼각형이 되어야 하므로 당연히 점 $(a, b)$ 의 a가 $ -x < a < x $ 여야 한다는 건 알았습니다.

처음엔 저 사이에만 있으면 무조건 예각삼각형이라고 착각했습니다.

중3때 배우는 기하학을 갖고와봅시다

반원에 대한 원주각은 항상 직각입니다.

$(x, 0)$ 와 $(-x, 0)$ 을 지름으로 하는, 반지름의 길이가 x이고 중심이 $(0, 0)$인 원을 생각하면

원안에 있는 모든 점들에 대해서 만들어지는 삼각형은 절대 예각삼각형이 될 수 없습니다.

따라서 임의의 기지국 좌표 $(a, b)$에 대해 $ -x < a < x $ 를 만족하면서  $ a^2 + b^2 > x^2$ 인 점들만 답이 될 수 있습니다.

그럼  $ -x < a < x $ 의 개수에서 $ a^2 + b^2 <= x^2$ 인 점의 개수를 빼주면 1번 쿼리를 처리할 수 있습니다.

쿼리의 개수가 $3*10^5$개 주어지는 좌표의 범위가 $[-10^9, 10^9]$ 이므로 당연히 완전탐색으로 쿼리를 처리할 수 없습니다.

1번쿼리는 특정 범위인 값의 개수, 2번쿼리는 특정 좌표를 추가하거나 삭제하는 쿼리이므로

세그먼트 트리를 생각할 수 있습니다.

그런데, 좌표의 범위가 크기때문에 좌표압축을 해줘야할 것 같은데 온라인으로 좌표가 주어지기때문에 힘들어 보입니다.

그래서 쿼리를 미리 다 받아서 나올 수 있는 모든 $x$좌표와 $x^2+y^2$의 값을 미리 계산하여 좌표압축 후에

세그먼트 트리를 적용하면 됩니다.

여기까지 생각하고 세그먼트 트리를 통해 구현을 하다가 pbds를 통해서도 충분히 위의 쿼리를 처리할 수 있다고 판단하여 pbds로 구현했습니다.

그리고, $x^2 + y^2$의 값들을 관리할때 좌표가 다르더라도 $x^2 + y^2$의 결과는 같을 수 있습니다.

따라서 기지국의 좌표를 따로 관리하는 자료구조(set, map..)도 필요합니다.

구현(c++)

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define NM 101010
#define MAX 1010100
#define BIAS 1048576
#define MOD 1000000007
#define X first
#define Y second
#define INF 100000000
#define FOR(i) for(int _=0;_<(i);_++)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
//typedef __int128 i128;
using namespace std;

//pbds -- order_of_key(x) := x미만의 원소의 개수(x가 들어가야할 인덱스 0-based) , find_by_order(k) := (k + 1)번째 원소가 있는 iter
using namespace __gnu_pbds;
// multi-set
using ordered_set_equal = tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update>;
using ordered_set_equal_pll = tree<pll, null_type, less_equal<pll>, rb_tree_tag, tree_order_statistics_node_update>;
// set
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;


int main() {
    fastio
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ordered_set_equal x_, xy_;
    ordered_set_equal_pll xy_cd;
    // multi-set 원소삭제
    auto pbds_erase = [&](ordered_set_equal &a, ll val)->void{
        auto it = a.find_by_order(a.order_of_key(val));
        if(*it == val) a.erase(it);
    };

    auto pbds_erase_pll = [&](ordered_set_equal_pll &a, pll val) -> void{
        auto it = a.find_by_order(a.order_of_key(val));
        if (*it == val) a.erase(it);
    };

    int q;
    cin >> q;
    while(q--){
        int oper;
        cin >> oper;
        if (oper&1){
            ll x;
            cin >> x;
            // (-x, x)구간의 갯수
            int x_cnt = x_.order_of_key(x) - x_.order_of_key(-x + 1);
            // a^2 + b^2 <= x^2인 (a, b)의 갯수
            int xy_cnt = xy_.order_of_key(x * x + 1);
            cout << x_cnt - xy_cnt<< endl;
        }else{
            ll x, y;
            cin >> x >> y;
            // x^2 + y^2
            ll cur = x * x + y * y;
            auto it = xy_cd.find_by_order(xy_cd.order_of_key({x, y}));
            // 이미 존재하는 기지국
            if (it->first == x && it->second == y) {
                pbds_erase(xy_, cur);
                pbds_erase(x_, x);
                pbds_erase_pll(xy_cd, make_pair(x, y));
            }else{
                xy_.insert(cur);
                x_.insert(x);
                xy_cd.insert(make_pair(x, y));
            }
        }
    }

    return 0;
}

기지국의 좌표를 관리하는건 굳이 pbds를 통해 관리하지 않아도 됩니다.

사진 출처 : http://trsketch.dothome.co.kr/a13012

https://boj.ma/31782/t 

문제 조건에 따라 낮동안에 정상체온이 되는 사람들의 그룹은 반드시 직사각형 형태가 됩니다.

밤에는 K명이 저체온증이 되는데 만들어지는 직사각형들 중 가로 또는 세로의 길이가 K보다 작거나 같다면 그 변에 있는 모든 사람이 저체온증에 걸리게 하면 낮동안에 정상체온이 될 방법이 없으므로 그 직사각형 그룹은 모두 저체온증이 됩니다.

따라서 bfs 한 번으로 정상체온 그룹을 만들어주고,

그룹을 만날때마다 가로, 세로 사이즈를 구해서 모두 K보다 크다면 직사각형의 크기만큼을  정답에 추가해주면 됩니다.

총 시간복잡도는 O(NM)입니다.

코드(python)

import sys
from collections import deque
input = sys.stdin.readline

def in_range(a, b):
    return 0 <= a < n and 0 <= b < m

n, m, k = map(int, input().split())
board = [list(input().strip()) for _ in range(n)]
q = deque()
visited = [[False] * m for _ in range(n)]
dxy = [(1, 0), (0, 1), (-1, 0), (0, -1)]
for i in range(n):
    for j in range(m):
        if board[i][j] == 'O':
            q.append((i, j))
            visited[i][j] = True

while q:
    x, y = q.popleft()
    board[x][y] = 'O'
    for dx, dy in dxy:
        nx, ny = x + dx, y + dy
        if not in_range(nx, ny):
            continue
        if visited[nx][ny]:
            continue
        if board[nx][ny] == '.':
            cnt = 0
            for ddx, ddy in dxy:
                nnx, nny = nx + ddx, ny + ddy
                if not in_range(nnx, nny):
                    continue
                if board[nnx][nny] == 'O':
                    cnt += 1
            if cnt >= 2:
                q.append((nx, ny))
                visited[nx][ny] = True
visited = [[False] * m for _ in range(n)]
ans = 0
for i in range(n):
    for j in range(m):
        if board[i][j] == 'O' and not visited[i][j]:
            garo = 0
            saero = 0
            x = i
            y = j
            while x < n and board[x][j] == 'O':
                x += 1
                saero += 1
            while y < m and board[i][y] == 'O':
                y += 1
                garo += 1
            q = deque()
            q.append((i, j))
            visited[i][j] = True
            while q:
                x, y = q.popleft()
                for dx, dy in dxy:
                    nx, ny = x + dx, y + dy
                    if not in_range(nx, ny):
                        continue
                    if visited[nx][ny]:
                        continue
                    if board[nx][ny] != 'O':
                        continue
                    q.append((nx, ny))
                    visited[nx][ny] = True
            if garo > k and saero > k:
                ans += garo * saero
print(ans)

가로세로 체크하며 이미 방문한 그룹을 다시 방문하지 않기 위해 BFS를 한 번 더 했는데 굳이 이렇게 하지 않고 더 효율적으로 하는 방법이 있습니다. 저는 비효율적으로 구현한것 같습니다.