사무자동화산업기사 프로그래밍일반 핵심 요약 정리

프로그래밍 언어의 분류

• 저급 언어: 기계어(0과 1, 번역 없이 실행, 기종마다 다름), 어셈블리어(기호 언어, 어셈블러로 번역)
• 고급 언어: 사람이 이해하기 쉬움, 컴파일러·인터프리터로 번역, 기종에 덜 종속
• 패러다임별 분류
• 절차적(명령형): FORTRAN(과학 계산), COBOL(사무 처리), C, Pascal
• 객체지향: C++, Java, Smalltalk, C#
• 함수형: LISP, Haskell / 논리형: PROLOG(인공지능)
• 스크립트: Python, JavaScript, PHP
• 시스템 프로그래밍에 알맞은 언어: C (UNIX 운영체제를 C로 작성)
• 최초의 고급 언어: FORTRAN / 교육용: BASIC, Pascal

언어별 특징과 예약어

• 기계어: 0과 1로 표현, 컴퓨터가 바로 이해해 실행 속도가 빠름 / 기계마다 달라 호환성 없음, 읽기·유지 보수 어려움
• 어셈블리어: 기계어를 기호로 바꾼 언어 → 기호 코드(Mnemonic Code)라고도 함
• C: 이식성 우수, UNIX 운영체제를 작성한 언어, 포인터로 번지 연산 (기호 코드가 아님)
• 언어별 특징
• SNOBOL: 문자열의 대치·복사·치환 등 문자열 처리에 강함
• ALGOL: 알고리즘 기술용, 블록 구조, BNF로 문법을 처음 정의
• ADA: 미 국방성 주도, 실시간·임베디드 / PL/1: 과학 계산 + 사무 처리 통합
• LISP: 리스트 처리, 선언문을 전혀 쓰지 않는 언어
• 객체지향 언어: C++, Java, Smalltalk, C# (ALGOL·COBOL·C는 아님)
• 예약어(지정어): 시스템이 특수 기능에 쓰도록 용도가 정해진 단어 → 변수 이름으로 쓸 수 없음 (int, else, while, for, return …)
• 변수: 값을 저장하는 기억 장소, 실행 중 값이 바뀔 수 있음 / 상수: 실행 중 값이 바뀌지 않음

언어의 설계 기준과 구조적 프로그래밍

• 좋은 언어의 조건: 가독성(읽기 쉬움), 작성력(쓰기 쉬움), 신뢰성, 직교성(적은 기본 요소의 조합으로 많은 것 표현), 이식성(다른 기종에서도 실행), 효율성
• 구조적 프로그래밍의 기본 구조: 순차(sequence), 선택(selection, if·switch), 반복(iteration, for·while)
• GOTO문 사용을 피함, 하나의 입구와 하나의 출구
• 반복문: C의 for·while, COBOL의 PERFORM, FORTRAN의 DO
• 모듈화: 프로그램을 기능 단위로 나눔 → 결합도는 낮게, 응집도는 높게
• 하향식 설계: 큰 기능에서 작은 기능으로 나눠 내려감

구문 표현: BNF와 EBNF

• BNF(Backus-Naur Form): 언어의 구문(문법)을 표현하는 메타 언어
• ::=: 정의(왼쪽은 오른쪽과 같다)
• |: 선택(또는)
• < >: 비단말 기호(더 풀어 쓸 대상)
• EBNF(확장 BNF): { }는 0번 이상 반복, [ ]는 생략 가능(선택), ( )는 묶음
• 구문 도표(syntax diagram): BNF를 그림으로 표현
• 파스 트리(구문 트리): 문장이 문법으로 유도되는 과정을 트리로 표현
• 모호한 문법: 한 문장에 파스 트리가 둘 이상 생김
• 구문(syntax)은 형식, 의미(semantics)는 뜻

바인딩과 바인딩 시간

• 바인딩: 프로그램의 요소(변수 등)에 속성(이름·형·값·주소)을 연결하는 것
• 바인딩 시간(이른 순)
• 언어 정의 시간: 자료 구조, 택일문(if·case) 같은 언어 구조 확정 (예: 정수형이 있다)
• 언어 구현 시간: 정수의 크기(비트 수) 등 컴파일러가 정함
• 번역(컴파일) 시간: 변수의 자료형 결정
• 링크 시간, 적재(로드) 시간: 변수의 메모리 주소
• 실행 시간: 변수의 값, 지역 변수의 기억 장소
• 정적 바인딩: 실행 전에 결정 (효율적) / 동적 바인딩: 실행 중에 결정 (유연함)
• 번역 시간 바인딩은 정적 바인딩 → 동적 바인딩이 이루어지는 때가 아님

변수의 속성과 영역

• 변수의 속성: 이름, 주소(l-value), 값(r-value), 자료형, 수명, 영역(scope)
• 영역(scope): 변수를 참조할 수 있는 범위
• 정적 영역: 프로그램 구조(소스 코드 위치)로 결정 — C, Pascal 등 대부분
• 동적 영역: 실행 중 호출 순서로 결정 — 옛 LISP, APL
• 수명: 변수가 기억 장소를 차지하는 기간 (정적 변수는 프로그램 끝까지, 지역 변수는 블록 끝까지)
• 별명(alias): 하나의 기억 장소를 두 개 이상의 이름으로 참조
• 상수: 값을 바꿀 수 없는 이름 / 리터럴: 코드에 직접 쓴 값

자료형과 형 검사

• 기본 자료형: 정수, 실수, 문자, 논리(불리언)
• 구조적 자료형: 배열(같은 형의 모음, 첨자로 접근), 레코드(구조체, 다른 형의 모음), 문자열, 집합
• 포인터: 다른 변수의 주소를 값으로 가짐 → 동적 자료 구조(연결 리스트)
• 문제: 허상 참조(dangling reference), 쓰레기(garbage)
• 가비지 컬렉션: 더 이상 쓰지 않는 메모리를 자동 회수 (Java, Python)
• 형 검사: 연산의 피연산자 형이 맞는지 확인 / 강형(strongly typed) 언어는 형 오류를 모두 찾음
• 형 변환: 자동(묵시적, 강제 변환 coercion) / 명시적(캐스트, 예: (int)3.7 → 3)
• 열거형(enum): 이름 붙은 상수의 목록

부프로그램과 매개변수 전달

• 부프로그램: 함수(값을 돌려줌), 프로시저(서브루틴) / 실매개변수(호출하는 쪽)와 형식매개변수(정의하는 쪽)
• 매개변수 전달 방식
• 값에 의한 호출(call by value): 값을 복사해 전달 → 호출된 쪽에서 바꿔도 원래 값 그대로
• 참조에 의한 호출(call by reference): 주소를 전달 → 바꾸면 원래 값도 바뀜
• 값-결과 호출(call by value-result): 복사해 쓰고 끝날 때 결과를 돌려씀
• 이름에 의한 호출(call by name): 이름 자체를 넘겨 쓸 때마다 계산 (ALGOL)
• 재귀: 함수가 자기 자신을 호출 → 스택에 활성 레코드가 쌓임, 종료 조건 필요
• 활성 레코드: 호출마다 만들어지는 정보(지역 변수, 매개변수, 복귀 주소)
• 코루틴: 서로 번갈아 실행을 넘기는 부프로그램

언어 번역기의 종류

• 컴파일러: 고급 언어 프로그램 전체를 한꺼번에 기계어(목적 프로그램)로 번역 → 실행 속도 빠름, 목적 프로그램 생성 (C, FORTRAN, COBOL)
• 인터프리터: 한 줄씩 번역하며 바로 실행 → 목적 프로그램 없음, 실행 속도 느림, 대화식 (BASIC, Python, LISP)
• 어셈블러: 어셈블리어 → 기계어
• 크로스 컴파일러: 다른 기종에서 실행될 기계어를 만드는 컴파일러 (임베디드 개발)
• 프리프로세서(전처리기): 컴파일 전에 #include, #define 같은 지시어 처리
• 번역 순서: 원시 프로그램 → (컴파일러) → 목적 프로그램 → (링커) → 실행 가능 프로그램(로드 모듈) → (로더) → 실행

컴파일 과정

• 컴파일 단계

1. 어휘 분석(lexical): 원시 코드를 토큰으로 나눔 — 스캐너

2. 구문 분석(syntax): 토큰을 문법에 맞게 파스 트리로 — 파서

3. 의미 분석: 형 검사 등 뜻이 맞는지 확인

4. 중간 코드 생성

5. 코드 최적화: 더 빠르고 작은 코드로

6. 목적 코드 생성

• 심볼 테이블: 변수 이름·형·주소 등 식별자 정보 저장
• 구문 분석 방법: 하향식(top-down, 재귀 하강·LL) / 상향식(bottom-up, LR)
• 토큰: 예약어, 식별자, 상수, 연산자, 구분자

로더·링커·매크로

• 로더의 기능: 할당(allocation, 메모리 공간 확보) → 연결(linking) → 재배치(relocation, 주소 조정) → 적재(loading)
• 로더 종류: 컴파일 즉시(Compile and Go), 절대 로더(적재만), 직접 연결 로더, 동적 적재
• 매크로: 반복되는 명령들을 하나의 이름으로 정의해 두고 호출하면 그 자리에 펼쳐짐(확장)
• 매크로 프로세서: 정의 인식 → 저장 → 호출 인식 → 확장
• 부프로그램은 호출 때 제어가 넘어가고, 매크로는 코드 자체가 복사됨
• 어셈블러: 1패스(한 번 읽기) / 2패스(1패스에서 기호표 작성, 2패스에서 기계어 생성 → 전방 참조 해결)
• 디버거: 오류 찾기 / 유틸리티: 정렬·병합·백업 등 보조 프로그램

C 언어의 자료형과 기억 클래스

• 기본 자료형: char(1바이트), short(2), int(4), long, float(4), double(8)
• 부호 지정자: signed, unsigned (자료형 자체가 아니라 수식어)
• integer, string, boolean은 C의 기본 자료형 이름이 아님 (C99부터 _Bool)
• 기억 클래스(storage class): auto(자동, 지역 변수 기본), register(CPU 레지스터), static(정적, 값 유지), extern(외부, 다른 파일의 전역 변수)
• 서식 문자: %d(10진 정수), %o(8진), %x(16진), %f(실수), %c(문자), %s(문자열), %e(지수형)
• 변수 이름: 영문자·숫자·_ 만, 숫자로 시작 불가, 대소문자 구분, 예약어 불가

C 연산자와 우선순위

• 산술: + - * / %(나머지) — 정수끼리 나누면 몫만 (7/2 = 3, 7%2 = 1)
• 증감: ++a(먼저 증가 후 사용), a++(사용 후 증가)
• 관계: == != > < >= <= / 논리: &&(AND) ||(OR) !(NOT)
• 비트: &(AND) |(OR) ^(XOR) ~(NOT, 보수) <<(왼쪽 시프트, ×2) >>(오른쪽 시프트, ÷2)
• 이항 연산: 피연산자가 2개 (+, -, AND, OR, XOR, 시프트) / 단항 연산: 1개 (NOT, complement(보수), ++, --, MOVE)
• 조건 연산자: 조건 ? 참일 때 값 : 거짓일 때 값
• 우선순위(높음 → 낮음): 단항 > 산술(* / % > + -) > 시프트 > 관계 > 비트 > 논리(&& > ||) > 조건 > 대입 > 콤마

C 제어문과 반복문 읽기

• if / else if / else, switch-case: case 끝에 break가 없으면 다음 case로 계속 실행
• for(초기식; 조건식; 증감식): 횟수가 정해진 반복
• while(조건): 조건이 참인 동안 반복 (처음부터 거짓이면 한 번도 안 함)
• do-while: 일단 한 번 실행한 뒤 조건 검사
• break: 반복문 탈출 / continue: 이번 반복의 나머지를 건너뛰고 다음 반복으로
• 예시: for(i=1; i<=10; i++) sum += i; → sum = 55
• 예시: for(i=0; i<10; i+=3) → i는 0, 3, 6, 9 (4번 반복)

배열·포인터·문자열

• 배열: int a[5]; → 첨자는 0부터 4까지. 배열 이름 a는 첫 원소의 주소(&a[0])
• 포인터: int *p = &x; → p는 x의 주소, *p는 x의 값
• & : 주소 연산자, * : 간접 참조 연산자
• p+1 은 다음 원소의 주소 (자료형 크기만큼 증가) → *(a+i) 는 a[i]
• 문자열: 문자 배열, 끝에 널 문자('\0')가 붙음 → char s[] = "abc"; 의 크기는 4
• 문자열 함수: strlen(길이, 널 문자 제외), strcpy(복사), strcat(이어 붙이기), strcmp(비교)
• 구조체: struct로 여러 형을 묶음, 멤버 접근은 . (포인터면 ->)

이스케이프 시퀀스와 변수 선언

• 이스케이프 시퀀스: \n 줄 바꿈(new line), \t 탭, \r 캐리지 리턴(그 줄 맨 앞으로), \b 백스페이스, \f 폼 피드, \0 널 문자
• unsigned: 정수형 앞에 붙여 0 이상의 값만 표현 (signed는 음수 포함, 기본값)
• 변수 선언 규칙: 예약어는 쓸 수 없음 → int else; (X) / int True; 는 가능 (C에서 True는 예약어가 아님)
• 외부 변수(전역 변수): 함수 밖에서 선언, 초기화하지 않으면 자동으로 0, 함수가 끝나도 값이 유지됨 (프로그램 끝까지)
• 다른 파일에서 선언된 변수를 extern으로 참조할 때는 초기화할 수 없음
• 문자형 연산: 'A'는 ASCII 65 → 'A' + 1 을 %d로 출력하면 66, %c로 출력하면 B
• 2차원 배열 주소: int a[2][3] (정수 2바이트, 시작 1000번지) → a[1][1] = 1000 + (1×3 + 1) × 2 = 1008
• 배열 이름은 첫 원소의 주소 → pc = array1; 은 pc = &array1[0]; 과 같음
• main 함수는 생략할 수 없음, 문자열 출력 함수 puts·printf

C 코드 실행 결과 따라가기

• 후위 증가와 비교: if (cnt++ > 12) → 먼저 cnt(12)로 비교한 뒤 증가
• cnt = 12에서 if·else if·else if·else 를 모두 거치면 비교마다 1씩, 마지막 else에서 1 → 16
• 우선순위: * 가 << 보다 먼저 → 4 * 3 << 1 = 12 << 1 = 24
• 비트 연산: 3 & 6 = 2, 3 | 6 = 7, 3 ^ 6 = 5, 5 | 6 = 7 (2진수로 바꿔 자리마다 계산)
• 논리 연산: && 가 || 보다 먼저, 결과는 참 1·거짓 0 → x=3, y=4, z=0 일 때 x || y && z = 1
• 삼항 연산자: k = (i > j) ? (i - j) : (i + j); → if (i > j) k = i - j; else k = i + j; 와 같음
• 홀짝 판별: if (num % 2 == 1) 홀수 else 짝수
• continue·break: 1~20 중 5의 배수는 건너뛰고(continue) 18에서 멈추면(break) 센 개수 = 17 − 3 = 14
• 피보나치 배열: a[0]=0, a[1]=1, a[i+2]=a[i+1]+a[i] → 0 1 1 2 3 5 8 13 21 34 (a[9])

객체지향의 개념

• 객체(object): 데이터(속성)와 그 데이터를 처리하는 연산(메소드)을 묶은 것
• 클래스: 같은 속성·메소드를 가진 객체들의 틀 / 인스턴스: 클래스로 만든 실제 객체
• 메소드: 객체가 메시지를 받았을 때 실행할 연산(함수)
• 메시지: 객체에게 일을 시키는 요청
• 특징
• 캡슐화: 데이터와 연산을 묶고 내부를 숨김 → 정보 은닉
• 상속: 상위 클래스의 속성·메소드를 하위 클래스가 물려받음 → 재사용
• 다형성: 같은 메시지에 객체마다 다르게 반응
• 추상화: 공통 특징만 뽑아냄
• 오버로딩: 같은 이름, 다른 매개변수의 메소드 여러 개 / 오버라이딩: 상속받은 메소드를 하위 클래스에서 재정의

추상화·캡슐화·생성자

• 추상화(Abstraction): 여러 객체의 공통 성질을 뽑아 슈퍼클래스를 만들고, 중요한 것에만 집중해 모델화
• 예: "자동차"와 "비행기"에서 "이동수단" 클래스를 만듦 / 클래스는 데이터를 추상화하는 단위
• 캡슐화: 세부 내용을 숨겨 변경의 파급 효과가 적고, 인터페이스가 단순해지며 재사용이 쉬움 → 객체 간 결합도가 낮아짐
• 상속성: 클래스 간 계층 관계에 따라 상위 클래스의 속성과 연산을 하위 클래스가 공유
• 생성자(Constructor): 객체를 생성할 때 초기화하는 특수 메소드, 클래스와 이름이 같고 반환형이 없음
• 객체지향의 장점: 절차지향보다 유지보수성과 재사용성이 좋음
• 객체지향 주요 개념: 추상 데이터형, 자료 은폐(정보 은닉), 상속 ("고정 자료형"은 아님)
• 럼바우 분석 기법: 객체 모델링(정보 모델링: 객체·속성·관계) → 동적 모델링 → 기능 모델링

Java와 Python 기초

• Java: 플랫폼 독립적 → 컴파일하면 바이트 코드(.class), JVM(자바 가상 머신)이 실행
• 다중 상속 불가(클래스) → 인터페이스로 대신
• 가비지 컬렉션으로 메모리 자동 관리, 포인터 없음
• 접근 제어자: public(어디서나) > protected(같은 패키지·자식) > default(같은 패키지) > private(클래스 안)
• 상속은 extends, 인터페이스 구현은 implements, 생성자는 클래스와 같은 이름
• Python: 인터프리터 언어, 들여쓰기로 블록 구분, 동적 자료형
• 리스트 [ ], 튜플 ( )(수정 불가), 딕셔너리 {키: 값}
• range(1, 5) → 1, 2, 3, 4 (끝값 제외)

Java 문법과 문자열 메소드

• 자료형: 정수 byte·short·int·long / 실수 float·double / 문자 char(한 글자) / 논리 boolean(true·false)
• short·byte는 정수형 → "실수형에 float, short, byte가 있다"는 틀림
• 배열: int[][] arr = new int[2][3]; → arr.length는 행의 수 2, arr[0].length는 3
• 향상된 for: for (int[] row : g) for (int e : row) …
• final: 값을 바꿀 수 없는 상수 / super: 상위 클래스 참조 / extends: 상속 / this: 자기 자신
• 증감: x = 5; y = x++; (y=5, x=6) z = --x; (x=5, z=5) → "5, 5, 5"
• 문자열(String) 메소드
• length(): 길이 / charAt(i): i번째 문자 / substring(시작, 끝): 부분 문자열 꺼내기 / split(구분자): 나누기
• equals: 대소문자 구분해 같으면 true / equalsIgnoreCase: 대소문자 무시
• compareTo: 같으면 0, 사전순으로 앞이면 음수, 뒤면 양수
• 반복 예시: for (i = 0; ; i += 2) if (i > 7) break; → i = 8

Python 기초

• 특징: 인터프리터 언어, 변수 자료형을 선언하지 않음(실행할 때 정해지는 동적 타입), 세미콜론 불필요, 들여쓰기로 블록 구분
• "실행 전에 컴파일러가 자료형을 미리 결정한다"는 틀림
• 다중 대입: x, y, z = 10, 20, 30
• 입력 나누기: x, y = input("값 입력 : ").split(' ') → "5 10"을 공백으로 나눠 x="5", y="10"
• 숫자로 바꾸려면 map(int, input().split())
• 문자열 메소드: upper() 모두 대문자, lower() 모두 소문자, capitalize() 문자열의 첫 글자만 대문자, title() 각 단어의 첫 글자를 대문자
• 리스트: a = [1, 2, 3] / a[-1] 마지막 원소 / a[1:3] 1번부터 2번까지(끝 제외) / append() 추가
• range(1, 5) → 1, 2, 3, 4

JavaScript와 HTML

• HTML에 넣는 방법
• 직접 입력: <script> document.write(100) </script>
• 외부 파일: <script src="abc.js"></script>
• 이벤트 속성: <input type="button" onclick="msg(100)">
• <javascript> 같은 태그는 없음
• 배열 속성·메소드
• push(): 끝에 추가 / pop(): 맨 끝 값 삭제 / shift(): 맨 앞 삭제 / unshift(): 맨 앞 추가
• join(구분자): 요소를 이어 하나의 문자열로 / length: 배열 길이
• slice(시작, 끝): 지정한 범위를 가져옴(원본 유지) / splice(시작, 개수, …): 요소를 삭제·삽입(원본 변경)
• indexOf(): 위치 찾기, reverse(), sort()
• 변수 선언: var, let, const(상수)

운영체제의 목적과 종류

• 운영체제: 하드웨어와 사용자 사이에서 자원을 관리하고 편리한 환경을 제공하는 시스템 소프트웨어
• 성능 평가 기준: 처리 능력(throughput)↑, 반환 시간(turnaround time)↓, 사용 가능도(availability)↑, 신뢰도(reliability)↑ — 비용은 평가 요소가 아님
• 운영 방식
• 일괄 처리(batch): 모아서 한꺼번에 처리 (급여 계산)
• 시분할(time sharing): CPU 시간을 잘게 나눠 여러 사용자가 대화식으로 사용 (라운드 로빈)
• 실시간 처리: 즉시 처리 (좌석 예약, 은행)
• 다중 프로그래밍: 여러 프로그램을 메모리에 올려 CPU를 번갈아 사용
• 다중 처리: CPU 여러 개 / 분산 처리: 여러 컴퓨터를 네트워크로 연결
• 구성: 제어 프로그램(감시·작업 관리·데이터 관리) + 처리 프로그램(언어 번역·서비스·문제 처리)
• 대표 OS: Windows, UNIX, Linux(오픈소스), macOS, Android, iOS

프로세스와 스케줄링

• 프로세스: 실행 중인 프로그램 / PCB(프로세스 제어 블록)에 상태·우선순위·레지스터 정보 저장
• 스레드: 프로세스 안의 실행 단위 (경량 프로세스)
• 프로세스 상태: 생성 → 준비(ready) → 실행(running) → 대기(blocked, 입출력 기다림) → 종료
• 준비 → 실행: 디스패치 / 실행 → 준비: 할당 시간 초과(타이머 런아웃)
• 스케줄링
• 비선점: FCFS(먼저 온 순서, FIFO), SJF(실행 시간 짧은 것 먼저), HRN(우선순위 = (대기 시간 + 서비스 시간) ÷ 서비스 시간)
• 선점: RR(라운드 로빈, 시간 할당량만큼 번갈아), SRT(남은 시간 짧은 것), 다단계 큐
• 문맥 교환(context switching): CPU를 다른 프로세스로 넘길 때 상태를 저장·복구

인터럽트와 스케줄링 보충

• 인터럽트: 실행 중 예기치 않은 일이 생기면 현재 작업을 멈추고 그 일을 먼저 처리한 뒤 복귀
• 인터럽트 종류
• 외부 인터럽트: 타이머의 시간 만료, 오퍼레이터의 콘솔 인터럽트 키, 전원 이상
• 입·출력 인터럽트: 입출력 완료·오류 → I/O 프로세서가 CPU에 완료를 알림
• 기계 검사 인터럽트: 하드웨어 고장 / 프로그램 검사 인터럽트: 0으로 나누기, 오버플로 등
• SVC(Supervisor Call) 인터럽트: 프로그래머가 입출력 수행·기억장치 할당 등을 요청할 때
• 선점 스케줄링: RR, SRT(남은 시간이 가장 짧은 것), MQ(다단계 큐), MFQ(다단계 피드백 큐: 짧은 작업·입출력 위주 작업에 우선)
• 비선점 스케줄링: FCFS, SJF(실행 시간이 가장 짧은 것 먼저), HRN, 우선순위
• 임계 자원(Critical Resource): 두 개 이상의 프로세스가 동시에 쓸 수 없는 자원 → 임계 구역, 상호 배제
• 커널: 프로세스·기억장치·입출력·파일 관리를 맡는 운영체제의 핵심

교착상태

• 교착상태(deadlock): 프로세스들이 서로가 가진 자원을 기다리며 무한히 멈춘 상태
• 발생 조건 4가지(모두 만족해야 발생)
• 상호 배제: 자원을 한 번에 하나의 프로세스만 사용
• 점유와 대기: 자원을 가진 채 다른 자원을 기다림
• 비선점: 다른 프로세스의 자원을 강제로 빼앗을 수 없음
• 환형 대기: 서로가 꼬리를 물고 원 모양으로 기다림
• 해결 방법
• 예방: 4가지 조건 중 하나를 없앰
• 회피: 안전한 상태일 때만 자원 할당 → 은행원 알고리즘(다익스트라)
• 발견: 자원 할당 그래프로 찾아냄 / 회복: 프로세스 종료, 자원 선점

기억장치 관리와 페이지 교체

• 배치 전략: 최초 적합(first fit, 처음 맞는 곳), 최적 적합(best fit, 가장 딱 맞는 곳), 최악 적합(worst fit, 가장 큰 곳)
• 단편화: 내부 단편화(할당 공간이 남음), 외부 단편화(빈 공간이 작아 못 씀) → 통합·압축으로 해결
• 가상 기억장치: 페이징(같은 크기로 나눔, 내부 단편화), 세그먼테이션(논리 단위로 다른 크기, 외부 단편화)
• 페이지 교체: FIFO(먼저 들어온 것), LRU(가장 오래 사용 안 한 것), LFU(사용 횟수가 가장 적은 것), OPT(앞으로 가장 오래 안 쓸 것, 이론상 최적), NUR
• 구역성(locality): 시간 구역성(최근 쓴 곳을 또 씀: 반복문·스택), 공간 구역성(가까운 곳을 씀: 배열·순차 코드)
• 워킹 셋(Working Set): 일정 시간 동안 자주 참조하는 페이지들의 집합
• 스래싱: 페이지 교체가 너무 잦아 실제 작업보다 교체에 시간을 더 씀

스택·큐·트리

• 선형 구조: 배열, 연결 리스트, 스택, 큐, 데크
• 스택: LIFO(후입선출), 한쪽 끝(top)에서만 삽입(push)·삭제(pop) → 함수 호출, 수식 계산, 재귀
• 큐: FIFO(선입선출), 뒤(rear)에서 삽입, 앞(front)에서 삭제 → 작업 스케줄링, 버퍼
• 데크: 양쪽 끝에서 삽입·삭제
• 비선형 구조: 트리, 그래프
• 트리: 계층 구조, 노드의 차수(자식 수), 단말 노드(자식 없음)
• 이진 트리 순회: 전위(Root-L-R), 중위(L-Root-R), 후위(L-R-Root)
• 수식 표기: 중위(A+B), 전위(+AB), 후위(AB+) — 후위식은 스택으로 계산
• 정렬: 버블, 선택, 삽입, 퀵(평균 O(n log n)), 힙, 병합 / 검색: 순차, 이진(정렬된 자료), 해싱

진법 변환과 수의 표현

• 진법 변환: 2진수 1011 = 8+0+2+1 = 11(10진수)
• 2진 → 8진: 3자리씩 묶음 / 2진 → 16진: 4자리씩 묶음 (예: 1010 1111 = AF)
• 음수 표현: 부호와 절댓값, 1의 보수(0↔1 뒤집기), 2의 보수(1의 보수 + 1, 현재 컴퓨터가 사용)
• 2의 보수는 0이 하나뿐이라 계산이 편함
• 문자 코드: ASCII(7비트, 128자), EBCDIC(8비트, 대형 컴퓨터), 유니코드(전 세계 문자, 한글 완성형 포함)
• BCD: 10진수 한 자리를 4비트로 / 그레이 코드: 이웃한 값끼리 1비트만 다름 (아날로그-디지털 변환)
• 해밍 코드: 오류를 검출하고 정정까지 / 패리티 비트: 오류 검출만
• n비트로 표현할 수 있는 가짓수: 2ⁿ