circuits

류한선·2025년 6월 23일

실기연습-2

목록 보기
31/95

맞아요, 말씀 이해했어요! 😊
백준 16357 Circuits 문제 자체는 굉장히 길고 복잡하지만, 거기서 쓰인 중요한 개념들(예: 구간 압축, 세그먼트 트리, lazy 전파, 구간 최대값 쿼리)은 정보처리기사 실기 알고리즘 문제로 출제될 수 있는 형태가 있어요.

실제 실기에서는 이렇게 큰 문제 대신에 단일 개념을 확실히 묻는 짧은 문제가 나오는 경우가 많아요. 그래서 아래와 같이 “실기용 연습 문제”를 정리해 줄게요.

🎯 정보처리기사 실기 스타일 문제

문제:
N개의 작업이 주어집니다. 각 작업은 시작 시각 s와 종료 시각 e를 가집니다.
이때 한 시각에 동시에 진행 중인 작업 수의 최댓값을 출력하는 프로그램을 작성하세요.

입력:

5
1 3
2 5
4 6
7 8
5 9

출력:

2

※ 위 출력에서 2는 가장 많은 작업이 겹친 수입니다.

이 문제는
✅ 선형 스위핑(Sweep Line)
✅ 구간 압축(좌표 압축)
✅ 세그먼트 트리 또는 우선순위 큐
중 하나로 풀 수 있습니다.

정보처리기사의 경우 이런 문제에서 요구하는 건 대체로 아래와 같습니다.

🧠 풀이 아이디어 (실기 답안 서술 연습용)

  1. 입력을 받는다.

  2. 이벤트 정리:

    • 시작 시각 → 작업 수 +1
    • 종료 시각 → 작업 수 -1

  3. 시간 순 정렬 후, 한 번 훑으면서 현재 진행 작업 수를 계산하고 최댓값을 추적한다.

  4. 출력.

💡 C언어 예제 코드 (짧고 실기용)

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int time;
    int delta;
} Event;

int compare(const void *a, const void *b) {
    Event *ea = (Event*)a;
    Event *eb = (Event*)b;
    if (ea->time != eb->time) return ea->time - eb->time;
    return ea->delta - eb->delta;
}

int main() {
    int N;
    scanf("%d", &N);
    Event events[N*2];
    for(int i=0;i<N;i++){
        int s,e;
        scanf("%d %d",&s,&e);
        events[i*2].time = s;
        events[i*2].delta = 1;    // 시작
        events[i*2+1].time = e;
        events[i*2+1].delta = -1; // 종료
    }
    qsort(events,N*2,sizeof(Event),compare);

    int cur = 0, ans = 0;
    for(int i=0;i<N*2;i++){
        cur += events[i].delta;
        if(cur>ans) ans = cur;
    }
    printf("%d\n", ans); // 출력
    return 0;
}

📝 한 줄 한 줄 해설 연습

이 문제에서 설명할 때도 실기 준비 방식처럼:

  • Event 구조체: time, delta(+1/-1) 역할 → 작업 시작/종료 표시
  • qsort로 정렬 기준 설명
  • for 루프로 이벤트 하나씩 처리하면서 현재 겹친 수를 계산
  • 최댓값 추적
  • 예제 (1,3), (2,5), ...를 대입해 상태 변화를 단계별 디버깅

이런 식으로 준비해 두면 좋아요!

좋아요! 😄 이제 int main() 안의 입력을 받는 부분을 한 줄 한 줄 디버깅하듯 자세히 설명해 드릴게요.
설명할 부분은 아래 코드예요:

int main() {
    int N;
    scanf("%d", &N);
    Event events[N*2];
    for(int i=0;i<N;i++){
        int s,e;
        scanf("%d %d",&s,&e);
        events[i*2].time = s;
        events[i*2].delta = 1;    // 시작
        events[i*2+1].time = e;
        events[i*2+1].delta = -1; // 종료
    }
    ...
}

🔍 한 줄 한 줄 디버깅하면서 자세히 설명

int N;

  • 📌 N이라는 정수를 선언합니다.
  • 🧠 역할: 작업의 개수를 담을 변수.
  • 🕐 프로그램 시작 시 아직 값이 없음.

scanf("%d", &N);

  • 📌 표준입력에서 정수 한 개를 읽어 N에 저장.

  • 🧠 이 부분에서 일어나는 일:

    • 사용자나 파일에서 정수를 받음. 예: 5라고 치면 N=5.

  • 🧠 왜 여기 있어야 하나?

    • N을 알아야 이후 메모리 할당(Event events[N*2];)을 위해서.

Event events[N*2];

  • 📌 이벤트 배열을 선언합니다.

  • 🧠 왜 N*2?

    • 작업마다 시작과 끝 두 이벤트가 필요하기 때문.
    • 예: 작업 5개 → 시작 이벤트 5개 + 종료 이벤트 5개 = 10개.

  • 🧠 events 안에는 time(언제 시작/끝나는지), delta(+1 or -1)가 담김.

for(int i=0;i<N;i++){ ... }

  • 📌 i=0부터 i=N-1까지 반복 → 작업 N개를 한 줄씩 읽을 거예요.

  • 🧠 왜 N번 돌까?

    • 각 작업마다 시작/종료 정보가 1세트씩 필요하기 때문.

int s,e;

  • 📌 시작(s)과 종료(e) 시간을 담을 지역변수를 선언.
  • 🧠 이 변수를 바로 아래에서 채우고, 이벤트 배열에 쓴다.

scanf("%d %d",&s,&e);

  • 📌 한 작업의 시작, 종료 시간을 읽음.
  • 🧠 예를 들어 1 3이 입력되면 s=1, e=3.
  • 🧠 이 시점에서 s와 e를 배열 events에 채우면 돼요.

events[i*2].time = s;

  • 📌 i번째 작업의 시작 이벤트 위치를 채움.

  • 🧠 i*2 계산:

    • i=0 → 0
    • i=1 → 2
    • i=2 → 4 ...

  • 🧠 이렇게 짝수 index를 시작 이벤트용 슬롯으로 예약.

  • 🧠 events[0].time = 1, events[2].time = 2 ... 이렇게 차곡차곡 쌓임.

events[i*2].delta = 1; // 시작

  • 📌 시작 이벤트니까 +1.
  • 🧠 의미: 이 time에서 작업 수가 하나 증가.
  • 🧠 나중에 이벤트를 정렬 후 스위핑하면서 현재 작업 수에 +1 하려고.

events[i*2+1].time = e;

  • 📌 i번째 작업의 종료 이벤트 위치.

  • 🧠 i*2+1 계산:

    • i=0 → 1
    • i=1 → 3
    • i=2 → 5 ...

  • 🧠 이렇게 홀수 index를 종료 이벤트용 슬롯으로 예약.

  • 🧠 events[1].time = e, events[3].time = e ... 형태로 쌓임.

events[i*2+1].delta = -1; // 종료

  • 📌 종료 이벤트니까 -1.
  • 🧠 나중에 정렬 후 스위핑할 때 cur--를 하여 현재 작업 수 감소.

🧠 한 작업 예시 디버깅

입력:

2
1 3
2 5
  • N = 2
  • events 크기 = 2*2 = 4

반복문:

  • i=0:

    • s=1, e=3
      → events[0].time = 1; delta = +1
      → events[1].time = 3; delta = -1

  • i=1:

    • s=2, e=5
      → events[2].time = 2; delta = +1
      → events[3].time = 5; delta = -1

최종 events 배열 상태:

index | time | delta
0     | 1    | +1
1     | 3    | -1
2     | 2    | +1
3     | 5    | -1

이 상태에서 정렬(qsort)하면 time 순으로 [ (1,+1), (2,+1), (3,-1), (5,-1) ]가 되고, 이를 쭉 돌며 +1/-1 계산하면서 최대값을 찾습니다.

좋아요! 🕵️‍♂️ 이제 qsort() 호출 부분과 compare() 함수 부분을 한 줄 한 줄 디버깅하면서 아주 자세히 설명해 드릴게요.

🎯 qsort() 호출 부분

qsort(events, N*2, sizeof(Event), compare);

이 한 줄의 역할을 쪼개서 설명해 보자:

  1. events:

    • 우리가 정렬할 배열의 시작 주소.
    • 아까 위에서 채운 Event 구조체들의 시작 지점.

  2. N*2:

    • 정렬할 요소의 개수.
    • 작업 N개 → 시작/종료 이벤트 N*2개.

  3. sizeof(Event):

    • 한 요소(Event)의 크기(바이트 단위).
    • qsort 내부에서 인덱스를 옮기며 메모리 접근할 때 필요.

  4. compare:

    • 비교를 수행할 사용자 정의 함수 포인터.
    • 정렬 기준을 담은 함수의 이름(주소) 전달.

🔄 qsort()가 내부에서 하는 일:

  1. 이벤트 배열을 섞고 비교해 가며 정렬하기 위해 compare() 호출.
  2. 정렬 기준에 맞춰 events 배열의 원소들의 위치를 바꿈.
  3. 정렬 끝나면 events가 오름차순 정리됨.

🎯 compare() 함수 부분 디버깅

여기서 중요한 건 compare()가 정렬 기준을 어떻게 정하는지를 정의한다는 것.

이 함수를 한 줄 한 줄 보자:

int compare(const void *a, const void *b) {
    Event *ea = (Event*)a;
    Event *eb = (Event*)b;
    if (ea->time != eb->time) return ea->time - eb->time;
    return ea->delta - eb->delta;
}

Event *ea = (Event*)a;

  • 📌 qsort()에서 a를 void 포인터로 넘겨주므로 우리가 원래 타입(Event *)로 변환.
  • 🧠 왜 이렇게 캐스팅?
    C의 qsort()는 어떤 타입이든 정렬할 수 있으므로 void *를 쓰는데, 우리는 Event 정렬이므로 캐스팅 필수.

Event *eb = (Event*)b;

  • 📌 위와 똑같은 이유로 b를 Event*로 캐스팅.

if (ea->time != eb->time) return ea->time - eb->time;

  • 📌 가장 먼저 **이벤트의 time(시각)**을 기준 정렬.

  • 🧠 ea->time과 eb->time 비교:

    • 음수 반환 → ea가 eb보다 앞으로
    • 양수 반환 → ea가 eb보다 뒤로
    • 0 반환 → 같은 값(같은 시각)

  • 🧠 왜 이렇게?
    시각이 작은 이벤트부터 큰 이벤트 순서대로 정렬하기 위해.

return ea->delta - eb->delta;

  • 📌 만약 time이 같다면 delta(+1/-1) 비교.

  • 🧠 왜 이렇게?
    같은 시각에 시작(+1)과 종료(-1)가 겹치면, 시작 이벤트를 먼저 처리해야 겹침 수 계산에서 손해보지 않도록 정렬.

  • 🧠 ea->delta - eb->delta:

    • 시작(+1) 먼저 오고 종료(-1)가 나중에 오도록 → +1 - (-1) = +2 → 반환값 양수 → 시작이 뒤로?

    • 여기 디버깅 포인트!
      현재 조건 ea->delta - eb->delta의 결과를 보자:

      • 만약 ea가 +1이고 eb가 -1이라면 1 - (-1) = 2 (>0) → ea가 뒤로 갑니다.
      • 우리가 원하는 건 시작(+1) 이벤트가 종료(-1) 이벤트보다 먼저 오도록 정렬하는 거죠.
      • 그런데 이렇게 하면 +1이 나중에 오므로 반대 방향이 됨.

🔧 정리 기준 수정하기

지금 compare가 ea->delta - eb->delta면, 종료 이벤트가 시작 이벤트보다 우선 오도록 정렬됨. 우리는 시작(+1)이 우선이길 원한다면 반대로 빼야 합니다.

✅ 따라서 이 부분을:

return eb->delta - ea->delta;

이렇게 바꿔주면:

  • ea=+1, eb=-1 일 때 eb->delta - ea->delta = -1-1 = -2(<0) → 시작 이벤트(+1)가 정렬에서 앞으로 오게 됨.

🧠 한 번 디버깅 예제

정렬 전 이벤트

time | delta
1    | +1  (e1)
3    | -1  (e2)
2    | +1  (e3)
3    | -1  (e4)

qsort() 호출 후 compare()가 호출되는 경우

케이스 1: 다른 시각 비교

예: (1,+1) vs (3,-1)

  • ea->time - eb->time = 1-3 = -2(<0) → (1,+1)이 앞.

케이스 2: 같은 시각 비교

예: (3,-1) vs (3,-1) → time 같고 delta 같음 → 0 반환
예: (3,-1) vs (3,-1) → 같으므로 무순서.

케이스 3: 같은 시각에서 시작과 종료 비교

예: (3,+1) vs (3,-1)

  • 현재 compare: ea->delta - eb->delta = +1 - (-1) = 2 → 양수 반환 → ea가 뒤로 감(원치 않는 정렬)
  • 수정한 compare: eb->delta - ea->delta = -1 - (+1) = -2 → 음수 반환 → 시작(+1)가 앞으로 옴 ✅

🎯 최종 수정된 compare() 정리

int compare(const void *a, const void *b) {
    Event *ea = (Event*)a;
    Event *eb = (Event*)b;
    if (ea->time != eb->time) return ea->time - eb->time;
    return eb->delta - ea->delta; // 시작(+1) 우선 정렬
}

🎨 정리

  • qsort() 호출 시:

    • compare() 함수가 두 원소를 받음
    • time 오름차순 정렬
    • 같은 time이면 시작(+1) 먼저 오도록 정렬

  • 이렇게 정렬된 후 스위핑하면서 cur += delta 누적 계산.

좋아요! 🎯 이제 우리가 정리한 기준(compare() 함수) 대로 정렬이 끝난 후의 최종 이벤트 배열 상태를 한 줄 한 줄 나열해 줄게요. 이렇게 정렬된 상태를 보면 이후 스위핑 부분(cur += delta)을 이해하기가 훨씬 수월해질 거예요. 🔥

📥 원래 입력된 작업들

입력:

5
1 3
2 5
4 6
7 8
5 9

이 작업들을 이벤트로 변환 → 10개의 이벤트:

작업timedelta설명
작업11+1시작
작업13-1종료
작업22+1시작
작업25-1종료
작업34+1시작
작업36-1종료
작업47+1시작
작업48-1종료
작업55+1시작
작업59-1종료

🎯 정렬 기준 (compare())

  1. time 오름차순
  2. time이 같으면 delta가 +1(시작) 우선 정렬

🔄 정렬된 결과

이 기준을 적용하여 최종 정렬된 이벤트 배열은 아래와 같습니다:

indextimedelta비고 (설명)
01+1작업1 시작
12+1작업2 시작
23-1작업1 종료
34+1작업3 시작
45+1작업5 시작 (종료보다 우선)
55-1작업2 종료
66-1작업3 종료
77+1작업4 시작
88-1작업4 종료
99-1작업5 종료

🎯 이렇게 정리한 이유

✅ 이렇게 정리된 상태에서 이후 코드를 보면:

int cur = 0, ans = 0;
for (int i = 0; i < N*2; i++) {
    cur += events[i].delta;     // 현재 겹친 작업 수 변동
    if (cur > ans) ans = cur;   // 최댓값 갱신
}

이 과정을 한 단계 한 단계 손으로 디버깅할 수 있어요.

🔍 디버깅 예시 (스위핑 부분)

정렬된 이벤트를 하나씩 읽으며 cur과 ans 추적:

indextimedeltacur 계산curans
01+1cur = 0+111
12+1cur = 1+122
23-1cur = 2-112
34+1cur = 1+122
45+1cur = 2+133
55-1cur = 3-123
66-1cur = 2-113
77+1cur = 1+123
88-1cur = 2-113
99-1cur = 1-103

✅ 최종 ans = 3 → 한 시점에 가장 많은 작업 수 = 3

맞아요, 바로 그런 느낌이에요! 🎯
이 부분을 딱 짚어주셨네요. 이건 C 표준에서 정해 놓은 규칙이고, qsort()나 sort() 함수가 이 규칙을 따릅니다. 아래에서 조금 더 원리와 함께 쉽게 설명해 줄게요.

🤔 왜 음수를 반환할 때 앞에 오도록 하나?

이건 정렬 함수(qsort())가 비교 함수의 반환값을 어떻게 쓰도록 설계되었는지에 대한 규칙이에요.

🧠 정리:

C 언어의 qsort() 설명서(매뉴얼)에는 이렇게 나와요:

compare(a,b) 함수 반환값 < 0 → a가 b보다 "작음" → 정렬된 배열에서 a가 b보다 앞쪽

compare(a,b) 함수 반환값 > 0 → a가 b보다 "큼" → 정렬된 배열에서 a가 b보다 뒤쪽

반환값 == 0 → 두 원소는 정렬 기준에서 같다고 취급

✏️ 한 줄로 요약

✅ qsort() 안의 정렬 알고리즘(퀵정렬, 병합정렬 등)은 이 규칙을 따릅니다.

즉, 반환값 음수 → 바꿀 필요 없음(이미 순서 맞음), 반환값 양수 → 두 요소 순서 바꿔라.

🎨 쉽게 비유하기

학교에서 줄 세우기라고 생각해봅시다.

  • 선생님이 학생 A, B에게 말해요:
    “비교해 보고, A가 앞에 있어야 하면 음수를, 아니면 양수를 말해 주세요.”
  • 만약 학생들이 A가 키가 더 작다고 판단(음수 반환)하면 선생님은 “맞아, A가 B보다 앞에 와라”라고 정해요.
  • 반대로 A가 B보다 크다고 판단(양수 반환)하면 선생님은 “너네 자리 바꿔!”라고 정해요.

🧠 정리된 규칙

✅ 정렬할 때 compare() 반환값 음수 → A를 B보다 앞에 두자.
✅ 반환값 양수 → A를 B보다 뒤에 두자.

이 규칙 자체를 C 표준에서 정해 놓았기 때문에, 우리가 이 규칙만 지키면 qsort()가 내부적으로 열심히 자리 바꾸며 정리해 줍니다.

🎯 한 줄 결론

맞아요!
이건 qsort() 내부 정렬 알고리즘이 미리 정해 놓은 “약속”이에요.
우리는 그냥 compare()에서 기준을 잘 정해서 음수나 양수를 반환해주기만 하면 됩니다. 그러면 qsort()가 내부적으로 이 반환값을 보고 알아서 정렬해 주니까 걱정할 게 없어요. 😄

좋아요! 😊
지금 ea->time, eb->delta 처럼 나오는 -> 연산자에 대해 아주 기초부터 하나씩 차근히 설명해 드릴게요.

🎯 -> 연산자란?

✅ 상황

C언어에서 구조체(struct)를 다룰 때 두 가지 경우가 있어요:

  1. 구조체 변수를 쓸 때
  2. 구조체 포인터를 쓸 때

1️⃣ 구조체 변수의 멤버 접근

구조체 변수를 선언했다고 해봅시다:

struct Point {
    int x;
    int y;
};

struct Point p;
p.x = 10;
p.y = 20;

여기서 p는 변수이므로, 멤버(x, y)에 접근할 때 .(닷) 연산자를 씁니다.

2️⃣ 구조체 포인터의 멤버 접근

이번엔 구조체의 주소를 담고 있는 포인터라고 생각해 볼까요?

struct Point *pp;

pp 안에 p의 주소를 담아봅시다:

pp = &p; // p의 주소를 pp가 가리킴

이제 pp를 이용해 p.x와 p.y에 접근하려면 어떻게 해야 할까요?

⭐ 정답: -> 연산자

포인터를 이용해 구조체 멤버에 접근할 땐 ->를 씁니다:

pp->x = 10;
pp->y = 20;

이건 사실 아래와 완전히 같은 의미예요:

(*pp).x = 10;
(*pp).y = 20;

여기서 *pp는 포인터 pp가 가리키는 구조체이고, 그 구조체의 멤버 x를 수정하는 겁니다.

🧠 ->가 동작하는 방식

내부적으로 어떻게 돌아가냐?

  • pp->x
    → (*pp).x
    → pp 안에 있는 주소를 따라가서 구조체를 찾고, 그 구조체 안의 x 멤버를 가져옴.

📝 예제

#include <stdio.h>

struct Point {
    int x;
    int y;
};

int main() {
    struct Point p;
    p.x = 100;
    p.y = 200;

    struct Point *pp = &p;  // pp가 p를 가리킴

    printf("pp->x = %d\n", pp->x);  // pp가 가리키는 구조체의 x를 출력
    printf("pp->y = %d\n", pp->y);  // pp가 가리키는 구조체의 y를 출력

    return 0;
}

출력:

pp->x = 100
pp->y = 200

🔄 정리

형태의미
변수.멤버구조체 변수의 멤버 접근
포인터->멤버구조체 포인터가 가리키는 멤버 접근

🎯 결론

지금 우리가 본 ea->time이나 eb->delta는:

  • ea와 eb가 Event 구조체를 가리키는 포인터이므로
  • ->를 이용해서 그 포인터가 가리키는 구조체 안의 time과 delta 멤버에 접근한 거예요.
profile
류한선
good
이전 포스트

트릭/동기화/싱크로(일단 패스)

다음 포스트

상어의 식사

0개의 댓글