Crash Course: Computer Science를 정리했습니다.
초기의 프로그래밍
방직기
이는 최초의 프로그래밍 방식 중 하나다.
펀치 카드
인구조사 통계 건으로 의뢰해 개발한 그것이다. 그러나 이는 단지 도표화 하나만 가능했으며 프로그래밍은 아니었다.
플러그보드
여기에 점점 빼고 곱하고 나누는 기능이 추가된다. 이런 기능을 수행할 수 있도록 프로그래머는 Control Panel 제어 패널을 조작한다. 이 패널은 작은 소켓들로 채워져 있고, 프로그래머가 케이블을 연결하여 값이나 신호를 기계의 다른 부분으로 보낼 수 있었다.
Stored-Program Computers
프로그램을 물리적인 플러그보드의 선으로 저장하는 대신에, 전체 프로그램을 이제 메모리 안에 저장할 수 있게 되었다!
폰 노이만 구조
프로그래밍 데이터를 단일 공유 메모리로 통합하는 것. 펀치카드 리더가 붙어있었다. 펀치카드 뭉치를 바른 순서대로 놔야했다.
프로그램 오류 수정은 말 그대로 '패치'를 붙였다. 여기에서 패치라는 단어가 유래되었다.
패널 프로그래밍도 있다
스위치와 버튼으로 가득 찬 거대한 패널, 표시등이 있는 거대한 제어 콘솔, 스위치를 켜고 끄면서 2진수를 입력했다.
최초의 프로그래밍 언어
하드웨어 차원에서 프로그래밍하는 건 번거롭고 어렵다. 그래서 소프트웨어가 등장하게 된다.
하드웨어는 원시 이진 명령어를 처리한다. 컴퓨터가 사용할 수 있는 유일한 언어는 기계어다. 따라서 먼저 종이로 고수준 언어(=의사 코드 pseudo-code)를 작성하고 이진 기계어로 opcode table 같은 걸 사용하여 번역하는 것이다.
어셈블러
1940-50년대에 약간 더 높은 수준의 언어가 개발되었다. opcode에는 mnemonics 니모닉이라는 간단한 이름을 지정했다. 어셈블리 언어를 읽어 기계어로 번역하는 것인데, 자동으로 JUMP 주소를 파악하는 등 기능이 있다.
그러나 어셈블리어는 기계어에 일대일로 매핑기 떄문에 기본 하드웨어에 묶여있는 한계가 있다. 즉, 어떤 레지스터와 메모리를 사용할지 생각해야 하는 것이다. 그래서 Hopper는 최초의 컴파일러를 고안한다.
IBM에서 만든 Fortran
초기 컴퓨터 프로그램을 지배한 fortran. 이 덕분에 더 많은 코드를 더 빠르게 읽을 수 있게 되었다.
COBOL
1950년대 대부분의 프로그래밍 언어와 컴파일러는 단일 유형의 컴퓨터에서만 실행 가능했다. 컴퓨터 업그레이드하면 종종 모든 코드를 다 다시 작성해야 하는 사태가 벌어지기도 했다. 이에 그레이스 호퍼의 고안으로 공통 프로그래밍 언어 개발을 위해, 산업, 학계의 컴퓨터 전문가들과 정부가 협회를 구성하여 데이터 시스템 언어위원회를 만든다.
COBOL (Common business-oriented)이란 사용하기 쉽고 고수준의 공통 비즈니스 지향 언어이다. 특징은 Write once, run aniwhere = 어떤 컴퓨터에서 실행되든 동일한 결과를 낸다는 것. (그러나 여전히 CPU와 관련이 있다는 한계가 있긴 했다)
이 모든 발전은 누구든지 사용하게 하기 위함이다.
시대별 대표적인 언어
1960년대 ALGOL, LISP, BASIC
1970년대 PASCAL, C, Smalltalk
1980년대 C++, Objective-C, Perl
1990년대 Python, Ruby, Java
2000년대 Swift, C#, Go
거의 모든 프로그래밍 언어가 제공하는 것들 (기본 구성 요소)
프로그래밍 언어에도 구문Syntax이 존재한다.
대입문 '='
등호의 오른쪽부터 체크하자.
변수를 초기화 Initialize
= 초기 값을 정하는 것. A = 1 은 A라는 새로운 변수를 초기화하고 1로 설정한다는 뜻이다.
제어흐름문 Control Flow Statement
If문이 가장 일반적 조건conditional문이다. if-then-else의 구조.
while (while loop)은 조건이 참일동안 반복하는 것이며, for문은 loop 횟수를 특정 횟수로 조정이 가능하다.
Functions = = Methods = Subroutines
함수 = 메서드 = 서브루틴
현대 프로그래밍에서는 모듈화로 인해 100줄 넘는 함수는 찾아보기 어렵다.
라이브러리
미리 작성된 함수 묶음을 뜻한다. 거의 모든 것을 위한 라이브러리가 존재한다!
알고리즘
알고리즘이 현대 컴퓨터 과학을 이끌어냈다!
가장 중요한 알고리즘 문제 중 하나는 정렬인데, 왜냐하면 컴퓨터는 항상 정렬을 사용한다! 연락처 정렬, 금액 정렬.. 등등
선택정렬
FUNCTION selectionSort(array)
FOR i = 0 TO end of array
smallest = i
FOR index = i+1 TO end of array
IF array item index < array item smallist
smallest = index
END IF
NEXT
swap array items at index and smallest
NEXT
RETURN array
FOR 루프가 다른 FOR 루프 안에 포함되어 있다 = N개의 항목을 정렬하고 싶다면 N번 반복해야 한다. 그 안에서 루프를 N번 반복하면 총합은 대략 N*N 루프 또는 N^2
입력하는 수의 크기input size와 실행되는 단계 수number of steps 사이의 관계는 선택 정렬 알고리즘의 복잡도complexity를 특징화한다.
→ 이는 얼마나 빨리 또는 느리게 알고리즘이 실행될지 근사치를 제공한다.
→ 이를 big O표기법으로 표기한다. O(n^2)
- N^2은 특별하게 효율적이지는 않다.
- 예를 들어 배열 크기를 80으로 늘린다면 6400이라는 결과가 나온다.
- 배열은 10배, 실행시간은 100배 증가! 커질수록 영향이 확대된다. 구글 같은 큰 회사에는 큰 문제다.
- n = 8개 항목이라면 8의 제곱 64
Merge Sort 병합 정렬
- 배열의 크기가 1보다 큰지 확인한다.
- 큰 경우 배열을 두 개로 나눈다.
- 1보다 여전히 크다면 계속 반복하여 두 개로 나눈다.
둘로 나눈 다음 작은 순서부터 병합하는 것이다. 양쪽배열 숫자가 여럿 있으면 그 둘을 하나씩 비교하는 느낌이다.
빅O표기법상 N * logN 로 표기한다. O(n log n)
- N은 비교하고 합병하는 데에 필요한 횟수만큼 발생한다.
- 이 횟수는 정렬안의 배열 항목수와 직접 비례한다.
- 로그 n은 병합 단계의 수에서 나온다.
- 반으로 나누니까 항목 수 사이에 로그관계를 가지게 된다.
- 정렬의 크기를 8의 두배인 16으로 하면 정렬할 항목 수는 두 배 늘어남 → 분할 단계 횟수는 1번 증가할 뿐!
- 따라서 선택정렬보다 효율적이다
로그는 지수 함수의 역함수이다. 어떤 수를 나타내기 위해 고정된 밑을 몇 번 곱하여야 하는지를 나타낸다고 볼 수 있다.
2^4 = 16
2^x = 16 = log₂16 = x
그래프 서치
node와 edge로 이루어진 그래프.
무차별적 접근 방식 = 모든 경로 다 조사
N! (n팩토리얼)
Dijkstra 다익스트라 알고리즘
가장 빨리 특정 node에서 특정 node로 도착하는 루트를 찾는 알고리즘이다.
그래프 안의 노드 수의 제곱만큼의 복잡도를 가진다 O(n^2) → 제곱은 효율이 좋지 않아! 따라서 몇 년 뒤 이 알고리즘은 개선되었다.
O(n log n + L라인수)
구글 지도의 길찾기 같은 서비스에서 실행된다. 이처럼 현대 세상은 알고리즘 없이는 생활이 불가능하다.
자료 구조
데이터 알고리즘이 실행되는 데이터가 어떻게 컴퓨터 메모리에 저장되는가
데이터가 읽고 불러오기 쉽게 잘 정리되어 있기 위함이다.
배열=리스트=벡터
- 메모리에 연속적으로 저장되어있는 값이다.
- 특정한 값 찾으려면 index 지정이 필요 → a[0]에서 0이 인덱스
- 배열은 0부터 시작하므로 인덱스가 5인 숫자는 6번째 숫자
- 유사한 것 string j = "string words"
- 메모리상에서 배열은 (이진법)0으로 끝난다 = null 문자 = 문자열의 끝을 나타낸다
- 이게 중요한 이유는?
- 만약 이 문자열을 print 같은 함수로 출력한다고 하면 언제 출력을 멈출지 알아야 하기 때문 (문자열 함수가 언제 끝나는지 알려준다)
- ex. 많은 프로그래밍 언어는 두 문자열을 입력받아서 두번째 문자열을 첫번째 문자열의 끝에 복사해주는 string concatenation = strcat (연속 문자열)이라는 함수를 갖고 있다.
2차원 배열
- 2차원으로 다루고 싶을 때 필요한 것 MATRIX 행
- 인덱스 두개 필요 j[2][1]
구조체 struct
- 연관된 것을 함께 저장하기 위해 사용된다.
- 변수 그룹은 struct(구조체)로 묶을 수 있다
- 복합데이터로 된 변수
- 배열은 만들어질 때 크기 고정됨, 더 확장되지 않음. 중간에 새로운 값 넣기 아려움
- 하지만 Struct 데이터 구조를 사용하면 보다 복잡한 구조를 저장 가능!
Linked List
- 각 node가 목록의 다음 노드를 가리키도록 pointer를 지정한다.
- 값 & pointer 값
- 이렇게 CIRCULATE가 되는데 다음 포인터 값을 null로 해주면 끝나게 된다 (null은 끝에 도달했다는 뜻)
- 크기를 상황에 따라 늘이거나 줄이기 가능. 포인터만 바꾸면 된다. 따라서 유연성이 좋다.
- 정렬 알고리즘에도 유용하게 쓰인다
- 이걸 기반으로 하는 것이 QUEUE(줄서기)와 STACK(팬케이크 더미)
2개의 포인터가 있다면 Tree구조를 만들 수 있다
맨 끝의 노드를 리프 노드라고 한다. 뿌리에서 잎까지의 하나의 길이가 존재한다는 게 중요하다.
무한 루프같은 건 그래프 데이터 구조를 사용한다
무엇이든 아무거나 가리킬 수 있기 때문이다.
각 자료구조들은 특정 계산에 유리하다
따라서 상황에 맞는 자료구조를 선택해야 한다!
라이브러리에는 이미 만들어진 자료구조들로 가득하다. (C++은 Standard Template Library, 자바는 Java Class Library 등)
