3주차 학습 내용 - 미션

자료구조 & 알고리즘

1. 지금까지 배운 5개의 정렬 알고리즘의 장단점과 시간 복잡도를 적어주세요.

1 ) 버블정렬

특징: 인접한 두 요소를 비교해서 큰 값을 뒤로 보내는 방식

시간복잡도: 최선: O(n) / 평균,최악: O(n²)

장점: 구현이 아주 간단하고 직관적임

단점: 성능이 너무 안 좋음, 실전에서 거의 사용 X

2 ) 선택정렬

특징: 가장 작은 값을 찾아서 앞으로 하나씩 정렬해가는 방식

시간복잡도: 최선,평균,최악: O(n²)

장점: 구현 쉬움, 자리 바꿈(Swap) 횟수가 적음

단점: 효율성 낮음, 데이터 크기 커지면 성능 ↓

3) 삽입정렬

특징: 정렬된 부분에 새 값을 '삽입'하는 방식

시간복잡도: 최선: O(n) / 평균,최악: O(n²)

장점: 거의 정렬된 상태일 땐 빠름, 구현 쉽고 안정 정렬

단점: 역순 정렬일 경우 성능 급감

4 ) 병합정렬

특징: 분할 → 정렬 → 병합하는 재귀 방식 (Divide & Conquer)**

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

장점: 성능 안정적, 정렬 정확도 높음, 안정 정렬

단점: 추가 메모리 공간 필요, 구현 복잡

5) 퀵정렬

특징: 피벗 기준으로 좌우 나눠 정렬하는 분할 정복 방식

시간복잡도: 평균: Θ(n log n) / 최악: O(n²)

장점: 평균적으로 가장 빠름, 메모리 추가 거의 없음

단점: 피벗 선택이 안 좋으면 성능 O(n²), 구현 어렵고 불안정

2. 메모리가 부족한 시스템에서 어떤 문제를 해결하는데 재귀로 쉽게 구현이 가능할 것 같습니다. 여러분이라면 메모이제이션과 타뷸레이션 중 어떤 걸 이용하실 건가요? 이유를 함께 적어주세요.

나는 무조건 타뷸레이션을 사용할 것 같다.

메모리가 부족한 상황이라면 어차피 타뷸레이션이나 메모이제이션이나 메모리를 아껴 써야 하는 조건은 비슷하다고 생각한다.

그렇다면 굳이 어려운 재귀를 써야 하는 메모이제이션보다는, 반복문 기반으로 더 직관적인 타뷸레이션이 훨씬 낫다.

솔직히 말해서 아직 재귀가 너무 어렵다… 그래서 재귀 없이 풀 수 있는 타뷸레이션 쪽을 더 선호하게 되는 것 같다. 😅

운영체제

1. 메모리의 종류는 어떤것들이 있나요? 각 메모리의 특징도 함께 적어주세요.

1 ) 레지스터

• CPU 내부에 존재하는 가장 빠른 기억장소

• 연산 중인 데이터나 주소 등을 저장

• CPU가 직접 접근 → 속도 가장 빠름

• 용량은 매우 작고 휘발성
  

2 ) 캐시

• CPU와 RAM 사이에 위치하는 고속 메모리

• CPU가 자주 접근하는 데이터를 미리 저장해서 → 메인 메모리 접근을 줄이고 속도 향상

• 캐시가 없으면 RAM까지 가야 하니까 느려짐

• 휘발성

  
  

  3) 메인메모리(RAM)

• 운영체제(OS)와 실행 중인 프로그램이 올라가는 공간

• 휘발성 메모리 → 전원이 꺼지면 데이터 사라짐

• 가격이 비싸기 때문에, 파일 저장용이 아닌 ‘작업 공간’으로 사용됨

• HDD/SSD보다 훨씬 빠르지만, 레지스터나 캐시보다는 느림
  

4) 보조저장장치

• 데이터를 영구적으로 저장하기 위한 장치

• 비휘발성 메모리 → 전원을 꺼도 데이터가 유지됨

• 가격이 저렴하고 용량이 큼, 대신 RAM보다 느림

• HDD

  • 자기 디스크를 회전시켜 읽고 쓰는 방식

  • 물리적인 회전이 필요해서 느림, 하지만 저렴하고 수명은 길다

  • 충격에 약하고, 소음 있음 

     

• SSD

  • 플래시 메모리 기반의 저장장치

  • 회전 없이 빠르게 데이터 처리 가능

  • HDD보다 훨씬 빠름, 충격에 강함, 소음 없음

  • 단점은 HDD보다 비싸고 수명(쓰기 횟수 제한)이 있음

2. 사용자 프로세스가 메모리의 운영체제 영역에 침범하지 못하도록 만든 레지스터는 어떤 레지스터일까요?

✅ 정답: 경계 레지스터 (Boundary Register)

경계 레지스터는 사용자 프로세스가 운영체제의 메모리 영역을 침범하지 못하도록 막아주는 역할을 한다.

CPU 내부에 존재하며, 메모리 관리자가 경계 값을 기준으로 프로세스가 허용된 영역을 벗어나는지 실시간으로 검사한다.

만약 프로세스가 지정된 경계를 넘어서려고 하면, 바로 프로세스를 강제 종료시켜서 시스템 보호를 수행한다.

3. 메모리 할당 방식에서 가변 분할 방식과 고정 분할 방식의 장단점은 뭔가요?

✅ 가변 분할 방식

• 프로세스 크기에 맞춰서 메모리를 유동적으로 나누는 방식

• 필요한 만큼만 메모리를 나눠 쓸 수 있어서 공간 활용은 유리함

• 하지만 계속 할당과 해제를 반복하다 보면 여기저기 쪼개진 빈 공간들이 생기며, 이걸 외부 단편화라고 하고, 빈 공간이 충분해 보여도 실제로는 새로운 프로세스를 넣기 힘든 상황이 생길 수 있음

✅ 고정 분할 방식

• 미리 정해진 크기로 메모리를 쪼개놓고, 거기에 프로세스를 할당하는 방식

• 구조가 단순해서 구현이 쉽고 오버헤드도 적음

• 근데 프로세스 크기랑 딱 안 맞는 경우가 많아서, 작은 프로세스가 큰 메모리 블록을 차지해 공간이 낭비되는 내부 단편화 발생

   

4. CPU 사용률을 올리기 위해 멀티프로그래밍을 올렸지만 스왑이 더 많이 이루어져 CPU 사용률이 0%에 가까워 지는 것을 뭐라고 할까요?

✅ 정답: 스레싱

멀티프로그래밍 수준을 높여서 CPU 사용률을 끌어올리려 했는데, 오히려 프로세스들이 메모리를 서로 차지하려고 계속 페이지 교체(스왑)만 일어나게 된다.

결국 CPU는 계속 대기만 하게 되고 실제 작업은 거의 하지 못하는 상태가 된다.

이런 상황을 스레싱(thrashing)이라고 부른다.

5. HDD나 SSD는 컴퓨터를 실행시키는데 꼭 필요한 걸까요?

이유를 함께 적어주세요.

조명처럼 켜두거나 그냥 전시용 벽돌로 둘 거라면 없어도 상관없다.

하지만 컴퓨터를 제대로 사용하려면 반드시 필요하다.
운영체제(OS), 프로그램, 각종 파일들이 저장되는 공간이 바로 HDD나 SSD이기 때문이다.

이 저장장치가 없다면 운영체제를 로딩할 수 없고, 프로그램도 실행할 수 없다.

결국 컴퓨터는 켜질 수는 있지만 아무것도 하지 못하는 상태가 된다.

6. 파일을 삭제해도 포렌식으로 파일을 복구할 수 있는 이유가 무엇일까요?

파일을 삭제해도 실제 데이터는 바로 없어지지 않기 때문

파일 시스템은 빈 저장 공간을 관리하기 위해 free block list를 사용한다. 이 리스트는 사용 가능한 블록들을 모아놓은 일종의 기록표다.

파일을 삭제하면 파일 시스템은 파일의 데이터 전체를 지우지 않고, 파일의 헤더 정보(위치 정보)만 지운다. 그리고 그 파일이 있던 위치를 free block list에 추가한다.

결과적으로 사용자 입장에서는 파일이 사라진 것처럼 보이지만, 실제로는 하드디스크 어딘가에 데이터가 남아 있는 상태다.