문제 설명

당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다. 홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면 이는 3번 폰켓몬 두 마리, 1번 폰켓몬 한 마리, 2번 폰켓몬 한 마리가 있음을 나타냅니다. 이때, 4마리의 폰켓몬 중 2마리를 고르는 방법은 다음과 같이 6가지가 있습니다.

1. 첫 번째(3번), 두 번째(1번) 폰켓몬을 선택
2. 첫 번째(3번), 세 번째(2번) 폰켓몬을 선택
3. 첫 번째(3번), 네 번째(3번) 폰켓몬을 선택
4. 두 번째(1번), 세 번째(2번) 폰켓몬을 선택
5. 두 번째(1번), 네 번째(3번) 폰켓몬을 선택
6. 세 번째(2번), 네 번째(3번) 폰켓몬을 선택

이때, 첫 번째(3번) 폰켓몬과 네 번째(3번) 폰켓몬을 선택하는 방법은 한 종류(3번 폰켓몬 두 마리)의 폰켓몬만 가질 수 있지만, 다른 방법들은 모두 두 종류의 폰켓몬을 가질 수 있습니다. 따라서 위 예시에서 가질 수 있는 폰켓몬 종류 수의 최댓값은 2가 됩니다. 당신은 최대한 다양한 종류의 폰켓몬을 가지길 원하기 때문에, 최대한 많은 종류의 폰켓몬을 포함해서 N/2마리를 선택하려 합니다. N마리 폰켓몬의 종류 번호가 담긴 배열 nums가 매개변수로 주어질 때, N/2마리의 폰켓몬을 선택하는 방법 중, 가장 많은 종류의 폰켓몬을 선택하는 방법을 찾아, 그때의 폰켓몬 종류 번호의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• nums는 폰켓몬의 종류 번호가 담긴 1차원 배열입니다.
• nums의 길이(N)는 1 이상 10,000 이하의 자연수이며, 항상 짝수로 주어집니다.
• 폰켓몬의 종류 번호는 1 이상 200,000 이하의 자연수로 나타냅니다.
• 가장 많은 종류의 폰켓몬을 선택하는 방법이 여러 가지인 경우에도, 선택할 수 있는 폰켓몬 종류 개수의 최댓값 하나만 return 하면 됩니다.

입출력 예

문제 풀이

나의 코드

소요 시간: 5분

시간 복잡도: O($n$)

import java.util.Map;
import java.util.HashMap;

class Solution {
    public int solution(int[] nums) {
        int answer = 0;
        int len = nums.length;
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < len; i++) {
            if (map.size() >= len / 2) {
                break;
            }    
            Integer mon = map.get(nums[i]);
            if (mon == null) { // 해시맵에 해당 포켓몬이 존재하지 않을 때
                map.put(nums[i], 1);
            }
            else {
                continue;
            }
        }

        return map.size();
    }
}

AI 코드

시간 복잡도: O($n$)

존재 여부만 확인하면 되므로 중복을 자동으로 제거하는 HashSet을 사용

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int solution(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int limit = nums.length / 2;

        for (int num : nums) {
            set.add(num);
            if (set.size() >= limit) break;
        }

        return set.size();
    }
}

문제 설명

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

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

제한사항

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

입출력 예

문제 풀이

나의 코드

소요 시간: 18분

시간 복잡도: O($n$)

import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
import java.util.stream.Collector;

class Solution {
    public String solution(String[] participant, String[] completion) {
        Map<String, Integer> map = new HashMap<>();
        List<String> list = new ArrayList<>();

        for (int i = 0 ; i < participant.length; i++) {
            String name = participant[i];
            map.put(name, map.getOrDefault(name, 0) + 1);
        }

        for (int i = 0; i < completion.length; i++) {
            String name = completion[i];
            map.put(name, map.get(name) - 1);
        }

        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if (entry.getValue() > 0) {
                list.add(entry.getKey());
            }
        }

        return String.join(", ", list);
    }
}

AI 코드

시간 복잡도: O($n$)

문제 조건을 보면 완주하지 못하는 사람은 1명이므로, 완주하지 못한 사람이 나오면 바로 그 값을 리턴하면 된다.

문제를 제대로 보지 않고 푸는 습관 때문에 코딩 테스트 문제를 풀며 알고리즘 설계를 처음부터 다시 시작하는 일이 꽤 잦았다. 문제를 꼼꼼히 살피는 습관을 가져야 할 것 같다.

import java.util.Map;
import java.util.HashMap;

class Solution {
    public String solution(String[] participant, String[] completion) {
        Map<String, Integer> map = new HashMap<>();

        for (String name : participant) {
            map.put(name, map.getOrDefault(name, 0) + 1);
        }
        for (String name : completion) {
            map.put(name, map.get(name) - 1);
        }
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if (entry.getValue() > 0) {
                return entry.getKey();  // 바로 반환
            }
        }

        return "";
    }
}

• 컴퓨터 시스템에 존재하는 다양한 저장소들로 구성되는 메모리 계층 구조를 이해하고 필요성을 안다.

• 메모리에 대한 물리 주소와 논리 주소를 이해하고 프로그램 실행 중에 논리 주소가 물리 주소로 변환됨을 안다.

• 프로세스의 실행에 필요한 메모리 할당 정책에 대해 이해한다.

• 연속 메모리 할당*

• 분할 메모리 할당*

• 모든 메모리 할당에는 사용할 수 없는 조각 메모리(단편화)가 발생하는데, 단편화에 대해 이해한다.

• 홀 선택(동적 메모리 할당)알고리즘을 이해한다.

• first-fit, best-fit, worst-fit*

• 메모리 관리 기법 중 세그멘테이션을 구체적으로 이해한다.

01. 메모리 계층 구조와 메모리 관리 핵심

1.1 메모리 계층 구조

메모리: CPU가 실행할 프로그램 코드와 데이터를 저장하는 물리 장치 메모리가 없는 컴퓨터는 존재할 수 없음

• 메모리는 컴퓨터 시스템 여러 곳에 계층적으로 존재

• 메모리 계층 구조의 중심은 메인 메모리(RAM)

• 전원이 끊어지면 저장된 정보가 사라짐 하드 디스크가 없는 컴퓨터는 존재할 수 있지만, 메인 메모리가 없는 컴퓨터는 존재할 수 없음*

• CPU로부터 멀어질수록 용량이 커지고, 속도가 느려지며, 가격이 비싸진다

메모리 계층화, 성능과 비용의 절충

• CPU 성능 향상 → 더 빠른 메모리 요구 → 작지만 빠른 off-chip 캐시 등장 → 더 빠른 액세스를 위해 on-chip 캐시 → 멀티 코에어 적합한 L1/2/3 캐시 빠른 메모리일수록 고가이므로 작은 용량 사용

• 컴퓨터의 성능 향상 → 처리할 데이터 대형화 → 저장 장치(하드디스크)의 대형화 → 빠른 저장 장치 요구 → SSD 등장

메모리 계층 구조의 각 요소

CPU 레지스터(CPU registers, $byte$)

• 현재 실행할 코드와 데이터, 혹은 다음에 실행할 몇 개의 코드와 데이터 저장

• 레지스터의 크기와 개수는 CPU의 종류에 따라 다름

캐시메모리(cache memory, $KB, MB$)

• CPU의 빠른 처리 속도에 맞추기 위해 도입됨

• 캐시 메모리가 있는 컴퓨터에서는 CPU가 캐시 메모리에서 프로그램 코드와 데이터를 읽어 실행함 → 코드와 데이터들은 메인 메모리로부터 캐시 메모리로 미리 복사되어야 함

• 캐시 메모리는 응답 속도와 위치에 따라 여러 레벨로 나누어 사용됨

• 멀티 코어 CPU의 경우, 코어 별로 L1/L2(MB 단위) 이름의 캐시를 두고, 모든 코어들이 공유하는 L3(KB 단위) 캐시를 둠(Core-i7의 경우 내부에 두기도 함)*

• SRAM(Static RAM)

• 전원이 공급되는 한 정보가 안정적으로 유지됨*

메인 메모리(main memory, RAM, $GB$)

• 현재 실행 중인 모든 프로세스의 코드와 데이터, 읽거나 쓰고 있는 여러 파일들의 블록, 운영체제의 커널 코드와 커널 데이터들이 저장됨

• 메모리에 있는 사용자 프로그램과 운영체제 커널을 구분하지 않고 당장 실행을 위해 필요한 일부분의 코드와 데이터가 캐시 메모리로 복사된다

• DRAM(Dynamic RAM)

• 시간이 지나면 저장된 정보가 사라지기 때문에,* 사라지기 전에 동일한 정보를 다시 기록해주어야 함( refresh )

• refresh를 지속적으로 수행해야 함*

보조기억장치(secondary memory, $TB$)

• 전원을 꺼도 지워지지 않는 대용량 저장 장치

• 파일이나 데이터베이스 등을 저장

• 메인 메모리의 크기 한게로 인해 메모리에 적재된 프로그램 코드와 데이터의 일부를 일시 저장(*스왑 영역 *)

속도도 잘 봐둘 것

프로그램의 실행과 메모리 계층 구조

• 보조기억장치에 저장된 실행 파일을 메인 메모리에 적재 → 메인 메모리의 일부 코드와 실행에 필요한 데이터가 L3 캐시로 복사 → L3 캐시에서 당장 실행할 코드와 데이터의 일부분이 L1/2 캐시로 복사 → CPU 코어는 L1/2 캐시에서 현재 실행할 명령과 데이터를 레지스터로 읽은 후 연산 실행

• 캐시가 없는 컴퓨터 → CPU가 메인 메모리로부터 데이터를 가져와 명령 실행 캐시를 가진 컴퓨터 → 캐시로부터만 프로그램 코드와 데이터를 읽고 실행

• 실행에 필요한 코드와 데이터는 반드시 캐시로 복사되어야 함*

메인 메모리와 캐시

캐시 미스(cache miss)

• CPU가 현재 프로세스나 스레드의 실행을 중단하고 다른 프로세스나 스레드를 실행할 때, L1/2 캐시에서 새로 실행하고자 하는 프로세스/스레드의 명령과 데이터를 찾을 수 없는 현상

• L1/2에 없다면 L3에서, L3에도 없다면 메인 메모리에서 데이터를 가져옴

• 캐시 미스는 연쇄적으로 발생함*

• 새로운 프로세스나 스레드의 코드와 데이터가 캐시로 들어오기 전에, 현재 캐시의 수정된 데이터는 다시 L3 캐시나 메인 메모리에 기록되어야 함

• 캐시 미스는 프로그램의 실행 중에도 발생

메인 메모리와 보조기억장치

가상 메모리(virtual memory)

• 메인 메모리 전체가 사용 중 이거나 빈 영역이 일정 이하로 줄어들었을 때, 메인 메모리에 적재된 코드나 데이터의 일부분을 하드디스크나 SSD에 저장하고 메인 메모리에 빈 공간 확보

1.2 메모리 계층화의 성공 이유, 참조의 지역성

참조의 지역성(locality of reference)

• 코드나 데이터, 자원 등이 아주 짧은 시간 내에 다시 사용되는 프로그램 특성

1.4 메모리 관리

메모리에는 현재 실행 중인 모든 프로세스들의 코드와 데이터, 그리고 운영체제의 코드와 데이터가 적재되어 있다.

메모리 관리 이유

메모리가 운영체제에 의해 관리되어야 하는 이유

• 1) 메모리는 공유 자원 여러 프로세스 사이에 메모리 공유 각 프로세스에게 물리 메모리 할당

• 2) 메모리 보호 프로세스의 독립된 메모리 공간 보장

• 다른 프로세스로부터 보호* 사용자 코드로부터 커널 공간 보호

• 3) 메모리 용량 한계 극복 설치된 물리 메모리보다 큰 프로세스 지원 필요 여러 프로세스의 메모리 합이 설치된 물리 메모리보다 큰 경우

• 4) 메모리 효율성 증대 가능한 많은 개수의 프로세스를 실행시키기 위함 (DOM, Degree of Multiprogramming)

• 프로세스당 최소한의 메모리만 할당*

메모리 관리 기능

기본적인 메모리 관리 기능은 할당과 보호의 2개로 요약할 수 있음 어떤 운영체제이든 이 2가지 기능은 반드시 지원되어야 함

• 메모리 할당 프로세스에게 메모리를 할당하는 기능

• 메모리 보호 프로세스가 다른 프로세스의 메모리 영역이나, 운영체제 영역을 침범·훼손하지 못하도록 보호하는 기능

메모리 주소

2.1 물리 주소와 논리 주소

메모리는 오직 주소를 이용해서만 접근됨

물리 주소(physical address): 실제 메모리 주소(하드웨어 주소)

• 물리 메모리(RAM)에 새겨진 주소

• 컴퓨터를 설계·제작하는 시점에 하드웨어에 의해 매겨지는 고정된 주소

• 0에서 시작하는 연속되는 주소 체계

• 메모리는 시스템 주소 버스를 통해 물리 주소(이진 신호)의 신호를 받음

논리/가상 주소(logical/virtual address): 프로그램 내에서 사용되는 주소

• 개발자/프로세스가 프로세스 내에서 사용하는 주소로 코드나 변수 등에 대한 주소

• 0에서 시작하여 연속되는 주소 체계, 프로세스 내에서 매겨진 상대 주소

• 프로그램에서 변수 n의 주소가 100번지라면, 논리 주소를 의미. 물리 주소는 알 수 없음*

• 컴파일러와 링커에 의해 매겨진 주소

• 실행 파일 내에 만들어진 목적 코드나 데이터의 주소들은 모두 논리 주소*

• CPU 내에서 프로세스를 실행하는 동안 다루는 주소는 모두 논리 주소

• 사용자나 프로세스는 결코 물리 주소를 알 수 없음

2.2 논리 주소의 물리 주소 변환

MMU(Memory Management Unit) 또는 주소 변환 하드웨어(Address Translation H/W)

• 논리 주소를 물리 주소로 바꾸는 하드웨어 장치

• CPU가 발생시킨 논리 주소는 MMU에 의해 물리 주소로 바뀌어 메모리에 도달*

• 오늘날 MMU는 MMU 덕분으로 여러 프로세스가 하나의 물리 메모리에서 실행되도록 됨 CPU 패키지에 내장 MMU 덕분으로 여러 프로세스가 하나의 물리 메모리에서 실행되도록 됨

• CPU가 발생시키는 주소 MMU가 CPU 칩(CPU 패키지) 외부에 위치 → 논리 주소 MMU가 CPU 칩 내부에 위치 → 물리 주소

• CPU 패키지 = CPU + MMU 등*

2.3 컴파일과 논리 주소, 논리 주소가 사용되는 이유

• 컴파일러는 프로그램을 논리 주소로 컴파일

• 컴파일 시점에 물리 메모리 몇 번지에 적재될지 알 수 없음* 코드와 전역 변수들은 0번지에서부터 시작하는 논리 주소에 할당

• 프로그램 실행 시작 시, 운영체제에 의해 프로그램을 물리 메모리의 적절한 위치에 적재하고, 매핑 테이블이 생성됨

• 현재 실행하는 명령의 물리 주소를 아는 것은 오직 MMU 밖에 없음

• 80386 칩은 CPU(Central Processing Unit), BIU(Bus Interface Unit),MMU(Memory Management Unit)로 구성됨

• MMU는 Segmentation Unit, Paging Unit으로 구성됨

• PAGE CACHE MMU 내부에 위치하며, 매핑 테이블의 일부를 저장해두는 캐시이다.

탐구 8-1

#include <stdio.h>
int n = 0;
int main() {
        printf("변수 n의 주소는 %p\n", &n); // n의 주소 출력
}

$ gcc -no-pie -o logical logicaladdress.c
$ ./logical
변수 n의 주소는 0x60103c
$ ./logical
변수 n의 주소는 0x60103c
$ ./logical
변수 n의 주소는 0x60103c
$

전역 변수 n의 주소는 논리 주소이기 때문에 실행할 때 마다 주소가 같다.

단, 온라인 터미널 (Cocalc)등에서 실행 시, 메모리 보호 기능인 PIE에 의해 전역 변수와 코드의 논리 주소가 매번 변경된다. PIE는 ASLR과 달리 코드 영역과 데이터 영역의 논리 주소까지 바꿈 $ gcc –no-pie –o logical logicaladdress.c: 보호 기능 제거 후 컴파일

TIP: ASLR

ASLR

• 해커들의 메모리 공격에 대한 대비책, 오늘날 대부분의 운영체제가 사용

• 주소 공간 랜덤 배치 프로세스의 주소 공간 내에서 스택이나 힙, 라이브러리 영역의 랜덤 배치 실행할 때 마다 논리 주소가 바뀌게 하는 기법 → 실행 마다 함수의 지역 변수와 동적 할당 받는 메모리의 논리 주소가 바뀜

• 코드와 전역 변수가 적재되는 데이터 영역의 논리 주소는 바뀌지 않음

03. 물리 메모리 관리

3.1 메모리 할당(memory allocation)

메모리 할당

• 운영체제가 새 프로세스를 실행시키거나 실행 중인 프로세스가 메모리를 필요로 할 때 프로세스에게 물리 메모리를 할당하는 것

• 프로세스의 실행은 할당된 물리 메모리에서 이루어짐

3.2 연속 메모리 할당(contiguous memory allocation)

• 프로세스별로 연속된 한 덩어리(single contiguous memory)의 메모리 할당
• 프로세스가 할당받은 메모리가 한 덩어리로 연속된 공간이라는 의미*

고정 크기 할당(fixed size partition allocation)

• 메모리를 고정 크기의 파티션으로 나누고, 프로세스 당 하나의 파티션 할당

• 파티션이 미리 나누어져 있기 때문에 고정 할당(fixed partitioning) 또는 정적 할당(static partitioning)이라고도 한다.

가변 크기 할당(variable size partition allocation)

• 메모리를 가변 크기의 파티션으로 나누고, 프로세스 당 하나의 파티션 할당

• 파티션이 미리 나누어져 있지 않고, 프로세스의 크기나 요청에 따라 바뀌므로 동적 할당(dynamic partiitioning)이라고도 한다.

단점

• 연속된 메모리를 할당하기 때문에 메모리 할당의 유연성이 부족

• 메모리 전체에 비어 있는 작은 공간(홀)들을 합하면 충분한 공간이 있음에도, 프로세스를 할당할만큼 연속된 메모리가 없어 적재할 수 없음

3.3 분할 메모리 할당(non-contiguous memory allocation)

• 프로세스에게 여러 덩어리의 메모리 할당

가변 크기 할당: 세그먼테이션(segmentation)

• 가변 크기의 덩어리 메모리를 여러 개 분산 할당

• 세그먼트(segment) 프로세스 내에서 하나의 단위로 다룰 수 있는 의미 있는 블록

• 하나의 함수, 객체가 될 수 있음* 프로세스에 존재하는 각 세그먼트의 크기가 다름

• 대부분의 시스템에서는 프로세스를 코드, 데이터, 스택, 힙의 4개 세그먼트로 분할·할당한다.

단점

• 프로세스들이 실해되고 종료되기를 반복하고 나면, 메모리에 적재된 세그먼트들 사이에 빈 공간이 생기게 되며, 일부는 크기가 작아 새 프로세스에게 할당하지 못하는 메모리 낭비(외부 단편화)가 초래됨

고정 크기 할당: 페이징(paging)

• 고정 크기의 덩어리 메모리를 여러 개 분산 할당

• 세그먼테이션의 메모리 낭비를 해결하기 위해 도입됨

• 프로세스를 논리적인 단위로 분할하지 않고, 논리주소 0번지부터 페이지(page)라고 부르는 고정 크기(동일한 크기)로 분할

• 물리 메모리 또한 페이지와 동일한 크기로 분할하여 프레임(frame)이라고 함

현대 컴퓨터 시스템은 페이징 기법을 기반으로 세그먼테이션을 혼합 사용함

04. 연속 메모리 할당

• 프로세스를 1개의 연속된 메모리 공간에 배치

• 메모리 전체를 여러 개의 파티션으로 분할*

• 각 프로세스에게 한 파티션 할당*

• 연속 메모리 할당은 초기 운영체제에서 사용

• MS-DOS: 한 프로세스가 전체 메모리 독점*

• 초기의 다중프로그래밍 운영체제*

4.1 고정 크기 할당

• 메모리를 처음부터 파티션(partition)이라고 부르는 고정 크기로 나누고, 프로세스에게 1개의 파티션을 할당
• 4/8/16KB 등 몇가지 파티션들을 만들어두고 적합한 파티션을 할당*

IBM OS/360 MFT(Multiple Programming with a Fixed Number of Tasks)

• 메모리 전체를 n개의 동일한 파티션으로 분할하여 프로세스마다 하나씩 할당

• 동시에 실행시킬 수 있는 프로세스 또한 n개

• 메모리가 부족할 때, 프로세스는 큐에서 대기

단점

• 프로세스가 파티션의 크기보다 작은 경우 메모리의 일부가 낭비됨

• 파티션보다 큰 크기의 프로세스는 처음부터 실행될 수 없음 → 시스템 운영자에 의해 실행시킬 전체 응용프로그램들의 크기가 사전에 계산됨

4.2 가변 크기 할당

• 고정 크기 할당의 메모리 낭비(내부 단편화)를 해결하기 위해 제시됨

• 처음부터 파티션을 나누어 놓지 않고, 프로세스와 동일한 크기의 메모리 할당

IBM OS/360 MVT(Multiple Programming with a Variable Number of Tasks)

• 할당되는 메모리 공간을 리전(region)이라고 부름

• 수용 가능한 프로세스의 개수는 가변적

고정 크기 할당과 가변 크기 할당 모두 가상 메모리 기법을 지원하지 않음

4.3 단편화(fragmentation)

• 프로세스에게 할당할 수 없는 조각 메모리들이 생기는 현상
• 조각 메모리를 홀(hole)이라고 부름

내부 단편화(internal fragmentation)

• 할당된 메모리 내부에 사용할 수 없는 홀이 생기는 현상
• 파티션보다 작은 프로세스를 할당하는 경우, 파티션 내에 홀 발생*
• IBM OS/360 MFT*

외부 단편화(external fragmentation)

• 할당된 메모리들 사이에 사용할 수 없는 홀이 생기는 현상

• 가변 크기의 파티션이 생기고 반환되는 과정에서 작은 홀 생성*

• 홀이 프로세스의 크기보다 작으면 할당할 수 없음*

• IBM OS/360 MVT*

• → MFT의 내부 단편화 문제를 해결하기 위해 만들어진 개선된 운영체제*

• 메모리 압축(memory compaction) 외부 단편화로 인해 할당할 메모리가 부족해지면 파티션을 이동시켜 홀을 없애는 방법

4.4 연속 메모리 할당 구현

• 연속 메모리 할당 구현을 위해서는 고정/가변 관계 없이 모두 하드웨어와 운영체제의 지원이 필요함

하드웨어 지원

• 논리 주소를 물리 주소로 변환하는 기능
• 프로세스가 다른 프로세스의 메모리 액세스를 금지하는 기능

base 레지스터: 현재 실행 중인 프로세스에게 할당된 물리 메모리 시작 주소 limit 레지스터: 현재 실행 중인 프로세스에게 할당된 메모리 크기 주소 레지스터: 현재 액세스하는 메모리의 논리 주소 주소 변환 하드웨어(MMU): 논리 주소를 물리 주소로 변환하는 장치

• MMU는 논리 주소를 논리 주소로 바꾸기 전, 다른 프로세스의 메모리 보호를 위해 논리 주소를 limit 레지스터의 값과 비교 할당된 메모리 주소 범위를 넘어섰다면 (논리주소 ≥ limit) → 오류 처리 커널 코드를 실행하고, 현재 프로세스를 강제 중단

현재 1000~1799번지에 적재된 상황

운영체제의 지원

• 운영체제는 모든 프로세스에 대해 할당된 물리 메모리의 시작 주소와

• 크기 정보*를 저장·관리 및 비어 있는 메모리 영역 관리

• 새 프로세스 스케줄링 시, 프로세스의 물리 메모리 시작 주소와 크기 정보를 CPU 내부의 base/limit 레지스터에 적재

4.5 홀 선택 알고리즘(hole selection algorithm)

• 또는 동적 메모리 할당(dynamic memory allocation)

• 프로세스를 처음 실행시키거나 실행 도중 메모리가 요구될 때, 적당한 홀을 선택해서 할당하는 기법

고정 크기

• 운영체제는 홀(파티션)들을 가용 메모리 리스트로 만들어 관리·선택함

가변 크기

• 홀마다 시작 주소와 크기 정보에 대한 홀 리스트 생성 및 관리

• first-fit 홀 리스트에서 처음 만나는 요청 크기보다 큰 홀 선택

• 할당 속도가 빠르지만, 외부 단편화로 인한 메모리 낭비가 큼*

• best-fit 홀 리스트에서 요청 크기를 수용하는 것 중 가장 작은 홀 선택

• 리스트가 정렬되지 않았을 때, 탐색 부담*

• 할당 후 가장 작은 홀이 생성됨*

• worst-fit 홀 리스트에서 요청 크기를 수용하는 것 중 가장 큰 홀 선택

• 리스트가 정렬되지 않았을 때, 탐색 부담*

• 할당 후 가장 큰 홀이 생성됨*

worst-fit 기법은 잘 사용하지 않음

단편화: 홀이 생기는 현상이 아닌, 메모리 할당 요청에 사용할 수 없게 된 작은 홀이 생기는 현상

4.6 연속 메모리 할당의 장단점

장점

• 논리 주소 → 물리 주소의 과정이 단순
• CPU의 메모리 액세스 속도 빠름
• 운영체제가 관리할 정보량이 적어서 부담이 덜함

단점

• 메모리 할당의 유연성이 떨어짐
• 작은 홀들을 합쳐 충분한 크기의 메모리가 있음에도, 연속된 메모리를 할당할 수 없는 문제가 발생

4.7 버디 시스템

• 오늘날 리눅스의 커널 메모리 관리에 사용되는 메모리 할당 알고리즘

• 고정 크기 할당과 가변 크기 할당의 장점을 결합하여 사용

05. 세그먼테이션 메모리 관리

5.1 세그먼테이션의 개요

세그먼트(segment)

• 프로그램을 구성하는 논리적 단위
• 각 세그먼트는 서로 크기가 다르다
• 세그먼트는 코드/데이터/스택/힙 세그먼트로 나뉨

세그먼테이션 기법

• 프로세스를 논리 세그먼트들로 나누고, 각 논리 세그먼트를 물리 메모리에 할당하는 메모리 관리 기법

프로세스의 주소 공간

• 프로세스의 주소 공간은 여러 개의 논리 세그먼트들로 구성
• 각 논리 세그먼트는 물리 세그먼트에 매핑
• 프로세스를 논리 세그먼트로 나누는 과정은 컴파일러와 링커에 의해 이루어짐
• • 컴파일러와 링커는 응용프로그램과 라이브러리의 코드를 모아 코드 세그먼트를 구성하고, 전역변수들을 모아 데이터 세그먼트 구성
• • 운영체제와 로더는 실행 파일에 구성된 각 논리 세그먼트를 물리 세그먼트에 할당, 논리 세그먼트 적재

5.2 논리 세그먼트와 물리 세그먼트의 매핑

• 운영체제는 프로세스의 각 논리 세그먼트가 할당된 물리 메모리 위치를 관리하기 위해 세그먼트 테이블을 구성함

• 세그먼트 테이블에는 세그먼트 크기를 담은 limit와 세그먼트 시작 물리 주소를 담은 base 정보가 저장된다.

• 세그먼트 테이블은 시스템에 1개만 존재함

• 프로세스의 실행과 종료에 따라 물리 메모리에는 홀이 생기며, 이로 인해 외부 단편화가 초래됨

• 새로운 프로세스가 실행되면 적절한 홀을 찾기 위한 홀 선택 알고리즘이나 동적 메모리 할당 알고리즘을 사용함

5.3 세그먼테이션의 구현

• CPU, 컴파일러와 링커, 운영체제, 로더 등이 모두 세그먼테이션을 지원
• 세그먼테이션의 구현은 CPU에 매우 의존적

하드웨어 지원

논리주소 구성 세그먼테이션의 논리주소 = [세그먼트 번호(s), 옵셋(offset)] 옵셋: 세그먼트 내 상대 주소

CPU

• 세그먼트 테이블의 시작 주소를 가리키는 레지스터 (segment table base register)

MMU 장치

• 논리 주소 → 물리 주소 변환 장치
• 논리 주소가 세그먼트 범위를 넘는지 판별(메모리 보호)
• (offset ≥ limit) 판별, offset이 더 작아야 함*
• 논리 주소의 물리 주소 변환(메모리 할당)

세그먼트 테이블

• 메모리에 저장
• 세그먼트별로 시작 물리 주소와 세그먼트 크기 정보
• 세그먼트 테이블의 일부를 MMU 내에 두기도 함

운영체제 지원

• 할당된 물리 세그먼트들과 빈 메모리(홀) 리스트로 만들고 관리

• 논리 세그먼트를 적재할 물리 세그먼트 할당·반환 기능

컴파일러, 링커, 로더 지원

• 사용자 프로그램은 컴파일러에 의해 사전에 정의된 세그먼트들로 분할·링킹

• 기계 명령에 들어가는 메모리 주소 [세그먼트 번호, 옵셋] 형식으로 컴파일

• 로더는 실행 파일에서 만들어진 논리 세그먼트 인지·세그먼트 테이블 갱신

5.4 단편화

• 세그먼테이션 기법은 가변 크기로 물리 세그먼트들을 할당하므로 외부 단편화가 필연적으로 발생

• 내부 단편화는 발생하지 않음

문제 설명

자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다.

• x에 n을 더합니다
• x에 2를 곱합니다.
• x에 3을 곱합니다. 자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요.

제한사항

• 1 ≤ x ≤ y ≤ 1,000,000
• 1 ≤ n < y

입출력 예

문제 풀이

1차 실행 오류

메모리 초과 동일한 숫자가 큐에 삽입되는 것이 원인

import java.util.Deque;
import java.util.ArrayDeque;

class Solution {
    public int solution(int x, int y, int n) {
        int answer = 0;
        Deque<int[]> queue = new ArrayDeque<>();
        queue.add(new int[]{x, 0});

        while(!queue.isEmpty()) {
            int[] cur = queue.poll();
            int X = cur[0], count = cur[1];

            if (X == y) {
                return count;
            }
            if (X * 2 <= y) {
                queue.add(new int[]{X * 2, count + 1});
            }
            if (X * 3 <= y) {
                queue.add(new int[]{X * 3, count + 1});
            }
            if (X + n <= y) {
                queue.add(new int[]{X + n, count + 1});
            }

        }

        return -1;
    }
}

나의 코드

소요 시간: 1시간 7분

시간 복잡도: O($y$)

x *= 3을 먼저 하고 x > y가 될 때 x /= 3을 하고 x *= 2... y / x도 해보며 이런저런 규칙을 찾아보려고 했지만, 규칙이 없었다.

claude AI에게 힌트를 요청했더니 BFS 방식으로 풀어야 한다고 알려주었다.

이를 통해 수학적인 규칙이 없는 문제들은 모든 조건을 탐색해야 한다는 깨달음을 얻었다.

이 문제의 경우 최소 조건을 알아내는 문제이므로 모든 조건을 탐색하는 DFS가 아닌, 최소 조건에 만족하면 바로 종료하는 BFS가 필요했다.

import java.util.Deque;
import java.util.ArrayDeque;

class Solution {
    public int solution(int x, int y, int n) {
        int answer = 0;
        Deque<int[]> queue = new ArrayDeque<>();
        boolean[] visited = new boolean[y + 1];
        queue.add(new int[]{x, 0});
        visited[x] = true;

        while(!queue.isEmpty()) {
            int[] cur = queue.poll();
            int X = cur[0], count = cur[1];

            if (X == y) {
                return count;
            }
            if (X * 2 <= y && !visited[X * 2]) {
                queue.add(new int[]{X * 2, count + 1});
                visited[X * 2] = true;
            }
            if (X * 3 <= y && !visited[X * 3]) {
                queue.add(new int[]{X * 3, count + 1});
                visited[X * 3] = true;
            }
            if (X + n <= y && !visited[X + n]) {
                queue.add(new int[]{X + n, count + 1});
                visited[X + n] = true;
            }

        }

        return -1;
    }
}

AI 코드

시간 복잡도: O($y$)

로직은 동일하나, forEach 문을 이용한 가독성을 증가시켰다.

import java.util.Deque;
import java.util.ArrayDeque;

class Solution {
    public int solution(int x, int y, int n) {
        if (x == y) return 0;

        boolean[] visited = new boolean[y + 1];
        Deque<int[]> queue = new ArrayDeque<>();
        queue.add(new int[]{x, 0});
        visited[x] = true;

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int X = cur[0], count = cur[1];

            for (int nx : new int[]{X * 2, X * 3, X + n}) {
                if (nx == y) return count + 1;
                if (nx < y && !visited[nx]) {
                    visited[nx] = true;
                    queue.add(new int[]{nx, count + 1});
                }
            }
        }

        return -1;
    }
}

문제 설명

영재는 택배상자를 트럭에 싣는 일을 합니다. 영재가 실어야 하는 택배상자는 크기가 모두 같으며 1번 상자부터 n번 상자까지 번호가 증가하는 순서대로 컨테이너 벨트에 일렬로 놓여 영재에게 전달됩니다. 컨테이너 벨트는 한 방향으로만 진행이 가능해서 벨트에 놓인 순서대로(1번 상자부터) 상자를 내릴 수 있습니다. 하지만 컨테이너 벨트에 놓인 순서대로 택배상자를 내려 바로 트럭에 싣게 되면 택배 기사님이 배달하는 순서와 택배상자가 실려 있는 순서가 맞지 않아 배달에 차질이 생깁니다. 따라서 택배 기사님이 미리 알려준 순서에 맞게 영재가 택배상자를 실어야 합니다.

만약 컨테이너 벨트의 맨 앞에 놓인 상자가 현재 트럭에 실어야 하는 순서가 아니라면 그 상자를 트럭에 실을 순서가 될 때까지 잠시 다른 곳에 보관해야 합니다. 하지만 고객의 물건을 함부로 땅에 둘 수 없어 보조 컨테이너 벨트를 추가로 설치하였습니다. 보조 컨테이너 벨트는 앞 뒤로 이동이 가능하지만 입구 외에 다른 면이 막혀 있어서 맨 앞의 상자만 뺄 수 있습니다(즉, 가장 마지막에 보조 컨테이너 벨트에 보관한 상자부터 꺼내게 됩니다). 보조 컨테이너 벨트를 이용해도 기사님이 원하는 순서대로 상자를 싣지 못 한다면, 더 이상 상자를 싣지 않습니다.

예를 들어, 영재가 5개의 상자를 실어야 하며, 택배 기사님이 알려준 순서가 기존의 컨테이너 벨트에 네 번째, 세 번째, 첫 번째, 두 번째, 다섯 번째 놓인 택배상자 순서인 경우, 영재는 우선 첫 번째, 두 번째, 세 번째 상자를 보조 컨테이너 벨트에 보관합니다. 그 후 네 번째 상자를 트럭에 싣고 보조 컨테이너 벨트에서 세 번째 상자 빼서 트럭에싣습니다. 다음으로 첫 번째 상자를 실어야 하지만 보조 컨테이너 벨트에서는 두 번째 상자를, 기존의 컨테이너 벨트에는 다섯 번째 상자를 꺼낼 수 있기 때문에 더이상의 상자는 실을 수 없습니다. 따라서 트럭에는 2개의 상자만 실리게 됩니다.

택배 기사님이 원하는 상자 순서를 나타내는 정수 배열 order가 주어졌을 때, 영재가 몇 개의 상자를 실을 수 있는지 return 하는 solution 함수를 완성하세요.

제한사항

• 1 ≤ order의 길이 ≤ 1,000,000
• order는 1이상 order의 길이 이하의 모든 정수가 한번씩 등장합니다.
• order[i]는 기존의 컨테이너 벨트에 order[i]번째 상자를 i+1번째로 트럭에 실어야 함을 의미합니다.

입출력 예

문제 풀이

1차 실행 오류

문제를 제대로 이해하지 못함 orders 배열의 원소 그 자체가 내려야 하는 순서로 이해함

그게 아니라 order[0] = 4 이면 첫번째로 내려야 하는 상자는 order[3]이 되는 것임

import java.util.Deque;
import java.util.ArrayDeque;

class Solution {
    public int solution(int[] orders) {
        Deque<Integer> container = new ArrayDeque<>();
        Deque<Integer> subContainer = new ArrayDeque<>();
        int order = 1;
        for (int i = 0; i < orders.length; i++) {
            if (orders[i] == order) { // 메인 컨테이너로 넣기
                container.push(orders[i]);
                order++;
            }
            else { // 서브 컨테이너로 넣기
                subContainer.push(orders[i]);
            }
        }
        while(!subContainer.isEmpty()) {
            if (subContainer.peek() == order) {
                container.push(subContainer.pop());
                order++;
            }
            else {
                break;
            }
        }
        return container.size();
    }
}

2차 실행 오류

orders = [1, 2, 3, 4, 5] 인 경우, i = 0일 때 subContainer에 [1, 1] 삽입 후 i = 1일 때 subContainer에서 pop() 후에 [2, 2] 가 저장이 되지 않음

조건문이 잘못되었음

import java.util.Deque;
import java.util.ArrayDeque;
import java.util.Map;

class Solution {
    public int solution(int[] orders) {
        Deque<Integer> container = new ArrayDeque<>();
        Deque<int[]> subContainer = new ArrayDeque<>();
        int index = 0;
        for (int i = 0; i < orders.length; i++) {
            if (subContainer.peek() != null && orders[index] == subContainer.peek()[0]) {
                container.push(subContainer.pop()[1]);
                index++;
            }
            else { // 서브 컨테이너로 넣기
                subContainer.push(new int[]{i + 1, orders[i]}); // 순서와 값 저장
            }
        }
        while(!subContainer.isEmpty()) {
            if (subContainer.peek()[0] == orders[index]) {
                container.push(subContainer.pop()[1]);
                index++;
            }
            else {
                break;
            }
        }
        return container.size();
    }
}

나의 코드

소요 시간: 1시간 3분

시간 복잡도: O($n$)

Stack을 이용하였다. 상자 하차 순서를 저장한 orders 배열을 index로 추적하게 하였고, 우선 subContainer에 상자를 넣은 후, 하차 순서와 비교해가며 꺼낼 수 있을 때 까지 비교하는 과정을 반복하였다.

그 후 subContainer에 남은 값을 꺼낼 수 있는지 루프를 돌아 마무리하였다.

import java.util.Deque;
import java.util.ArrayDeque;

class Solution {
    public int solution(int[] orders) {
        Deque<Integer> container = new ArrayDeque<>();
        Deque<int[]> subContainer = new ArrayDeque<>();
        int index = 0;
        for (int i = 0; i < orders.length; i++) {
            subContainer.push(new int[]{i + 1, orders[i]});
            while(true) {
                if (subContainer.peek() != null && orders[index] == subContainer.peek()[0]) {
                    container.push(subContainer.pop()[1]);
                    index++;
                }
                else {
                    break;
                }
            }
        }
        while(!subContainer.isEmpty()) {
            if (subContainer.peek()[0] == orders[index]) {
                container.push(subContainer.pop()[1]);
                index++;
            }
            else {
                break;
            }
        }
        return container.size();
    }
}

AI 코드

시간 복잡도: O($n$)

메인 컨테이너에는 어떤 값이 들어있어도 관계 없기 때문에 container를 Stack으로 정의할 필요가 없음

container를 count로 대체하고, pop()[1]같은 경우도 그냥 pop()을 사용함

import java.util.Deque;
import java.util.ArrayDeque;

class Solution {
    public int solution(int[] orders) {
        Deque<int[]> subContainer = new ArrayDeque<>();
        int index = 0;
        int count = 0;

        for (int i = 0; i < orders.length; i++) {
            subContainer.push(new int[]{i + 1, orders[i]});
            while (!subContainer.isEmpty() && orders[index] == subContainer.peek()[0]) {
                subContainer.pop();
                count++;
                index++;
            }
        }
        while (!subContainer.isEmpty()) {
            if (orders[index] == subContainer.peek()[0]) {
                subContainer.pop();
                count++;
                index++;
            } else {
                break;
            }
        }

        return count;
    }
}

문제 설명

신입사원 어피치는 카카오톡으로 전송되는 메시지를 압축하여 전송 효율을 높이는 업무를 맡게 되었다. 메시지를 압축하더라도 전달되는 정보가 바뀌어서는 안 되므로, 압축 전의 정보를 완벽하게 복원 가능한 무손실 압축 알고리즘을 구현하기로 했다.

어피치는 여러 압축 알고리즘 중에서 성능이 좋고 구현이 간단한 LZW(Lempel–Ziv–Welch) 압축을 구현하기로 했다. LZW 압축은 1983년 발표된 알고리즘으로, 이미지 파일 포맷인 GIF 등 다양한 응용에서 사용되었다.

LZW 압축은 다음 과정을 거친다.

1. 길이가 1인 모든 단어를 포함하도록 사전을 초기화한다.
2. 사전에서 현재 입력과 일치하는 가장 긴 문자열 w를 찾는다.
3. w에 해당하는 사전의 색인 번호를 출력하고, 입력에서 w를 제거한다.
4. 입력에서 처리되지 않은 다음 글자가 남아있다면(c), w+c에 해당하는 단어를 사전에 등록한다.
5. 단계 2로 돌아간다. 압축 알고리즘이 영문 대문자만 처리한다고 할 때, 사전은 다음과 같이 초기화된다. 사전의 색인 번호는 정수값으로 주어지며, 1부터 시작한다고 하자.

예를 들어 입력으로 KAKAO가 들어온다고 하자.

1. 현재 사전에는 KAKAO의 첫 글자 K는 등록되어 있으나, 두 번째 글자까지인 KA는 없으므로, 첫 글자 K에 해당하는 색인 번호 11을 출력하고, 다음 글자인 A를 포함한 KA를 사전에 27 번째로 등록한다.
2. 두 번째 글자 A는 사전에 있으나, 세 번째 글자까지인 AK는 사전에 없으므로, A의 색인 번호 1을 출력하고, AK를 사전에 28 번째로 등록한다.
3. 세 번째 글자에서 시작하는 KA가 사전에 있으므로, KA에 해당하는 색인 번호 27을 출력하고, 다음 글자 O를 포함한 KAO를 29 번째로 등록한다.
4. 마지막으로 처리되지 않은 글자 O에 해당하는 색인 번호 15를 출력한다.

이 과정을 거쳐 다섯 글자의 문장 KAKAO가 4개의 색인 번호 [11, 1, 27, 15]로 압축된다.

입력으로 TOBEORNOTTOBEORTOBEORNOT가 들어오면 다음과 같이 압축이 진행된다.

입력 형식

입력으로 영문 대문자로만 이뤄진 문자열 msg가 주어진다. msg의 길이는 1 글자 이상, 1000 글자 이하이다.

출력 형식

주어진 문자열을 압축한 후의 사전 색인 번호를 배열로 출력하라.

입출력 예제

문제 풀이

나의 코드

소요 시간: 1시간 1분

시간 복잡도: O($n^2$)

HashMap을 사용하여 해시맵에 존재하지 않을 때 까지 문자를 계속 더한다.

존재하지 않는 문자가 나올 경우엔 해당 문자를 제외한 해시맵 값을 리스트에 저장

제외한 값은 다시 문자의 시작이 됨

import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;

class Solution {
    public int[] solution(String msg) {
        int index = 1;
        Map<String, Integer> map = new HashMap<>();
        List<Integer> list = new ArrayList<>();

        // 해시맵에 색인 번호와 단어 추가
        for (char c = 'A'; c <= 'Z'; c++) {
            map.put(String.valueOf(c), index++);
        }
        String str = "";

        for (int i = 0; i < msg.length(); i++) {
            char c = msg.charAt(i);
            str += c;
            if (map.get(str) == null) { // 해시맵에 해당 키 값이 존재하지 않을 때
                map.put(str, index++); // 해시맵에 해당 값 저장
                list.add(map.get(str.substring(0, str.length() - 1))); // 이전의 문자열의 해시맵 값을 저장
                str = String.valueOf(c);
            }
        }
        if (str != "") { // 마지막 남은 문자 삽입
            list.add(map.get(str));
        }

        return list.stream().mapToInt(Integer::intValue).toArray();
    }
}

AI 코드

시간 복잡도: O($n$)

str +=는 매번 새로운 객체를 생성하므로 StringBuilder 사용

import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;

class Solution {
    public int[] solution(String msg) {
        int index = 1;
        Map<String, Integer> map = new HashMap<>();
        List<Integer> list = new ArrayList<>();

        for (char c = 'A'; c <= 'Z'; c++) {
            map.put(String.valueOf(c), index++);
        }

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < msg.length(); i++) {
            sb.append(msg.charAt(i));
            String str = sb.toString();
            if (!map.containsKey(str)) {
                map.put(str, index++);
                list.add(map.get(sb.substring(0, sb.length() - 1)));
                sb.setLength(0);
                sb.append(msg.charAt(i));
            }
        }
        if (sb.length() > 0) {
            list.add(map.get(sb.toString()));
        }

        return list.stream().mapToInt(Integer::intValue).toArray();
    }
}

• Q1. 한 세션에서 단계가 진행될수록, 컨텍스트는 가벼워지는가? 무거워지는가?

• Q2. 세션이 끊기고 새 세션을 시작하면 AI는 무엇을 기억하고 무엇을 잊나?

실제 컨텍스트 흐름

이전 단계에서 진행한 모든 컨텍스트를 다시 읽음. 단계가 진행될수록 컨텍스트가 누적되고 읽어야 할 컨텍스트가 많아짐

Spec-Kit 작동 원리

큰 컨텍스트 윈도우

• 200k의 컨텍스트 윈도우를 가짐, (보통 프로젝트는 100k 이하)

  잘 구조화된 문서

• spec.md, plan.md는 정형화된 형식이라 토큰 효율이 좋음

  헌법이 닻 역할

• 헌법 원칙은 항상 참조
• 일관성의 기준점

한계: 큰 프로젝트의 경우

컨텍스트 오버플로

• 사용자 스토리 10개 + 또는 작업 50개 + → 200k 한도 초과 시 앞부분 잘림

Implement 후반 품질 저하

• T001 깨끗 → T030은 100K + 누적 → 뒷부분 작업 품질이 앞부분만 못함 (context rot)

토큰 비용 증가

• 매 명령마다 누적 컨텍스트 전체 처리 → 후반으로 갈수록 한 번 호출 비용↑

대응 전략: 세션 분리

큰 프로젝트는 의도적으로 세션을 끊을 것

세션 분리 후

사라지는 것

• 이전 대화 기록
• AI가 기억하던 미묘한 맥락
• 진행 중이던 작업의 상태
• 임시 결정 사항

남는 것

• 모든 .specify/ 파일들
• 작성 코드 파일들
• tasks.md의 [X] 마커
• git 히스토리

영속적인 것에 의존하는 것이 spec-kit의 핵심

새 세션 시작 후: T009부터 다시 시작할 때

복원되는 컨텍스트

• constitution.md
• tasks.md
• T009 관련 문서
• ex) constracts/storage.md*

시나리오 별 위험도

끊는 지점은 깔끔한 작업 완료 시점

Implement 중간 상태 3가지

• 1) T008이 끝난 후 T009은 시작도 하지 않은 상태 → OK!

• 2) T009 코드를 절반쯤 쓰다가 종료한 경우 tasks.md에는 T009가 빈 박스이지만, 코드 폴더에는 T009의 일부 코드가 존재 다음 세션의 AI는 T009를 처음부터 다시 시작하려고 함 → 이미 존재하는 절반의 코드와 충돌 가능

• 3) TDD 중간 단계: 테스트는 작성했지만, 구현은 하지 않은 상태 → AI가 이를 어떻게 해석할 지 애매함

안전한 운영 체크리스트

종료 전 체크

• tasks.md에 체크되어 있지 않다면, 수동으로 체크할 것
• 대화 중 결정 사항이 spec.md, plan.md에 반영되었는지 확인
• 다음에 무슨 작업을 할 지 tasks.md나 README에 작성하기

세션이 중단되고 다시 시작할 때, 매 단계마다 모든 문서를 다시 읽어야 하나?

정답은 필요한 것만 선택적으로 읽기

단, 새로 읽는 파일은 선택적이지만, 이미 읽은 내용은 컨텍스트에 누적됨

AI는 정말 "기억"하는가?

AI는 기억하지 않는다

정답은 파일을 AI의 메모리처럼 쓴다

문서 계층과 참조 방향

각 단계에서 읽어야 할 문서가 자동으로 결정됨 모든 것을 다 읽을 필요가 없음

단계별 읽기 패턴

4가지 핵심 원칙

1) 피라미드 위→아래 참조

• 아래 단계는 위 문서를 읽음
• 위 단계는 아래를 무시

2) Constitution은 항상 읽힘

• 7단계 중 6단계가 참조
• 공통 context의 닻 (anchor)

3) 템플릿 vs 인스턴스 분리

• 템플릿: 한번 읽으면 끝
• 인스턴스: 단계별로 필요한 것만

4) Tasks.md가 체크포인트

• [X] 마커로 진행 상황 기록
• 재개 시 복구 포인트

재개 시나리오

A) constitution 작성 후, /speckit.specify 실행

AI가 읽는 파일

• .specify/memory/constitution.md
• .specify/templates.spec-template.md // spec을 작성할 때의 형식을 명시

읽지 않아도 되는 것

• 과거 세션1의 대화 기록
• 헌법 작성 시의 토론 내용
• 이전 명령어 히스토리

결국 이전 대화 내용은 읽지 않아도 됨

B) T001 ~ T008 완료, T009 중 실행 중단

읽는 것

• tasks.md(체크포인트)
• constitution.md (T009만 참조)

읽지 않는 것

• research.md(기술 결정 끝)
• 완료된 소스 파일
• 이전 세션 대화 기록

*tasks.md의 [x]마커가 세션 복구 포인트* (T009부터 재개, T009가 참조하는 문서만 선택적 로딩)

파일 시스템 = 외부 메모리

• 세션 간 상태 유지
• 병렬 작업 가능
• 도구 간 이식성

한계

코드-문서 불일치

• 직접 코드 수정 시, tasks.md 상태와 어긋남 → 수동 동기화 필요

  뉘앙스 손실

• 미묘한 맥락은 대화에서만 → Clarification에 명시 필수

  기능 간 얽힘

• 여러 기능이 같은 data-model 수정 시 복잡도 ↑ → /speckit.analyze 필수

  디버깅 부적합

• 해당 에러에 대한 질문은 대화형이 빠름 → spec-kit 외부에서 디버깅 후 반영

마무리

AI는 기억하지 않고, 문서가 기억한다.

한번에 다 밀어넣지 말고, 필요한 것만 읽혀라

세션이 끊겨도 괜찮다, 파일이 남아있다.

• GitHub에서 공개한 오픈소스 툴킷
• SDD를 실천할 때에 필요한 것들을 한 상자에 모아놓은 것

구성 요소

• Specify CLI 프로젝트 초기 세팅 도구 프로젝트 폴더 구조 자동 생성

• 템플릿 모음 명세·계획·작업 표준 양식 명세서는 어떻게 생겨야 하는지, 계획서에는 어떠한 항목들이 들어가야 하는지

• 슬래시 명령어 /speckit.* AI 역할 정의 AI와 대화할 때 특별한 명령어를 쓸 수 있게 해줌

7단계 워크플로 전체 그림

각 단계의 산출물이 다음 단계의 입력이 됨

1. Constitution

.specify/memory/constitution.md

• 프로젝트의 헌법
• AI의 시키지도 않은 일 까지 하려는 경향을 원천 차단

예)

• 모든 코드 테스트를 먼저 작성(TDD)
• 프로젝트는 최대 3개까지만
• 프레임워크는 직접 사용, 래퍼 금지
• API 응답은 500ms 이내

위반 시 ERROR로 중단·모든 단계의 기준점

2. 문서 계층 구조

• 위로 갈수록 '왜'(철학)
• 아래로 갈수록 '어떻게'(실행)
• 변경은 위→아래로만 전파
• 관심사 분리: 각 단계는 자기 차원의 고민만
• spec: 요구사항, plan: 기술, Tasks: 순서*
• 이러한 구조 덕분에 프로젝트가 커져도 추적이 가능함

3. 자동 검증 장치

• Constitution Check: Plan 단계 기술 선택이 헌법 위반이 아닌지 확인 위반 시 ERROR로 중단

• Analyze Cross-Validation: TASKS 후 spec·plan·tasks 모순 검증 CRITICAL / HIGH / MEDIUM 심각도

• TDD GATE: Implement 단계 테스트 없이 코드 작성 금지 Red→Green 사이클 강제

AI를 자유롭게 풀어주는 것이 아닌, 구조 안에서 자유롭게 움직이게 하는 것

8개 명령어 전체 요약

핵심 명령(5개, 필수)

/speckit.constitution: 헌법 수립 /speckit.specify: 명세 작성 /speckit.plan: 기술 설계 /speckit.tasks: 작업 분해 /speckit.implement: 코드 구현

선택 명령(3개, 품질)

/speckit.clarify: spec 모호할 때 /speckit.checklist: 도메인별 품질 /speckit.analyze: 구현 전 검증

3가지 핵심

1. 말하기 전에 쓰기

• 명세가 먼저, 코드는 그 다음. AI는 우리 머릿속을 보지 못함

  2. AI의 자유를 제한하라

• 헌법·게이트·체크리스트가 일관된 결과를 만든다.

  3. 문서는 공통 언어다

• spec.md는 팀원과도, AI와도, 미래의 나와도 소통하는 매개체

Specify

1) spec.md - user story

• Given, When, Then

2) Functional Requirements(FR-001~)

• 시스템이 반드시 해야할 일

3) Success Criteria(SC-001~)

• 성공 기준
• 측정 가능한 지표로만 작성*

4) Assumptions

• 가정

NEEDS CLARIFICATION

• AI가 확신하지 못한 부분을 명시적으로 남김
• 다음 단계인 clarify 단계에서 Q&A로 해결함*

Clarify

• NEEDS CLARIFICATION이 있을 때만 실행

Plan

• 기술 스택을 결정하는 단계
• Constitution Check Plan의 내용이 Constitution에 대해 원칙을 지키는지 점검
• 하나라도 만족하지 못할 시, 진행 불가*

1) research.md

• 기술 선택에 대한 근거

  Decision: useReducer
  Rationale: 배열 상태 단순
  Alternatives:
    Redux, Zustand

2) data-model.md

• 데이터 구조

  interface Todo {
    id: string;
    date: string;
    text: string;
    completed: boolean;
  }

3) contracts/storage.md

// localStorage 스키마
key: "calendar-todos"
value: Todo[]
        (JSON 배열)

4) quickstart.md

• 앱이 제대로 만들어졌는지 검증할 시나리오

5) plan.md

• 위 모든 문서들을 총괄하는 문서

5개의 문서는 서로 일관되어야 함 데이터 모델의 타입이 컨트랙트에 나타나야 하며, 스펙의 성공 기준이 퀵스타트에서 검증되어야 하는 등 → analyze 단계에서 체크함

Tasks

• 플랜을 실제 손으로 쓸 수 있는 작업 단위로 쪼갬

• phase로 구분함
• [P]: parallel, 병렬 실행 가능

Analyze

• 지금까지 만든 4개의 문서 spec, plan, taks, constitution이 서로 모순되지 않는지 검사
• 파일을 절대 수정하지 않음, 읽기 전용

CRITICAL, HIGH는 반드시 해결

Implement

• 실제 코드 작성

<student>

<instructor>

Union

select * from student union select * from instructor;

• 연산 시, 열의 개수와 각 열의 타입이 같아야 함
• 기본적으로 중복을 제거하여 출력함
• 중복을 허용하고 싶다면 union all 사용*

intersect

select dept_name from student intersect select dept_name from instructor;

except

select dept_name from student except select dept_name from instructor where dept_name = '음악학과';

테이블 수정

참고

• drop: 테이블 자체를 삭제
• delete: 테이블 내용을 삭제

ALTER TABLE

• 기존의 테이블 구조를 변경하는 데에 사용

alter table ~ add ALTER TABLE student ADD age INT;

• 새로운 속성(필드, 열)을 추가할 때 사용

alter table ~ drop ALTER TABLE student DROP COLUMN age;

• 기존 속성(필드, 열)을 삭제할 때 사용
• 저장되어 있던 데이터도 함께 삭제

alter table ~ modify ALTER TABLE student MODIFY name CHAR(10);

• 기존 속성(필드, 열)의 자료형, 크기, 제약조건 등을 변경할 때 사용
• 데이터 유형을 변경할 때, 해당 열은 비워져 있어야 함 ALTER TABLE student MODIFY stu_year NULL; // not null 제약 해제 UPDATE student SET stu_year = null; // 비우기 ALTER TABLE student MODIFY stu_year char(12);

describe

• desc or describe: 특정 테이블의 구조를 보여줌
• 해당 테이블의 열 이름, 데이터 유형, null 허용 여부 등

<student>

desc student;

ID는 키본키이므로 실제로는 unique 제약 포함. 따로 보이지만 않음

ALTER TABLE student ADD stu_year INT; UPDATE student SET stu_year = 1; ALTER TABLE student MODIFY stu_year NOT NULL; → ALTER TABLE student ADD stu_year INT DEFAULT 1 NOT NULL;

<MySQL> alter table student add age int after name; 이름 뒤에 age 속성 추가 기본값은 맨 뒤

테이블 정의

create table student(
    ID            varchar(5) primary key,
    name        varchar(20) not null,
    dept_name    varchar(20)
                    references department(dept_name),
    tot_cred    numeric(3, 0));

단, 속성 옆에 primary/foreign key 등을 붙이는 방식은 단일 속성으로 key가 되는 경우에만 적용 가능 (복합키의 경우 사용 불가능)

문제 설명

땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.

예를 들면,

| 1 | 2 | 3 | 5 |

| 5 | 6 | 7 | 8 |

| 4 | 3 | 2 | 1 |

로 땅이 주어졌다면, 1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸 (8)은 밟을 수 없습니다.

마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요. 위 예의 경우, 1행의 네번째 칸 (5), 2행의 세번째 칸 (7), 3행의 첫번째 칸 (4) 땅을 밟아 16점이 최고점이 되므로 16을 return 하면 됩니다.

제한사항

• 행의 개수 N : 100,000 이하의 자연수
• 열의 개수는 4개이고, 땅(land)은 2차원 배열로 주어집니다.
• 점수 : 100 이하의 자연수

입출력 예

문제 풀이

1차 실행 오류

시간 초과 오류

class Solution {
    private int answer = 0;
    public void route(int[][] land, int col, int sum, int before) {
        if (col >= land.length) {
            answer = Math.max(answer, sum);
            return;
        }
        for (int i = 0; i < land[0].length; i++) {
            if (i == before) {
                continue;
            }
            else {
                route(land, col + 1, sum + land[col][i], i);
            }
        }
    }
    int solution(int[][] land) {
        route(land, 0, 0, -1);

        return answer;
    }
}

AI 코드

DP(Dynamic Programming, 동적 프로그래밍)을 사용하여 해결

어차피 바로 이전 행은 더하지 못하므로 그 전 값은 어떤 값을 골라도 가장 큰 값만 골라도 다음 행과 더하는 데에 전혀 영향을 주지 않음

행렬 문제가 너무 많이 헷갈리고 어렵다. 더 많은 연습이 필요하다.

class Solution {
    int solution(int[][] land) {
        int rows = land.length;
        int cols = land[0].length;

        // dp[i][j] = i행 j열까지 왔을 때 최댓값
        int[][] dp = new int[rows][cols];

        // 첫 행 초기화
        for (int j = 0; j < cols; j++) {
            dp[0][j] = land[0][j];
        }

        // 각 행마다 이전 행의 다른 열 최댓값 + 현재 값
        for (int i = 1; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                for (int k = 0; k < cols; k++) {
                    if (k == j) continue;  // 같은 열 스킵
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][k] + land[i][j]);
                }
            }
        }

        // 마지막 행의 최댓값
        int answer = 0;
        for (int j = 0; j < cols; j++) {
            answer = Math.max(answer, dp[rows-1][j]);
        }
        return answer;
    }
}

• Scaffold를 이해하고 사용할 수 있다
• 앱바(App Bar)를 이해하고 사용할 수 있다
• 메뉴(DropdownMenu)를 이해하고 사용할 수 있다
• 다이얼로그(AlertDialog BottomSheet)를 구현할 수 있다
• 네비게이션(NavigationBar, NavigationDrawer, NavHost)을 이해·구현할 수 있다
• 스낵바(Snackbar)를 이해하고 사용할 수 있다.
• 코틀린 코루틴을 이해하고 설명할 수 있다.

Scaffold

• Material Design에서 복잡한 사용자 인터페이스를 위한 기본 구조
• App Bar, Floating Action Button등을 포함하고 일관된 디자인 제공

앱바(App Bar)

• 사용자에게 현재 화면에 필요한 액션과 네비게이션 액션을 제공하는 컨테이너
• 앱의 상단 또는 하단에 표시됨
• TopAppBar
• • 네비게이션 및 현재 필요 액션
• BottomAppBar
• • 현재 화면에 필요한 액션 중심

메뉴(DropdownMenu)

• 사용자가 아이콘, 텍스트 필드 또는 기타 컴포넌트를 클릭한 다음 일시적으로 나타나는 드롭다운 메뉴(옵션 목록)에서 옵션을 선택할 수 있음

• DropdownMenu, DropdownMenuItem을 이용하여 구현

• DropdownMenu

• • expanded: 메뉴 표시 여부
• • onDismissRequest: 메뉴가 닫힐 때 호출
• • content: 드롭다운 메뉴 옵션, DropdownMenuItem 컴포저블 사용

• DropdownMenuItem

• • text: 메뉴 옵션 이름
• • onClick: 옵션 선택 시 호출

다이얼로그(AlertDialog)

• 앱 콘텐츠 위에 대화상자로 메시지를 표시하거나 입력 받기 위한 UI
• • 파일 삭제와 같은 작업 진행 전에 사용자에게 확인 요청
• • 일정 관리에서 일정 추가할 때 사용자 입력을 받아야 하는 경우

Bottom Sheet Dialog

• 앱 아래쪽에 표시하는 다이얼로그

NavigationBar

• 보통 BottomBar에 같은 수준의 3-5개 대상 화면에 대해 화면 전환할 때 사용

• NavigationBar로 대상 선택 메뉴 구성

• • NavigationBarItem

• NavHost로 실제 보여질 화면을 구성

• NavigationBar와 NavHost의 연결은 navigation controller를 통해서

NavHost와 navigation controller를 사용하지 않아도 됨

NavigationDrawer

• 앱의 여러 화면으로 전환하는 대상을 선택할 수 있는 서랍
• ModalNavigationDrawer, ModalDrawerSheet를 이용하여 탐색 서랍을 구성
• • NavigationDrawerItem으로 대상 하나를 정의

Snackbar

• 화면 하단에 표시되는 간단한 알림

코틀린 코루틴(Coroutines)

• 협력적 멀티태스킹

• 모바일 앱은 애니메이션, 네트워크 통신이나 DB 접근처럼 시간이 오래 걸리는 작업이 많음

• • 문제점 작업이 완료될 때 까지 기다리는 동안 메인 스레드가 멈추게 되면(Blocking), 화면이 멈추고 ANR(Application Not Responding) 발생 가능
• • 해결책 기다리는 동안 스레드를 양보하고, 작업이 끝나면 다시 돌아오는 비차단(non-blocking) 방식 필요

• 코루틴은 스레드에 비해 가벼움

• • 스레드는 생성 및 컨텍스트 스위칭 비용이 높고, 강제로 선점
• • 코루틴은 자발적인 양보를 필요로 하며, 매우 가볍고 부담 없음
• • 하나의 스레드에 여러 코루틴이 자발적으로 양보하며, 협력적으로 멀티태스킹을 수행
• • 함수 앞에 suspend 키워드로 코루틴임을 나타냄

• suspend fun myCoroutine()*

코루틴 3대 요소

코루틴 스코프(CoroutineScope)

• 코루틴이 수행되는 범위, 코루틴은 반드시 코루틴 스코프 내에서 실행
• 예) viewModelScope: 뷰모델 생명주기에 맞춰 종료 lifecycleScope: 액티비티/프래그먼트 생명주기에 맞춰 종료*

디스패쳐(Dispatcher) = 스레드

• 어떤 스레드에서 실행?
• Dispatcher.Main: UI 업데이트용 (메인 스레드)
• Dispatcher.IO: 네트워크 디스크 읽기/쓰기 등 무거운 작업용
• Dispatcher.Default: CPU 집약적인 계산 작업용

Coroutine Context

• 어떤 정보를 담고 있는가?
• 코루틴의 이름, Dispatcher, Job 등을 담고 있는 컨텍스트

문제 설명

튜브가 활동하는 코딩 동아리에서는 전통적으로 해오는 게임이 있다. 이 게임은 여러 사람이 둥글게 앉아서 숫자를 하나씩 차례대로 말하는 게임인데, 규칙은 다음과 같다.

1. 숫자를 0부터 시작해서 차례대로 말한다. 첫 번째 사람은 0, 두 번째 사람은 1, … 열 번째 사람은 9를 말한다.
2. 10 이상의 숫자부터는 한 자리씩 끊어서 말한다. 즉 열한 번째 사람은 10의 첫 자리인 1, 열두 번째 사람은 둘째 자리인 0을 말한다. 이렇게 게임을 진행할 경우, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4, … 순으로 숫자를 말하면 된다.

한편 코딩 동아리 일원들은 컴퓨터를 다루는 사람답게 이진수로 이 게임을 진행하기도 하는데, 이 경우에는 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, … 순으로 숫자를 말하면 된다.

이진수로 진행하는 게임에 익숙해져 질려가던 사람들은 좀 더 난이도를 높이기 위해 이진법에서 십육진법까지 모든 진법으로 게임을 진행해보기로 했다. 숫자 게임이 익숙하지 않은 튜브는 게임에 져서 벌칙을 받는 굴욕을 피하기 위해, 자신이 말해야 하는 숫자를 스마트폰에 미리 출력해주는 프로그램을 만들려고 한다. 튜브의 프로그램을 구현하라.

입력 형식

진법 n, 미리 구할 숫자의 갯수 t, 게임에 참가하는 인원 m, 튜브의 순서 p 가 주어진다.

• 2 ≦ n ≦ 16
• 0 ＜ t ≦ 1000
• 2 ≦ m ≦ 100
• 1 ≦ p ≦ m 출력 형식 튜브가 말해야 하는 숫자 t개를 공백 없이 차례대로 나타낸 문자열. 단, 1015는 각각 대문자 AF로 출력한다.

입출력 예제

문제 풀이

나의 코드

소요 시간: 24분

시간 복잡도: O(n log n)

k진수에서 소수 개수 구하기 문제에서 사용했던 toString()을 사용하여 쉽게 풀 수 있었다.

class Solution {
    public String solution(int n, int t, int m, int p) {
        String answer = "";
        int index = 0;
        int order = 1; // 전체 순서
        int currentOrder = 1; // 현재 순서
        int count = 0; // 현재 구한 숫자의 개수
        while(true) {
            if (count >= t) {
                break;
            }
            String str = Integer.toString(index, n).toUpperCase(); // n진수 변환
            for (int i = 0; i < str.length(); i++) {
                if (currentOrder == p) {
                    answer += str.charAt(i);
                    count++;
                    if (count >= t) {
                        break;
                    }
                }
                currentOrder = order % m + 1;
                order++;
            }
            index++;
        }
        return answer;
    }
}

AI 코드

시간 복잡도: O(n log n)

+=를 사용하면 계속해서 새 객체를 생성하므로 StringBuilder를 이용하여 불필요한 객체 생성을 방지 또한 길이 추적도 count변수를 따로 두는 것이 아닌, 문자의 총 길이로 추적함

class Solution {
    public String solution(int n, int t, int m, int p) {
        StringBuilder sb = new StringBuilder();
        int index = 0;
        int total = 0; // 전체 문자 순서

        while (sb.length() < t) {
            String str = Integer.toString(index++, n).toUpperCase();
            for (int i = 0; i < str.length() && sb.length() < t; i++) {
                total++;
                if (total % m == p - 1) {  // p번째 순서
                    sb.append(str.charAt(i));
                }
            }
        }

        return sb.toString();
    }
}

1단계: 제품 명세서 작성

• prd.md 작성

사람은

• AI에게 기초적인 아이디어를 제공

AI는

• 기초적인 아이디어를 구체화하고, 요구사항을 논리적으로 정의
• prd.md 파일을 완성할 수 있도록 상세한 가이드를 제공

2단계: 기술 설계서 작성

• techspec.md (기술 설계 문서 또는 design.md) 작성

• 앞에서 만든 prd.md를 바탕으로 시스템의 뼈대를 잡는 과정

• AI의 도움을 받아 시스템 구조와 데이터베이스, API 등을 설계

• 이 단계가 끝나게 되면 개발의 전체적인 청사진이 완성됨

3단계: 구현 계획 수립

• tasks.md 파일이 준비됨

• techspec.md를 바탕으로 실제 개발에서 해결해야 할 세부 작업들을 정의

• AI는 복잡한 설계를 작은 단위의 태스크로 나누고, 우선순위를 정함

4단계: 티켓 주도 개발 진행

• 칸반 보드에 올라온 작업 티켓을 하나씩 해결

• AI와의 협력으로 실제 코드를 구현하고 테스트

• AI는 코드 작성 뿐만 아니라 버그 수정과 최적화까지 지원

0. 문서 정보

• 메타 데이터(Meta data) 이 문서가 언제 작성됐고, 누가 썼으며, 현재 확정된 버전인지 아니면 아직 고치고 있는 'Draft' 상태인지를 명시

1. 프로젝트 개요

1.1 배경 및 목적(Background)

• 프로젝트를 시작하는 이유

• 단순히 기능을 나열하는 것이 아닌, 현재 사용자가 겪는 고통(Pain Point)과 우리가 그것을 해결해야 하는 이유

• 이 문서 한장으로 '이 문서는 무엇이며, 우리는 왜 이 일을 하는가?' 에 대한 대답이 되어야 함*

1.2 목표 및 가치(Goals)

• 목표: 프로젝트가 끝났을 때 도달해야 할 목적지

• Core Goal: "이 제품을 통해 사용자에게 어떤 가치를 줄 것인가?"를 한 문장으로 정의

1.3 범위(Scope)

• In-Scope: 이번 버전에서 반드시 개발할 기능
• Out-Of-Scope: 이번 버전에서 제외된 기능

2. 유저 스토리

사용자 시나리오

• 사용자의 관점에서 소프트웨어가 제공해야 하는 기능을 짧고 명확하게 기술

• 3단 구성 공식: [누가, who]로서 [무엇, what]을 원한다. 왜냐하면 [이유, why] 때문이다.

AC(Acceptance Criteria)

• 인수 기준은 명확하고 구체적이어야 한다.

• 좋은 인수 기준은 "테스트할 수 있는가?"

• 예) 사용하기 편해야 한다 [X] - 편하다는 기준은 사람마다 다름 업로드 버튼을 누르고 1초 이내에 메시지가 떠야 한다 [O]*

• 더 체계적이고 전문적으로 쓰고 싶을 경우 EARS(Easy Approach to Requirements Syntax) 문법을 활용

  • 자연어 요구사항의 모호함을 제거하기 위해, 상황별 키워드를 사용하여 시스템의 동작을 표준화된 템플릿 형태로 기술하는 작성 방법론

• 할루시네이션을 방지하거나 줄이는 데에 핵심 도구*

AI의 역할

• 스토리 생성: 모호한 아이디어를 표준 템플릿 문장으로 변환

우선순위(Prioritization)-중증도 분류(Triage): 기능 우선순위

• P0 (Immediate) "이게 없으면 제품이 아니다" 싶은 필수 기능

• P1 (Urgent) "있으면 정말 좋지만, 없어도 당장 죽지는 않는" 기능

• P2 (Non-Urgent) "여유가 생기면 추가할 사치품"

이러한 우선순위를 잘 정해놓아야, 마감 기한이 다가왔을 때 무엇을 버릴지 잘 결정할 수 있음

사용자 스토리 우선순위 정하기: MoSCoW 기법 우리가 가진 제한된 시간과 자원 내에서 사용자에게 최대의 가치를 전달하기 위해 무엇에 집중해야 할지 결정하는 나침반

3. 대상 사용자(Target-Audience)

"모두를 만족시키는 제품은 누구도 만족시키지 못하는 결과물이 됨"

주요 페르소나(Primary Persona) 핵심 타겟의 특성 및 행동 양식

사용자 세그먼트(User Segmentation) 그룹 분류 (숙련도, 연령 등)

사용자 니즈(User Needs) 제품을 통해 해결하고자 하는 요구사항

4. 핵심 성과 지표(KPIs)

4.1 비즈니스 지표(Business Metrics)

• 재방문률(Retension) 사용자가 얼마나 우리 앱에 자주 들어오는지 보여줌

• 전환율(Conversion Rate) 실제로 물건을 구매했는지 보여줌

4.2 기술 지표(Technical Metrics)

• 로딩 속도, 에러율 등의 목표 수치

북극성 지표(North Star Metric)

• 모든 지표 중 팀이 가장 우선적으로 바라봐야 할 단 하나의 목표

• 구체적이고 측정 가능하며, 달성 가능한 숫자로 적어야 함

5. 상세 기능 요건(Functional Requirements)

• 앞에서 무엇을 만들지를 결정했다면, 이제는 그 기능들이 실제로 어떻게 움직여야 하는지 시스템의 언어로 번역

5.1 기능 그룹

• 개발자가 코드를 짤 때, 오해의 소지가 없도록 아주 정밀하게 로직(Logic)을 정의하는 것이 핵심

상세 기능 요건을 작성할 때, 고려해야 할 조건 3가진

• 로직(Logic) 시스템이 동작하는 기본 원리와 알고리즘

• 밸리데이션(validation) 입력값의 유효성을 검사하는 규칙

• 엣지 케이스(Edge Case) 예외적이거나 극단적인 상황에서의 처리 방식

우선 순위와 기능 요건의 연결

각 요건에는 F-01, F-02와 같은 고유한 ID를 부여해야 함

비즈니스 우선 순위가 높은 것 부터 시스템의 언어로 풀어가는 과정임

6. UI/UX 상세 요건

• 예쁜 그림을 보여주는 곳이 아닌, 사용자가 어떤 경로로 이동하고 화면이 어떤 논리적 구조를 갖는지 정의

• 디자인의 느낌보다 컴포넌트의 배치와 동작 규칙을 전달

1. 사용자 흐름(User Flow)

• 사용자가 서비스에 접속해서 목적을 달성할 때 까지 거치는 모든 단계

2. 와이어프레임(Wireframe)

• 정밀한 디자인 파일이 없더라도, 헤더에는 무엇이 들어가고, 메인 영역은 몇개의 열로 구성되는지 등의 정의

3. 인터랙션 규칙(Interaction Rules)

• 버튼을 눌렀을 때 로딩 표시를 어떻게 할 지 등

7. 기술적 제약

품질 속성 (Qualiy Attributes)

비기능 요구사항(Non-Functional Requirements, NFR)

• 기능이 무엇을 하는지(what)라면, 품질 속성은 그것을 얼마나 잘 하는지(How Well)

• 시스템의 기능이 수행되는 동안 만족해야 하는 운영적 특성이나 제약 사항

• 예) 개발자가 코드를 짤 때, 기능은 구현할 대상 품질 속성은 구현의 범위와 한계를 정하는 제약 조건 *

• 품질 속성은 반드시 측정 가능, measureable 해야 함

• 기능은 동작을 정의
• 품질은 상태를 정의

PRD 생성 전략

1. 프롬프트 템플릿 기반 전략

• AI에게 아주 명확한 청사진(템플릿)을 미리 제공하는 것
• 일관성과 전문성
• 조직 내에서 즉시 공유 가능한 수준의 PRD 초안을 얻을 수 있음

• Input Section에서 사용자는 아이디어를 모호하게 전달하지만, AI는 정해진 Role에 따라 이를 구체적인 아이디어로 구현해감
• 최소한의 Input 데이터를 통해, 고성능의 결과물을 뽑아내는 과정*

2. 질문 유도 방식

• 일부 주도권을 AI에게 넘기는 방식
• AI는 사람에게 탐색형 질의를 던짐
• 이러한 과정 속에서 추상적이었던 아이디어가 구체적으로 다듬어짐*
• AI와의 문답 과정을 통해 사용자의 Pain Point를 AI가 질문으로 짚어줌
• 기획의 빈틈을 매우는 데 탁월함*
• 아이디어가 아직 구체화되지 않은 초기 단계에서 강력함

3. 단계별 전략(step by step) or chain of thought(COT)

• 시스템 전체를 논리적인 단계에 따라 작업을 쪼개서 진행
• 비전 정의 → 사용자 스토리 → 구체적 인수 기준의 과정을 통해 AI의 인지 부하를 줄여 할루시네이션을 최소화, 각 섹션의 상세도를 극대화

1. 비전 정의 게임 개발을 예로 들었을 때, 게임의 본질적인 목적과 타켓 사용자를 정의해야 함 방향성이 이 단계에서 결정됨 *사용자가 해당 프로그램을 통해 얻을 수 있는 가장 중요한 가치 정의*

2. 사용자 경험 설계 이 과정에서 시스템의 필수 요소들이 자연스럽게 리스트업 됨

3. 핵심 로직 상세화 핵심 비즈니스 로직을 기술적으로 상세화하는 과정임 반드시 edge 케이스와 validation 로직을 이 단계에서 보완해야 함

4. 수용 기준 확정 각 기능이 완벽하게 구현되었는지 판단할 수 있는 기준인 Acceptance Criteria를 확정하며 문서를 마무리

이 세 가지 전략을 상황에 따라 유연하게 결합하는 하이브리드 접근법이 가장 강력

학습목표

• 평행투상과 원근투상의 차이점을 이해한다.
• 가시부피 설정방식을 이해한다.
• glOrtho() 함수와 glPerspective() 함수 파라미터를 이해한다.
• 전방 절단면은 되도록 시점에서 멀리 가져가는 이유를 이해한다.
• 시점좌표, 절단좌표, 정규화 장치좌표, 화면좌표로의 변환과정을 이해한다.

01. 투상

투상(Projection) = 가시변환(Viewing Transformation)

• 투상면(View Plane, Projection Plane)

• 관찰자 위치(View Point, Eye Position) = 카메라 위치(Camera Position) = 투상중심(Center of Projection, COP) = 시점좌표계 원점(Origin of VCS)

• 투상선(Projectors): 물체 곳곳을 향함

• 시선(Line of Sight): WCS 원점 또는 초점을 향함

• 투상면(Projection Plane, View Plane)

1-1 평행 투상(Parallel Projection)

원근법을 고려하지 않고 시점이 물체로부터 무한대의 거리에 있다고 간주

• 투상선이 평행
• 원래 물체의 평행선은 투상 후에도 평행
• 시점과의 거리에 무관하게 같은 길이의 물체는 같은 길이로 투상

1-2 원근 투상(Perspective Projection)

시점이 물체로부터 유한한 거리에 있다고 간주

• 투상선이 시점에서 출발하여 방사선 모양으로 펴져감
• 카메라나 사람의 눈이 물체를 포착하는 방법

*원근감 * 동일한 크기의 물체라도 시점으로부터 멀리 있는 것은 작게 보이고, 가까운 것은 크게 보임

소실점이 생겨남

원근변환(Perspective Transformation)

• 직선→직선, 평면→평면
• 직선은 그대로 직선을, 평면은 그대로 평면을 유지함*

02. 지엘의 투상 변환

2-1 지엘의 평행 투상

투상: void glMatrixMode(GL_PROJECTION); P' = MParallel · P

|1  0  0  0|
|0  1  0  0|
|0  0  0 -d|
|0  0  0  1|

역행렬이 존재하지 않음(특이변환)

해당 행렬은 암기해놓기

기본 평행투상

• 모델 좌표, 전역 좌표, 시점 좌표 순서로 변환된 상태
• P, P'은 시점 좌표계 기준의 좌표. 거리 d에 무관하게 동일
• 특이변환(Singular Transformation): 역변환이 없는 변환
• • 점 P→P', Q→P'은 가능하지만, P'→P, P'→Q는 불가능함
• • 그러나 나중에 깊이 정보(P'→Q, P'→P 거리)를 활용하기 때문에, 실제로 지엘은 이러한 변환을 가하지 않음
• • 개념적 설명임
• • 실제 지엘 내부에서는 투상결과 여전히 3차원 좌표가 유지됨
• 눈이 원점에 있다고 가정하고 -z 방향으로 관찰하고 있다고 생각함
• 모든 것은 눈을 기준으로 한 좌표*

가시부피에 의한 평행투상

가시부피(View Volume): 장면의 범위를 지정할 필요성

void glOrtho(GLdouble left, righ, bottom, top, near, far)

• 모두 카메라 기준 좌표계(눈)의 좌표
• near, far은 [-near, -far]로 변환된다(-z축의 방향이기 때문)

정규화 가시부피

정규화 가시부피(CVV: Canonical View Volume)

• 가로, 세로, 높이가 2인 정육면체로 투상
• 정규화 변환(Normalization Transformation)
• 변환 후 z축 방향이 반대가 됨
• 계산의 편리를 위함*

정규화 이유

• 평행투상, 원근투상을 동일한 모습의 정규화 가시부피로 변형

• 동일 파이프라인 사용*

• 정육면체를 기준으로 하면 연산이 간단함

• 다양한 해상도의 화면 좌표계로 변환하기가 간단함

정규화 가시부피 변환

T변환(중점 이동) → S변환(크기변환) → R변환(z축 반대로 이동)

예제) 점(l,b,-n,1), (r,t,-f,1)의 변환 후 좌표를 구하시오.

이렇게 만들어진 좌표계를 절단 좌표계(Clip Coordinate System, CCS) 라고 함

2-2 지엘의 원근 투상

4행의 3열에 특정 숫자가 있다 = 원근 투상이다?

현재

|  x  |
|  y  |
| -z  |
| z/d |

에서 실제 3차원 공간의 x, y, z 좌표를 계산하기 위해서는 동차좌표의 마지막 요소(z/d)로 이전 요소로 나누는 작업이 필요함 이러한 작업을 원근분할(Perspective Division)이라고 함

정규화 가시 부피에 의한 투상

절단 사각뿔(frustum) = 절두체

• 절두체 내부에 있는 물체만 관측 가능하고, 외부에 있는 물체는 관측 불가능함

원근 투상에서의 가시 부피 정규화

일반적 형태의 가시부피 void glFrustum(GLdouble left, right, bottom, top, near, far)

1. (a) 형태의 모양을 좌우 대칭시켜서 (b) 모양으로 만듦
2. (b) 형태의 모양을 늘려서 각도를 90º로 만듦
3. (c) 형태의 좌표를 (d) 좌표로 표현함

문제 설명

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

제한사항

• prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
• prices의 길이는 2 이상 100,000 이하입니다.

입출력 예

문제 풀이

나의 코드

소요 시간: 32분

시간 복잡도: O($n$)

뒤에 있는 큰 수 찾기 문제와 같은 알고리즘을 사용하여 Monotonic Stack을 사용해서 뒤에 큰 수가 오면 일괄적으로 해결하는 방식을 사용하였다.

현재 값보다 큰 값은 while에서 전부 제거되기 때문에 스택에 큰 값이 남아있을 수가 없다.

import java.util.Deque;
import java.util.ArrayDeque;

class Solution {
    public int[] solution(int[] prices) {
        int len = prices.length;
        int n;
        int[] answer = new int[len];
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i < len; i++) {
            while(!stack.isEmpty() && prices[stack.peek()] > prices[i]) {
                n = stack.pop();
                answer[n] = i - n;
            }
            stack.push(i); // [0]: 인덱스값, [1]: 실제 값
        }
        while(!stack.isEmpty()) {
            n = stack.pop();
            answer[n] = len - n - 1;
        }

        return answer;
    }
}

AI 코드

시간 복잡도: O($n$)

변수 선언 위치만 변경됨 int n은 스택 메모리에 할당되는데, 루프마다 선언/해제가 일어나도 스택 메모리는 매우 빠르고 컴파일러가 최적화함.

변수는 사용하는 범위(scope)에서만 선언하는 게 좋은 습관임. 성능보다 코드 안전성과 가독성을 위한 것임.

import java.util.Deque;
import java.util.ArrayDeque;

class Solution {
    public int[] solution(int[] prices) {
        int len = prices.length;
        int[] answer = new int[len];
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i < len; i++) {
            while (!stack.isEmpty() && prices[stack.peek()] > prices[i]) {
                int n = stack.pop();  // n을 루프 안에서 선언
                answer[n] = i - n;
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            int n = stack.pop();
            answer[n] = len - n - 1;
        }

        return answer;
    }
}

Java 컬렉션 스택/큐 구조

Deque (인터페이스)
├── ArrayDeque    // 배열 기반, 가장 빠름 ✅ 권장
└── LinkedList    // 연결 리스트 기반

Stack (클래스)   // 구식, 잘 안 씀
└── Vector 상속

Queue (인터페이스)
├── LinkedList
├── PriorityQueue
└── ArrayDeque

Deque<Integer> deque = new ArrayDeque<>();

// 스택으로 사용 (LIFO)
deque.push(1);    // 앞에 삽입
deque.pop();      // 앞에서 꺼내기

// 큐로 사용 (FIFO)
deque.offer(1);   // 뒤에 삽입
deque.poll();     // 앞에서 꺼내기

// 양방향
deque.addFirst(1);  // 앞에 삽입
deque.addLast(1);   // 뒤에 삽입
deque.peekFirst();  // 앞 보기
deque.peekLast();   // 뒤 보기

chapter_01

변화하는 채용환경, 전략적 취업준비?

2026 채용시장 특징

• 인공지능 활용 증가
• 직무중심 채용 증가
• 경력중심 채용 증가

희망직무와 자기소개서의 지원 동기는 반드시 일치해야 함

자격증

• 취득일자가 최신 또는 직무에서 가장 임팩트 있는 것 부터 맨 앞에 배치

활동, 경력사항

• 돈을 받고 하면 경력 + 어떤 역할을 했는지?
• 고객 응대 및 재고 관리 → 월 고객 클레임 20% 감소에 기여

자소서 쓰기 전

경험정리

• 학년별 경험정리
• 만다라트, 마인드 맵

직무 설정 및 분석

희망기업 분석

자소서 작성 기법

SOARA 기법

지원동기

회사 분석과 그에 따른 내가 하고자 하는 기여 주요포인트에 대한 나만의 생각과 목표 주요포인트에 대한 나의 경험 서술 회사/직무에 기여하고 싶은 부분

입사 후 포부

회사에서 이루고 싶은 것(장기적) 목표를 이루기 위한 플랜 직무에 대해 연차별 계획 한번 더 이루고자 하는 꿈 CDP

실습 희망분야

이 분야에 관심을 갖게 된 구체적 계기? 연결 경험과 보유 역량 이 기업을 선택한 이유 실습을 통해 얻고 싶은 것

직무 전문성(SOARA 기법으로 작성)

핵심역량 정의와 자신의 역량 관련 경험 경험 관련 상황/과제/문제 구체적인 문제해결을 위한 노력 성과 및 기여 의지

열정/도전 경험

도전 동기 & 상황 정의 포기하지 않은 이유 & 나만의 생각 구체적 행동 결과 & 배운점

성격 장단점

회사에서 일을 하는데에 필요한 성격인가? 장점 언급

장점 사례 단점과 단점으로 인한 문제 극복방법과 마무리

문제 설명

양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다.

• 0P0처럼 소수 양쪽에 0이 있는 경우
• P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우
• 0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우
• P처럼 소수 양쪽에 아무것도 없는 경우
• 단, P는 각 자릿수에 0을 포함하지 않는 소수입니다.
• • 예를 들어, 101은 P가 될 수 없습니다.

예를 들어, 437674을 3진수로 바꾸면 211020101011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 왼쪽부터 순서대로 211, 2, 11이 있으며, 총 3개입니다. (211, 2, 11을 k진법으로 보았을 때가 아닌, 10진법으로 보았을 때 소수여야 한다는 점에 주의합니다.) 211은 P0 형태에서 찾을 수 있으며, 2는 0P0에서, 11은 0P에서 찾을 수 있습니다.

정수 n과 k가 매개변수로 주어집니다. n을 k진수로 바꿨을 때, 변환된 수 안에서 찾을 수 있는 위 조건에 맞는 소수의 개수를 return 하도록 solution 함수를 완성해 주세요.

제한 사항

• 1 ≤ n ≤ 1,000,000
• 3 ≤ k ≤ 10

입출력 예

문제 풀이

1차 실행 오류

런타임 에러 및 실패 str에 0이 저장되는 경우 발생

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

class Solution {
    private String str = "";
    private List<Integer> list = new ArrayList<>();
    public void baseK(int num, int k) {
        if (num == 0) {
            return;
        }
        baseK(num / k, k);
        if (str != "" && (num % k) == 0) {
            list.add(Integer.parseInt(str));
            str = "";
        }
        else {
            str += String.valueOf(num % k);
        }
    }
    public boolean isPrime(int num) {
        if (num == 1) {
            return false;
        }
        for (int i = 2; i < num / 2; i++) {
            if (num % 2 == 0) {
                return false;
            }
        }
        return true;
    }
    public int solution(int n, int k) {
        int answer = 0;
        baseK(n, k);
        if (str != "") { // n이 비지 않았을 때
            list.add(Integer.parseInt(str));
        }
        for (int i = 0; i < list.size(); i++) {
            if (isPrime(list.get(i))) {
                answer++;
            }
        }
        return answer;
    }
}

2차 실행 오류

런타임 오류 및 실패 String을 ==를 이용한 비교 오류, .equals()사용해야함 isPrime() i % 2로만 나누는 오류 발견

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

class Solution {
    private String str = "";
    private List<Integer> list = new ArrayList<>();
    public void baseK(int num, int k) {
        if (num == 0) {
            return;
        }
        baseK(num / k, k);
        if (str != "" && (num % k) == 0) {
            list.add(Integer.parseInt(str));
            str = "";
        }
        else if (num % k != 0) {
            str += String.valueOf(num % k);
        }
    }
    public boolean isPrime(int num) {
        if (num == 1) {
            return false;
        }
        for (int i = 2; i < num / 2; i++) {
            if (num % 2 == 0) {
                return false;
            }
        }
        return true;
    }
    public int solution(int n, int k) {
        int answer = 0;
        baseK(n, k);
        if (str != "") { // n이 비지 않았을 때
            list.add(Integer.parseInt(str));
        }
        for (int i = 0; i < list.size(); i++) {
            if (isPrime(list.get(i))) {
                answer++;
            }
        }
        return answer;
    }
}

3차 실행 오류

런타임 오류

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

class Solution {
    private String str = "";
    private List<Integer> list = new ArrayList<>();
    public void baseK(int num, int k) {
        if (num == 0) {
            return;
        }
        baseK(num / k, k);
        if (!str.equals("") && (num % k) == 0) { // str이 비어있지 않고, num % k == 0일 때 저장
            list.add(Integer.parseInt(str));
            str = "";
        }
        else if (num % k != 0) { // str에는 0 저장하지 않음
            str += String.valueOf(num % k);
        }
    }
    public boolean isPrime(int num) {
        if (num < 2) {
            return false;
        }
        for (int i = 2; i < num / 2; i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
    public int solution(int n, int k) {
        int answer = 0;
        baseK(n, k);
        if (!str.equals("")) { // n이 비지 않았을 때
            list.add(Integer.parseInt(str));
        }
        for (int i = 0; i < list.size(); i++) {
            if (isPrime(list.get(i))) {
                answer++;
            }
        }
        return answer;
    }
}

나의 코드(AI 활용)

소요 시간: 58분

시간 복잡도: O(√n × log n)

int로 변환되는 수가 범위를 초과할 가능성이 있기 때문에 long 타입으로 선언해주어야 함 타입의 범위 초과 오류를 고려해서 코드를 작성할 것

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

class Solution {
    private String str = "";
    private List<Long> list = new ArrayList<>();
    public void baseK(int num, int k) {
        if (num == 0) {
            return;
        }
        baseK(num / k, k);
        if ((num % k) == 0) { // str이 비어있지 않고, num % k == 0일 때 저장
            if (!str.equals("")) {
                list.add(Long.parseLong(str));
                str = "";
            }
        }
        else { // str에는 0 저장하지 않음
            str += String.valueOf(num % k);
        }
    }
    public boolean isPrime(long num) {
        if (num < 2) {
            return false;
        }
        for (long i = 2; i * i <= num; i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
    public int solution(int n, int k) {
        int answer = 0;
        baseK(n, k);
        if (!str.equals("")) { // n이 비지 않았을 때
            list.add(Long.parseLong(str));
        }
        for (int i = 0; i < list.size(); i++) {
            if (isPrime(list.get(i))) {
                answer++;
            }
        }
        return answer;
    }
}

AI 코드

.toString() 오버로딩 방법에 따라

• 1) 그냥 문자열 반환
• 2) n진수를 문자열로 반환

class Solution {
    public boolean isPrime(long num) {
        if (num < 2) return false;
        for (long i = 2; i * i <= num; i++) {
            if (num % i == 0) return false;
        }
        return true;
    }

    public int solution(int n, int k) {
        // 1. k진수 변환 (Java 내장 함수 사용)
        String converted = Integer.toString(n, k);

        // 2. 0으로 split 후 바로 소수 판별
        int answer = 0;
        for (String part : converted.split("0", -1)) {
            if (part.isEmpty()) continue;
            if (isPrime(Long.parseLong(part))) answer++;
        }

        return answer;
    }
}

• 식사하는 철학자 문제를 통해 처음으로 제기된 교착상태 개념을 이해한다.
• 컴퓨터 시스템에서의 교착상태 정의와 교착상태를 판단할 수 있는 자원 할당 그래프를 이해한다.
• 교착상태가 유발 가능한 코프만의 4가지 조건을 이해한다.
• 교착상태의 해결 방법을 이해한다.
• 교착상태 예방, 회피, 감지 및 복구, 무시*
• 현대에서 교착상태 해결 방법은 교착상태 무시 방법임을 안다.

01. 교착상태 문제 제기

1.1 무한 대기와 교착상태

교착상태(deadlock)

• 자원을 소유한 채, 모두 상대방이 소유한 자원을 기다리면서 무한 대기
• 컴퓨터 시스템에서 교착상태는 다중프로그래밍 도입과 함께 발생하게 되었다.*
• 스레드 동기화 문제의 연장선

1.2 식사하는 철학자 문제(Dining Philosophers Problem)

문제의 개요

1965 년 Edsger Dijkstra에 의해 처음으로 문제화 병렬처리(concurrent programming)에서의 동기화 이슈와 해결 방법을 설명하고자 낸 학생 시험 문제(네델란드의 Eindhoven University of Technology)

• 5명의 철학자가 원탁에서 식사. 식사 시간은 서로 다를 수 있음
• 자리마다 스파게티 1개와 양 옆에 포크 있음
• 각 철학자는 옆의 철학자에게 말할 수 없음
• 식사를 하기 위해서는 양 옆의 포크를 모두 확보하여야 함
• 왼쪽 포크를 먼저 들고, 다음 오른쪽 포크를 드는 순서
• 포크가 사용 중이면 대기

문제 모두 거의 동시에 왼쪽 포크를 든 후, 오른쪽 포크를 들려고 할 때, 모두 상대가 가진 포크를 기다리면서 먹을 수 없는 교착 상태 발생

해결 방법 5명 중 마지막 사람을 제외한 4명이 왼쪽 포크를 먼저 잡고, 오른쪽 포크를 잡는 순서로 진행하고, 마지막 사람은 오른쪽 포크를 잡고 왼쪽 포크를 잡도록 함

철학자가 식사하는 모든 경우 분석

철학자들의 교착상태 원인 - 환형 요청/대기(circular request/wait)

• 5명 모두 왼쪽 포크를 가지고 오른쪽 포크를 요청하는 환형 고리 형성
• 환형 고리는 스스로 인식하거나 해체 불가

교착상태 해결 - 환형 요청/대기가 생기지 않게 규칙 변경

• 마지막 철학자만 오른쪽 포크를 먼저 잡고 왼쪽을 잡도록 규칙 수정 → 알고리즘으로 어떻게 표현할 것인가?

1.3 식사하는 철학자와 컴퓨터 시스템

식사하는 철학자 문제는 교착 상태 문제를 비유

교착상태는 다중프로그래밍 시스템 초기에 노출된 문제점

• 철학자: 스레드
• 포크: 자원
• 스파게티: 스레드가 처리할 작업

02. 교착상태

2.1 교착상태 정의

교착상태(deadlock)

• 자원을 소유한 2개 이상의 스레드들 사이에서, 각 스레드는 다른 스레드가 소유한 자원을 요청하여 무한정 대기하는 현상
• 1965년 Dijkstra의 banker's algorithm research에서 처음 제기*
• 풀지 못하는 포옹(deadly embrace)이라고도 함*

교착상태 발생 위치

• 사용자가 작성한 멀티스레드 응용프로그램에서 주로 발생

• 정교하지 못한 코딩에서 비롯*

• 커널 내에서도 발생

• 하지만 거의 발생하지 않음, 매우 정교하게 작성되었기 때문*

• 교착상태를 막도록 운영하는 컴퓨터 시스템은 거의 없음

• 막는 데에 많은 시간과 공간 비용 때문*

• 교착상태가 발생하도록 두고, 교착상태가 발생한 것 같으면, 사용자가 시스템 재시작, 또는 의심스러운 몇몇 프로그램 종료*

전형적인 멀티스레드 교착상태 사례

• 2개의 스레드가 각각 락 소유하고, 상대가 가진 락을 요청하고 기다릴 때

• 단일 CPU/다중 CPU 모두에서 발생 T1과 T2가 서로 다른 CPU에서 실행될 때에도 발생*

• 락과 자원에 대한 경쟁이 있는 한 교착상태는 언제든 발생 가능

2.2 컴퓨터 시스템에 잠재된 교착상태 유발 요인

1) 자원

• 자원은 교착 상태의 발원지
• 교착상태는 멀티스레드가 자원을 동시에 사용하려는 충돌이 요인
• 컴퓨터 시스템의 자원*
• 소프트웨어 자원*: 뮤텍스, 스핀락, 세마포, 파일, 데이터베이스 파일 락
• 파일 락: 스레드가 파일의 일부나 전체를 독점 사용하기 위한 잠금 (Unix에서 flock, POSIX의 파일락 등)*
• 하드웨어 자원*: 프린터, 메모리, 프로세서 등

2) 자원과 스레드

• 한 스레드가 여러 자원을 동시에 필요로 하는 상황이 요인 한 개의 자원만 필요한 경우 교착상태가 발생하지 않음

3) 자원과 운영체제

• 한 번에 하나씩 자원을 할당하는 운영체제 정책이 요인
• 스레드가 자원을 필요로 할 때, 반드시 운영체제로부터 할당받아야 함
• 운영체제로부터 필요한 자원을 한 번에 모두 할당받는다면, 교착상태가 발생하지 않을 수 있음*

4) 자원 비선점

• 할당된 자원은 스레드가 자발적으로 내놓기 전에 강제로 뺏지 못하는 정책
• 대부분의 운영체제는 스레드가 할당받은 자원을 강제로 빼앗지 못한다.
• 강제로 빼앗아 기다리는 스레드에게 줄 수 있다면, 교착상태가 발생하지 않는다.*
• 빼앗긴 스레드에게는 문제가 발생*

2.3 교착상태 모델링

자원 할당 그래프(Resource Allocation Graph, RAG)

• 컴퓨터 시스템에서 자원 할당 그래프를 이용하여 교착 상태를 표현하고 이 그래프를 기반으로 교착상태 예방, 회피, 감지 등이 운용됨

• 컴퓨터 시스템에 존재하는 자원과 스레드들의 상태를 나타내는 방향성 그래프(graph)이다.

부모/자식 관계가 성립하는 트리 구조로는 구현할 수 없음

그래프의 요소

• 꼭짓점(vertex) 스레드(원), 자원(사각형)
• 간선(edge) 할당 간선(allocation edge)과 요청 간선(request edge), 소유-요청 관계

표현되는 정보

• 컴퓨터 시스템에 실행 중인 전체 스레드와 자원
• 각 자원의 총 인스턴스 개수와 할당 가능한 인스턴스 개수
• 각 스레드가 할당받아 소유하고 있는 자원의 인스턴스 개수
• 각 스레드가 실행에 필요한 자원 유형과 인스턴스 개수

교착상태가 발생한 자원 할당 그래프 모양

• 스레드들이 교착 상태에 있게 되면, 스레드와 자원들을 연결하는 간선들의 환형 고리가 나타남

03. 교착상태 해결

3.1 코프만 조건(coffman condition)

• 교착상태를 유발할 수 있는 4가지의 필요충분 조건

다음 4가지 조건을 모두 가진 시스템에서는 언제든 교착 상태가 발생할 수 있음

• 상호 배제(Mutual Exclusion) 각 자원은 한 번에 한 스레드에게만 할당

• 소유하면서 대기(Hold & Wait) 스레드가 자원을 소유하면서 다른 자원 대기

• 강제 자원 반환 불가(No Preemption) 스레드에게 할당된 자원을 강제로 빼앗지 못함

• 환형 대기(Circular Wait) 한 그룹의 스레드들에서 각 스레드가 다른 스레드가 소유한 자원을 요청하는 환형 고리 형성

→ 이 4가지 조건 중 한가지라도 성립되지 않으면 교착상태에 빠지지 않음

3.2 교착상태 해결 방법

1) 교착상태 예방(prevention)

• 코프만의 4가지 조건 중 하나 이상의 조건이 아예 성립되지 못하도록 시스템을 설계하고 구성하여 교착상태가 발생할 여지가 없도록 예방하는 것

2) 교착상태 회피(avoidance)

• 운영체제가 자원을 할당할 때 교착상태에 빠지지 않을 것이라고 확신하는 경우에만 자원을 할당

• 시스템을 안전한 상태와 불안전한 상태로 분류하여 안전한 상태인 경우에만 자원 할당

• 자원을 할당할 때 마다 교착상태 가능성을 검사하므로 시스템의 성능을 많이 저하시킴

3) 교착상태 감지 및 복구(detection and recovery)

• 운영체제가 교착상태를 감지하는 별도의 프로그램을 백그라운드로 구동시켜 교착상태에 빠진 스레드 그룹을 발견하면, 교착상태로부터 해제

• 교착상태를 감시하는 작업이 주기적으로 실행되어야 하므로 시스템에 많은 부담

4) 교착상태 무시(ignore reboot)

• 교착상태가 발생하도록 내버려 두는 방법

• 교착상태는 웬만해서 발생하지 않으며, 발생했을 때 사용자나 관리자가 대책을 세우면 된다고 생각함

• 교차상태가 발생한다 하더라도, 범용 시스템에서는 큰 문제가 되지 않음

• 현재 대부분의 범용 운영체제에서 사용하고 있음

• 교착상태 무시 알고리즘을 ostrich 알고리즘(타조 알고리즘)이라고 함

TIP 교착상태로 인해 시스템 전체가 중단되는가?

• 교착상태가 발생한다고 해서 시스템 전체가 멈추지 않음
• 많은 스레드들이 교착상태에 있을 때는 시스템을 재시작(reboot)

3.3 교착상태 예방

• 코프만의 4가지 조건 중 최소 하나를 성립하지 못하게 함

1. 상호배제(Mutual Exclusion) → 상호배제 없애기

• 2개 이상의 스레드가 동시에 자원을 사용할 수 있도록 허용

근본적으로 적용 불가능한 방법

2. 소유하면서 대기(Hold & Wait) → 기다리지 않게

• 1) 스레드가 필요한 자원을 처음부터 모두 가지게 함

• 당장 사용하지 않는 자원을 스레드에게 묶어두기 때문에 자원 활용률이 떨어짐*

• 2) 스레드가 자원을 소유한 상태에서 새로운 자원이 필요하게 되면, 현재 할당받은 모든 자원을 반환하고, 필요한 모든 자원을 한꺼번에 모두 요청하는 방법

1, 2 모두 가능하지 않거나, 매우 비효율적 범용 시스템에서는 불가능, 임베디드 시스템에서는 가능

3. 강제 자원 반환 불가(No-Preemption) → 자원의 선점 허용

• 더 높은 순위의 스레드가 자원을 요청하면, 자원을 가진 낮은 순위의 스레드에게서 강제로 자원을 빼앗음

• 하지만 자원을 강제 반환하게 된 스레드가 자원을 다시 사용하게 될 때, 이전 상태로 되돌아갈 수 있도록 상태를 관리해야함

간단하지 않으며 오버헤드가 큼

4. 환형 대기(Circular Wait) → 환형 대기 제거

• 모든 자원에 번호를 매기고, 스레드는 반드시 번호 순으로 자원을 할당

3.4 교착상태 회피

• 자원할당 알고리즘을 이용하여 교착상태를 방지하는 기법

• 자원 할당 알고리즘 자원 할당을 요청받았을 때, 앞으로 환형 대기가 발생하지 않는다는 확신이 서는 경우에만 자원을 할당

banker's 알고리즘

• Edsger Dijkstra에 의해 개발된 알고리즘

• 자원 할당 전에 미래에 교착 상태가 발생하지 않을 것인지 판단하는 알고리즘

• 안전한 상태 현재 프로세스들을 어떤 순서로 실행시켰을 때, 모든 프로세스들이 자신이 요청하는 자원을 가지고 실행할 수 있는 상태

• 불안전한 상태 환형 대기에 빠질 수 있는 상태

• 알고리즘 1) 각 프로세스가 실행 시작 전에 필요한 전체 자원의 수를 운영체제에게 알림 2) 자원을 할당할 때 마다 안전한 상태인지, 불안전한 상태인지 판단 3) 이러한 상태는 각 스레드가 필요로 하는 자원의 개수, 현재 실행 중인 각 스레드가 할당 받은 자원의 개수, 시스템 내 할당할 수 있는 자원의 개수를 토대로 판단함

• 비현실적 각 프로세스가 실행 전에 필요한 자원의 개수를 아는 것은 불가능 프로세스의 개수도 동적으로 변하기 때문에, 미리 프로세스의 개수를 정적으로 고정시키는 것은 불가능

사용할 자원의 개수를 미리 알 수 있는 임베디드 시스템이나, 실시간 제어 시스템에서 사용 가능

3.5 교착상태 감지 및 복구

• 교착상태를 감지하는 백그라운드 프로그램을 상시적으로 실행시켜, 교착상태를 감지하고 해제한다

• 자원 할당 그래프에 환형 대기 모양을 갖는 부분이 있는지 판단

자원 강제 선점(preemption)

• 교착 상태에 빠진 스레드 중 하나를 선택하고, 스레드가 소유한 자원을 강제로 빼앗아 이 자원을 기다리는 스레드에게 할당
• 이렇게 함으로써 스레드의 환형 대기 고리를 끊음*

롤백(rollback)

• 교착상태가 발생할 것으로 예측되는 스레드들의 상태를 주기적으로 저장
• 교착상태가 발생하면 가장 최근에 저장해둔 상태로 복구
• 다시 시작하면 스케줄링 등 여러 요인에 의해 자원 할당 순서가 달라짐

롤백을 위한 주기적인 상태 저장으로 인해, 시스템의 시간과 저장 공간을 소모하여 시스템 성능을 저하시킴

스레드 강제 종료(kill process)

• 교착 상태에 빠진 스레드 중 하나를 강제로 종료시키는 방법
• 사용자나 시스템 관리자가 사용하는 방법

3.6 교착상태 무시: 타조(ostrich) 알고리즘

ostrich: 현실도피주의자

교착상태를 해결할 필요가 있을까?

• 컴퓨터 시스템에서 교착상태에 대한 통계치 없음

교착상태는 반드시 발생함

• 하지만, 발생 가능성이 극히 적고, 피하기 위한 비용이 많이 들어감

최적의 알고리즘: 타조 알고리즘

• put your head in the sand 접근법 교착상태는 발생하지 않을 것이라 생각하고 아무 대책을 취하지 않는 접근법

• Unix(리눅스)와 윈도우 등 거의 모든 운영체제에서 사용 의심 가는 스레드를 종료시키거나 시스템 재시작(reboot)

• 관련 데이터를 잃어버릴 수 있으나, 비용 면에서 더 나은 방법임*

• 핵 시스템, 비행기, 미사일 등 시스템 재시작이 파국을 초래할 수 있는 hard-real time 시스템이나, 환자 감시 시스템 등에는 적합하지 않음

*"Not everything worth doing is worth doing well"*

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다. Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

제한 사항

• scoville의 길이는 2 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

입출력 예

문제 풀이

1차 실행 오류

K 이상으로 만들 수 없는 경우 -1을 리턴하는 조건문을 추가했지만, 여전히 오류 실패, 런타임 오류, 실행 시간 초과

import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.stream.Collectors;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;

        List<Integer> list = Arrays.stream(scoville).boxed().collect(Collectors.toCollection(ArrayList::new));
        list.sort(null); // 오름차순 정렬
        while(true) {
            if (list.get(0) >= K) {
                break;
            }
            int first = list.get(0);
            list.remove(0);
            int second = list.get(1);
            list.remove(0);
            int res = first + second * 2;
            list.add(res);
            list.sort(null);
            answer++;
        }
        return answer;
    }
}

2차 실행 오류

second를 가져올 때 인덱스가 당겨진 상태라 0을 가져왔어야 하는데 1을 가져옴 실패, 런타임 오류, 실행 시간 초과

import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.stream.Collectors;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;

        List<Integer> list = Arrays.stream(scoville).boxed().collect(Collectors.toCollection(ArrayList::new));
        list.sort(null); // 오름차순 정렬
        while(true) {
            if (list.size() < 2 && list.get(0) < K) {
                return -1;
            }
            if (list.get(0) >= K) {
                break;
            }
            int first = list.get(0);
            list.remove(0);
            int second = list.get(1);
            list.remove(0);
            int res = first + second * 2;
            list.add(res);
            list.sort(null);
            answer++;
        }
        return answer;
    }
}

3차 실행 오류

sort()로 인한 실행 시간 오류

import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.stream.Collectors;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;

        List<Integer> list = Arrays.stream(scoville).boxed().collect(Collectors.toCollection(ArrayList::new));
        list.sort(null); // 오름차순 정렬
        while(true) {
            if (list.size() < 2 && list.get(0) < K) {
                return -1;
            }
            if (list.get(0) >= K) {
                break;
            }
            int first = list.get(0);
            list.remove(0);
            int second = list.get(0);
            list.remove(0);
            int res = first + second * 2;
            list.add(res);
            list.sort(null);
            answer++;
        }
        return answer;
    }
}

AI 코드

PriorityQueue를 이용한 자동 정렬

import java.util.PriorityQueue;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;

        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int x : scoville) {
            pq.add(x);
        }

        while (pq.peek() < K) {
            if (pq.size() < 2) return -1;

            int first = pq.poll();
            int second = pq.poll();
            pq.add(first + second * 2);
            answer++;
        }

        return answer;
    }
}

인터페이스 = 구조체 패턴

Collection (인터페이스)
├── List        → 순서 O, 중복 O
│   ├── ArrayList     // 동적 배열, 조회 빠름
│   ├── LinkedList    // 연결 리스트, 삽입/삭제 빠름
│   └── Vector        // ArrayList의 동기화 버전 (구식)
│
├── Set         → 순서 X, 중복 X
│   ├── HashSet       // 순서 없음, 가장 빠름
│   ├── LinkedHashSet // 삽입 순서 유지
│   └── TreeSet       // 자동 오름차순 정렬
│
└── Queue       → FIFO (선입선출)
    ├── LinkedList    // 일반 큐
    ├── PriorityQueue // 우선순위 큐 (최소 힙)
    └── ArrayDeque    // 양방향 큐 (스택으로도 사용)

    └──Deque (인터페이스)
    ├── ArrayDeque  // ✅ 권장
    └── LinkedList

    Stack (클래스, 구식)
    └── Vector 상속

Map (인터페이스) → Key-Value 쌍
├── HashMap           // 순서 없음, 가장 빠름
├── LinkedHashMap     // 삽입 순서 유지
└── TreeMap           // 키 기준 자동 오름차순 정렬