오늘의 할일
1. 코드카타 정리
2. 세션 정리
코드카타 정리
1. 체육복
문제 설명
점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.
전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.
#include <string>
#include <vector>
using namespace std;
int solution(int n, vector<int> lost, vector<int> reserve) {
int answer = 0;
// 체육복 개수를 기록할 출석부(n + 1)
// 처음엔 모든 학생 체육복 1로 세팅
vector<int> clothes(n + 1, 1);
// 도난당한 체육복 개수 1개씩 빼기 (1벌 -> 0벌)
for (int i = 0; i < lost.size(); i++) {
int student_num = lost[i];
clothes[student_num]--;
}
// 여벌 체육복 개수 1개씩 더하기
for (int i = 0; i < reserve.size(); i++) {
int student_num = reserve[i];
clothes[student_num]++;
}
// 1번 학생부터 n번 학생까지 순서대로 확인하며 체육복을 빌리기
for (int i = 1; i <= n; i++) {
// 만약 i번 학생이 체육복이 없다면 (0벌)
if (clothes[i] == 0) {
// 무조건 앞번호(i - 1)에게 먼저 여유분이 있는지(2벌)
if (i - 1 >= 1 && clothes[i - 1] == 2) {
clothes[i - 1]--; // 앞번호 것 1벌 빼고
clothes[i]++; // 내 것 1벌 추가
}
// 앞번호 친구가 못 빌려주면 뒷번호(i + 1)
else if (i + 1 <= n && clothes[i + 1] == 2) {
clothes[i + 1]--; // 뒷번호 것 1벌 빼고
clothes[i]++; // 내 것 1벌 추가
}
}
}
// 최종적으로 체육복이 1벌 이상 있는 학생
for (int i = 1; i <= n; i++) {
if (clothes[i] >= 1) {
answer++;
}
}
return answer;
}AI가 작성한 코드
#include <vector>
using namespace std;
int solution(int n, vector<int> lost, vector<int> reserve) {
// 1. 센티넬 패딩(Sentinel Padding): 경계 검사를 없애기 위해 (n + 2) 크기의 정적 배열을 씁니다.
// 학생 수가 최대 30명이므로, 최대 크기를 넉넉히 32로 잡아 스택(Stack) 메모리에 0으로 초기화합니다.
// 0: 기본(1벌), -1: 도난(0벌), 1: 여벌 있음(2벌)
int clothes[32] = {0};
// 2. 범위 기반 for문으로 증감만 깔끔하게 기록합니다.
for (int l : lost) clothes[l]--;
for (int r : reserve) clothes[r]++;
int answer = 0;
// 3. 1번부터 n번 학생까지 순회하며 빌리기와 정답 카운팅을 동시에 끝냅니다.
for (int i = 1; i <= n; i++) {
if (clothes[i] == -1) {
// 패딩(0번과 n+1번 칸)이 마련되어 있으므로 i-1 >= 1 같은 경계 검사 없이 즉시 접근합니다.
if (clothes[i - 1] == 1) {
clothes[i - 1] = 0;
clothes[i] = 0;
} else if (clothes[i + 1] == 1) {
clothes[i + 1] = 0;
clothes[i] = 0;
}
}
// 4. 별도의 카운팅 루프를 돌지 않고, 현재 학생의 최종 상태를 그 자리에서 바로 확인합니다.
if (clothes[i] >= 0) {
answer++;
}
}
return answer;
}센티넬 패딩 (Sentinel Padding / 경계선 쿠션 깔기)
배열 크기를 아예 양옆으로 한 칸씩 더 넓게(n + 2 크기, 코드에서는 최대치인 32) 만들어 두면 어떨까요? 0번 칸과 n+1번 칸이라는 빈 쿠션(값은 0)이 존재하기 때문에, 범위 체크 if문을 아예 지워버려도 메모리 침범 에러가 절대 나지 않습니다.
스택(Stack) 배열을 통한 Zero-Allocation
문제 조건에서 전체 학생 수 n은 최대 30명입니다. int clothes[32] = {0}; 처럼 고정 크기 배열을 선언하는 것이 압도적으로 빠릅니다. 함수가 호출되는 동시에 CPU와 가장 가까운 스택 메모리에 찰나의 속도로 생성되고 사라집니다.
단일 패스 (Single-Pass) 루프 병합
i번 학생이 체육복을 빌리는 순간(i-1이나 i+1에게 빌림) i번 학생의 운명은 그 자리에서 확정됩니다. 다음 차례인 i+1번 학생은 절대 앞번호(i)의 체육복을 뺏어 입지 않기(여벌이 있는 게 아니므로) 때문입니다. 따라서 체육복을 빌리자마자 바로 아래에서 if (clothes[i] >= 0) answer++;로 생존 여부를 카운트할 수 있습니다.
2. 문자열 나누기
문제 설명
문자열 s가 입력되었을 때 다음 규칙을 따라서 이 문자열을 여러 문자열로 분해하려고 합니다.
먼저 첫 글자를 읽습니다. 이 글자를 x라고 합시다.
이제 이 문자열을 왼쪽에서 오른쪽으로 읽어나가면서, x와 x가 아닌 다른 글자들이 나온 횟수를 각각 셉니다. 처음으로 두 횟수가 같아지는 순간 멈추고, 지금까지 읽은 문자열을 분리합니다.
s에서 분리한 문자열을 빼고 남은 부분에 대해서 이 과정을 반복합니다. 남은 부분이 없다면 종료합니다.
만약 두 횟수가 다른 상태에서 더 이상 읽을 글자가 없다면, 역시 지금까지 읽은 문자열을 분리하고, 종료합니다.
문자열 s가 매개변수로 주어질 때, 위 과정과 같이 문자열들로 분해하고, 분해한 문자열의 개수를 return 하는 함수 solution을 완성하세요.
#include <string>
#include <vector>
using namespace std;
int solution(string s) {
int answer = 0; // 분해한 문자열의 총 개수
char x = ' '; // 기준이 되는 첫 글자를 담아둘 바구니
int same_count = 0; // x와 같은 글자가 나온 횟수
int diff_count = 0; // x와 다른 글자가 나온 횟수
for (int i = 0; i < s.length(); i++) {
// 만약 새로 분해를 시작하는 타이밍이라면
if (same_count == 0) {
x = s[i]; // 현재 읽은 글자 -> 새로운 기준(x)
same_count = 1; // 기준 글자가 방금 1번 나왔으니 1로 시작
answer++;
}
// 이미 기준 글자(x)가 정해져 있는 상태라면
else {
if (s[i] == x) {
same_count++; // 기준 글자와 같으면 same 증가
} else {
diff_count++; // 기준 글자와 다르면 diff 증가
}
// 방금 숫자를 셌는데, 두 횟수가 처음으로 같아졌다면? -> 분해 완료
if (same_count == diff_count) {
// 카운트를 0으로 리셋
same_count = 0;
diff_count = 0;
}
}
}
return answer;
}AI가 작성한 코드
#include <string>
using namespace std;
int solution(const string& s) {
int answer = 0;
int balance = 0; // 같은 글자면 +1, 다른 글자면 -1을 누적할 단일 저울 변수
char x = '\0';
// 인덱스 변수(i) 없이 범위 기반 for문으로 문자를 직접 순회합니다.
for (char c : s) {
// 저울이 평형(0) 상태라면 새로운 덩어리의 시작점입니다.
if (balance == 0) {
answer++;
x = c;
balance = 1; // 첫 글자(x)가 들어왔으니 +1로 시작
} else {
// 삼항 연산자를 이용해 분기문을 한 줄의 수식으로 압축합니다.
balance += (c == x) ? 1 : -1;
}
}
return answer;
}수학적으로 두 횟수가 같다는 것은 같은 글자 수에서 다른 글자 수를 빼면 0이 된다는 뜻과 완전히 같습니다. balance라는 저울 변수 하나만 두고 기준 글자와 같으면 +1, 다르면 -1을 해주면, 저울이 0을 가리키는 순간이 곧 두 횟수가 같아져 분해가 완료된 시점이 됩니다.
삼항 연산자를 통한 분기 예측 최적화 (balance += (c == x) ? 1 : -1)
CPU는 if-else 문을 만나면 어느 쪽 길로 갈지 미리 예측하는데, 예측이 빗나가면 하던 작업을 취소하고 다시 읽어야 해서 속도가 느려집니다.
이 코드는 if-else 대신 삼항 연산자(? :)를 사용하여, 컴파일러가 이를 조건부 이동 명령어(CMOV)나 단순 산술 연산으로 변환하기 쉽게 만들었습니다.
매개변수 상수 참조 (const string& s)
문제의 조건상 문자열 s의 길이는 최대 10,000자입니다. 함수가 호출될 때 10,000글자를 메모리에 새로 복사하는 비용을 아끼고 원본 데이터의 주소만 받아와 즉시 읽기 시작하므로, 공간 복잡도 과 메모리 할당 제로를 달성합니다.
Unreal Engine 멀티플레이어 게임 개발 : 4회차 정리
궁금증 해결하기
