데이터구조 & 알고리즘의 목적

• 복잡한 문제를 풀기 위해 컴퓨터가 이해할 수 있는 언어로 바꿔줘여 함 (e.g. matrix)
• 명시적으로 “강남역”에서 “안암역”까지 가는 문제로 정의되다면, 이 solution은 반복적으로 사용할 수 없는 알고리즘이 됨
• $X_1$(임의의 역)에서 $X_2$(임의의 역)에서 adaptive하게 solution을 찾고 cost-efficient하는 것이 목적

Data Structrue

1. Set of fields: 변수들의 모임 (e.g. 사람: 팔, 눈, 머리)
   • Control field: 눈에는 보이지는 않지만, 프로그램을 수행할 때 필요한 데이터 구조
     (e.g. 윈도우에서 더블클릭 -> 해당파일디스크의 파일이미지를 메모리로 불러들이고 점프한 후 실행)
   • Operation: ‘눈’이는 structure가 있다면, “본다”라는 Operation 연산이 필요
2. Abstract data type: python의 class와 같은 역할
   • bulit-in types: 프로그램 언어가 만들어 질 때 부터 이해 할 수 있는 타입 (e.g. int, char)
3. Object-oriented laugange
   • Abstract data type이 학생이라고 하면, 한 학생.인스턴스로 표현하면 내부적으로 앞에 있는 연산을 수행하게 됨
   • procedure(개별적인 진행과정)보다 결과중심 언어

Algorithm

• 알고리즘
  1. A finite list of well-defined instructions($\sim$ micro operation)
     • micro operation: 개별적인 하나하나의 operation (너무 detail한 표현)
     • atomic operation: 한번 실행되면 멈출 수 없는 operation
  2. Instructions: initial state에서 end state까지 가는 데 sequence of action(changeable)
     • initial state: 시계가 12시에 맞춰져 있음
     • end state: 우리가 원하는 결과는 내는 시점
     • changeable action(값)으로 바꿔주기 위해 값을 assignment

• Implementation
  1. Design
     • Data structure & Algorithm 구현
     • $H_2$ 와 $O$ 분자가 만나면 $H_2O$(물)이 되는 것처럼 모호성(ambiguity)이 없도록 디자인
  2. Correctness
     • Proof by induction
       • Claim(property 정의)
       • n에서 동작하는지 확인
       • n+1에서 동작하는지 확인
     • Counter example: 반례
     • Contradiction: “소수는 유한하다”, 유한하다는 가정하에 무한하다는 것을 증명
  3. 언어 구현
     • complier: 사람의 언어(C언어)를 CPU가 이해할 수 있도록 바꾸는 Tool
     • C 코드: complier가 있음
     • Pseudo 코드: complier가 없음, 긴 알고리즘을 단순히 표현할 수 있음
  4. 성능평가(complexity)

디지털 시스템 용어 정리

• CPU
  • 가장 간단한 operation을 수행할 수 있도록 만들어짐
  • 그 operation를 활용하여 내가 필요한 기능으로 만들 수 있음
  • 따라서 다양한 서비스를 가능하게 하도록 함
  • e.g) 2개 구멍을 내는 공정에서 3개의 구멍을 내는 공정으로 바꾸고 싶은 상황 일 때, 비 효율적으로 다 바꾸기 보단, 각 역할(기능)을 하는 구성요소들(components)를 생성하는 것이 효율적
• Unix
  • C로 만든 운영체제
• Linux
  • 개인용 PC를 위한 Unix