첫 번째 방법(사용자 공간)의 라이브러리 함수 호출은 사용자 공간의 지역함수를 호출하게 되는 것을 의미하고, 두 번째 방법(커널 수준 라이브러리) 함수 호출은 커널 시스템 콜을 부르는 결과를 낳는다.

현재 주로 사용되는 라이브로리는 POSIX Pthreads, Windows, Java가 있다.

POSIX Pthreads는 사용자 또는 커널 수준 라이브러리로 제공될 수 있다. Windows 스레드는 윈도우 시스템에서 사용 가능한 커널 수준 라이브러리이다. Java 스레드는 자바 프로그램에서 직접 생성과 관리를 가능케 한다. JVM은 운영체제에서 실행되기 때문에 Java 스레드는 호스트 시스템에서 사용 가능한 스레드 라이브러리로 구현된다.

• windows - windows API
• UNIX,Linux,macOS - Pthreads

Pthreads

Pthreads는 POSIX가 스레드 생성 및 동기화를 위해 저장한 표준 API이다. 즉, 명세일 뿐, 구현은 운영체제 설계자가 한다.

사용자 스레드는 커널 위에서 지원되며, 커널의 지원 없이 사용자 공간에서 관리된다. ex)POSIX Pthreads, Windows threads, Javathreads

커널 스레드는 운영체제가 직접 지원하고 관리한다.

즉, 사용자 스레드는 사용자가 자유롭게 생성할 수 있지만, 실제로 CPU에서 실행되기 위해서는 커널 스레드를 통해야 한다.

다대일 모델(Many-to-One)

많은 사용자 수준 스레드를 하나의 커널 스레드로 사상한다. 문제는 한 스레드가 봉쇄형 시스템 콜을 할 경우, 전체 프로세스가 봉쇄된다. 또한 한 번에 하나의 스레드만 커널에 접근 가능해 병렬 실행이 불가능하다.

일대일 모델(One-to-One)

사용자 스레드와 커널 스레드가 1대1 매칭이 된다. 하나의 쓰레드가 봉쇄 되어도 다른 쓰레드는 실행된다. 병렬적으로 멀티프로세싱이 가능하다. 다만 너무 많은 쓰레드를 올리면 시스템 자원이 고갈될 수 있다.

다대다 모델(Many-to-Many)

여러개의 사용자 모델과 작거나 같은 수의 커널 스레드로 멀티플렉스한다. 죽, 필요한 만큼 사용자 스레드를 생성하고 그에 상응하는 커널 스레드를 통해 병렬로 수행할 수 있다,

그러나 1.구현이 너무 어렵고 2.요새는 워낙 코어가 많아서 굳이 사용하지 않는다.

두 수준 모델(two-level model)

다대다 모델과 일대일 모델을 섞었다. 그러나 구현이 어려워 사용하지 않는다.

결론

현대 운영체제는 일대일 모델을 사용한다!

스레드는 CPU이용의 기본 단위이다.전통적인 프로세스는 하나의 스레드만 가지지만, 만일 프로세스가 다수의 스레드를 갖게 된다면 동시에 하나 이상의 작업을 수행할 수 있다. 또한 같은 프로세스 내의 여러 스레드는 서로 자원들을 공유한다.

스레드의 구성은 어떻게 될까?

• 스레드ID
• 프로그램 카운터(PC)
• 레지스터 집합
• 스택

스레드가 필요한 이유는?

프로세스의 생성 작업은 매우 많은 시간을 소요하고 많은 자원을 필요로 한다. 그런데 새 프로세스의 작업이 기존 프로세스의 작업과 동일하다면..? 새로 만드는 것 보다 같은 프로세스안에 여러 스레드를 만드는 것이 효율적이다. 스레드는 프로세스의 자원을 공유하기 때문에!

스레드 사용 예시

웹 서버는 여러개의 클라이언트로부터 요청을 받으면, 그 요청을 수행한 별도의 프로세스를 만든다.

장점

이러한 스레드 프로그래밍은 어떤 이점이 있을까?

1. 응답성 응용 프로그램이 긴 작업을 수행하더라도, 연산이 오래 걸리는 작업을 별도의 스레드에서 실행된다면 프로그램이 계속 수행되는 것을 허용함으로써 사용자의 응답성을 증가시킨다.
2. ** 자원 공유** 프로세스들은 공유 메모리와 메시지 전달 기법을 통해 자원을 공유한다. 그러나 스레드는 그들이 속한 프로세스의 자원들과 메모리를 공유한다.
3. ** 경제성** 자원 공유를 통해 스레드를 생성 및 문맥 교환시 프로세스를 생성하거나 문맥 교환하는 것보다 경제적이다.
4. 규모 적응성 다중 스레드는 다중 처리기 구조에서 각각의 스레드가 병렬로 수행될 수 있으므로 적응성이 높다.

구현 방법

자바에서 스레드를 생성하는 방법은 1.스레드를 상속받거나 2.Runnable인터페이스를 구현하는 방법이 있다.

1. 스레드 상속 스레드의 실행은 run()메서드를 통해 실행된다. run() 함수를 오버라이드 하면 된다.

class ThreadEx1_1 extends Thread {
    public void run() {
        for (int i=0; i<5; i++){
            System.out.println(getName());
        }
    }
}

2.runnable interface 인터페이스를 구현하여 쓰레드 객체를 생성하면 된다. 마찬가질 run()메서드를 구현해야 한다.

class ThreadEx1_2 implements Runnable {
    @Override
    public void run() {
        for (int i=0; i<5; i++){
            System.out.println(Thread.currentThread().getName());
            public static native Thread currentThread(); 
            //Thread의 static 메소드로 자신의 스레드를 참조함 <- 자신의 스레드의 getName()을 부르는 거임

        }
    }
}

아래는 runnable interface를 통한 스레드 객체 생성 방식이다.

public Thread(Runnable task) {
    this(null, null, 0, task, 0, null);
} // <- Thread 생성자: Runnable 객체를 받아서 Thread 객체를 생성함

public void run() {
    Runnable task = holder.task;  // Thread에 저장된 Runnable 객체 가져오기
    if (task != null) {
        Object bindings = scopedValueBindings();  // 스코프 바인딩 정보 가져오기
        runWith(bindings, task);  // 실제 Runnable 실행
    } // <- Thread의 run() 메서드: 저장된 Runnable의 run() 메서드를 실행함
}

스레드는 thread.start()를 통해 실행되고,실행되면 run()을 통해 진행한다. thread.run()을 진행하면 새로운 스택을 실행하는 것이 아닌 main쓰레드의 스택을 사용하므로 주의해야 한다.

    public static void main(String[] args) {

        ThreadEx1_1 t1 = new ThreadEx1_1(); // thread 자손 클래스의 인스턴스 생성
        Runnable r = new ThreadEx1_2(); // runnable을 구현한 클래스의 인스턴스 생성
        Thread t2 = new Thread(r);
        t1.start();//스레드를 생성하고 사용될 호출스택 생성 -> run() 만들어진 호출스택에 생성
        t2.start();
        t1 = new ThreadEx1_1();
        t1.start(); //스레드 다시 실행시 예외 발생
    }
}

thread.start()와 thread.run() 차이

- thread.run()
Main Thread Call Stack
┌────────────────────────────┐
│ main()                     │
│ └─ thread.run() 호출        │
│     └─ run() 메서드 실행      │
└────────────────────────────┘
- thread.start()
 Main Thread Call Stack          New 
Thread Call Stack
┌────────────────────────┐     ┌─────────────────────┐
│ main()                 │     │ run()               │
│ └─ thread.start() 호출  │     └─────────────────────┘
└────────────────────────┘     

getName() 과Thread.currentThread().getName()의 차이

Thread 객체의 이름을 가져오는 메서드는 getName()이다. 하지만 Runnable 인터페이스를 구현한 객체는 Thread가 아니기 때문에 getName() 메서드를 직접 호출할 수 없다. 따라서 현재 실행 중인 스레드의 이름을 얻고 싶다면, Thread.currentThread()를 호출해 현재 스레드 객체를 얻은 뒤, getName()을 호출해야 한다.

this 가 가르키는 객체

• thread - thread
• runnable - runnable 구현 객체

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

학교 알고리즘 시간에 그리디를 배우고 있어서 문제를 풀어봤다. 분할 가능한 배낭문제 인것 같다.

풀이 과정

1. 도착 시간이 빠른 순서대로 정렬한다.
2. 같을 경우, 출발 시간은 같은 순서대로 정렬한다.
3. 출발~도착까지의 적재 가능한 양보다 적으면 박스의 무게만큼 더한다. 3-1. 만약 적재 가능한 양보다 크다면 가능한 만큼만 쪼개서 더한다.
4. 반복한다.

구현

import java.util.*;

class boxes implements Comparable<boxes> {
    int start;
    int end;
    int weight;

    public boxes(int s, int e, int w) {
        start = s;
        end = e;
        weight = w;
    }

    @Override
    public int compareTo(boxes o) {
        if (this.end == o.end) {
            return this.start - o.start;
        }
        return this.end - o.end;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int c = sc.nextInt();
        int m = sc.nextInt();

        boxes[] boxes = new boxes[m];
        for (int i = 0; i < m; i++) {
            boxes[i] = new boxes(sc.nextInt(), sc.nextInt(), sc.nextInt());
        }

        Arrays.sort(boxes);

        int[] village = new int[n + 1];
        int cnt = 0;

        for (boxes box : boxes) {
            int maxC = c;

            for (int i = box.start; i < box.end; i++) {
                maxC = Math.min(maxC, c - village[i]);
            }

            int lowWeight = Math.min(box.weight, maxC); //만약 적재량 < 박스 무게라면 박스를 쪼갬.

            for (int i = box.start; i < box.end; i++) {
                village[i] += lowWeight;
            }

            cnt += lowWeight;
        }

        System.out.println(cnt);
    }
}

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

험난했던 시험 기간을 끝내고 다시 돌아온 백준 시간. 오늘 푼 문제는 알고리즘 시간에 배운 행렬곱셈 순서를 실제로 풀어본 문제이다. 현재 학교 알고리즘 과목에서 DP를 배우고 있다.

풀이 방법

우선 행렬의 곱셈 성질에 대해서 알아야 한다. 행렬 A(p*q) 와B(q*r)를 곱하면 총 연산은p*q*r이고, AB크기는p*r이 된다.

이를 인지했으니, 본격적으로 시작해보자. $A_1$부터 $A_n$까지의 행렬이 존재하였을 때, $A_n$이 가능한 곱셈의 연산 횟수는 n-1이다. $(A_1 * A_2 .. A_{n-1}) * A_n$ $(A_1 * A_2 .. A_{n-2})(A_{n-1} * A_n)$ 등등.. 이 중 가장 연산 횟수가 적은 값을 찾으면 된다는 것이다. 그렇다면 $(A_1 * A_2 .. A_{n-1})$의 값은? 마찬가지로 n-2의 경우의 수 중에서 가장 작을 값을 ... 이렇게 계속 내려가 재귀적으로 구할 수 있다. 그러나, 정말 재귀적으로 풀기에는 경우의 수도 많고, 중복된 내용도 많다. 또한 큰 문제를 해결하기 위해, 작은 부분을 해결하는 최적 부분 구조도 가지고있다. 그러므로 DP를 사용해서 풀어야 한다.

최적부분 구조

$A_i$ ~ $A_j$까지의 최소 연산을 $C_{i~j}$라고 한다면,

$C_{ij}$는 임 의의 K(i<=k<=j-1)을 기준으로 **$C_{ik}$ + $C_{k+1~j}$ + 두 행렬의 곱셈 연산 수**이다.

예) $C_{14}$를 구할 때, $C_{12}$와 $C_{3~4}$를 가지고 구함 (1=A 2=B 3=C 4=D)

즉, 이 된다. 이제 연산을 구해보자. 우선, 행렬의 곱의 특징은, 곱하려는 AB의 행과 열이 같아야 한다. 즉, 겹치는 부분이 존재한다. $A_1$~$A_4$까지의 행렬이 있으면 p*q q*r r*x x*z 이렇게 행렬이 겹친다. 중복된 부분을 제거해보자.

$A_i$의 행은 i-1, 열은 i가 됨을 알 수 있다.이를 연산에 집어 넣어보면 $P_{i-1}P_{K}P_{j}$가 된다.(만약 이부분이 이해가 안된다면 행렬을 곱했을 때, 연산 후 행렬의 크기가 p*r임을 잊지 말자)

후, 이제 최적부분 구조도 알았겠다,이제 아래서부터 차근차근 올라가보자 그룹의 체인(괄호로 묶는 묶음)은 자기 자신n개까지 즉, 1개,2개..n개만큼 묶을 수 있다. 나 자신만을 묶는다면 $C_{ii}$가 될 것이고, 2개를 묶는다면 $C_{ii+1}$이 될 것이다.결국ij까지의 원소가 모두 묶일때까지 반복한다.

시간복잡도 체인의 길이n * 행렬의 개수n *

코드

import java.util.Scanner;

public class Main {


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] p= new int[n+1];
        for(int i=1;i<=n;i++){
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            p[i-1]=a;
            p[i]=b;
        }
        int[][] m = new int[n+1][n+1];
        for(int i=1;i<=n;i++){
            m[i][i] = 0;
        }
        for(int r=2;r<=n;r++){
            for(int i=1;i<=n-r+1;i++){
                int j =i+r-1;
                int minValue = Integer.MAX_VALUE;
                for(int k=i;k<=j-1;k++){
                    minValue = Math.min(minValue,m[i][k]+m[k+1][j]+(p[i-1]*p[k]*p[j]));
                }
                m[i][j] = minValue;
            }
        }
        System.out.println(m[1][n]);
    }
}

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

값이 중복되지 않게 예외 처리를 해줘야 하는데 이 점을 내가 간과해서 꽤나 애를 먹었다.

풀이 과정

1. 세 수를 합해야 하므로 모든 수를 따지면 $N^3$이므로 시간 초과이다.
2. 그러나 두 수를 더하고 0에 수렴하는 나머지 수를 찾는다면 $N^2logN$이 된다. n<10000이므로 $N^2$은 1억이라 4초안엔 어지간하면 해결될 것 같다.
3. 그래서 나는 두 수를 찾는 이중 포문과 두 값과 더했을 때 0이 되는 값을 이진 탐색으로 찾았다.
4. 다만 같은 값이 여러개 있어도 모두 독립된 값이므로 이를 예외처리 하기 위해 upper_bound - lower_bound 하여 개수를 더하였다.
5. 또한 0번배열부터 순차적으로 조합해 나가므로 m번 배열에선 m-1번 배열까지는 쳐다 볼 필요도 없다. 이를 예외처리 해줘야 한다.

구현

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);
    int n;
    cin>>n;
    int arr[10000];
    for(int i=0; i<n; i++){
        cin>>arr[i];
    }
    sort(arr,arr+n);
    long long cnt=0;
    for(int i=0; i<n-2; i++){
        for(int j=i+1; j<n-1; j++){
            int tmp = arr[i] + arr[j];
            int lower = lower_bound(arr +(j+1), arr + n, -tmp) - arr;
            int upper = upper_bound(arr+(j+1), arr + n, -tmp) - arr;
            cnt +=  upper - lower ; 
        }
    }
    cout<<cnt;
    return 0;
}

1. 유저가 로그인하면 todo를 불러오자.

먼저 클라이언트에 todo가 보일 수 있게 todo를 저장하는 state를 만들자.

const [todoList, setTodoList] = useState([]);

이제 todo를 서버에서 읽어와야한다. todo에 userId를 저장한다고 가정하고 restAPI를 구현해보자

  const readList = async () => {
    if (!token) {
      console.log("No token available, cannot read list");
      return;
    }

    try {
      const { data } = await axios.get(`http://localhost:4444/todos?userId=${userId}`, {
        headers: { Authorization: `Bearer ${token}` }
      });
      setTodoList(data);
      console.log("Todo list loaded:", data);
    } catch (error) {
      console.error("할 일 목록 읽기 실패:", error.response?.data || error.message);
    }
  };

그러면 언제 todo를 읽어와야 할까? 1.todo가 삭제될 때 2.todo가 생성될 때 3.로그인 할 때

1,2번은 post도 구현해야하니 3번부터 구현하자. 로그인하면 token이 저장되니 token값이 바뀌면 readList 함수를 불러오게끔 해보자

  useEffect(() => {
    if (token) {
      readList();
    }
  }, [token]);

2.실질적으로 할 일을 추가할 수 있도록 하자.

우선 화면에 보일 수 있도록 jsx를 작성한다.

const [description, setDescription] = useState("");

{/* Todo Form */}
      {token && (
        <>
          <h2>추가하기</h2>
          <input
            placeholder="할 일"
            type="text"
            value={description}
            onChange={(e) => setDescription(e.target.value)}
          />
          <button onClick={handleSubmit}>추가하기</button>
          <br />
        </>
      )}

이제 버튼을 눌렀을 때 실제로 할 일이 추가되도록 하자. todo를 만들기 위해선 1.todo의 내용 2.수행여부 3.userId가 필요하다. 이 내용들을 body에 넣어 restAPI를 보내보자.

  const handleSubmit = async () => {
    try {
      const { data } = await axios.post(
        "http://localhost:4444/todos",
        {
          description,
          isCompleted: false,
          userId 
        },
        {
          headers: { Authorization: `Bearer ${token}` }
        }
      );
      alert(data.description + "이 추가되었습니다.");
      setDescription("");
      await readList(); 
    } catch (error) {
      console.error("할 일 추가 실패:", error.response?.data || error.message);
    }
  };

이제 직접 값을 넣어보자! 값이 야무지게 들어온다.

그렇다면 이제 할 일 목록이 보이게끔 해보자!

      {/* Todo List */}
      {token && (
        <div>
          <h2>할 일 목록</h2>
          <ul>
            {todoList?.map((todo) => (
              <div key={todo.id}>
                <li>{todo.description}</li>
                <button
                  onClick={() => toggleCompleteBtn(todo.id, todo.isCompleted)}
                >
                  {todo.isCompleted ? "완료" : "미완료"}
                </button>
                <button onClick={() => deleteTodoBtn(todo.id)}>삭제하기</button>
              </div>
            ))}
          </ul>
        </div>
      )}

이제 수행여부와 삭제버튼을 만들어보자. 수행여부는 그냥 boolean값을 반대로 해주면 된다.

  const toggleCompleteBtn = async (id, isCompleted) => {
    try {
      await axios.patch(
        `http://localhost:4444/todos/${id}`,
        {
          isCompleted: !isCompleted,
        },
        {
          headers: { Authorization: `Bearer ${token}` }
        }
      );
      await readList();
    } catch (error) {
      console.error("할 일 상태 변경 실패:", error.response?.data || error.message);
    }
  };

삭제는 delete메소드를 사용했다.

  const deleteTodoBtn = async (id) => {
    try {
      await axios.delete(`http://localhost:4444/todos/${id}`, {
        headers: { Authorization: `Bearer ${token}` }
      });
      await readList();
    } catch (error) {
      console.error("할 일 삭제 실패:", error.response?.data || error.message);
    }
  };

완성!

참고 https://minhanpark.github.io/%EC%8B%9C%EB%A6%AC%EC%A6%88/json-server-auth/

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

이진탐색의 사용은 무궁무진하구나... 처음엔 엥? 아무리봐도 dp문제인데? 했는데 시간복잡도가 O(N^2)이면 못푸는 문제더라...^^ 아무리봐도 모르겠어서 인터넷 보면서 풀었다..

풀이 과정

1. 결과 배열을 만들고 첫 번째 입력 배열 값을 넣는다.

2. 입력 배열을 돌며 현재 저장된 결과 배열의 마지막 값 보다 큰지 확인한다.

3. 만약 크면 뒤에 삽입, 그렇지 않으면 현재 원소보다 크거나 같은 첫 번째 결과 값과 바꾼다.

   {10,20,30,15,20,25} 가 존재한다고 했을 때 i=0) result = {10} i=2) result = {10,20,30} i=3) restlt = {10,15,30}

   이유는 다른 부분배열로 대체하기 위해서이다. 20을 15로 바꾼다고해서 길이가 달라지진 않는다. 다만 다음에 20을 만나면 30위치에 20이 들어오고, 25를 만나면 길이가 증가하게 된다. 즉, 15부터 reslt의 end까지 언제나 바뀔 준비를 하고있는 것이다.증가하는 부분 수열이므로 결국 작은 값부터 순차적으로 바뀌는 것 이니깐..

4. 끝까지 돌고 나서 길이를 출력한다. (result 배열 자체는 증가하는 부분 수열이 아닐 수도 있다. 3번의 이유로 바뀔 준비를 하다가 만 배열일 수도 있기 때문이다.그러나 길이는 동일하다.)

시간복잡도

3번에서 대체할 수를 찾는 방법으로 이진탐색을 쓰면 logN으로 금방 찾을 수 있다. n번을 탐색하니 $O(nlogn)$

구현

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);

    int n;
    cin >> n;
    vector<int> seq(n + 1);
    vector<int> res;

    for(int i = 1; i <= n; i++){
        cin >> seq[i];
    }

    res.push_back(seq[1]);

    for(int i = 2; i <= n; i++){
        if(seq[i] > res.back()) {
            res.push_back(seq[i]);
        } else {
            auto it = lower_bound(res.begin(), res.end(), seq[i]);
            *it = seq[i];
        }
    }

    cout << res.size() << endl;

    return 0;
}

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

와!! 이분탐색 문제중에 처음으로 보자마자 슥슥 접근하고 바로 구현해냈다.. 사실 규칙이 쉬워서 금방 발견한거긴 하지만..

문제 풀이

우선 문제가 요구하는 값은 '마지막 도토리가 들어가는 상자의 번호'이다. 마지막 도토리라는 것은 D번째 도토리라는 것이다. 도토리 D가 있을때, 1~i번째 상자까지의 도토리의 합이 D가 된다면 마지막 상자가 된다는 것도 알 수 있다. 그리고 마지막 상자는 결국 '최댓값'이다. 와! 앞서 풀었던 파라메트릭 서치 문제인 것이다.

그렇다면 i번째의 상자까지의 도토리 D개는 어떻게 알 수가 있을까? '규칙대로'더해보면 되지 않을까? 규칙을 보면 C번마다 반복하여 도토리를 추가하는 것을 알 수 있었다.즉 C로 나누기를 하면 된다. 다만 시작값과 끝 값이 정해져 있으니 이를 유의해서 계산해주면 된다.

구현

#include <iostream>
#include <vector>
using namespace std;

struct rule
{
    int s,e,j;
    rule(int s,int e, int j):s(s),e(e),j(j){};
};


int main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);
    int result;
    int n, k;
    int d;
    cin>>n>>k>>d;
    int s=0,&e=n;
    vector <rule> rule;
    for(int i=0; i<k; i++){
        int a,b,c;
        cin>>a>>b>>c;
        rule.push_back({a,b,c});
    }
    while (s<=e)
    {
        long long cnt=0;
        int m = (s+e)/2;
        for(auto&r : rule){
            if(m < r.s) continue;
            cnt += (min(m,r.e)-r.s)/r.j + 1;
        }
        if(cnt<d){
            s=m+1;
        }
        else{
            result=m;
            e=m-1;
        }
    }
    cout<<result;

    return 0;
}

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

처음엔 크루스칼 알고리즘밖에 떠오르지 않았다. 가중치의 최댓값을 작고 점점 작게 탐색한다면... 쉽게 할 수 있을 것 같았다. 그러나! 나는 이분 탐색을 공부 중이기때문에, 이분 탐색으로 어케할지 이리저리 고민해봤다...

파라메트릭 서치

문제를 풀고 여러 블로그들을 돌아보니, 이런 종류의 문제에서 사용된 이분 탐색기법을 파라메트릭 서치라고 불렀다.

파라메트릭 서치란 어떠한 정렬된 리스트에서 원하는 값을 찾는 이분 탐색과 달리** 조건에 부합하는 값을** 찾는 것이다.

파라메트릭 서치를 사용하기 위해선 세가지 조건이 있다.

• 조건을 만족하는 최대,최소를 구하는 문제여야 한다.
• 최댓값이 조건을 만족한다면, 최댓값보다 작은 값도 만족해야 한다.
• 답의 범위가 정수이거나 허용 오차 범위가 있어야 한다.

시간 복잡도

• 이진 탐색 $O(log(maxWeight))$ * bfs탐색(정점n + 간선 m) $O(n+m)$ => $O(nlogn)$

문제 풀이

1. 입력을 받으며 최대 가중치를 구함
2. 최대 가중치와 최소 가중치의 중간 값을 구함
3. 시작지점부터 bfs를 하며 간선을 이동
   • 만약 간선의 가중치가 2번에서 구한 값보다 크면 계속 움직이고 아니면 break
4. 도착지점 까지 움직였으면 최소 가중치를 2번 값 + 1
5. 아니라면 최대 가중치를 2번 값 - 1

구현

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int n, m;
    cin >> n >> m;

    vector<vector<pair<int, int>>> edge(n + 1); // [start] first:end second:w
    int max_weight = 0;

    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        edge[a].push_back({b, c});
        edge[b].push_back({a, c}); 
        max_weight = max(max_weight, c);
    }

    int s, e;
    cin >> s >> e;

    int min_weight = 1;

    while (min_weight <= max_weight) {
        int current_weight = (min_weight + max_weight) / 2;

        vector<bool> visit(n + 1, false);
        visit[s] = true;

        queue<int> q;
        q.push(s);

        bool can_reach = false;

        while (!q.empty()) {
            int start = q.front();
            q.pop();

            if (start == e) {
                can_reach = true;
                break;
            }

            for (auto& edg : edge[start]) {
                int next = edg.first;
                int w = edg.second;

                if (!visit[next] && w >= current_weight) {
                    visit[next] = true;
                    q.push(next);
                }
            }
        }

        if (can_reach) min_weight = current_weight + 1;
        else max_weight = current_weight - 1;
    }

    cout << max_weight;

    return 0;
}

참고 https://ialy1595.github.io/post/parametric-search/

프론트엔드를 개발하다보면 백엔드 api가 없어 개발에 난감한 경우가 있다. 그렇다고 openAPI만 사용하기엔 커스텀할 수 있는 내용이 적어 원하는 기능을 테스트 해보기가 어려운 순간도 있다. 그래서 가짜 api통신이 가능하도록 moke api를 만들려고 한다. 가짜 api를 만드는 방법은 여러가지가 있지만, 그중에서 json-server가 가장 간단하게 구현할 수 있다는 생각이 들어 채택했다.

설치

npm i json-server-auth json-server

설치 후 파일 의존성이 잘 되어있는지 확인할 필요가 있다. 나는 처음에 에러가 떠서 뭔가 했는데 알고보니 의존성 오류였다..

시작

우선 api의 json을 저장할 db.json 파일을 루트폴더에 만든다. 파일엔 유저를 저장할 users를 만든다.

{
  "users": []
}

앞으로 회원가입시 user에 유저들이 들어올 것이다. pakege.json 파일의 skript에 명령어를 만든다.

  "scripts": {
    "server": "json-server-auth --watch db.json --port 4444"
  }

watch 뒤에는 db가 저장된 json파일을 적고, port 뒤에는 서버를 열 포트 번호를 붙여준다. port를 붙이지 않으면 기본적으로 3000으로 열리는데, 리액트와 번호가 같으니 변경해주자.

인증

json-server-auth의 경우 JWT로 인증이 가능하다.

회원가입

셋중 어떤 routes를 써도 상관 없다. POST /register POST /signup POST /users register에는 아래와 같은 정보를 요구한다.

POST /register
{
  "email": "olivier@mail.com",
  "password": "bestPassw0rd"
}

회원가입시 자동으로 db.json에 값이 저장된다.

  "users": [
    {
      "email": "test@test.com",
      "password": "$2a$10$YEM/FjW29ESgJenmfIE9t.HWQ0zQB5k.X1y9dtMifedhy4sXSI/0m",
      "id": 1
    }
  ]

로그인

POST /login POST /signin login 또한 이메일과 비밀번호를 필요로한다.

POST /login
{
  "email": "olivier@mail.com",
  "password": "bestPassw0rd"
}

JWT토큰을 전달받는다.

{
  "accessToken": "xxxx-xxxxx-xxxx",
  "user": {
    "email": "test@test.com",
    "id": 1
  }
}

구현

import axios from "axios";
import React, { useEffect, useState } from "react";

function App() {
  const [token, setToken] = useState("");
  const [userId, setUserId] = useState("");
  const [email, setEmail] = useState("");
  const [password, setPassword] = useState("");
  const [signupEmail, setSignupEmail] = useState("");
  const [signupPassword, setSignupPassword] = useState("");


  const login = async () => {
    try {
      const { data } = await axios.post("http://localhost:4444/login", {
        email,
        password
      });
      console.log(data)
      setToken(data.accessToken);
      setUserId(data.user.id); 
      console.log(data.accessToken);
      alert("로그인 성공");
    } catch (error) {
      console.error("로그인 실패:", error.response?.data || error.message);
    }
  };

  const signup = async () => {
    try {
      await axios.post("http://localhost:4444/signup", {
        email: signupEmail,
        password: signupPassword
      });
      alert("회원가입이 완료되었습니다.");
      setSignupEmail("");
      setSignupPassword("");
    } catch (error) {
      console.error("회원가입 실패:", error.response?.data || error.message);
    }
  };

  return (
    <>

      {/* Signup Form */}
      <div>
        <h2>회원가입</h2>
        <input
          placeholder="이메일"
          type="email"
          value={signupEmail}
          onChange={(e) => setSignupEmail(e.target.value)}
        />
        <input
          placeholder="비밀번호"
          type="password"
          value={signupPassword}
          onChange={(e) => setSignupPassword(e.target.value)}
        />
        <button onClick={signup}>회원가입</button>
        <br />
      </div>

      {/* Login Form */}
      <div>
        <h2>로그인</h2>
        <input
          placeholder="이메일"
          type="email"
          value={email}
          onChange={(e) => setEmail(e.target.value)}
        />
        <input
          placeholder="비밀번호"
          type="password"
          value={password}
          onChange={(e) => setPassword(e.target.value)}
        />
        <button onClick={login}>로그인</button>
        <br />
      </div>


    </>
  );
}

export default App;

참고 https://www.npmjs.com/package/json-server-auth

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

나무자르기 문제를 풀고 이진탐색을 좀 집중공략할 필요가 있다고 생각이 들어서 당분간 이진탐색 문제를 집중적으로 풀려고 한다. 이 문제의 경우 아까와 비슷한 방식으로 이진탐색 > n번 탐색 의 알고리즘을 가진다.

풀이 방법

1. 집의 좌표를 정렬한다.
2. 좌표의 간격의 최댓값과 최솟값을 구한다.
   • 최소 간격: 1
   • 최대 간격: 좌표가 제일 큰 집 - 제일 작은 집
3. 간격을 이분탐색하며 적절한 간격을 구한다.
   • 만약 집 간의 간격이 이분탐색의 mid값보다 크면 cnt++
   • cnt가 m보다 많다면 result = mid(현재까지의 최대 간격)
     • min값을 mid로 설정하고 더 큰 간격이 있는지 이진탐색 시작
   • cnt가 m보다 작다면 max=mid로 설정하고 더 좁은 간격에서 m만큼의 공유기가 설치된 간격을 찾음

시간 복잡도

이진탐색($logm$) * n =$O(nlogn)$

구현

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

    int n;
    int m;
    int house[200000];

    cin >> n >> m;
    for(int i = 0; i < n; i++){
        cin >> house[i];
    }
    sort(house, house + n);

    int min = 1, max = house[n-1] - house[0];
    int result = 0;

    while (min <= max) {
        int mid = (min + max) / 2;
        int current = house[0];
        int cnt = 1; 

        for(int i = 1; i < n; i++){
            if(house[i] - current >= mid) {
                cnt++;
                current = house[i];
            }
        }

        if(cnt >= m){
            result = mid;
            min = mid + 1;
        } else {
            max = mid - 1;
        }
    }

    cout << result;
    return 0;
}

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

예전에 class3 에센셜 문제를 다 풀었었는데, 새롭게 한 문제가 생겼길래 풀어봤다. 제일 까다로웠던 부분이 나무의 길이가 '넘침'>'적음'>'넘침'으로 갈 때 종료 조건을 어떻게 할까였는데, 생각하다가 max-min>1일때(예를 들어 13~15면 middle이 14로 고정이므로)로 설정했다.

• 참고로 다른 사람들은 (min < max)로 값이 엇갈리는지 확인하는 방식도 사용했다. 왜 나는 문제 풀면서 이리 쉬운 생각을 못했을까.. 이진 탐색 연습이 많이 필요해보인다.

  풀이 과정

1. 나무의 최댓값을 찾는다.
2. 최댓값과 최솟값의 중간 값 만큼 나무를 자른다.
3. 자른 나무가 m보다 크다면 min을 middle로 바꾼다.
4. 자른 나무가 m보다 작으면 max를 middle로 바꾼다.
5. max-min이 1보다 작거나 같을때까지 반복한다.
   • max-min이 1이 되면 middle이 정해지기 때문에 더 할 필요가 없다.

시간 복잡도

이진탐색($logm$) * 나무의 개수($n$) = $O(nlogm)$

구현

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int n;
    long long m;
    int arr[1000000];

    cin>>n>>m;
    for(int i=0; i<n; i++){
        cin>>arr[i];
    }
    int min=0,max=*max_element(arr, arr + n);// 최대 나무 길이 찾기
    while (max-min>1) // 중간 값이 고정 됨
    {  
        int middle = (min+max)/2;
        long long cnt=0;
        for(int i=0; i<=n-1; i++){ // 나무 길이 합하기
            if(arr[i]-middle>0) cnt+= arr[i]-middle;
        }
        if(cnt == m) break;
        else if (cnt > m){ // m보다 합이 크면 >> 더 조금 잘라야 함
            min = middle;
        }
        else { //m 보다 합이 작으면 >> 더 많이 잘라야 함
            max = middle;
        }
    }
    cout<<(min+max)/2; 

    return 0;
}

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

나는 투 포인터를 활용해서 풀었는데, 이진탐색을 사용해서 푼 사람들도 많았다. 시간복잡도는 거의 동일하니 편한 방법을 쓰면 될 것 같다. 소요 시간만 놓고 보면 투포인터가 조금 더 빠르게 찍혔는데, 코드 길이 생각하면 그냥 이진탐색 쓰고 말듯. + 해시맵 방법도 있어서 해봤는데 구현 속도도, 시간복잡도도 이진탐색이 좋은 것 같다.

시간 복잡도

O($n^2 logm$) -> 아래에서 자세히 설명

투 포인터

풀이 과정

1. A부분합과 B부분합을 모두 구한다.
2. A부분합을 오름차순, B부분합을 내림차순 한다.
3. A부분합+B부분합이 t가 되는 경우를 구한다.
4. 만약 t가 된다면 t가 되는 A부분합의 개수 * B 부분합의 개수를 count에 더한다.
   • 경우의 수를 구하는 것 이기 때문
5. 만약 t보다 크다면 B부분합의 idx--, t보다 작다면 A부분합의 idx++

   구현

   #include <iostream>
   #include <vector>
   #include <algorithm>
   

using namespace std;

int main() { ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); int T, n, m; cin >> T >> n;

int A[1000];
for (int i = 0; i < n; i++) {
    cin >> A[i];
}
cin >> m;
int B[1000];
for (int i = 0; i < m; i++) {
    cin >> B[i];
}

// A의 모든 부분 배열의 합 계산
vector<int> sumA;
for (int i = 0; i < n; i++) {
    int current_sum = 0;
    for (int j = i; j < n; j++) {
        current_sum += A[j];
        sumA.push_back(current_sum);
    }
}

// B의 모든 부분 배열의 합 계산
vector<int> sumB;
for (int i = 0; i < m; i++) {
    int current_sum = 0;
    for (int j = i; j < m; j++) {
        current_sum += B[j];
        sumB.push_back(current_sum);
    }
}

// sumA는 오름차순, sumB는 내림차순으로 정렬
sort(sumA.begin(), sumA.end());
sort(sumB.begin(), sumB.end(), greater<int>());

long long count = 0;
int i = 0, j = 0;

// 투 포인터를 이용한 두 리스트의 합 비교
while (i < sumA.size() && j < sumB.size()) {
    int a = sumA[i];
    int b = sumB[j];
    int sum = a + b;

    if (sum == T) {
        long long countA = 0;
        long long countB = 0;

        // sumA[i]와 같은 값의 개수를 모두 카운트
        while (i < sumA.size() && sumA[i] == a) {
            countA++;
            i++;
        }

        // sumB[j]와 같은 값의 개수를 모두 카운트
        while (j < sumB.size() && sumB[j] == b) {
            countB++;
            j++;
        }

        // 두 개수의 곱만큼 결과에 더하기 (쌍을 구하는 것 이므로 곱함)
        count += countA * countB;
    } else if (sum < T) {
        i++;
    } else {
        j++;
    }
}

cout << count;
return 0;

}

## 이진 탐색

### 풀이 과정
1. A부분합과 B부분합을 구한다.
2. B부분합을 정렬한다.
3. t-A부분합을 저장한다.
4. t-A==B부분합이 되는 첫 지점과, 초과하는 부분을 찾는다(같은 부분합의 개수 구하기 위해)
5. count에 초과하는 부분 - 첫 지점을 한다.
### 구현
```cpp
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int T, n, m;
    cin >> T >> n;

    int A[1000];
    for (int i = 0; i < n; i++) {
        cin >> A[i];
    }
    cin >> m;
    int B[1000];
    for (int i = 0; i < m; i++) {
        cin >> B[i];
    }

    // A의 모든 부분 배열의 합 계산
    vector<int> sumA;
    for (int i = 0; i < n; i++) {
        int current_sum = 0;
        for (int j = i; j < n; j++) {
            current_sum += A[j];
            sumA.push_back(current_sum);
        }
    }

    // B의 모든 부분 배열의 합 계산
    vector<int> sumB;
    for (int i = 0; i < m; i++) {
        int current_sum = 0;
        for (int j = i; j < m; j++) {
            current_sum += B[j];
            sumB.push_back(current_sum);
        }
    }

    long long count = 0;   
    sort(sumB.begin(), sumB.end());
    for(auto& a : sumA){
        int tmp = T-a;
        auto l = lower_bound(sumB.begin(), sumB.end(), tmp);//tmp와 같은 첫 값
        auto r = upper_bound(sumB.begin(), sumB.end(), tmp);//tmp 첫 초과값
        count += (r-l);
    }

    cout << count;
    return 0;
}

시간 복잡도

• 이진 탐색

$m^2$번 정렬($logm$)하므로 O($m^2 log m$)

sort(sumB.begin(), sumB.end());

sumA번($n^2$) sumB($m^2$)을 이진탐색 하므로 O($n^2 log{m}$ )

for(auto& a : sumA){
    int tmp = T-a;
    auto l = lower_bound(sumB.begin(), sumB.end(), tmp);
    auto r = upper_bound(sumB.begin(), sumB.end(), tmp);
    count += (r-l);
}

=> O($(n^2+m^2)log{m}$)

• 투 포인터

$n^2$번 정렬하고 $m^2$번 정렬 하므로 O($n^2 log n + m^2 log m$)

sort(sumA.begin(), sumA.end());
sort(sumB.begin(), sumB.end());

투 포인터의 경우

0$n^2$까지, $m^2$0까지 이므로 O($n^2+m^2$)이므로 영향 X

int i = 0, j = sumB.size() - 1;

while (i < sumA.size() && j >= 0) {
    int sum = sumA[i] + sumB[j];

    if (sum == T) {
        long long countA = 0, countB = 0;
        int a = sumA[i], b = sumB[j];

        while (i < sumA.size() && sumA[i] == a) {
            countA++;
            i++;
        }

        while (j >= 0 && sumB[j] == b) {
            countB++;
            j--;
        }

        count += countA * countB;
    } else if (sum < T) {
        i++;
    } else {
        j--;
    }
}

=>O($n^2 log n + m^2 log m$)

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

무려 DP를 2번이나 구현해야하는 문제이다.

풀이 과정

1. 팰린드롬 구하기 palindrome[i][j] = palindrome[i + 1][j - 1];

   • 문자열의 범위(0~len)일때 ,구하려는 범위의 시작을 i, 끝을 j로 두자
   • 범위가 1일때: 무조건 true
   • 범위가 2일때: 두글자가 모두 같으면 true
   • 범위가 3이상 일때:양끝 글자가 같고, 그 속 글자들이 모두 같을때 (ㅁOOOOㅁ) 양 끝 안의 값이 같은지 어떻게 알지? -> i+1~j-1까지가 성립하는지 확인하면 됨

2. 최소 분할 개수 구하기 ans[j] = min(ans[j], ans[i-1] + 1)

   • 0~i까지의 범위 중 ture인 값을 구하기
   • 0~i까지 ture라면? 쪼개진게 없으므로 1
   • ji까지 ture라면? j까지 쪼개진거 + 1 (j+1i까지 새롭게 쪼개짐)

3. len-1의 최소 분할 개수 출력

구현

#include <iostream>
#include <vector>
#include <string>
#include <climits> 

using namespace std;

int main() {

    string s;
    cin >> s;
    int l = s.length();
    bool palindrome[2501][2501] = {false};
    for (int i = 0; i < l; i++) { // 1개일때 모두 트루
        palindrome[i][i] = true;  
    }

    for (int j = 1; j < l; j++) {
        for (int i = 0; i < j; i++) {
            if (s[i] == s[j]) {
                if (j - i == 1) {
                    palindrome[i][j] = true; // 2개일때(aa) 
                } else {
                    palindrome[i][j] = palindrome[i + 1][j - 1]; //OㅁㅁㅁㅁㅁO
                }
            }
        }
    }

    vector<int> ans(l, INT_MAX);  // 0부터 n까지의 최소 분할 개수 저장
    for (int j = 0; j < l; j++) {
        if (palindrome[0][j]) ans[j] = 1;  // 0~j까지가 true면 1로 끝.
        else {
            for (int i = 1; i <= j; i++) {
                if (palindrome[i][j]) ans[j] = min(ans[j], ans[i-1] + 1); // 분할됐으므로 +1
            }
        }
    }

    cout << ans[l - 1]; 

    return 0;
}

참고 https://byeo.tistory.com/entry/boj-1509-%ED%8C%B0%EB%A6%B0%EB%93%9C%EB%A1%AC-%EB%B6%84%ED%95%A0

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

알고리즘의 묘미랄까.. 다 풀고 남들의 코드를 보는데 나와 다른 부분이 있어 흥미로웠다.

1. 시작 지점을 구하는 방법
   • 내 방법: 입력을 받으며 테두리일 경우 '.'인 경우 따로 저장
   • 찾은 방법: '.'으로만 이루어진 테두리를 하나 만들어 감싼다. 예) (3,3)이 있다면, (4,4)로 만들고 테두리들을 모두'.'으로 채운다
2. 잠긴 문을 만났을 때, 어떻게 할 것인가
   • 내 방법: 일단 스탑하고, 열쇠를 만난다면 그동안의 visited를 초기화 하고 다시 시작한다.
   • 찾은 방법: 따로 저장해 뒀다가 열쇠를 찾으면 저장해 뒀던 것을 큐에 옮긴다.

즉, 내 알고리즘의 시간복잡도는 최악의 경우 키의 개수인 26 * 맵의 크기인 nm 이었고, 찾은 방법은 최악의 경우 nm이었다. 결국 상수곱이므로 크게 차이는 나지 않지만, 그래도 좀 더 좋은 알고리즘이 있다면 그 방법을 택하는게 좋은거니 찾은 방법을 기준으로 서술하겠다.

풀이 과정

1. 테두리를 '.'으로 채운 뒤 (1,1)부터 값을 입력 받는다.
2. 테두리를 시작 값으로 bfs를 실행한다. 만약 '$'를 찾으면 cnt를 증가시킨다.
3. 만약 문이 잠겨 있다면 queue[알파벳 번호]에 문의 좌표를 저장해 둔다.
4. 만약 키를 찾았다면 queue[알파벳 번호]에 저장되어 있던 좌표들을 bfs에 꺼낸다.
5. bfs 큐가 빌 때까지 반복한다.

구현

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <cstring>  
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        //map과 visited 초기화
        char map[102][102];  
        bool visited[102][102]; 
        memset(visited, false, sizeof(visited)); 
        memset(map, '.', sizeof(map));  

        //map 입력 - 테두리를 제외해 1부터 n까지에 채운다
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                cin >> map[i][j];
            }
        }


        // Key 설정
        string key;
        cin >> key;
        bool keyArr[26] = {false};
        if (key != "0") {
            for (char c : key) {
                keyArr[c - 'a'] = true;
            }
        }

        // BFS 
        int move[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
        queue<pair<int, int>> q;
        queue<pair<int, int>> door[26];

        q.push({0,0});
        visited[0][0] = true;

        int cnt = 0;
        while (!q.empty()) {
            int i = q.front().first;
            int j = q.front().second;
            q.pop();

            for (auto& mv : move) {
                int mi = i + mv[0];
                int mj = j + mv[1];
                if (mi < 0 || mi > n+1 || mj < 0 || mj > m+1) continue;
                if (map[mi][mj] != '*' && !visited[mi][mj]) {
                    char next = map[mi][mj];
                    if (next == '$') {
                        cnt++;
                    }
                    else if ('A' <= next && next <= 'Z') { // 문을 만날 경우
                        if (!keyArr[next - 'A']) {  // 키가 존재하지 않을 경우
                            door[next - 'A'].push({mi, mj}); 
                            continue;  
                        }
                    }
                    else if ('a' <= next && next <= 'z') { // 키를 만날 경우
                        if (!keyArr[next - 'a']) {
                            keyArr[next - 'a'] = true;
                            while (!door[next - 'a'].empty()) {
                                q.push(door[next - 'a'].front());
                                door[next - 'a'].pop();
                            }
                        }
                    }

                    q.push({mi, mj});
                    visited[mi][mj] = true;
                }
            }
        }

        cout << cnt << '\n'; 
    }

    return 0;
}

참고 https://yabmoons.tistory.com/97

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

소수를 구하고 누적합과 투포인터를 사용하면 쉽게 풀 수 있는 문제이다. 소수를 효과적으로 구하는 방법을 찾아 보니 에라토스테네스의 체라는 방법이 있었다.

풀이 과정

1. 에라토스테네스의 체를 활용해 소수를 구한다.
2. n까지의 소수들을 누적합 한다.
3. 투포인터를 사용하여 구간합을 구한다.(끝 값의 누적합 - 시작 값의 누적합)
   • 끝 값을 증가시키면 값이 커지고, 시작 값을 증가시키면 값이 작아진다.
4. 구간 합을 n과 비교한다.
   • n과 같으면 cnt++ 하고 끝 값을 증가 시킨다.
   • 누적 합이 n보다 크다면 시작 값을 증가 시킨다.
   • 누적 합이 n보다 작으면 끝 값을 증가 시킨다.
5. 끝 값이 소수들의 개수보다 커지면 종료한다.

구현

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;

    if (n <= 1) {
        cout << 0;
        return 0;
    }

    vector<bool> Pri(n + 1, true); 
    Pri[0] = Pri[1] = false; 

    for (int i = 2; i * i <= n; i++) {
        if (Pri[i]) {
            for (int j = i * i; j <= n; j += i) {
                Pri[j] = false;
            }
        }
    }

    vector<int> sums;
    sums.push_back(0); 

    for (int i = 2; i <= n; i++) {
        if (Pri[i]) {
            sums.push_back(sums.back() + i);
        }
    }

    int s = 0, e = 0;
    int cnt = 0;

    while (e < sums.size()) {
        int sum = sums[e] - sums[s];

        if (sum == n) {
            cnt++;
            e++;
        } else if (sum < n) {
            e++;
        } else {
            s++;
        }
    }

    cout << cnt;
    return 0;
}

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

으아아 아직 그리디 문제에 대한 감이 부족한 것 같다. 그리디 문제를 좀 많이 풀어봐야겠다.

보석의 무게와 배냥의 무게를 정렬해야겠다는 생각까지는 하였으나, 가치를 어떻게 정렬 해야할지 고민을 제대로 하지 않고 처음엔 보석과 배낭의 크기를 정렬하고 하나씩 증가하며 비교를 하려고 했는데, 양이 무지하게 많아 시간초과가 되었고, 풀이를 보니 기존 계산한 값을 우선순위 큐에 저장하는 그리디 문제였다.

시간 복잡도로 생각해보면, 우선순위 큐를 사용하지 않을 경우 n번의 보석을 k번 비교하므로 O(NK)이고, 우선순위 큐를 사용할 경우, O(logN)을 N (idx<n) 번 반복하므로 O(NlogN)이 된다.

풀이과정

1. 보석과 가방을 오름차순으로 정렬한다.
2. 가방의 용량이 작은 것 부터, 들어갈 수 있는 모든 보석들을 우선순위 큐에 저장한다.
   • 용량이 큰 가방은 작은 가방이 넣을 수 있는 보석을 모두 넣을 수 있기 때문이다.
3. 우선순위 큐에서 보석 하나를 빼 작은 가방에 넣는다.

예) 보석의 무게가 {1} {2} {3} {4} 라면, 무게가 2인 가방은 {1},{2}를 큐에 넣고 이들 중 가치가 큰 보석을 하나 빼온다. 그 후 무게가 4인 가방은 이미 있는 큐에 {3} {4}의 무게를 가진 보석을 넣고 그들 중 가장 가치가 큰 보석을 꺼낸다.

구현

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;

    vector<pair<int, int>> jewel(n);
    vector<int> bag(k);

    for (int i = 0; i < n; i++) {
        cin >> jewel[i].first >> jewel[i].second;
    }

    for (int i = 0; i < k; i++) {
        cin >> bag[i];
    }

    sort(jewel.begin(), jewel.end());
    sort(bag.begin(), bag.end());

    priority_queue<int> pq;
    long long sum = 0;
    int idx = 0;

    for (int i = 0; i < k; i++) {
        while (idx < n && jewel[idx].first <= bag[i]) {
            pq.push(jewel[idx++].second);
        }
        if (!pq.empty()) {
            sum += pq.top();
            pq.pop();
        }
    }

    cout << sum;

    return 0;
}

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

위상정렬을 이용한 문제이다.

도착 위치가 3 일때,{1}->{3} 으로 바로 가는 경우와 {1}->{2}->{3}으로 다른 노드를 거쳐 가는 경우가 존재할 때, 이를 어떻게 해결할지만 조심하면 바로 풀리는 문제이다.

풀이 과정

1. 현재 노드 까지의 최솟값을 구하기 위해선, 해결해야 할 노드들을 전부 동시에 해결해야 한다. ⇒ 위상정렬 알고리즘 사용

2. 현재 노드의 최솟값 해결해야 할 노드들 중, 가장 오래 걸린 노드 + 현재 노드를 계산 한다.(모든 노드를 동시에 해결한다면, 제일 오래 걸린 노드가 완료될 때까지 기다려야 하기 때문) ⇒ 기존에 있던 값을 활용하므로 다이나믹 프로그래밍

구현

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main()
{

    int t;
    cin>>t;
    while (t--)
    {
        int n,k;
        int build[1001]; // 짓는데 소요 시간
        int result[1001];
        int in[1001] = {0,}; // 진입 차수
        vector<vector<int>> edge(1000, vector<int>());
        cin>>n>>k;
        for(int i=1; i<=n; i++){
            cin>>build[i];
            result[i] = build[i];
        }
        for(int i=1; i<=k; i++){
            int s, e;
            cin>>s>>e;
            edge[s].push_back(e);
            in[e] ++;
        }
        int w;
        cin >> w;

        queue <int> q;
        for(int i=1; i<=n; i++){
            if(in[i] == 0){
                q.push(i);
            }
        }

        while (!q.empty())
        {
            int s = q.front();
            q.pop();
            for(auto& e : edge[s]){
                result[e] = max(result[e], result[s] + build[e]);
                if(--in[e] == 0){
                    q.push(e);
                }

            }
        }
        cout<<result[w]<<"\n";

    }




    return 0;
}