정보처리기사(필기) 📝 02. 소프트웨어 개발

📌 데이터 구조 (Data Structure)

🔹 1. 선형 구조 (Linear Structure)

• 선형 구조는 데이터를 순서대로 저장하는 방식으로, 배열, 연결 리스트, 스택, 큐 등이 있다.

✅ 배열 (Array)

• 같은 타입의 데이터를 연속된 공간에 저장하는 자료구조
• 특징
  • 검색(인덱스로 접근): O(1)
  • 삽입/삭제: O(N) (중간 요소 변경 시 전체 이동 필요)
  • 크기 변경 불가 (고정된 메모리)

✅ 예제 (JavaScript)

const arr = [10, 20, 30, 40, 50];
console.log(arr[2]); // 30

✅ 예시 (C 코드)

int arr[5] = {10, 20, 30, 40, 50};  // 정수형 배열 선언
printf("%d", arr[2]);  // 3번째 요소(30) 출력

---

✅ 연결 리스트 (Linked List)

• 각 노드가 데이터 + 다음 노드를 가리키는 포인터로 구성됨
• 동적 메모리 할당을 사용하여 크기를 유동적으로 조절 가능
• 배열보다 삽입/삭제가 빠름 (O(1)), 탐색은 느림 (O(N))

✅ 예시 (단순 연결 리스트)

class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

let head = new Node(10);
head.next = new Node(20);
head.next.next = new Node(30);
console.log(head.next.data); // 20

✅ 연결 리스트 구조

📌 배열 vs 연결 리스트

	배열	연결 리스트
메모리 할당	정적 할당	동적 할당
접근 속도	O(1)	O(N)
삽입/삭제	O(N)	O(1) (처음/끝에서)

---

✅ 스택 (Stack)

• LIFO (Last In, First Out) 방식으로 동작
• 주요 연산: push(), pop()

📌 활용 예시: 함수 호출(재귀 함수), 웹 브라우저 뒤로 가기

✅ 예시 (JavaScript)

const stack = [];
stack.push(10);
stack.push(20);
console.log(stack.pop()); // 20 제거됨

---

✅ 큐 (Queue)

• FIFO (First In, First Out) 방식으로 동작
• 주요 연산: enqueue(), dequeue()

📌 활용 예시: CPU 프로세스 스케쥴링, 프린터 작업 처리

✅ 예시 (JavaScript)

const queue = [];
queue.push(10);
queue.push(20);
console.log(queue.shift()); // 10 제거됨

✅ 큐 구조

---

🔹 2. 비선형 구조 (Non-Linear Structure)

✅ 트리 (Tree)

• 계층적인 구조를 가지는 데이터 저장 방식
• 이진 탐색 트리(BST): 왼쪽 자식 < 부모 < 오른쪽 자식

✅ 이진 탐색 트리 예시

        50
       /  \
      30   70
     / \   / \
    20 40 60 80

📌 활용 예시

• 파일 시스템 디렉토리 구조
• 이진 탐색 트리(BST) 기반 데이터 탐색

✅ 트리 구조

---

✅ 해시 테이블 (Hash Table)

• 키(Key)-값(Value) 쌍으로 데이터를 저장하는 자료구조
• 해시 함수를 사용해 빠르게 데이터 검색 가능
• 시간 복잡도: 평균 O(1), 최악 O(N) (충돌 발생 시)

📌 활용 예시

• 자바스크립트의 Map 객체
• 데이터베이스의 인덱스
• 캐싱(Cache)

✅ 예제 (JavaScript)

const map = new Map();
map.set("name", "홍길동");
map.set("age", 30);
console.log(map.get("name")); // 홍길동

---

📌 알고리즘 및 응용

🔹 1. 정렬 알고리즘

✅ 퀵 정렬 (Quick Sort)

• 기준점(Pivot)을 기준으로 작은 값과 큰 값을 나누어 정렬
• 평균 시간 복잡도 O(N log N)

✅ 예시

function quickSort(arr) {
    if (arr.length <= 1) return arr;
    let pivot = arr[Math.floor(arr.length / 2)];
    let left = arr.filter(x => x < pivot);
    let middle = arr.filter(x => x === pivot);
    let right = arr.filter(x => x > pivot);
    return [...quickSort(left), ...middle, ...quickSort(right)];
}

console.log(quickSort([3, 6, 8, 10, 1, 2, 1]));

✅ 퀵 정렬 과정

📌 정렬 알고리즘 비교

알고리즘	평균 시간 복잡도	최악 시간 복잡도	특징
버블 정렬	O(N²)	O(N²)	간단하지만 비효율적
선택 정렬	O(N²)	O(N²)	최소값을 찾아 정렬
삽입 정렬	O(N²)	O(N²)	거의 정렬된 경우 효율적
병합 정렬	O(N log N)	O(N log N)	안정적인 정렬
퀵 정렬	O(N log N)	O(N²)	빠르지만 최악의 경우 발생 가능

---

🔹 2. 탐색 알고리즘

✅ 이진 탐색 (Binary Search)

• 정렬된 배열에서 중앙값을 기준으로 반씩 줄여가며 탐색
• 시간 복잡도: O(log N)

✅ 예제 (JavaScript)

function binarySearch(arr, target) {
    let left = 0, right = arr.length - 1;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) return mid;
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}
console.log(binarySearch([1, 3, 5, 7, 9], 5)); // 2

📌 비교

탐색 방식	시간 복잡도	특징
순차 탐색	O(N)	정렬 필요 없음
이진 탐색	O(log N)	정렬 필요

---

📌 운영체제 (OS)

✅ 프로세스 vs 스레드

구분	프로세스 (Process)	스레드 (Thread)
정의	실행 중인 프로그램	프로세스 내 작업 단위
메모리 공유	별도 메모리 공간 할당	같은 프로세스 내에서 공유
예제	브라우저, 메신저 앱	브라우저 탭, 채팅 메시지 전송

📌 멀티스레딩 활용 예시

• 웹 서버 (동시 사용자 요청 처리)
• 게임 엔진 (AI, 렌더링 분리 실행)

✅ CPU 스케줄링 알고리즘

알고리즘	설명
FCFS	먼저 온 프로세스부터 실행
SJF	실행 시간이 짧은 프로세스를 우선 실행
Round Robin (RR)	정해진 시간(Time Quantum) 동안 실행 후 다음 프로세스로 전환

✅ 예시 (FCFS vs SJF)

FCFS: P1(10ms) → P2(5ms) → P3(3ms) → 총 18ms

SJF: P3(3ms) → P2(5ms) → P1(10ms) → 총 18ms

✅ 메모리 관리 (Memory Management)

📌 가상 메모리 (Virtual Memory)

• 물리적 메모리 부족 시 디스크 일부를 RAM처럼 사용
• 페이지 교체 알고리즘
  • FIFO (First-In, First-Out)
  • LRU (Least Recently Used)

---

📌 데이터베이스 (DB)

✅ 정규화(Normalization) 과정

• 1NF (제1 정규형)
  • 중복 데이터 제거
• 2NF (제2 정규형)
  • 부분 종속성 제거 (기본 키에 완전 종속)
• 3NF (제3 정규형)
  • 이행적 종속 제거

✅ 예시 (정규화 과정)

📌 비정규화된 테이블

학생ID	학생명	과목명	교수명
1	홍길동	데이터베이스	김교수
1	홍길동	운영체제	이교수

📌 3NF 적용 후

• 학생 테이블(Student), 과목 테이블(Subject)로 분리

✅ 학생 테이블 (Student)

학생ID	학생명
1	홍길동

✅ 과목 테이블 (Subject)

과목ID	과목명	교수명
101	데이터베이스	김교수
102	운영체제	이교수

✅ 학생-과목 관계 테이블 (Student_Subject)

학생ID	과목ID
1	101
1	102

📌 정규화의 장점

• 데이터 중복 최소화
• 무결성 유지
• 데이터 삽입/삭제/수정 시 일관성 유지

---

✅ 트랜잭션 (Transaction)

• 데이터베이스에서 하나의 논리적인 작업 단위
• ACID 특성
  • Atomicity (원자성): 부분 실행 없이 전부 실행되거나 전부 취소
  • Consistency (일관성): 데이터 무결성 유지
  • Isolation (고립성): 트랜잭션 간 영향 없음
  • Durability (지속성): 실행된 결과는 영구적으로 저장

📌 트랜잭션 예시 (SQL)

BEGIN;
UPDATE accounts SET balance = balance - 1000 WHERE id = 1;
UPDATE accounts SET balance = balance + 1000 WHERE id = 2;
COMMIT;