[기초] 컴퓨터구조, 자료구조, 알고리즘 간략 정리

컴퓨터 구조

: 컴퓨터가 효율적으로 작동할 수 있도록 하드웨어 및 소프트웨어의 기능을 고안하고 구성하는 방법

 

컴퓨터의 기능 구조에 대한 설계

: 컴퓨터가 연산을 효율적으로 하기 위해 어떤 기능들이 컴퓨터에 필요한지 고민하고, 설계하는 분야 ex) 폰 노이만 구조, 하버드 구조, 수정된 비트 구조 등

• 폰 노이만 구조
  : 컴퓨터 핵심 기능(연산, 제어, 저장)이 필요하다 생각
  • 중앙처리장치 (CPU) - 연산, 제어
    : 프로그램 연산 처리 및 시스템 관리. 프로세스의 코드를 불러오고, 실행하고, 결과를 저장하는 모든 과정 수행
    • 구성
      1. 산술논리장치 (ALU, Arithmetic Logic Unit) : 산술/논리 연산 처리
      2. 제어장치 (Control Unit) : CPU 제어
      3. 레지스터 (Register) : CPU에 필요한 데이터 저장
  • 기억장치 (Memory) - 저장
    : 컴퓨터가 동작하는데 필요한 여러 데이터를 저장하기 위해 사용
    1. 주기억장치 : 프로그램 실행 과정에서 필요한 데이터 임시 저장
       ex) 램 (RAM, Random-Access Memory)
    2. 보조기억장치 : 운영체제, 프로그램 등과 같은 데이터 장기간 보관
       ex) 하드 드라이브 (HDD, Hard Disk Drive), SSD (Solid State Drive)
  • 버스 (Bus) - 장치 간 데이터 or 제어 신호 교환
    : 컴퓨터 부품 간 또는 컴퓨터 간 신호 전송 통로
    • 데이터 버스 (Data Bus) : 데이터 이동
    • 주소 버스 (Address Bus) : 주소 지정
    • 제어 버스 (Control Bus) : 읽기/쓰기 제어
    • 랜선이나 데이터 전송 소프트웨어, 프로토콜 등을 포함

 

CPU 기능에 대한 설계

: 명령어 집합구조 (Instruction Set Architecture). CPU가 처리해야 하는 명령어를 설계하는 분야
ex) ARM, MIPS, AVR, 인텔의 x86-64 등

• 명령어 집합구조 (ISA, Instruction Set Architecture) = CPU 설계도
  : 어떤 구조의 메모리와 호환이 가능한지 명시.
  프로그램 실행 시 기계어 명령어들을 CPU가 읽기 및 처리.
  명령어 집합 / 레지스터 집합 / 메모리 구조 정의
  ISA는 IA-32, x86-64(x64), MIPS, AVR 등 다양하게 존재.
  • Intel x86-64 아키텍처 ( =x64, AMD64, Intel 64)
    : 인텔의 64비트 CPU 아키텍처
    인텔의 32비트 CPU 아키텍처인 IA-32를 64비트 환경에 사용할 수 있도록 확장
    32비트 모델보다 훨씬 더 많은 양의 가상 메모리와 물리적 메모리 지원 → 더 많은 양의 데이터 저장 가능
    • n비트 아키텍처
      → n : CPU가 한번에 처리할 수 있는 데이터 크기
      → WORD : CPU가 이해할 수 있는 데이터 단위 
      
      
    • Intel x64의 레지스터
      • 레지스터 : CPU가 데이터를 빠르게 저장하고 사용할 때 이용하는 보관소. 산술 연산에 필요한 데이터를 저장하거나 주소를 저장하고 참조하는 등 다양한 용도로 사용
      1. 범용 레지스터 (General Register) : 주용도는 있으나, 그 외의 다양한 용도로 사용될 수 있는 레지스터
      2. 세그먼트 레지스터 (Segment Register) : cs, ss, ds, es, fs, gs 총 6가지 세그먼트 레지스터 존재
      3. 명령어 포인터 레지스터 (IP, Instruction Pointer Register) : 프로그램을 구성하는 기계어 코드들 중 CPU가 어느 부분의 코드를 시행할지 가리킴
      4. 플래그 레지스터 (Flag Register) : 프로세서의 현재 상태를 저장하고 있는 레지스터
         
         

CPU의 하드웨어적 설계

: 마이크로 아키텍쳐(Micro Architecture). 정의된 명령어 집합을 효율적으로 처리할 수 있도록, CPU의 회로를 설계하는 분야

 

---

 

자료구조(Data Structure)

: 여러 데이터들의 묶음을 저장하고, 사용하는 방법을 정의한 것. 데이터의 효율적인 관리 및 사용을 위해 필요.

 

데이터(Data) : 문자, 숫자, 소리, 그림, 영상 등 실생활을 구성하고 있는 모든 값으로 그 자체만으로 어떤 정보를 가지기 힘듦

자료구조의 종류

1. 단순 구조 : 자료 값 사용을 위해 컴퓨터가 기본적으로 제공하는 자료형 ex) 2진수, 정수, 실수, 문자, 문자열
2. 선형 구조 : 자료를 구성하는 데이터를 순차적으로 나열시킨 형태로 자료들 간의 관계가 1:1인 자료 ex) 배열, 연결 리스트, 텍, 스택, 큐
3. 비선형 구조 : 하나의 자료 뒤에 여러 개의 자료가 존재할 수 있는 것 ex) 그래프, 트리
4. 파일 구조 : 서로 관련 있는 필드로 구성된 레코드 집합인 파일에 대한 자료구조. 보조 기억 장치에 데이터가 실제로 기록되는 형태로 메모리에 한 번에 올릴 수 없는 대용량을 다룸. ex) 순차 파일, 색인 파일, 직접 파일

선형자료구조

• 스택 (Stack)
  : 데이터 삽입과 추출이 한쪽방향만 가능한 구조 (stack = 쌓다, 한쪽만 뚫림)
  
  • 푸시 (push) : 스택에 데이터를 넣는 작업
  • 팝 (pop) : 스택에서 데이터를 꺼내는 작업
  • Top : 스택의 가장 윗부분
  • Bottom : 스택에 가장 아랫부분
  • 후입선출 (LIFO, Last In First Out) 방식
• 큐 (Queue)
  : 데이터 삽입과 추출이 양방향으로 가능한 구조 (양쪽 모두 뚫림)
  • 선입선출(FIFO, First In First Out) 방식
• 리스트 (List)
  : 선형리스트. 항목 간의 순서를 정한 데이터가 나열된 자료구조. 구현 방법에 따라 순차 리스트와 연결 리스트로 구분.
  • 순차 리스트 (Array List)
    : 순차적인 메모리 공간을 할당하여 구현하는 리스트로 보통 배열로 구현
  • 연결 리스트 (Linked List)
    : 데이터가 불연속 공간에 흩어져 있는 상태에서 다음 데이터의 위치 정보를 보유하게 하는 자료구조로 메모리 동적 할당 기법을 이용하여 구현
    • 다른 여러 자료구조 (스택, 큐, 트리, 그래프) 구현시 활용

비선형자료구조

• 트리 (Tree)  
  : 계층적인 구조를 나타냄. 하나의 루트 노드를 가지고 있으며, 각 노드는 0개 이상의 자식 노드를 가질 수 있음.
  • 노드(Node) : 트리의 기본 단위, 데이터를 저장하는 요소
  • 루트(Root) : 트리의 맨 위에 있는 노드
  • 부모(Parent) : 다른 하나 이상의 노드(자식 노드) 가리키는 노드
  • 자식(Child) : 부모 노드가 가리키는 노드
  • 조상(Ancestor) : 특정 노드에서 루트까지 이어지는 경로 상의 모든 노드
  • 자손(Descendant) : 특정 노드에서 아래 쪽으로 이어지는 모든 노드
  • 형제(Sibling) : 같은 부모 노드를 가진 자식 노드들
  • 잎(Leaf) : 자식 노드를 가지지 않는 노드, 트리의 가장 하위에 위치
  • 서브트리(Subtree) : 특정 노드와 그 하위 자손들로 이루어진 부분 트리

---

알고리즘

정렬 알고리즘

: 목록 안에 저장된 요소들을 특정한 순서대로 재배치하는 알고리즘. 입력 데이터는 보통 배열과 같은 데이터 구조.

• 선택정렬 (Selection Sort) : 선택된 값과 나머지 데이터 중에 비교하여 알맞은 자리를 찾는 알고리즘 (안전성 보장되지 않음)
• 삽입정렬 (Insertion Sort) : 데이터 집합을 순회하면서 정렬이 필요한 요소를 뽑아내어 이를 다시 적당한 곳으로 삽입하는 알고리즘 (버블정렬보다 좋은 성능)
• 버블정렬 (Bubble Sort) : 인접한 두 수 를 비교하여 오름차순/내림차순으로 정렬하는 알고리즘 (안전성 보장되지 않음)
• 병합정렬 (Merge Sort) : 둘 이상의 부분 집합으로 가르고, 각 부분 집합을 정렬한 다음 부분 집합들을 다시 정렬된 형태로 합치는 알고리즘 (분할정복법(Divide and Conquer), 안전성 보장됨)
• 힙 정렬 (Heap Sort) : 트리 기반으로 최대 힙 트리/최소 힙 트리를 구성해 정렬하는 알고리즘 (안전성 보장되지 않음, 내림차순 정렬-최대 힙, 오름차순 정렬-최소 힙)
• 퀵 정렬 (Quick Sort) : 데이터 집합 내에 임의의 기준(pivot) 값을 정하고 해당 피봇으로 집합을 두 개의 부분 집합(pivot보다 큰 부분과 작은 부분)으로 나누어 정렬하는 알고리즘 (안전성이 보장되지 않음)