둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다릴 때 무한 대기에 빠지는 상황

✅자원 할당 그래프 : 교착 상태 상황 확인

교착 상태는 자원 할당 그래프를 통해 단순하게 표현할 수 있다. 자원할당 그래프는 어떤 프로세스가 어떤 자원을 사용하고 있고, 어떤 프로세스가 어떤 자원을 기다리고 있는지를 표현하는 그래프이다.

1. 프로세스는 원으로, 자원의 종류는 사각형으로 표현

2. 사용할 수 있는 자원의 개수는 자원 사각형 내의 점으로 표현

3. 프로세스가 자원을 할당 받아 사용중이라면 자원에서 프로세스를 향해 화살표를 표시

• 하드디스크의 자원 하나는 프로세스 A에 할당
• CPU의 자원은 프로세스 B,C에 할당

4. 프로세스가 어떤 자원을 기다리고 있다면 프로세스에서 자원으로 화살표를 표시

• 프로세스 D는 CPU의 할당을 기다리는 중

📌그렇다면 어느 경우에 교착 상태가 발생할까?

❗자원 할당 그래프가 원의 형태를 띠고 있을 때 교착상태가 발생한다

✅교착 상태 발생 원인

1️⃣상호 배제(mutual exclusion)

• 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상태

2️⃣점유와 대기(hold and wait)

• 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태

3️⃣비선점(nonpreemptive)

• 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하는 상태

4️⃣원형 대기(circularwait)

• 프로세스들이 원의 형태로 자원을 대기하는 형태

➡️ 위 네 가지 조건을 모두 만족할 때, 교착 상태가 발생할 수 있다.

✅교착 상태 해결 방법

☑️교착 상태 예방

• 애초에 교착 상태가 발생하지 않도록 하는 방식
• 교착 상태 발생 조건(상호 배제, 점유와 대기, 비선점, 원형 대기) 중 하나를 만족시키지 않는 방법으로 예방

1. 상호 배제를 없애보자

• 모든 자원을 프로세스들이 공유하도록 만들어야한다 → 현실적으로 불가능

2. 점유와 대기를 없애보자

• 특정 프로세스에 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 배분 →** 자원의 활용률 낮아짐**

3. 비선점을 없애보자

• 선점하여 사용할 수 있는 일부 자원에 대해서는 효과적이나 모든 자원이 선점 가능한 것이 아니다.
• 대표적으로 선점이 가능한 자원 : CPU

4. 원형 대기 조건을 없애보자

• 자원에 번호를 붙이고 오름차순으로 할당하면 원형대기는 발생하지 않는다.
• 1번 포크 → 2번 포크 → 3번 포크 →...→5번 포크에서 다시 1번 포크는 잡지 못한다.
• 위 3가지 방식에 비해 현실적인 방식이지만 어떤 자원에 어떤 번호를 붙이느냐에 따라 자원 활용률이 달라지게 된다.

➡️교착 상태를 사전에 방지하는 예방 방식은 교착 상태가 발생하지 않음을 보장할 수는 있지만, 여러 부작용이 따르게 된다.

☑️교착 상태 회피

• 교착 상태가 발생하지 않을 정도로만 자원을 할당하는 방식

안전 순서열

• 교착 상태 없이 안전하게 모든 프로세스들에 자원을 할당할 수 있게 하는 순서

안전 상태

• 교착 상태없이 모든 프로세스가 자원을 할당받고 종료될 수 있는 상태
• 안전 순서열이 있는 상태

불안전 상태

• 교착 상태가 발생할 수도 있는 상태
• 안전 순서열이 없는 상태

➡️교착 상태 회피는 항시 안전 상태를 유지하며 자원을 할당하는 방식으로, 대표적인 알고리즘에는 은행원 알고리즘이 있다.

☑️교착 상태 검출 후 회복

• 교착 상태 발생을 인정하고 사후에 조치하는 방식
• 교착 상태를 회복하는 방식에는 두 가지가 있다.

1. 선점을 통한 회복

• 교착 상태가 해결이 될 때까지 한 프로세스씩 자원을 몰아주는 방식

2. 프로세스 강제 종료를 통한 회복

• 교착 상태에 놓인 프로세스를 모두 강제 종료 하는 방식 → 단점 : 작업 내역을 잃을 위험성 존재
• 교착 상태가 해결될 때까지 한 프로세스씩 강제 종료하는 방식 → 단점 : 한 프로세스 종료 후 교촉 상태가 해결되었는지 확인하는 작업 반복 -> 오버헤드 발생

여러 프로세스가 공유 자원의 일관성을 유지하는 것

• 간단하게는 프로세스 수행 시기를 맞추는 것을 의미하며,
• 정확히는 프로세스 실행 순서를 제어하고 동시에 접근할 수 없는 자원에 하나의 프로세스만 접근하게 하는 것을 뜻한다.
• 프로세스는 이를 통해 데이터 일관성을 유지할 수 있다.

프로세스들의 수행 시기를 맞추는 것은 크게 아래 두가지를 일컫는다

• 실행 순서 제어 : 프로세스를 올바른 순서대로 실행하기
• 상호 배제 : 동시에 접근해서는 안되는 자원에 하나의 프로세스만 접근하게 하기

✅실행 순서 제어를 위한 동기화

reader writer problem

Writer라는 프로세스와 Reader라는 프로세스가 동시에 실행중이라고 가정해보자.

• Writer 프로세스 : Book.txt 파일에 값을 저장하는 프로세스
• Reader 프로세스 : Book.txt 파일에 저장된 값을 읽어 들이는 프로세스

• 이 두 프로세스는 아무 순서대로 실행되어서는 안되며, Writer프로세스의 실행이 끝나야 Reader프로세스의 실행이 가능하다.
• 즉, Writer프로세스가 Book.txt에 값을 저장하기도 전에 Reader 프로세스가 Book.txt를 읽어 들이는 것은 올바른 실행 순서가 아니며, Reader 프로세스는 Book.txt안에 값이 존재한다는 특정 조건이 만족되어야만 실행을 이어나갈 수 있다.

✅상호 배제를 위한 동기화

bank account problem

가령 계좌에 10만원이 저죽되어 있다고 가정해보자.

• 프로세스 A : 현재 저축된 금액에 2만원을 넣는 프로세스

• ** 프로세스 B** : 현재 저축된 금액에 5만원을 넣는 프로세스

• 프로세스 A와 B가 동시에 실행되었다고 가정할 경우, 당연히 우리는 17만원이 계좌에 남을것을 기대한다. 하지만 동기화가 제대로 이루어지지않은 경우 전혀 다른 결과가 나올 수 있다.
• 그 이유는 A와 B모두 잔액 이라는 데이터를 동시에 사용하는데, A가 끝나기도 전에 B가 잔액을 읽어버리고, 작업을 실행하였기 때문이다.
• 이렇게 동시에 접근해서는 안되는 자원에 동시에 접근하지 못하게 하는 것이 상호 배제를 위한 동기화이다.

생산자와 소비자 문제

• 생산자와 소비자는 총합이라는 데이터를 공유하고 있다.
• 생산자 : 버퍼에 물건을 넣은 후 물건의 총합에 해당하는 변수를 1증가 시킴
• 소비자 : 버퍼에 물건을 빼낸 후 물건의 총합에 해당하는 변수를 1감소 시킴

• 총합을 10으로 가정하고, 위와 같은 상태에서 생산자를 100,000번, 소비자를 100,000번 동시에 실행하면 우리는 총합 변수가 계속 10일 것이라고 기대한다.
• 하지만 막상 동시에 실행해보면 10이 아닌 다른수가 되거나 실행 중 오류가 난다.
• 이는 생산자 프로세스와 소비자 프로세스가 제대로 동기화되지 않았기 때문에 발생한 문제로, 총합이라는 데이터를 동시에 사용하지만 생산자와 소비자가 서로 작업이 끝나기도 전에 총합을 수정했기 때문이다.

✅공유 자원과 임계 구역

1️⃣공유 자원(shared resource)

• 여러 프로세스 혹은 스레드가 공유하는 자원

2️⃣임계 구역(critical area)

• 공유 자원에 접근하는 코드 중 동시에 실행하면 문제가 발생하는 코드 영역

3️⃣경쟁 조건(race condition)

• 여러 프로세스가 동시 다발적으로 임계 구역의 코드를 실행하여 문제가 발생하는 상황

✅임계 구역 문제 해결 조건

위와 같은 임계구역 문제는 아래 세가지 원칙 하에 해결한다. 즉, 상호 배제를 위한 동기화를 위해서는 아래 세가지 원칙이 반드시 지켜져야만 한다.

1️⃣상호 배제(mutual exclusion)

• 한 프로세스가 임계 구역에 진입했다면 다른 프로세스는 임계 구역에 들어올 수 없다.
• 임계구역 내에는 한번의 하나의 프로세스만 있어야함.

  2️⃣진행의 융통성(progress flexibility)

• 임계구역에 어떤 프로세스도 진입하지 않았다면, 진입하고자 하는 프로세스는 들어갈 수 있어야 함.

  3️⃣유한 대기(bounded waiting)

• 한 프로세스가 임계 구역에 진입하고 싶다면, 그 프로세스는 언젠가는 임계 구역에 들어올 수 있어야 함.
• ** 임계 구역에 들어오기 위해 무한정 대기해서는 안됨.**

💡동기화 기법

✅뮤텍스 락(Mutex lock)

락을 가진 단 한명만 접근 가능

• 상호 배제를 위한 동기화 도구
• 임계 구역에 진입하는 프로세스는 지금 임계 구역에 있음을 알리기 위해 뮤텍스 락을 이용해 임계 구역에 자물쇠를 걸어둠
• 다른 프로세스는 임계 구역이 잠겨 있다면 기다리고, 잠겨있지 않다면 임계구역에 진입 가능

  acquire();        // 자물쇠가 잠겨 있는지 확인, 잠겨 있지 않다면 잠그고 들어가기
  // 임계구역          // 임계구역에서의 작업 진행
  release();        // 자물쇠 반환

while (lock == true) /* 만약 임계 구역이 잠겨 있다면 */
; /* 임계 구역이 잠겨 있는지를 반복적으로 확인 */

• acquire() 에서는 임계 구역에 잠겨 있을 경우 프로세스가 반복적으로 lock을 확인한다. → 바쁜 대기(busy wait)발생(CPU 사이클 낭비)

✅세마포어(semaphore)

접근 가능 개수 제한

• 공유 자원이 여러 개 있는 상황에서도 적용이 가능한 동기화 도구

• Semaphore(n)

  • 사용 가능한 공유 자원의 개수를 나타내는 전역 변수

• P(wait)

  • 임계구역에 들어가기 전에 호출하는 함수
  • 자원을 요청하고 획득하는 코드 (잠금 수행)
  • RS가 0보다 크면(사용 가능한 자원 있다는 뜻) 1만큼 감소시키고 임계구역에 진입함
  • 0보다 작으면(사용 가능한 자원 없다는 뜻) 0보다 커질 때까지 기다림(PCB 대기큐 삽입)
  • block()은 wake_up() 신호를 보낼 때까지 기다리는 함수

• *V(signal) *

  • 임계구역에서 나올 때 호출하는 함수
  • 자원을 반환하고 해제하는 코드 (잠금 해제)
  • RS 값을 1 증가 시키고 세마포어에서 기다리는 프로세스에 임계구역에 진입해도 좋다는 wake_up() 신호 보냄

📌세마포어의 바쁜 대기 해결 방법

• 사용할 수 있는 자원이 없을 경우 대기 상태로 만듦 (해당 프로세스의 PCB를 대기 큐에 삽입)
• 사용할 수 있는 자원이 생겼을 경우 대기 큐의 프로세스를 준비 상태로 만듦 (해당 프로세스의 PCB를 대기 큐에서 꺼내 준비 큐에 삽입)

✅모니터(monitor)

• 공유 자원을 내부적으로 숨기고 공유 자원에 접근하기 위한 인터페이스만 제공함으로써 자원을 보호하고 프로세스 간에 동기화하는 방법

1️⃣ 임계구역에 접근하고자 하는 프로세스는 직접 P()나 V()를 사용하지 않고 모니터에 작업 요청을 함 2️⃣ 모니터는 요청받은 작업을 모니터 큐에 저장한 후 순서대로 처리하고 그 결과만 해당 프로세스에 알려줌

CPU 스케줄링은 언제 어떤 프로세스에 CPU를 할당할지 결정하는 작업을 의미한다. 이 알고리즘은 CPU 이용률은 높게, 주어진 시간에 많은 일을 하게, 준비 큐에 있는 프로세스는 적게, 응답시간은 짧게 설정하는 것을 목표로 한다.

✅프로세스 우선순위

• 입출력 작업이 많은 프로세스의 우선순위는 CPU 작업이 많은 프로세스의 우선순위보다 높다
• 입출력 작업이 많은 프로세스를 입출력 집중 프로세스, CPU 작업이 많은 프로세스를 CPU 집중 프로세스라한다.
• CPU 집중 프로세스는 CPU를 많이 사용해야 하는 프로세스이고, 입출력 집중 프로세스는 그렇지 않은 프로세스인데 두 프로세스 모두 동일한 빈도로 CPU를 사용하는 것은 비합리적이다.

• 그래서 운영체제는 프로세스의 중요도에 맞게 프로세스가 CPU를 이용할 수 있도록 우선순위를 부여한다.
• 각 프로세스의 PCB에 우선순위를 명시하고, 그 우선순위를 기준으로 먼저 처리할 프로세스를 결정하게 된다.

✅스케줄링 큐

• 운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것
• CPU를 사용할 다음 프로세스를 찾기 위해 모든 프로세스의 PCB를 확인하는 것은 비효율적이기 때문에 각 자원을 사용하고 싶어하는 프로세스들을 줄을 세워서 관리한다. 이 줄을 스케줄링 큐라고 부른다.

☑️준비 큐(Ready queue)

• CPU를 이용하고 싶은 프로세스들이 서는 줄을 의미

☑️대기 큐(waiting queue)

• 입출력장치를 이용하기 위해 대기 상태에 접어든 프로세스들이 서는 줄을 의미

✅선점형, 비선점형 스케줄링

☑️선점형 스케줄링

• 어떤 프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 CPU를 강제로 빼앗을 수 있는 스케줄링 방식
• 인터럽트 처리 같이 현재 실행 중인 작업을 중단하고 다른 프로세스가 CPU를 사용할 수 있다.
• 한 프로세스의 자원 독점을 막고 골고루 자원 배분이 가능하지만, 그만큼 문맥 교환 과정에서 오버헤드가 발생할 수 있다.
• RR(Round Robin), SRT, 다단계 큐, 다단계 피드백 큐

☑️비선점형 스케줄링

• 어떤 프로세스가 CPU를 점유하면 다른 프로세스가 이를 빼앗을 수 없는 스케줄링 방식
• 프로세스가 종료되거나 자발적으로 대기 상태에 들어가기 전까지는 계속 CPU를 사용할 수 있는 방식
• 문맥 교환으로 발생하는 오버헤드가 적지만, 긴 작업이 CPU를 오랫동안 점유하면 다른 프로세스의 응답성이 크게 저하될 수 있다.
• FCFS(First-Come, First-Served), 비선점형 SJF, HRN

💡CPU 스케줄링 알고리즘

✅FCFS(First Come First serverd)

• 준비 큐에 도착한 순서대로 CPU를 할당하는 비선점형 방식으로, 선입 선출 스케줄링이라고도 한다.
• 이 스케줄링 알고리즘은 처리 시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스들은 하염없이 기다리느라 시스템의 효율성이 떨어지는데, 이를 호위효과(Convoy effect)라고 한다.

✅SJF(Shortest Job First)

• 준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식으로, 최단 작업 우선 스케줄링이라고도 한다.
• 작은 작업을 먼저 실행하기 때문에 시스템의 효율성은 좋아지지만, 어떤 프로세스는 CPU 할당이 계속 연기될 수 있다 -> 기아 상태(Starvation)

📌에이징(Aging)기법

• 기아 상태를 해결하기 위한 대표적인 기법
• 오랫동안 대기한 프로세스의 우선 순위를 나이처럼 점차 높이는 방식
• 프로세스가 시간이 지남에 따라 노화되어 결국 CPU를 할당받을 기회를 보장함으로써 Starvation을 해소

✅HRN(Highest Response Ratio Next)

• SJF 스케줄링에서 발생할 수 있는 기아 상태를 해결하기 위해 만들어진 비선점형 알고리즘으로, 최고 응답률 우선 스케줄링이라고도 한다.
• SJF의 우선순위 판단 기준이 프로세스 실행 시간이었다면, HRN은 대기시간과 CPU의 사용시간(실행시간)을 고려하여 스케줄링 하는 방식이다.

✅RR(Round Robin)

• FCFS 스케줄링에 타임슬라이스라는 개념이 더해진 선점형 스케줄링 방식
• 타임 슬라이스 : 각 프로세스가 CPU를 사용할 수 있는 정해진 시간을 의미
• 타임 슬라이스가 지나치게 크면 FCFS와 다를 바 없어 호위효과가 생길 여지가 있고, 타임 슬라이스가 지나치게 작으면 문맥 교환에 발생하는 비용이 커져 평균 대기시간이 더 크게 나올 수 있다.

✅SRT(Shortest Remainig Time)

• ** SJF 스케줄링과 라운드 로빈 스케줄링을 혼합한 방식**으로 최소 잔류 시간 우선 스케줄링이라고도 한다.
• SJF 스케줄링의 선점형 버전
• 프로세스들은 정해진 타임슬라이스만큼 CPU를 사용하되, CPU를 사용할 다음 프로세스로는 남아있는 작업시간이 가장 적은 프로세스가 선택된다.
• SJF 스케줄링과 마찬가지로 운영체제가 프로세스 종료 시간을 예측하기 어렵고 기아 상태가 일어나기 때문에 잘 사용하지 않는다.

✅다단계 큐 스케줄링(Multi-Level Queue)

• 우선순위에 따라 준비 큐를 여러개 사용하는 방식
• 프로세스는 운영체제로부터 부여받은 우선순위에 따라 해당 우선순위의 큐에 삽입된다.
• 우선순위 큐는 라운드 로빈 방식으로 운영되므로 프로세스가 큐에 삽입되는 것만으로도 우선순위 큐에서의 PCB 우선순위가 결정된다.
• 우선순위는 고정 우선순위를 사용하며, 상단 우선순위 큐에 있는 모든 프로세스의 작업이 끝나야 다음 우선순위 큐의 작업이 시작된다.
• 우선순위가 높은 프로세스때문에 우선순위가 낮은 프로세스의 작업이 연기되는데, 이러한 문제를 해결하기 위해 다단계 피드백 큐 스케줄링이 등장한다.

✅다단계 피드백 큐 스케줄링(Multi-Level Feedback Queue)

• 다단계 큐 스케줄링 + 에이징 기법이 적용된 스케줄링 기법
• 다단계 큐 스케줄링과 다른점은** 프로세스들이 큐 사이를 이동**할 수 있다는 점이다.
• 새로 준비 상태가 된 프로세스가 있다면 우선 순위가 가장 높은 우선순위 큐에 삽입되고, 일정 시간(타임 슬라이스)동안 실행된다.
• 만약 프로세스가 해당 큐에서 실행이 끝나지 않는다면 다음 우선순위 큐에 삽입되어 실행됨을 반복한다. -> CPU를 오래 사용해야 하는 프로세스는 점차 우선순위가 낮아짐.
• 또한, 어떤 프로세스의 CPU 이용 시간이 길면 낮은 우선순위 큐로 이동시키고, 어떤 프로세스가 낮은 우선순위 큐에서 너무 오래 기다린다면 높은 우선순위 큐로 이동시킬 수 있는 알고리즘이다.
• 구현이 복잡하지만, 가장 일반적인 CPU 스케줄링 알고리즘으로 알려져있다.

프로세스와 스레드는 운영체제에서 프로그램이 실행될 때 사용되는 기본적인 단위이다. 웹 서버나 애플리케이션에서 동시에 여러 작업을 처리하려면 프로세스와 스레드에 대한 이해가 필요하다. 두 개념은 자원관리, 성능 최적화, 동시성 처리에 직접적인 영향을 주지만 관리와 자원사용 측면에서 차이점이 있다. 이 개념들을 이해하면 시스템에서 작업이 어떻게 실행되고 관리되는지 알 수 있다.

💡프로세스(Process)

✅프로세스란?

실행 중인 프로그램을 의미하며, 프로그램이 실행되면 운영체제가 메모리, CPU시간, 자원 등을 할당하여 독립적으로 실행되는 단위이다. 각각의 프로세스는 고유의 메모리 공간(코드, 데이터, 힙, 스택)을 가지고 있다.

✅프로세스의 특징

• 독립적인 메모리 공간 : 각 프로세스는 운영체제로부터 자신만의 고유한 메모리 공간(스택, 레지스터, 데이터 등)의 자원을 할당 받아 독립적으로 실행된다. 따라서 다른 프로세스와 메모리를 공유하지 않으며, 프로세스 간에는 서로의 데이터에 접근할 수 없다. 다른 프로세스와의 상호작용이 필요할 때는 프로세스 간 통신(IPC, Inter-Process Communication)을 사용해야한다. 프로세스 간 통신은 파이프, 소켓, 공유 메모리 등의 다양한 방법이 있다.

• 자원관리 : 프로세스는 운영체제로부터 실행에 필요한 시스템 자원(CPU, 메모리, 파일 디스크립터 등)을 할당받는다. 각 프로세스는 고유한 프로세스 ID(PID)를 통해 식별된다.

• 무거움 : 프로세스는 각각의 독립적인 자원을 가지므로 시스템 자원을 많이 사용하며 생성 및 종료에 시간이 오래걸리며, 문맥 교환 비용이 크다.

✅프로세스의 자원 구조

하나의 프로세스는 독립적인 메모리 공간을 가지며, 크게 4가지 메모리 영역으로 나누어져 있다.

• 코드(Code) : 프로그램의 실행 코드(기계어)
• 데이터(Data) : 전역 변수, 정적 변수 등
• 힙(Heap) : 런타임 중 동적으로 생성되는 객체(예시:new 연산자)
• 스택(Stack) : 함수 호출, 지역 변수, 매개 변수 등

또한, 프로세스는 위 4가지 메모리 영역 외에도 여러 자원을 독립적으로 소유한다.

• 파일 디스크립터 : 운영체제가 파일, 소켓, 파이프 등 I/O 자원을 식별하기 위해 부여하는 번호
• 프로세스ID(PID) : 운영체제가 각 프로세스를 고유하게 식별하기 위해 부여하는 고유한 번호
• PCB(프로세스 제어 블록) : 운영체제가 프로세스의 상태, 메모리 정보, CPU 레지스터 등을 저장해 프로세스를 관리하는 데 사용하는 데이터 구조로, 커널 영역에 생성된다.

코드 영역과 데이터 영역은 그 크기가 변하지 않아 정적 할당 영역이라고 부르며, 힙 영역과 스택 영역은 프로세스 실행 과정에서 그 크기가 변할 수 있는 영역이라 동적 할당 영역이라고 부른다.

✅프로세스의 예시

• 크롬을 두 번 실행하면 각각의 창은 독립적인 프로세스
• IDE, 메모장, 그림판 등은 각각 별도의 프로세스로 동작함

✅프로세스의 상태

여러개의 프로세스들은 빠르게 번갈아 가면서 실행되는데, 그 과중에서 하나의 프로세스는 여러 상태를 거치며 실행된다. 그리고 운영 체제는 프로세스의 상태를 PCB를 통해 인식하고 관리한다. 프로세스가 가질 수 있는 대표적인 상태는 5가지로 나눌 수 있다.

1. 생성 상태(new)

• 프로세스를 생성중인 상태
• 이제 막 메모리에 적재되어 PCB를 할당받은 상태
• 생성 상태를 거쳐 실행할 준비가 완료된 프로세스는 준비상태가 되어 CPU의 할당을 기다린다.

2. 준비 상태(ready)

• 당장이라도 CPU를 할당받아 실행할 수 있지만, 자신의 차례를 기다리고 있는 상태
• 차례가 되면 CPU를 할당받아 실행 상태가 된다.
• 준비 상태인 프로세스가 실행 상태로 전환되는 것을 디스패치(dispatch)라고 한다.

3. 실행 상태(running)

• CPU를 할당받아 실행중인 상태
• 실행 상태인 프로세스는 할당된 일정 시간 동안만 CPU를 사용할 수 있으며, 할당된 시간을 모두 사용하면 다시 준비상태로 전환된다.
• 실행 도중 입출력장치를 사용하여 입출력 장치의 작업이 끝날 때까지 기다려야 한다면 대기 상태가 된다.

4. 대기 상태(waiting/blocked)

• 프로세스는 실행 도중 입출력장치를 사용하는 경우가 있는데, 입출력 작업은 CPU에 비해 처리 속도가 느리다.
• 입출력 작업을 요청한 프로세스는 입출력장치가 입출력을 끝날때까지 기다려야 한다.
• 이렇게 입출력 작업을 기다리는 상태를 대기상태라고 한다.
• 입출력 작업이 완료되면 해당 프로세스는 다시 준비 상태로 CPU 할당을 기다린다.

5. 종료 상태(terminated)

• 프로세스가 종료된 상태
• 프로세스가 종료되면 운영체제는 PCB와 프로세스가 사용한 메모리를 정리한다.

💡스레드(Thread)

✅프로세스의 한계

과거에는 프로그램을 실행할 때 하나의 프로세스만을 사용했었다. 하지만 기술이 발전됨에 따라 프로그램이 복잡해지고 다채로워지면서 프로세스 작업 하나만을 사용해서 프로그램을 실행하기에는 한계가 있었고, 멀티 작업을 위해 여러 개의 프로세스를 만들게 되면 그만큼 메모리를 차지하고 CPU에서 할당받는 자원이 중복되게 될 것이다. 스레드는 이러한 프로세스 특성의 한계를 해결하기 위해 탄생하였다.

✅스레드란?

스레드란 하나의 프로세스 내에서 동시에 진행되는 작업 갈래, 흐름의 단위를 말한다. 하나의 프로세스는 여러 개의 스레드를 가질 수 있으며, 이 스레드들은 프로세스의 자원을 공유하면서 동시에 실행될 수 있다.

✅스레드의 특징

• 메모리 공유 : 스레드는 같은 프로세스 내의 메모리(코드, 데이터, 파일 등)를 공유한다. 즉, 프로세스 내에서 여러 스레드가 같은 데이터에 접근하고 수정할 수 있다. 이로 인해 스레드 간의 통신이 빠르고 효율적이지만, 동기화 문제가 발생할 수 있다.
• 빠르고 가벼움 : 스레드는 독립적인 자원을 갖지 않기 때문에 프로세스에 비해 생성과 종료가 빠르고 자원을 적게 사용하며 문맥교환이 빠르다. 하지만 메모리를 공유하기 때문에 동시성 문제가 발생할 수 있다.
• 독립적인 실행 흐름 : 스레드는 각자 독립적인 실행 흐름(스틱)을 가지며, 동시에 여러 작업을 수행할 수 있다. 이를 통해 CPU 활용도를 높일 수 있다.

📌Context Switching(문맥교환)

CPU가 작업A를 실행하다가 시간이 다 되어 작업B로 CPU 사용을 양보한다고 가정해보도록 하자. 이 상황에서 바로 직전까지 실행된 작업 A는 프로그램 카운터와 각종 레지스터 값, 메모리 정보 등 지금까지의 정보를 백업해야 한다. 그래야 다음 작업 차례에서 이전까지 실행했던 내용에 이어 다시 실행을 재개할 수 있으니까! 이러한 중간 정보를 문맥(Context)라고 한다. 문맥은 PCB에 저장되며, 실행 순서가 넘어갈 때마다 실행중인 작업의 문맥을 PCB에 백업하고, 새로운 작업을 실행하기 위해 문맥을 PCB에 복구하여 새로운 작업을 실행하는 것을 문맥 교환(Context Switching)이라고 한다. 문맥 교환 시 자원과 시간이 소모되며, 문맥 교환을 너무 자주 하게 되면 오버헤드가 발생할 수 있다. 스레드 간 전환은 가볍지만, 프로세스 간 전환은 무겁고 비용이 크다.

✅스레드의 자원 구조

스레드는 프로세스 내부의 실행 단위이기 때문에, 같은 프로세스 안의 여러 스레드들은 일부 자원을 공유하고, 일부는 개별로 소유한다. 스레드는 프로세스 자원을 공유한 채 실행에 필요한 최소한의 정보만으로 실행된다.

📍스레드 간 공유 자원

• 코드 영역
• 힙 영역
• 전역/정적 변수

📍스레드 개별 소유 자원

• 스택 영역(지역변수, 호출기록)
• 레지스터, PC(프로그램 카운터)
• 스레드 ID, 상태

✅스레드의 예시

• 크롬 한 프로세스 내에서 각 탭은 별도의 스레드로 동작
• 웹서버가 여러 요청을 처리할 때 각각의 요청을 별도의 스레드로 처리

☑️프로세스와 스레드의 차이

💡멀티 프로세스

✅멀티 프로세스란

멀티 프로세스란 하나의 작업을 여러개의 프로세스로 나누어 동시에 실행하는 방식을 말한다.

✅멀티 프로세스의 특징

⭕멀티 프로세스의 장점

• 메모리 침범 문제를 OS차원에서 해결가능
• 여러 자식 프로세스 중 하나에 문제가 발생하여도 그 프로세스만 타격 -> 영향이 확산되지 않음

❗멀티 프로세스의 단점

• Context Switching 과정에서 캐쉬 메모리 초기화 등 무거운 작업이 진행되고 많은 시간이 소모되는 등의 오버헤드가 발생하게 됨
• 프로세스는 각각의 독립된 메모리 영역을 할당받기 때문에 프로세스 사이에서 공유하는 메모리가 없어 Context Switching이 발생하면 캐쉬에 있는 모든 데이터들을 모두 리셋하고 다시 캐쉬 정보를 불러와야 함
• 프로세스 간의 복잡한 통신 (IPC) 가 필요함

💡멀티스레드

✅멀티 스레드란

멀티 스레드란 하나의 프로세스 안에서 여러 스레드가 동시에 실행되며 작업을 분담하는 방식이다.

✅멀티 스레드의 특징

⭕멀티 스레드의 장점

• 메모리 공간, 시스템 자원의 효율성 증가
• Data, Heap 영역을 이용해 데이터를 주고 받으므로 스레드간 통신이 간단함
• context switching시 비용이 적음(교환해야 할게 적으니까) -> 시스템 처리량 향상, 프로그램 응답 시간 단축됨

❗멀티 스레드의 단점

• 서로 다른 스레드가 Stack을 제외한 메모리 공간을 공유하기 때문에 동기화 문제가 발생할 수 있음
• 하나의 스레드에 문제가 생기면 전체 프로세스가 영향을 받음
• 주의 깊은 설계가 필요하며 디버깅이 까다로움

문제 링크

문제 설명

평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA”는 DNA 문자열이 아니지만 “ACCA”는 DNA 문자열이다. 이런 신비한 문자열에 완전히 매료된 민호는 임의의 DNA 문자열을 만들고 만들어진 DNA 문자열의 부분문자열을 비밀번호로 사용하기로 마음먹었다.

하지만 민호는 이러한 방법에는 큰 문제가 있다는 것을 발견했다. 임의의 DNA 문자열의 부분문자열을 뽑았을 때 “AAAA”와 같이 보안에 취약한 비밀번호가 만들어 질 수 있기 때문이다. 그래서 민호는 부분문자열에서 등장하는 문자의 개수가 특정 개수 이상이여야 비밀번호로 사용할 수 있다는 규칙을 만들었다.

임의의 DNA문자열이 “AAACCTGCCAA” 이고 민호가 뽑을 부분문자열의 길이를 4라고 하자. 그리고 부분문자열에 ‘A’ 는 1개 이상, ‘C’는 1개 이상, ‘G’는 1개 이상, ‘T’는 0개 이상이 등장해야 비밀번호로 사용할 수 있다고 하자. 이때 “ACCT” 는 ‘G’ 가 1 개 이상 등장해야 한다는 조건을 만족하지 못해 비밀번호로 사용하지 못한다. 하지만 “GCCA” 은 모든 조건을 만족하기 때문에 비밀번호로 사용할 수 있다.

민호가 만든 임의의 DNA 문자열과 비밀번호로 사용할 부분분자열의 길이, 그리고 {‘A’, ‘C’, ‘G’, ‘T’} 가 각각 몇번 이상 등장해야 비밀번호로 사용할 수 있는지 순서대로 주어졌을 때 민호가 만들 수 있는 비밀번호의 종류의 수를 구하는 프로그램을 작성하자. 단 부분문자열이 등장하는 위치가 다르다면 부분문자열이 같다고 하더라도 다른 문자열로 취급한다.

입력

첫 번째 줄에 민호가 임의로 만든 DNA 문자열 길이 |S|와 비밀번호로 사용할 부분문자열의 길이 |P| 가 주어진다. (1 ≤ |P| ≤ |S| ≤ 1,000,000)

두번 째 줄에는 민호가 임의로 만든 DNA 문자열이 주어진다.

세번 째 줄에는 부분문자열에 포함되어야 할 {‘A’, ‘C’, ‘G’, ‘T’} 의 최소 개수가 공백을 구분으로 주어진다. 각각의 수는 |S| 보다 작거나 같은 음이 아닌 정수이며 총 합은 |S| 보다 작거나 같음이 보장된다.

출력

첫 번째 줄에 민호가 만들 수 있는 비밀번호의 종류의 수를 출력해라.

예제

✅나의 문제 풀이

public class Main {
    static int checkArr[];
    static int myArr[];
    static int checkSecret;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());

        //DNA 문자열의 길이
        int S = Integer.parseInt(st.nextToken());
        //부분 문자열의 길이
        int P = Integer.parseInt(st.nextToken());
        //정답 값 저장받을 변수
        int Result = 0;
        //비밀번호 체크 배열(A가 몇개 필요한지, G가 몇개 필요한지 등 기준 저장 하는 배열. 예시에서는 2 0 1 1)
        checkArr = new int[4];
        //현재 상태 저장할 배열(현재 A가 몇개있고, G가 몇개 있고.. myArr의 값이 checkArr와 같으면 조건 충족되는것 ->checkSecret++)
        myArr = new int[4];
        //4개중 현재 몇개가 비밀번호 요건에 충족되는지 카운트 하는 변수 -> checkSecret이 4면 result ++
        checkSecret = 0;
        //문자열을 입력받을 배열
        char[] A = bf.readLine().toCharArray();

        st = new StringTokenizer(bf.readLine());
        //각각의 dna가 몇개 필요한지 입력 받는 for문(2 0 1 1)
        for (int i = 0; i < 4; i++) {
            checkArr[i] = Integer.parseInt(st.nextToken());
            //checkArr[i]가 0이면 해당 DNA는 없어도됨 -> 이미 조건이 충족되었으니 checkSecret++
            if (checkArr[i] == 0)
                checkSecret++;
        }

        //초기(첫번째) 부분 문자열 처리 부분
        for (int i = 0; i < P; i++) {
            Add(A[i]);
        }

        //checkSecret이 4 -> 조건 모두 충족하여 유효한 비밀번호임
        if (checkSecret == 4)
            Result++;

        // 슬라이딩 윈도우 처리 부분
        int left = 0;   //왼쪽 값
        int right = P;  //오른쪽 값
        while(right < S){   //배열 인덱스는 0부터 시작이므로 right < S까지
            Add(A[right++]);  
            Remove(A[left++]);  
            if (checkSecret == 4)
                Result++;
        }
        System.out.println(Result);
        bf.close();
    }

    //새로 들어운 문자를 처리해주는 메서드
    //각각의 문자열 중 같은게 있으면 myArr[]에 1을 더해주고, myArr[]과 checkArr[]가 같다면 checkSecret++
    private static void Add(char c) {
        switch (c) {
            case 'A':
                myArr[0]++;
                if (myArr[0] == checkArr[0])
                    checkSecret++;
                break;
            case 'C':
                myArr[1]++;
                if (myArr[1] == checkArr[1])
                    checkSecret++;
                break;
            case 'G':
                myArr[2]++;
                if (myArr[2] == checkArr[2])
                    checkSecret++;
                break;
            case 'T':
                myArr[3]++;
                if (myArr[3] == checkArr[3])
                    checkSecret++;
                break;
        }
    }

    //제거되는  문자를 처리해주는 메서드
    //각각의 문자열 중 같은게 있으면 myArr[]에 1을 빼주고, myArr[]과 checkArr[]가 같다면 checkSecret--
    private static void Remove(char c) {
        switch (c) {
            case 'A':
                if (myArr[0] == checkArr[0])
                    checkSecret--;
                myArr[0]--;
                break;
            case 'C':
                if (myArr[1] == checkArr[1])
                    checkSecret--;
                myArr[1]--;
                break;
            case 'G':
                if (myArr[2] == checkArr[2])
                    checkSecret--;
                myArr[2]--;
                break;
            case 'T':
                if (myArr[3] == checkArr[3])
                    checkSecret--;
                myArr[3]--;
                break;
        }
    }
}

• 이 문제는 크기를 유지한 상태로 한칸씩 이동하면서 조건에 맞는지 탐색하는 슬라이딩 윈도우를 이용하는 문제이다.
• 주어진 DNA 문자열을 대조하면서 조건에 맞는지 탐색해야한다.

✅문제 핵심 짚어보기

필요한 변수 설정

이 문제는 변수가 많아서 헷갈리기 쉬운데, 변수를 먼저 짚고 넘어가보도록하자. 첫째줄에는 입력받을 전체 DNA 문자열의 길이와 부분 문자열의 길이를 입력받고, 두번째 줄에는 DNA 문자열을 입력받는다. 마지막으로 세번쨰 문자열은 부분 문자열에 포함되어야 할 A,C,G,T의 최소 개수를 입력받는다.

• 첫째줄 : 입력받을 전체 DNA 문자열의 길이(S), 부분 문자열의 길이(P)
• 둘째줄 : DNA 문자열(char[] A)
• 셋째줄 : 부분 문자열에 포함되어야 할 A,C,G,T의 최소 개수(int[] checkArr)
• 결과 값을 입력받을 변수(result)

예제에 나온 걸로 파악했을때 변수는 이렇게 5가지이다. 하지만 문제풀이를 할때 변수가 더 필요한데 먼저, 현재 A가 몇개있고, G가 몇개 있고 등 현재 상태를 저장할 배열 int[] myArr가 필요하다. 또, myArr의 값과 checkArr의 값이 같으면 해당 문자는 조건이 충족되는 것이므로 그걸 체크할 변수 checkSecret도 필요하다. checkSecret이 4면 해당 비밀번호는 유효한 비밀번호 이므로 result를 1증가시켜주면 된다.

☑️흐름 파악 하기

1. 우선 입력받은 전체 DNA 문자열을 A배열에 저장하고, 비밀번호 체크 배열인 checkArr에 각 문자의 최소 개수를 저장한다.

2. 슬라이딩 윈도우에 포함된 문자열로 현재 상태 배열을 만들고, 현재 상태 배열과 비밀 번호 체크 배열을 비교하여 유효한 비밀번호 인지 판단한다.

• p크기 만큼 문자열을 잘라서 비교해봐야하므로 p크기만큼의 부분 문자열을 A 배열에서 가져온다.
• 그리고 비밀번호 체크 배열(checkArr)와 현재상태 배열(myArr)를 비교하여 조건에 부합하면 각 문자마다 checkSecret에 1을 더해준다.
• 예제에서는 A의 조건은 2개이상이지만 현재 상태는 1개 이므로 조건에 부합하지 않는다.

3. 윈도우를 한칸씩 이동하며 현재 상태 배열을 업데이트한다. 현재 상태 배열을 업데이트할 때는 빠지는 문자열(왼쪽에서 한칸), 추가되는 신규 문자열(오른쪽에서 한칸)만 확인하여 업데이트 하는 방식으로 진행한다.

• 윈도우를 한칸씩 이동하게 되면 맨 왼쪽의 C가 빠지고, 맨 오른쪽의 G가 추가된다.
• 마찬가지로 비밀번호 체크 배열(checkArr)와 현재상태 배열(myArr)를 비교하여 조건에 부합하면 각 문자마다 checkSecret에 1을 더해준다.
• 위 예제도 유효한 비밀번호가 아니다.

4. A 배열의 끝에 도달할 때 까지 한칸씩 이동한다.

☑️코드 순서대로 뜯어보기

입력받을 값을 모두 입력받았다는 전제하에 코드를 뜯어보자.(A,C,G,T의 최소 개수 입력 제외)

1. 문자 갯수(A,C,G,T 총 4)만큼 for문을 돌려 checkArr에 저장

//각각의 dna가 몇개 필요한지 입력 받는 for문(2 0 1 1)
for (int i = 0; i < 4; i++) {
    checkArr[i] = Integer.parseInt(st.nextToken());
    //checkArr[i]가 0이면 해당 DNA는 없어도됨 -> 이미 조건이 충족되었으니 checkSecret++
    if (checkArr[i] == 0)
        checkSecret++;
}

• 마지막 줄에 입력받는 A,C,G,T의 최소 개수를 for문을 돌려서 checkArr에 저장한다.
• 순서대로 A,C,G,T이며, 첫번째 예시를 예로 들면 (2 0 1 1)
• checkArr[0] = 2, checkArr[1] = 0, checkArr[2] = 1, checkArr[1] 이 저장된다.
• 만약 해당 값이 0이라면(checkArr[1] = 0) 해당 DNA는 문자열에 없어도 된다. 즉, 이미 이 문자는 조건이 충족된것이므로 checkSecret을 증가시켜준다.

2. 초기(첫번째)부분 문자열을 처리한다.

//초기(첫번째) 부분 문자열 처리 부분
for (int i = 0; i < P; i++) {
    Add(A[i]);
}

//checkSecret이 4 -> 조건 모두 충족하여 유효한 비밀번호임
if (checkSecret == 4) Result++;

//새로 들어운 문자를 처리해주는 메서드
//각각의 문자열 중 같은게 있으면 myArr[]에 1을 더해주고,
//myArr[]과 checkArr[]가 같다면 checkSecret++
private static void Add(char c) {
    switch (c) {
        case 'A':
            myArr[0]++;
            if (myArr[0] == checkArr[0])
                checkSecret++;
            break;
        case 'C':
            myArr[1]++;
            if (myArr[1] == checkArr[1])
                checkSecret++;
            break;
        case 'G':
            myArr[2]++;
            if (myArr[2] == checkArr[2])
                checkSecret++;
            break;
        case 'T':
            myArr[3]++;
            if (myArr[3] == checkArr[3])
                checkSecret++;
            break;
        }
    }

• 첫번째 문자열은 슬라이딩하지 않고 바로 각 문자만 비밀번호 체크 배열(checkArr)와 비교해준다.
• case 문을 이용해서 각각 어떤 문자인지 분기를 나누고, 현재상태 배열(myArr)을 업데이트 해준 후 현재상태 배열(myArr)와 비밀번호 체크 배열(checkArr)의 값이 같으면 checkSecret에 1을 더해준다.
• 그 후, checkSecret이 4가 되면 해당 비밀번호는 유효한 비밀번호이므로 결과값을 저장하는 result에 1을 더해준다.

3. 슬라이딩 윈도우를 이용하여 처리한다.

 // 슬라이딩 윈도우 처리 부분
int left = 0;   //왼쪽 값
int right = P;  //오른쪽 값
while(right < S){   //배열 인덱스는 0부터 시작이므로 right < S까지
    Add(A[right++]);  
    Remove(A[left++]);  
    if (checkSecret == 4)
        Result++;
    }
    System.out.println(Result);
    bf.close();
}

//제거되는  문자를 처리해주는 메서드
//각각의 문자열 중 같은게 있으면 myArr[]에 1을 빼주고
//myArr[]과 checkArr[]가 같다면 checkSecret--
private static void Remove(char c) { 
    switch (c) {
        case 'A':
             if (myArr[0] == checkArr[0])
                 checkSecret--;
            myArr[0]--;
            break;
        case 'C':
            if (myArr[1] == checkArr[1])
                checkSecret--;
            myArr[1]--;
            break;
        case 'G':
             if (myArr[2] == checkArr[2])
                 checkSecret--;
            myArr[2]--;
             break;
        case 'T':
            if (myArr[3] == checkArr[3])
                checkSecret--;
            myArr[3]--;
            break;
    }
    }
}

• 초기부분이 지나면 한칸씩 이동하여 슬라이딩하고, 문자를 체크해야한다.
• 슬라이딩 부분만 빼면 초기 문자 비교는 똑같다.
• 우선 슬라이딩 시작과 끝을 알리는 left, right 변수를 선언하고, right변수가 전체 문자열의 길이(S)보다 작을동안 while문을 돌려준다. -> right < S 로 범위를 설정한 이유는 배열 인덱스는 0부터 시작이므로!
• 그 후, 한칸 옮겨간 right는 포함하고, 한칸 빠진 left는 빼준다.
• Add메서드를 이용해서 A[right]를 추가해주고, 후위연산으로 right를 증가시킨다.
• Remove메서드를 이용해서 A[left]는 제거하고, 후위연산으로 left를 감소시킨다.

4. 결과값을 출력한다.

• result값을 출력한다.

문제 링크

문제 설명

N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.

N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.

수의 위치가 다르면 값이 같아도 다른 수이다.

입력

첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 A_i가 N개 주어진다. (|A_i| ≤ 1,000,000,000, A_i는 정수)

출력

좋은 수의 개수를 첫 번째 줄에 출력한다.

예제

나의 문제 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        //N : 수의 개수
        int N = Integer.parseInt(br.readLine());
        int count = 0;

        StringTokenizer st = new StringTokenizer(br.readLine());

        long[] arr = new long[N];
        for (int i = 0; i < N; i++) {
            arr[i]= Long.parseLong(st.nextToken());
        }
        //배열 정렬
        Arrays.sort(arr);

        for(int k=0; k<N; k++){
            long find = arr[k];   //찾고자하는값
            int start = 0;
            int end = N-1;
            while (start < end){
                //합이 같으면
                if(arr[start] + arr[end] == find){
                    //find가 서로 다른 두 수의 합인지 체크 -> find가 5이고, start 0, end가 5일때와 같은 예외처리
                     if(start != k && end != k){
                         count ++;
                         break;
                     }else if(start==k){    //포인터중 하나가 타깃 k를 가리키면 그 포인터를 한칸 움직인다.
                        start ++;
                     }else if(end == k){
                         end --;
                     }
                //더한 값이 find보다 작으면 더 큰값을 만들기 위해 start++
                }else if(arr[start] + arr[end] < find){
                    start++;
                //더한 값이 find보다 크면 더 작은값을 만들기 위해 end--    
                }else{
                    end--;
                }
            }
        }
        System.out.println(count);
    }
}

• N개의 수 중에서 어떤 수가 다른 수 두 개의 합을 나타내는 갯수를 찾는것이다.
• 이것도 정렬 + 투포인트 알고리즘을 사용한다.
• 단, 정렬된 데이터에서 자기자신을 좋은 수 만들기에 포함하면 안되므로 예외처리해줘야한다!

문제 풀어보기

1. 수를 입력받아 배열 A에 저장한 후 정렬한다.

2. 투 포인터 i,j를 배열 A의 양쪽 끝에 위치시키고, 투 포인터 이동 원칙을 활용해 탐색을 수행한다.(판별의 대상이 되는 수는 K라 한다.)

(1) A[i]+A[j] == find(찾고자 하는 값)이면

• 서로 다른 두수의 값인지 체크 후 서로 다른 값이면 count++후 탐색 종료
• 탐색 종료를 하는 이유는 좋은수가 되는 순서쌍의 개수를 찾는 것이 아니라, 좋은 수의 "개수"를 세는것이기 때문에 k가 이미 좋은 수라고 판명났기 때문에 탐색종료 하는것!
• 만약 find와 값은 같지만 i가 타깃 인덱스 k와 같으면 i++, j와 타깃 인덱스 k가 같으면 j--

(2) A[i]+A[j] < find 이면

• 더 큰값을 만들기 위해 i++

(3) A[i]+A[j] > find 이면

• 더 작은 값을 만들기 위해 j--

문제 링크

문제 설명

주몽은 철기군을 양성하기 위한 프로젝트에 나섰다. 그래서 야철대장을 통해 철기군이 입을 갑옷을 만들게 하였다. 야철대장은 주몽의 명에 따르기 위하여 연구에 착수하던 중 아래와 같은 사실을 발견하게 되었다.

갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다. 갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 되면 갑옷이 만들어 지게 된다. 야철대장은 자신이 만들고 있는 재료를 가지고 갑옷을 몇 개나 만들 수 있는지 궁금해졌다. 이러한 궁금증을 풀어 주기 위하여 N(1 ≤ N ≤ 15,000) 개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고유한 번호들이 공백을 사이에 두고 주어진다. 고유한 번호는 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 갑옷을 만들 수 있는 개수를 출력한다.

예제

나의 문제 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        //N : 재료의 갯수
        int N = Integer.parseInt(br.readLine());

        //M : 갑옷이 완성되는 번호의 합
        int M = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());

        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i]= Integer.parseInt(st.nextToken());
        }
        //배열 정렬
        Arrays.sort(arr);

        int count = 0;
        int start = 0;
        //배열 인덱스는 0부터 시작이므로 끝 값은 N-1
        int end = N-1;

        //start가 end보다 작을때까지
        while(start<end){
            if(arr[start]+arr[end] < M){
                start++;
            }else if(arr[start]+arr[end] > M){
                end--;
            }else{
                count++;
                start++;
                end--;
            }
        }
        System.out.println(count);
    }
}

• 투포인터 + 배열 정렬을 쓰는 문제이다.
• 각각의 재료는 한번쓰면 없어진다고 생각해야한다.

문제 풀어보기

1. 재료 데이터를 배열에 저장한 후 오름차순으로 정렬한다.

2. 투포인터를 각각 양쪽 끝에 위치 시킨 후, 조건에 따라 포인터를 이동시키고, 포인터가 만날때 까지 반복한다.

(1) 더한 값이 M보다 작을 때

• i의 값을 1 증가시킨다. -> 더 큰 값을 찾아야하므로!

(2) 더한 값이 M과 같을 때

• count값을 1 증가시키고, i는 1증가, j는 1 감소 시킨다.

(3) 더한 값이 M보다 클 때

• j의 값을 1 감소시킨다. -> 더 작은 값을 찾아야 하므로

문제 링크

문제 설명

어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한다. 이때, 사용하는 자연수는 N이하여야 한다.

예를 들어, 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5의 4가지가 있다. 반면에 10을 나타내는 방법은 10, 1+2+3+4의 2가지가 있다.

N을 입력받아 가지수를 출력하는 프로그램을 작성하시오.

입력

첫 줄에 정수 N이 주어진다.

출력

입력된 자연수 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 출력하시오

✅나의 문제 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        //N : 입력 받을 수의 갯수
        int N = Integer.parseInt(st.nextToken());

        //예시의 경우, 15처럼 연속된 수가 아닌 하나의 수로도 합을 나타낼수 있기때문에 미리 1세팅
        int count = 1;
        //start와 end가 1로 시작하므로, sum도 1로 초기값 세팅
        int sum = 1;
        int start = 1;
        int end = 1;
        //end가 N이 아닐때까지 출력
        // (end가 N일때는 마지막 값에서 하나의 수로도 합을 나타낼 수 있기 때문에-> 이 경우는 이미 count = 1로 미리 세팅해둠)
        while (end != N){
            //sum과 n이 같으면 count ++, end 한칸 뒤로 옮긴 후 그값을 sum에 더해줌
            if(sum==N){
                count++;
                end ++;
                sum = sum + end;

            //sum이 N보다 크면 sum에서 start를 빼주고, start 한칸 뒤로 옮김    
            }else if (sum > N){
                sum = sum - start;
                start++;

            //sum이 N보다 작으면 end를 한칸 뒤로 옮기고, sum에 end를 더함    
            }else {
                end++;
                sum=sum+end;
            }
        }
        System.out.println(count);
    }
}

• 연속된 자연수의 합을 구하는 문제이므로 시작인덱스와 종료 인덱스를 지정하는 투포인터를 이용하여 문제를 풀어야한다.

✅투포인터

말그대로 포인터 두개를 가지는 방식이다. 위 문제와 같이 특정한 합을 가지는 부분 연속 수열 찾기 문제에서 주로 사용된다.

문제 풀어보기

1. 필요한 변수 초기화

• count는 자연수의 합 갯수를 저장하는 변수이며, sum은 연속된 수의 합을 저장하는 변수이다.
• count를 1로 초기화하는 이유는 N이 자기자신일 때의 경우의 수를 미리 넣고 초기화했기 때문이다.(예제에서는 N이 15이므로, 15 하나의 수로도 15를 만들 수 있으므로)
• start_index와 end_index는 두개의 포인터를 의미한다. 처음엔 둘다 1부터 시작한다.

2. 인덱스 증가 시키면서 N이 되는 값 찾기

(1) sum이 N보다 작으면

• 누적합인 sum이 N보다 작으면 더 큰 수를 찾기 위해 end_index를 오른쪽으로 이동시킨다.
• 위와 같이 sum이 N보다 작으면 두가지 로직이 실행되어야한다.
• • • 1. end_index 1 증가시키기
      • 2. sum의 누적합 갱신**
• 여기서 유의할 점은 end_index를 먼저 증가시키고, 누적합을 갱신시킨다는 것이다.
• 즉, [start, end] → [start, end+1]로 확장하는 것이기 때문에 end를 먼저 증가 시킨 후 누적합을 갱신하는게 맞다.

(2) sum이 N과 같으면

• sum과 N이 같다는 건 우리가 찾는 연속된 자연수의 합이 N과 같다는 것을 뜻한다.
• sum이 N과 같다면 세가지 로직이 실행되어야 한다.
• • • 1. count 1 증가시키기
      • 2. end_index 1 증가시키기
      • 3. sum의 누적합 갱신**

(3) sum이 N보다 크면

• sum이 N보다 크면 누적합을 줄여주어야한다. 즉, start_index를 증가시켜야한다.

• sum이 N보다 크면 두가지 로직이 실행되어야 한다.

• • • 1. sum의 누적합 감소시키기
      • 2. start_index 1 증가 시키기**

• 여기서 유의할 점은 sum의 누적합을 먼저 감소 시킨 후, start_index를 1 증가시키는 것이다.

• 즉, [start, end] → [start+1, end] 로 감소시키는 것 이기 때문에 sum에서 먼저 start_index를 빼는 것이 맞다.

위의 풀이처럼 코드를 짜면 된다! 이해만 한다면 쉽다.

문제 링크

문제 설명

수 N개 A₁, A₂, ..., A_N이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.

즉, A_i + ... + A_j (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 10⁶, 2 ≤ M ≤ 10³)

둘째 줄에 N개의 수 A₁, A₂, ..., A_N이 주어진다. (0 ≤ A_i ≤ 10⁹)

출력

첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다.

예시

✅나의 문제 풀이

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

        //N : 입력 받을 수의 갯수, M : 나눌 수
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        //합배열과 같은 나머지 인덱스 카운트 배열
        long[] S = new long[N];
        long[] C = new long[M];
        long answer = 0;

        //합배열 생성
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            //인덱스가 0이면 0-1시 예외발생하므로 if문으로 0인지 체크
            if(i==0){
                S[i] = Long.parseLong(st.nextToken());
            }else {
                S[i] = S[i - 1] + Long.parseLong(st.nextToken());
            }
        }
        //합배열의 모든값에 %M 하기
        for(int i=0; i<N; i++){
            int reminder = (int) (S[i] % M);
            //나머지가 0이면 결과값에 1씩 더하기
            if(reminder == 0) {
                answer += 1;
            }
            //나머지가 같은 인덱스의 개수 카운트하기(ex. 나머지가 1인 수가 3개면 C[1] = 3
            C[reminder]+=1;
        }

        for(int i=0; i<M; i++){
            //나머지가 같은 인덱스중 2개를 뽑는 경우의 수 이므로 인덱스의 값이 2이상인거만
            //ex. 6개면 6C2 -> 6*5 / 2 -> 15개.
            if(C[i] > 1){
                answer = answer + (C[i] *(C[i]-1)/ 2);
            }
        }
        System.out.println(answer);
    }
}

처음에 문제 이해를 못해서 많이 애먹었다... 첫번째 줄에 입력되는 첫번째 숫자N은 2번째 줄의 숫자의 갯수고, 그 다음 입력되는 M은 나누어 떨어지는 수(나눌 수)를 의미한다. 그리고 합이 M으로 나누어 떨어지는 (i,j)쌍의 개수를 구하라고 하는데, 예시의 1 2 3 1 2를 예로 들어보자면

• 인덱스1 부터
  • A[1] = 1 → 나머지3
  • A[1]+A[2] = 1+2 = 3 → 나머지0
  • A[1]+A[2]+A[3] = 1+2+3 = 6 → 나머지0
  • A[1]+A[2]+A[3]+A[4] = 1+2+3+1 = 7 → 나머지1
  • A[1]+A[2]+A[3]+A[4]+A[5] = 1+2+3+1+2 = 9 → 나머지0
• 인덱스2 부터
  • A[2] = 2 → 나머지1
  • A[2]+A[3] = 2+3 = 5 → 나머지1
  • A[2]+A[3]+A[4] = 2+3+1 = 6 → 나머지0
  • A[2]+A[3]+A[4]+A[5] = 2+3+1+2 = 8 → 나머지2

...

• 이런식으로 누적합을 더해서 그 누적합에서 m으로 나눴을 때 나누어떨어지는 쌍의 개수를 구하는 것이다.

문제 풀이 순서

1. 원본 배열인 A배열의 합배열 S를 생성한다.

S[i] = S[i-1] + A[i]

2. 합 배열 S의 모든 값에 대해 M으로 나머지 연산을 수행하여 합배열을 업데이트 한다

• 여기서 이해가 안될 수도 있는데, 1에서 구한 합배열을 M(예시에선 3)으로 나머지 연산을 수행하고, 해당 값의 나머지를 배열의 값으로 업데이트 하는것이다.
• 그리고 배열의 원소값이 0인 개수를 정답에 더한다.
• 예시에서는 나머지가 0인 인덱스가 3개이므로 3을 더한다.
• 이렇게 하는 이유는 원소의 값이 0이라는 뜻은 원본 배열의 0부터 i까지의 구간 합이 이미 M으로 나누어 떨어진다는 뜻이기 때문!

3. 나머지 값이 같은 합 배열의 개수를 구하고 2개의 원소를 뽑는 모든 경우의 수를 구한다.

• (A + B)% C는 ((A %C) + (B% C)) % C와 같다.
• 즉, 이말은 구간 합 전체에 한 번 나머지를 취한 것과 각 원소의 나머지를 미리 계산해 더한 뒤 다시 나머지를 취한 결과는 같다는 소리!
• 그래서 나머지가 같은 값이 2개 이상은 것들 중에, 2개의 원소를 뽑는 모든 경우의 수를 구하여 정답에 더하면 된다.
• 위 예에서 0은 3개, 1은 2개이므로 3C2, 2C2로 경우의 수를 구하면된다.
• 3C2 = 3*2 / 2 = 3
• 2C2 = 2*1 / 2 = 1

모든 경우의 수를 더한다

• 2에서 구한 원소의 값이 0인 인덱스 + 3에서 구한 경우의수를 모두 더한 3+3+1 = 7 이 답이다.

문제 링크

문제 설명

N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.

예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.

여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.

표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

입력

첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다. 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)

출력

총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지 합을 구해 출력한다.

예제

✅나의 문제 풀이

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

        //N : 배열 크기, M : 질의 갯수
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        //인덱스 편의성을 위해 +1
        int[][] A = new int[N+1][N+1];

        //1. 원본 배열 저장
        for(int i=1; i<=N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<=N; j++){
                A[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int[][] D = new int[N+1][N+1];
        //2. 합배열 저장
        for(int i=1; i<=N; i++){
            for(int j=1; j<=N; j++){
                D[i][j] = D[i-1][j] + D[i][j-1] + A[i][j] - D[i-1][j-1];
            }
        }

        //3. 질의 계산 및 출력
        for(int i = 0; i<M; i++){
            //질의 입력받기
            st = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(st.nextToken());
            int y1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());

            //구간 합 배열로 질의 계산 하기
            int result = D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1];
            sb.append(result).append('\n');
        }
        System.out.println(sb.toString());
    }
}

이 문제도 1차원 구간 합배열과 마찬가지로 질의마다 합을 구하면 시간초과로 통과를 못한다. 구간 합배열을 2차원으로도 어떻게 작성하는지 알아보자.

✅2차원 구간 합 배열

A[X][Y]는 원본 배열을 의미하며, D[X][Y]는 원본 배열 A의 (0,0)부터 (X,Y)까지의 사각형 영역 안에 있는 수의 합이다.

먼저 비교적 간단한 1행, 1열을 구해보도록하자.

1행 구간 합 구하기

• 위 예시로 1행의 구간 합을 구한다고 생각해보자.
• D[1][3]의 구간합을 구하고 싶다면 바로 직전의 구간 합 + 현재의 값(원본 배열의 A[1][3])을 더해야한다.
• 즉, D[1][3] = D[1][2] + A[1][3] → D[1][3] = 3 + 3 = 6 이 된다.
• 이것을 수식으로 표현하면, D[1][[j] = D[1][j-1] + A[i][j] 로 표현 가능하다.

1열 구간 합 구하기

• 마찬가지로 위 예시로 1열의 구간 합을 구한다고 생각하자.
• D[4][1]의 구간 합을 구하고 싶다면 바로 직전의 구간 합 + 현재의 값(원본 배열의 A[4][1]을 더해야한다.
• D[4][1] = D[3][1] + A[4][1] → D[4][1] = 6 + 4 = 10
• 이것을 수식으로 표현하면 D[i][1] = D[i-1][1] + A[i][1]이 된다.

그렇다면 나머지 값은 어떻게 구하지?

원리만 이해하면 매우 쉽다! 위 1행, 1열을 구한것과 마찬가지로 각각 [i][j-1]과 [i-1][j]를 더하고, 현재의 값(원본 배열의 값)을 더하면 된다. 하지만 이렇게만 하게되면 오차가 생기게된다. 그 이유는 위 이미지와 마찬가지로 겹치는 부분이 생기기 때문이다.(예시에서는 D[1][1]이 겹치는 부분이다) 그래서 이 겹치는 부분을 제거해줘야하는데, 그 수식까지 포함한 공식은 아래와 같다.

D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j]

문제 링크

문제 설명

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

출력

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

✅나의 문제풀이

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        //첫줄 : 데이터의 개수, 질의 개수
        int num = Integer.parseInt(st.nextToken());
        int quizNo = Integer.parseInt(st.nextToken());

        //인덱스의 편의성을 활용하기 위해 num+1.
        //plus[0]은 아무것도 더하지 않은값인 0으로 세팅하기 위해서
        int[] plus = new int[num+1];
        st = new StringTokenizer(br.readLine());

        //합배열 구하기
        for(int i=1; i<=num; i++){
            plus[i] = plus[i-1] + Integer.parseInt(st.nextToken());
        }

        //질의 입력 받은 후 구간 합 구하기
        for(int q=0; q<quizNo; q++){
            st = new StringTokenizer(br.readLine());
            int i = Integer.parseInt(st.nextToken());
            int j = Integer.parseInt(st.nextToken());

            sb.append(plus[j] - plus[i-1]).append('\n');
        }
        System.out.println(sb);
    }
}

✅구간 합 구하기

이 문제는 각 인덱스마다 값을 더하는 건데, 여기서 구간마다 합을 매번 계산하면 모든 계산을 시간 안에 끝낼 수 없다. 이럴 때 구간합을 이용하는 것이다!

☑️합 배열 공식

S[i] = S[i-1] + A[i]

• 예를 들어 A[3]까지의 합배열을 구하는 것이라면

• S[3] = S[2] + A[3] → S[3] = 9+3 → S[3] = 12 가 된다.

• 위 공식을 이용하여 합배열을 생성한 후, 구간 합 공식을 이용하여 구간합을 구하면 된다.

☑️구간 합 공식

S[j] - S[i-1]

• 질의가 (1,3) *일 때 : *S[3] - S[1-1] = 12 - 0 = 12
• 질의가 (2,4) 일 때 : S[4] - s[2-1] = 14 - 5 = 9
• 질의가 (5,5) 일 때 : S[5] - S[5-1] = 15 - 14 = 1

문제 링크

문제 설명

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -2³¹ 보다 크거나 같고 2³¹보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

✅나의 문제 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        //입력받을 정수의 갯수
        int n = Integer.parseInt(br.readLine());

        int[] arr = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        for(int i = 0; i < n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr);

        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine(), " ");


        for(int i=0; i < m; i++){
            if(Arrays.binarySearch(arr, Integer.parseInt(st.nextToken()))>= 0){
                sb.append(1).append('\n');
            }else{
                sb.append(0).append('\n');
            }
        }
        System.out.println(sb);

    }

}

문제 링크

문제 설명

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
• completion의 길이는 participant의 길이보다 1 작습니다.
• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
• 참가자 중에는 동명이인이 있을 수 있습니다.

입출력 예

입출력 예 설명

예제 #1
"leo"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #2
"vinko"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #3
"mislav"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

✅나의 문제 풀이

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        Map<String, Integer> m = new HashMap<>();
        for (int i = 0; i < participant.length; i++) {
            if (m.containsKey(participant[i])) {
                int n = m.get(participant[i]);
                m.put(participant[i], n + 1);
            } else {
                m.put(participant[i], 1);
            }
        }

        for (int i = 0; i < completion.length; i++) {
            if (m.containsKey(completion[i])) {
                int n = m.get(completion[i]);
                m.put(completion[i], n - 1);
            }
        }

        String answer = null;
        for (Map.Entry<String, Integer> entry : m.entrySet()) {
            if(entry.getValue() != 0){
                answer = entry.getKey();
            }
        }
        return answer;
    }
}

✅나의 문제 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        //입력받을 문자열 갯수
        int T = Integer.parseInt(br.readLine());

        for(int i = 0; i< T; i++){
            sb.append(solve(br.readLine())).append('\n');
        }
        System.out.println(sb);
    }

    public static String solve(String s){
        Stack<Character> stack = new Stack<>();

        for(int i=0; i<s.length(); i++){
            char c = s.charAt(i);

            //여는 괄호일 경우 스택에 넣는다.
            if(c=='('){
                stack.push(c);
            }

            //닫는 괄호일 경우
            else if (c == ')') {
                //stack이 비어있으면(즉, 짝꿍인 여는 괄호가 없으면)
                if (stack.empty()) {
                    return "NO";
                }
                //그게 아니라면(정상적이라면)
                stack.pop();
            }
        }

        if(stack.empty()){
            return "YES";
        }else {
            return "NO";
        }
    }
}

스택

• push() : 스택에 데이터를 추가하는 메서드
• pop() : 스택에 들어있는 데이터를 삭제하는 메서드
• peek() : 데이터는 삭제하지 않고 스택 맨 위에 있는 값을 확인하는 메서드
• size() : 현재 스택에 저장되어 있는 요소의 개수를 알려주는 메서드
• empty() : 스택이 비어있는지, 데이터가 들어있는지 확인하는 메서드(true/false)

문제 풀이

괄호 검사는 후입선출 방식인 스택이 적합하다. 기본적인 검사 방식은 아래와 같다

1. 여는 괄호 '('를 만날 경우 -> 스택에 넣는다 (push)
2. 닫는 괄호 ')'를 만날 경우 -> 스택에서 삭제한다(pop)
3. 마지막 괄호까지 조사 후, 스택에 남아있는게 없으면 올바른 경우

해당 괄호가 올바른지 판단하는 분기는 3가지가 있다.

1. 여는 괄호와 닫는 괄호가 올바른 경우(여는괄호의 수와 닫는 괄호의 수가 동일한 경우) 예시 : ( ( ( ( ) ( ) ) ( )

2. 괄호가 남는 경우(여는 괄호의 수가 더 많은 경우) 예시 : ( ( ) ) ( ) )

• 모든 괄호를 검사한 후 스택에 괄호가 남는 경우는 여는 괄호가 많은 경우라는 의미다. 즉, 이는 온전한 수식이 아니라는 것!

3. 괄호가 부족한 경우(닫는 괄호가 더 많은 경우) 예시 : ( ( ) ) ( ) )

• 위 이미지를 보면, 6번째 과정에서 pop을 하면 스택이 비어있다. 스택이 비어있다는 것은 현재까지는 완전한 수식이라는 건데, 그 이후에(7번째) 닫는 괄호가 또 나온다면 pop할 요소가 없기 때문에 올바른 경우가 아니다.

이 분기를 통해 3가지 조건문을 만들 수 있다.

//여는 괄호일 경우 스택에 넣는다.
if(c=='('){
    stack.push(c);
}

//닫는 괄호일 경우
else if (c == ')') {
//stack이 비어있으면(즉, 짝꿍인 여는 괄호가 없으면)
    if (stack.empty()) {
        return "NO";
    }
//그게 아니라면(정상적이라면)
    stack.pop();
    }
}

• 우선, 제일 먼저 여는 괄호 일 경우 stack에 넣는다.
• 닫는 괄호인데 stack이 비어있다면 즉, 현재 스택에 짝꿍인 여는 괄호가 없다면 올바른 수식이 아니므로 NO를 리턴한다.
• 닫는 괄호인데 스택이 비어있지 않으면 올바른 수식이므로 pop을 한다.

Stream API란 Java 8에서 도입되어 데이터 컬렉션을 함수형 스타일로 처리할 수 있게 하는 기능이다. 이는 데이터를 추상화하고 처리하는 다양한 연산을 수행할 수 있게 해준다. 특히, 데이터 소스에 대한 계산 로직을 고수준에서 간결하게 표현할 수 있어, 코드의 가독성과 유지보수성이 향상된다.

List<String> myList = Arrays.asList("a1", "a2", "b1", "b2", "c1", "c2");
myList.stream()
  .filter(s -> s.startsWith("c"))
  .map(String::toUpperCase)
  .sorted()
  .forEach(System.out::println);

✅Stream이란?

스트림이란 데이터 처리 연산을 지원하도록 소스에서 추출된 연속된 요소로 정의할 수 있다.

연속된 요소

• 컬렉션과 마찬가지로 스트림은 특정 요소 형식으로 이루어진 연속된 값 집합의 인터페이스를 제공한다.
• 컬렉션은 자료구조이므로 시간과 공간의 복잡성과 관련된 요소 저장 및 접근 연산이 주를 이룬다.
• 반면 스트림은 filter, sorted, map 처럼 표현 계산식이 주를 이룬다.

소스

• 스트림은 컬렉션, 배열, I/O 자원 등의 데이터 제공 소스로부터 데이터를 소비한다.
• 정렬된 컬렉션으로 스트림을 생성하면 정렬이 그대로 유지된다.
• 즉, 리스트로 스트림을 만들면, 스트림의 요소는 리스트의 요소와 같은 순서를 유지한다.

데이터 처리 연산

• 스트림은 함수형 프로그래밍 언어에서 일반적으로 지원하는 연산과 데이터베이스와 비슷한 연산을 지원한다.
• filter, map, reduce, finde, match, sort 등으로 데이터 조작가능 하다.
• 스트림 연산은 순차적 또는 병렬로 실행 가능하다.

✅Stream API의 특징

저장소가 없음(No Storage)

• 스트림 자체는 데이터를 저장하지 않는다.
• 컬렉션, 배열, I/O 채널 등의 데이터 소스를 표현하는데 사용된다.

함수형(Functional in nature)

• 스트림 연산은 주로 람다 표현식을 사용하여 함수형 프로그래밍의 접근 방식을 취한다.
• 이로 인해 외부 반복 대신 내부 반복을 사용할 수 있다.

지연성 추구(Laziness-seeking)

• 많은 스트림 연산들은 지연된다는 특징을 갖고 있다.
• 즉, 실제로 필요할때까지 계산을 수행하지 않는다.

무한성(Possibly unbounded)

• 스트림은 한정된 데이터 뿐만 아니라 무한한 데이터에 대해서도 작업을 수행할 수 있다.

소비 가능성(Consumable)

• 스트림의 요소들은 소비된다.
• 즉, 한 번 사용된 스트림은 재사용할 수 없다.

✅Collection vs Stream

위에서 설명한 것을 보면 Collection과 Stream이 다르다는 것을 얼추 느꼈을 것이다. 기존에 존재하뎐 Collection과 Stream은 무슨차이가 있을까?

📘Collection

• 모든 값을 메모리에 저장하는 자료구조다.
• 따라서 Collection에 추가하기 전에 미리 계산이 완료되어 있어야 한다.
• 외부 반복을 통해 사용자가 직접 반복 작업을 거쳐 요소를 가져올 수 있다(for-each)

📗Stream

• 요청할 때만 요소를 계산한다.
• 내부 반복을 사용하므로, 추출 요소만 선언해주면 알아서 반복 처리를 진행한다.
• 스트림에 요소를 따로 추가 혹은 제거하는 작업은 불가능 하다.

✅외부 반복과 내부 반복

Collection은 외부 반복, Stream은 내부 반복이라고 했는데 이 둘은 또 뭘까?

내부 반복은 작업을 병렬 처리하면서 최적화된 순서로 처리해주므로 성능면에서는 내부 반복이 비교적 좋다고 볼 수 있다. 외부 반복은 명시적으로 컬렉션 항목을 하나씩 가져와서 처리해야 하기 때문에 최적화가 불리하다. 즉, Collection에서 병렬성을 이용하려면 직접 Synchronized를 통해 관리해야만 한다.

✅Stream 연산

스트림은 연산 과정이 중간과 최종으로 나누어진다.

• filter, map, limit등 파이프라이닝이 가능한 연산을 중간 연산
• count, collect 등 스트림을 닫는 연산을 최종 연산

중간 연산에서는 호출해도 실제 연산을 수행하지 않고 파이프 라인만을 구성해두며, 최종 연산이 호출될때 비로소 중간 연산에서 만들어 둔 파이프 라인이 실행되어 실제로 연산이 수행된다.

예시로, Item 중에 가격이 1000이상인 item 이름을 5개 선택하는 Stream 연산을 구현해보자.

List<String> items = item.stream()
                .filter(d->d.getPrices()>=1000)
                          .map(d->d.getName())
                          .limit(5)
                          .collect(tpList());

위에서 filter와 map은 다른 연산이지만, 한 과정으로 병합된다. 만약 Collection이였다면

• 가격이 1000이상인 아이템을 찾고,
• 이름을 따로 저장한뒤
• 5개를 선택해야 한다.

연산 최적화와 가독성면에서 Collection보다 Stream이 더 좋다.

📌Stream 중간 연산

• filter(Predicate) : Predicate를 인자로 받아 true인 요소를 포함한 스트림 반환
• disctinct() : 중복 필터링
• limit(n) : 주어진 사이즈 이하 크기를 갖는 스트림 반환
• skip(n) : 처음 요소 n개 제외한 스트림 반환
• map(Function) : 매핑 함수의 result로 구성된 스트림 반환
• flatMap() : 스트림의 콘텐츠로 매핑함. map과 달리 평면화된 스트림 반환

중간 연산은 모두 스트림을 반환한다.

📌Stream 최종 연산

• (boolean) allMatch(Predicate) : 모든 스트림 요소가 Predicate와 일치하는지 검사
• (boolean) anyMatch(Predicate) : 하나라도 일치하는 요소가 있는지 검사
• (boolean) noneMatch(Predicate) : 매치되는 요소가 없는지 검사
• (Optional) findAny() : 현재 스트림에서 임의의 요소 반환
• (Optional) findFirst() : 스트림의 첫번째 요소
• reduce() : 모든 스트림 요소를 처리해 값을 도출. 두 개의 인자를 가짐
• collect() : 스트림을 reduce하여 list, map, 정수 형식 컬렉션을 만듬
• (void) forEach() : 스트림 각 요소를 소비하며 람다 적용
• (Long) count : 스트림 요소 개수 반환

✅지연 평가(Lazy evaluation)

지연 평가(Lazy evaluation)는 필요해지기 전까지 계산을 미루는 전략이다. 값이나 연산을 바로 계산하지 않고, 실제로 그 값이 요구되는 시점에 계산을 수행하여 불필요한 계산을 줄이고 메모리/시간을 아낄 수 있다는 장점이 있다. *Stream의 중간 연산은 바로 실행 되지 않고 대기하다가 최종 연산이 호출되는 순간 실제 연산이 수행된다. *

지연 평가가 중요한 이유는 아래와 같다.

1️⃣불필요한 연산 회피

findFirst, anyMatch, limit 같은 단축 연산은 조건이 만족되면 즉시 파이프라인을 종료하므로 시간이 절약 된다.

2️⃣파이프라이닝

파이프라인은 중간 연산들을 결합해 요소 하나를 끝까지 처리한 뒤 다음 요소로 넘어간다. 즉, 중간 결과 컬렉션을 만들지 않기 때문에 메모리 사용과 GC 압박이 감소된다.

3️⃣성능 최적화

스트림은 연산 순서와 조합에 따라 처리량이 크게 달라진다. 예를 들어, filter로 먼저 요소를 걸러 필요한 대상만 남기면, 그 뒤에 오는 map과 같이 무거운 연산의 호출 횟수가 줄어들어 전체 성능이 좋아진다.

가비지 컬렉션은 자바의 메모리 관리 방법 중 하나로, JVM의 Heap 영역에서 동적으로 할당했던 메모리 중 필요 없게 된(사용하지 않는) 메모리 객체를 모아 주기적으로 제거하는 프로세스를 뜻한다.

C/C++은 이러한 가비지 컬렉션이 없어 프로그래머가 수동으로 메모리 할당과 해제를 일일이 해줘야 한다. Java는 개발자 입장에서 메모리 관리와 메모리 누수 문제에 대해 신경쓰지 않아도 되어 좀더 수월하게 개발 할 수 있다.

하지만, 이런 가비지 컬렉션에도 단점이 있는데, 이런 단점을 Stop-The-World라고 한다. 자동으로 처리해준다 해도 메모리가 언제 해제되는지 정확하게 알수 없어 제어하기 힘들며, 가비지 컬렉션이 동작하는 동안에는 다른 동작을 멈추기 때문에 오버헤드가 발생되는 문제점이 있다. 이로 인해 GC가 너무 자주 실행되면 소프트웨어 성능 하락의 문제가 되기도 한다.

✅가비지 컬렉션의 대상

일반적으로 아래와 같은 경우에 GC의 대상이 된다.

1. 객체가 NULL인 경우 (String str = null)
2. 블럭 실행 종료 후, 블럭 안에서 생성된 객체
3. 부모 객체가 NULL인 경우, 포함하는 자식 객체 GC는 Weak Generational Hypothesis 에 기반하는데, 이게 무엇인지 알아보기 전에 GC의 메모리 해제 과정에 대해 살펴보자.

✅GC의 메모리 해제 과정

GC가 메모리를 해제할 때는 Mark And Sweep이란 알고리즘을 사용한다. 가비지 컬렉션은 대상 객체를 식별(Mark)하고, 제거(Sweep)하며 객체가 제거되어 파편화된 메모리 영역을 앞에서부터 채워나가는 작업(Compaction)을 수행하게 된다.

1️⃣ Mark

• Root Space로부터 그래프 순회를 통해 연결된 객체들을 찾아내어 어떤 객체를 참조하고 있는지 찾아서 마킹한다.
• 참조하고 있는 객체가 없는 객체가 바로 GC의 대상인 사용하지 않는 객체이다.

2️⃣Sweep

• Mark 과정에서 찾은 참조하고 있지 않은 객체들 즉, 사용하지 않는 객체를 Heap에서 제거한다.

3️⃣Compact

• Sweep 후에 남아있는 객체(사용중인 객체들)을 Heap의 시작 주소로 모아 묶는다.
• 이들을 묶음으로써 공간이 생기므로 새로운 메모리 할당 시에 더 쉽고 빠르게 진행이 가능하다.

✅Weak Generational Hypothesis

JVM의 Heap영역은 처음 설계될 때 다음과 같은 2가지 전제로 설계되었다.

• 대부분의 객체는 금방 접근 불가능한 상태(Unreachable)가 된다.
• 오래된 객체에서 새로운 객체로의 참조는 매우 적게 존재한다.

즉, 객체는 대부분 일회성이며, 메모리에 오랫동안 남아있는 경우는 드물다는 것이다.

이 가설에 기반하여 Java는 객체의 생존기간에 따라 물리적인 Heap영역을 Young영역과 Old 영역으로 나누게 되었다. 신규로 생성되는 객체는 Young 영역에, 오랫동안 살아남은 객체는 Old 영역에 보관한다.

💡Generational Garbage Collection

✅Generational Garbage Collection의 구조

Young 영역

• 새롭게 생성되는 객체가 할당되는 영역
• 대부분의 객체가 금방 Unreachable상태가 되기 때문에 많은 객체가 Young 영역에 생성되었다가 사라진다.
• Young 영역에 대한 가비지 컬렉션을 Minor GC라고 부른다.

Old 영역

• Young 영역에서 살아남은 객체가 복사되는 영역
• Young 영역보다 크게 할당되며, 영역의 크기가 큰 만큼 가비지는 적게 발생한다.
• Old 영역에 대한 가비지 컬렉션을 Major GC 또는 Full GC라고 부른다.

또 다시 힙 영역은 더욱 효율적인 GC를 위해 Young 영역을 3가지 영역으로 나눈다.

Eden

• new를 통해 새로 생성된 객체가 위치
• 장기적인 쓰레기 수집 후 살아남은 객체들은 Survivor영역으로 보냄

Survivor 0 / Survivor 1

• 최소 1번의 GC 이상 살아남은 객체가 존재하는 영역
• Survivor 0 또는 Survivor 1 둘중 하나는 꼭 비어 있어야 한다는 규칙이 존재.

✅Minor GC 과정

• Yong Generaion 영역은 짧게 살아남는 메모리들이 존재하는 공간이다.
• 모든 객체는 처음에 Young Generation에 생성된다.
• Old Generation에 비해 공간이 상대적으로 작기 때문에 메모리 상의 객체를 찾아 제거하는데 적은 시간이 걸린다.

1. 처음 생성된 객체는 Young Generation 영역의 일부인 Eden 영역에 위치

2. 객체가 계속 생성되어 Eden 영역이 꽉차게 되면 Minor GC가 발생

3. Mark 동작을 통해 참조되는 객체 탐색

4. Eden 영역에서 살아남은 객체는 Survivor 영역으로 이동

5. Eden영역에서 사용되지 않은 객체의 메모리를 해제(sweep)

6. 살아남은 모든 객체들의 age 값이 1씩 증가

7. 또다시 Eden 영역에 신규 객체들로 가득차게 되면 다시 Minor GC가 발생되고 mark 실행

8. marking한 객체들을 비어있는 Survivor 1(다른 Survivor 영역)으로 이동하고 sweep

9. 다시 살아남은 모든 객체들의 age 1씩 증가

10. 이 모든 과정을 반복

✅Major GC 과정

• Old Generation은 길게 살아남는 메모리들이 존재하는 공간
• Old Generation의 객체들은 거슬러 올라가면 처음에는 Young Generation에 의해 시작되었으나, GC 과정 중에 제거되지 않은 경우 age 임계값이 차게되어 이동된 객체들이다.
• Major GC는 객체들이 계속 Promotion되어 Old 영역의 메모리가 부족해지면 발생하게 된다.

1. 객체의 age가 임계값(예시는 8)에 도달하게 되면

2. 이 객체들은 Old Generation으로 이동된다.(promotion)

3. 위 과정이 반복되어 Old Generaion 영역이 가득 차게되면 Major GC가 발생한다.

Major GC는 Old Generation 영역이 가득 찼을 때 실행된다. 이때 GC는 Old Generation에 존재하는 객체들을 검사해 참조되지 않는 객체들을 한꺼번에 정리한다.

Old Generation은 Young Generation보다 공간이 훨씬 크기 때문에, Major GC가 수행될 때는 더 많은 객체를 스캔하고 해제해야 한다. 그 결과 GC 처리 시간이 길어질 수 있다.

이때, Stop-The-World 문제가 발생하게 된다. Major GC가 실행되는 동안에는 애플리케이션 스레드가 일시 중지되며, GC 작업이 완료될 때까지 모든 요청 처리가 멈추게 되는데, 이로 인해 지연이나 성능 저하가 발생할 수 있으며, 이를 흔히 GC 오버헤드 문제라고 부른다.

따라서 이런 문제를 해결하고 최적화하기 위해 다양한 가비지 컬렉션 알고리즘이 개발되었다.

가비지 컬렉션 알고리즘 종류

Serial GC

• 서버의 CPU 코어가 1개 일때 사용하기 위해 개발된 가장 단순한 GC
• GC를 처리하는 스레드가 1개여서 가장 Stop-The-World의 시간이 가장 길다
• **보통 실무에서는 사용하지 않는다.
• *

Parallel GC

• Java 8의 디폴트 GC
• Serial GC와 기본적인 알고리즘은 같지만, Young 영역의 Minor GC를 멀티쓰레드로 수행(Old 영역은 여전히 싱글 스레드)

Parallel Old GC

• Parallel GC를 개선한 버전
• Young 영역 뿐만 아니라 Old 영역에서도 멀티스레드로 GC 수행
• 새로운 가비지 컬렉션 청소 방식인 Mark-Summary-Compact 방식을 이용

CMS GC

• 어플리케이션의 스레드와 GC 스레드가 동시에 실행되어 Stop-The-World 시간을 최대한 줄이기 위해 고안된 GC
• GC 과정이 매우 복잡하며 메모리 파편화 문제 존재
• GC 대상을 파악하는 과정이 복잡한 여러단계로 수행되기 때문에 다른 GC 대비 CPU 사용량이 높음
• Java14에서부터 사용이 중지

G1 GC

• CMS GC를 대체하기 위해 나온 GC
• Java 9+ 버전의 디폴트 GC로 지정
• 기존의 GC 알고리즘에서는 Heap 영역을 물리적으로 고정된 Young / Old 영역으로 나누어 사용하였지만, G1 gc는 아예 이러한 개념을 뒤엎는 Region이라는 개념을 새로 도입하여 사용.전체 Heap 영역을 Region이라는 영역으로 체스같이 분할하여 상황에 따라 Eden, Survivor, Old 등 역할을 고정이 아닌 동적으로 부여

Shenandoah GC

• Java 12에 release
• 레드햇에서 개발한 GC
• 기존 CMS가 가진 단편화, G1이 가진 pause의 이슈를 해결
• 강력한 Concurrency와 가벼운 GC 로직으로 heap 사이즈에 영향을 받지 않고 일정한 pause 시간이 소요가 특징

ZGC

• Java 15에 release
• G1의 Region 처럼,  ZGC는 ZPage라는 영역을 사용하며, G1의 Region은 크기가 고정인데 비해, ZPage는 2mb 배수로 동적으로 운영됨. (큰 객체가 들어오면 2^ 로 영역을 구성해서 처리)
• ZGC가 내세우는 최대 장점 중 하나는 힙 크기가 증가하더도 'stop-the-world'의 시간이 절대 10ms를 넘지 않는다는 것

이전에 JVM, JRE, JDK의 개념에 대해서 알아보는 시간을 가졌다.이번엔 좀 더 자세히 JVM의 구조에 대해서 알아보도록 하자. JDK, JRE, JVM의 개념

🧐JVM이 뭐였지?

JVM은 자바 가상 머신으로, 자바 바이트 코드를 각 운영체제에 맞는 기계로 바꾸어 실행하는 가상머신이다. 즉, 자바 바이트 코드(.class)를 해석하여 실행 시켜주는 머신인데, 대체 어떤 방법으로 자바 바이트 코드를 해석하고, 프로그램 실행까지 시키는지 알아보도록 하자.

✅JVM의 구성요소

JVM은 크게 5가지의 요소로 나누어진다.

1. 클래스 로더 (Class Loader)

2. 런타임 데이터 영역 (Runtime Data Area)

3. 실행 엔진 (Execution Engine)

4. JNI - 네이티브 인터페이스 (Java Native Interface)

5. 네이티브 메서드 라이브러리 (Native Method Libraries)

1️⃣클래스 로더(Class Loader)

클래스 로더는 JVM 안에서 클래스 파일(.class)을 동적으로 로드하고, JVM의 메모리 영역인 Runtime Data Area에 메모리를 할당하여 실행 가능한 상태로 만든다. 프로그램 실행 시 필요한 클래스만 동적으로 적재하여 메모리 사용을 최적화한다. 더 자세히 말하자면, 클래스 로더는 클래스의 로드(Load), 연결(Link), 초기화(Intialization) 과정을 통해 실행을 준비하게 된다. 즉, 클래스 로더 클래스 파일을 가져와 메모리에 로드하고, 클래스에 문제가 없는지 검증하고 변수를 적절한 값으로 초기화 하는 과정을 담당한다.

2️⃣런타임 데이터 영역(Runtime Data Area)

런타임 데이터 영역은 JVM이 실행하는 동안 데이터를 저장하는 메모리 영역이다.

1) 메서드 영역

• 바이트 코드를 처음 메모리 공간에 올릴 때 초기화되는 대상을 저장하기 위한 공간
• 정적 필드와 클래스 구조만을 가지고 있다.
• JVM 메모리의 정적 영역으로, 모든 스레드가 공유하는 메모리 공간
• JVM이 동작하고 클래스가 로드될 때 적재되어 프로그램이 종료될 때까지 저장됨

2) 힙 영역

• new 연산자로 생성되는 클래스, 인스턴스 변수, 배열 등 Reference Type이 저장되는 공간
• 가비지 컬렉터가 관리
• 모든 스레드가 공유하는 영역

3) 스택 영역

• int, long, boolean 등 기본 자료형 생성 시 저장하는 공간
• 각 스레드마다 독립적으로 할당되는 공간
• 메서드 호출시마다 프레임이 생성되어 지역 변수, 매개 변수 등이 저장됨

4) PC(Program Counter) 레지스터

• 각 스레드 별로 하나씩 존재
• 현재 실행중인 JVM 명령의 주소를 저장하는 공간

5) 네이티브 메서드 스택

• 실제 실행할 수 있는 기계어로 작성된 프로그램을 실행 시키는 영역
• 자바 의외의 네이티브 코드(C/C++) 실행 시 사용되는 메모리 영역이기도 함

3️⃣실행 엔진(Execution Engine)

실행 엔진은 클래스 로더를 통해 런타임 데이터 영역에 배치된 바이트 코드를 명령어 단위로 읽어서 실행한다. 자바 바이트 코드(.class)는 가상 머신이 이해할 수 있는 중간 레벨로 컴파일된 코드이다. 그래서 실행 엔진은 바이트 코드를 JVM내부에서 실제로 기계가 실행할 수 있는 형태로 바꿔준다. 이 때, 바이트 코드를 실행 시키는 방법은 크게 두가지로 분류 할 수 있다.

1) 인터프리터(Interpreter)

• 바이트 코드 명령어를 하나씩 읽어서 해석하고 바로 실행
• JVM안에서 바이트 코드는 기본적으로 인터프리터 방식으로 동작
• 같은 메소드라도 여러번 호출이 된다면 매번 해석하고 수행해야 되므로 *전체적인 속도는 느림 *

2) JIT 컴파일러(Just-In-Time Compiler)

• 인터프리터의 단점(속도, 효율)을 보완하기 위해 도입한 방식
• 반복되는 코드를 런타임 중에 기계어로 컴파일하고 재사용하는 방식
• 한번 기계어로 컴파일하여 캐싱 한 코드를 실행하므로 속도가 비교적 빠름

두 방식의 장단점이 있기 때문에 어떤 방식을 사용할지는 컴파일 임계치라는것을 계산하여 결정한다. 메서드가 호출된 횟수와 메서드가 종료된 횟수를 통해 컴파일 임계치를 계산하고, 이를 초과하면 JIT 방식으로 기계어를 캐싱하게 된다.

3) 가비지 컬렉터

실행엔진에는** 가비지 컬렉터도 포함되어 있다. **가비지 컬렉터는 자동으로 메모리를 관리해주는 JVM 기능으로, Heap 메모리 영역에서 더 이상 사용하지 않는 메모리를 자동으로 회수해 준다. C언어 같은 경우는 직접 개발자가 메모리를 해제해줘야 하지만, JAVA는 이 가비지 컬렉터를 이용하여 자동으로 메모리를 실시간 최적화 시켜준다.

4️⃣네이티브 인터페이스(JNI)

JNI는 자바가 다른 언어로 만들어진 어플리케이션과 상호 작용할 수 있는 인터페이스를 제공하는 프로그램이다. C, C++ 등으로 작성된 라이브러리를 실행할 때 주로 사용하며, JAVA를 통해 실행할 수 없는 하드웨어, OS의 기능에 접근할 수도 있다.

네이티브 메서드 라이브러리(Native Method Libraries)

네이티브 메서드 라이브러리는 C, C++로 작성된 라이브러리를 뜻한다. 만일 헤더가 필요하다면 JNI는 이 라이브러리를 로딩해 실행한다.

☑️다시보는 JVM 실행과정

1. 자바 프로그램을 실행하면 JVM은 OS로부터 메모리를 할당받는다.

2. 자바 컴파일러(javac)가 자바 소스코드(.java)를 자바 바이트 코드(.class)로 컴파일 한다.

3. 클래스 로더는 동적 로딩을 통해 필요한 클래스들을 로딩 및 링크하여 런타임 데이터 영역에 올린다.

4. 런타임 데이터 영역에 로딩된 바이트 코드는 실행 엔진을 통해 해석된다.

5. 이 과정에서 실행 엔진에 의해 가비지 컬렉터의 작동과 스레드 동기화가 이루어진다.

✅나의 문제 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        //입력받을 문자열 갯수
        int n = Integer.parseInt(br.readLine());
        int last = -1;

        //큐 정의
        Queue<Integer> queue = new LinkedList<>();

        for(int i = 0; i<n; i++){
            String line = br.readLine();
            if(line.startsWith("push")){
                //offer : 큐에서 주어진 값을 넣는 명령어
                int val = Integer.parseInt(line.substring(5).trim());
                queue.offer(val);
                last = val; //마지막 값 갱신
            }else if(line.equals("pop")){
                //poll : 큐에서 값 하나를 출력하고 그 값을 큐에서 제거
                sb.append(queue.isEmpty()? -1 : queue.poll()).append('\n');
            }else if(line.equals("size")){
                //size : 큐에 들어있는 데이터의 개수 출력
                sb.append(queue.size()).append('\n');
            }else if(line.equals("empty")){
                //isEmpty : 큐가 비어있는지 확인. 비어있으면 true
                sb.append(queue.isEmpty() ? 1 : 0).append('\n');
            }else if(line.equals("front")){
                //peek : 큐에서 값 하나 출력 제거는 안함.
                sb.append(queue.isEmpty()? -1 : queue.peek()).append('\n');
            }else if(line.equals("back")){
                sb.append(queue.isEmpty()? -1 : last).append('\n');
            }
        }
        System.out.println(sb.toString());
    }
}

큐(FIFO)

• offer() : 큐에 값을 넣는 메서드
• poll() : 큐에서 값 하나를 출력하고 그 값을 큐에서 제거
• peek() : 큐에서 값 하나를 출력. 큐에서 제거는 안함
• size() : 큐에 들어있는 데이터 개수 출력
• isEmpty() : 큐가 비어있는지 확인. 큐가 비어있으면 true, 비어있지 않으면 false

✅나의 문제 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder out = new StringBuilder();

        //입력받을 문자열 갯수
        int n = Integer.parseInt(br.readLine());
        Stack<Integer> stack = new Stack<>();   //스택 정의

        for(int i=0;i<n; i++){
            String line = br.readLine();    //명령어 입력받음
            if(line.startsWith("push")){
                //명령어가 push로 시작하면 push 이후 뒷부분(6번째 글자부터)자르고, 그 값을 stack에 넣는다
                stack.push(Integer.parseInt(line.substring(5).trim()));
            }else if(line.equals("pop")){
                //stack.empty() : 스택이 비었으면 true, 아니면 false
                //스택이 비어있으면 -1 + 개행, 비어있지않으면 pop()으로 맨 위 원소 꺼내고
                //StringBuilder에 결과와 개행을 붙여서 버퍼링(나중에 한번에 출력)
                out.append(stack.empty()? -1 : stack.pop()).append('\n');
            }else if(line.equals("size")){
                out.append(stack.size()).append('\n');
            }else if(line.equals("empty")){
                out.append(stack.empty()? 1 : 0).append('\n');
            }else if(line.equals("top")){
                out.append(stack.empty()? -1 : stack.peek()).append('\n');
            }
        }
        System.out.println(out.toString());
    }
}

• 먼저 스택을 정의해주고, 입력받을 문자열 개수만큼 for문을 돌린다.
• for문안에 if문을 이용해서 명령어를 구분하고, 그에 맞게 명령어를 처리한다.
• 특히 push는 push 5와 같이 push 이후에 정수로 스택에 넣을 값을 지정해주기 때문에, startsWith() 메서드를 이용하여 명령어가 push로 시작하는지 판별하고, push로 시작한다면 substring으로 push 이후의 글자를 자른다.

스택

• push() : 스택에 데이터를 추가하는 메서드
• pop() : 스택에 들어있는 데이터를 삭제하는 메서드
• peek() : 데이터는 삭제하지 않고 스택 맨 위에 있는 값을 확인하는 메서드
• size() : 현재 스택에 저장되어 있는 요소의 개수를 알려주는 메서드
• empty() : 스택이 비어있는지, 데이터가 들어있는지 확인하는 메서드(true/false)

문자열 입력

• 문자열 입력은 Scanner가 아니라 BufferedReader를 사용했다.
• BufferdReader는 문자를 버퍼에 모아서 한꺼번에 읽는 자바의 입력 클래스이다.
• 보통 BufferdReader로 문자열을 입력받고, StringBuilder로 출력을 모은다.

기본 구성

BufferedReader br =
    new BufferedReader(new InputStreamReader(System.in)); // 표준 입력

String line = br.readLine();    //한 줄 읽기

자주 쓰는 패턴

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder out = new StringBuilder();

int n = Integer.parseInt(br.readLine());
for (int i = 0; i < n; i++) {
    String line = br.readLine();
    // 필요 시:
    // StringTokenizer st = new StringTokenizer(line);
    // String[] parts = line.split("\\s+");
    out.append(line).append('\n'); // 결과 모으기
}
System.out.print(out.toString());  // 한 번에 출력

Scanner vs BufferedReader

• Scanner : 사용 간단하지만 속도가 느림.
• BufferedReader : 라인 단위로 읽고 직접 파싱하며, Scanner보다 빠르다.

자바는 3년정도의 텀으로 LTS(Long Term Support) 릴리스가 제공된다. LTS란 Long Term Support의 약자로 장기 지원 버전을 의미한다. 자바의 LTS 버전은 특정 기간 동안 안정적인 지원과 업데이트를 제공받을 수 있다. 일반적으로 3년마다 출시되며, 출시 후 5년동안 기술 지원이 제공된다.

✅LTS버전을 사용해야 하는 이유는?

1. 장기적인 지원 Long Term Support란 이름과 같이 장기적으로 보안 업데이트와 버그 수정을 지원해준다

2. 안정성 광범위하게 테스트되고 안정화된 후 릴리스되므로 높은 신뢰성을 갖고 있다.

3. 기업 환경에 적합 많은 기업에서 규제 요구 사항을 충족하기 위해 장기적으로 지원되는 소프트웨어를 사용해야 한다

4. 커뮤니티 및 생태계 지원 LTS 버전은 많은 개발자와 기업에서 사용되므로 강력한 커뮤니티와 생태계를 갖고있다. 또한, 주요 라이브러리와 프레임 워크가 LTS 버전을 우선적으로 지원하기 때문에 호환성이 높다.

💡자바 버전별 특징

📌Java 8

Java 8의 변경점으로는 크게 람다 표현식과 함수형 프로그래밍 지원이 있다. 이로 인해 코드의 가독성이 높아지고 간결한 코드를 작성할 수 있게 되었다.

1️⃣람다 표현식(Lambda Expressions)

• 함수형 프로그래밍을 지원하여 코드의 간결성과 가독성을 높임

  Arrays.sort(strArray, (String s1, String s2) -> s2.length() - s1.length());

2️⃣디폴트 메서드(Default Methods)

• 인터페이스에 기본 메서드를 정의하여 기존 코드를 깨지 않고 기능을 추가할 수 있다.

  default public Stream<T> stream() {
  return StreamSupport.stream(spliterator(), false);
  }

3️⃣스트림 API (Stream API)

• 컬렉션 데이터의 반복, 필터링, 매핑 등을 간단하게 처리할 수 있는 API 도입

  List<String> filtered = list.stream()
  .filter(s -> s.startsWith("a"))
  .collect(Collectors.toList());

4️⃣Optional 클래스

• null 참조를 다루기 위한 컨테이너 클래스로, 보다 안전한 코드를 작성할 수 있다.
• 참고

  Optional<String> optional = Optional.of("Hello");
  optional.ifPresent(System.out::println);

📌Java 11

1️⃣지역 변수 유형 추론(var 키워드)

• 변수 선언 시 타입을 명시하지 않아도 컴파일러가 자동으로 타입을 추론해주는 기능 도입

  var list = new ArrayList<String>();
  list.add("Hello, Java 11");

2️⃣새로운 HTTP 클라이언트 API

• java.net.http 패키지에 새로운 HTTP 클라이언트를 도입하여 HTTP/2 및 WebSocket을 지원

  HttpClient client = HttpClient.newHttpClient();
  HttpRequest request = HttpRequest.newBuilder()
  .uri(URI.create("https://example.com"))
  .build();
  HttpResponse<String> response = client.send(request, BodyHandlers.ofString());
  System.out.println(response.body())

📌Java 17

1️⃣패턴 매칭 for switch

• switch 문에서 패턴 매칭을 사용하여 코드의 가독성을 높임

  switch (obj) {
  case Integer i -> System.out.println("Integer: " + i);
  case String s -> System.out.println("String: " + s);
  default -> System.out.println("Unknown type");
  }

2️⃣Sealed Classes

• 상속 구조를 제한하여 더 안전하고 예측 가능한 클래스 계층을 설계할 수 있게 함

  public abstract sealed class Shape permits Circle, Square {}

3️⃣Record Patterns

• 간단하게 불변 데이터 클래스를 정의할 수 있는 기능 정식 도입

  public record Point(int x, int y) {}

📌Java 21

1️⃣Virtual Threads

• 고성능 동시성을 제공하는 새로운 경량 스레드 모델 도입

  Thread.startVirtualThread(() -> {
  System.out.println("Hello from a virtual thread");
  });

2️⃣Record Patterns

• 레코드 패턴을 활용한 더 나은 데이터 추출 및 처리 가능

3️⃣Foreign Function & Memory API

• 자바 애플리케이션이 외부 메모리와 상호 작용하는 새로운 방식 제공