Go라고 써있긴 하지만, 1~6강 동안에는 컴퓨터가 어떻게 작동하는지에 대한 원리를 설명해준다.
트랜지스터 - 논리소자 - 계산기 - 원시 컴퓨터(튜링/폰 노이만) - 현재의 컴퓨터로 빠르면서도 간결하게 얘기해줘서
진짜 기술의 발전이 컴퓨터에 집약되어 있구나 하는 생각이 들었다.
그 외에 언어별로 구분하는 동적/정적 언어에 대한 구분법(일종의)이나 컴파일러, 기계어와 같은 개념도 알게 되었다.
요리로 비유해서 컴퓨터의 동작을 설명하는 부분이 진짜 압권이다.
저장소(HDD - 마트)에서 bus(실제로 케이블 이름이 버스임)를 통해 메모리(냉장고)에 불러오고,
그 메모리에서 재료들을 '움큼'(필요한 것만 빼는게 아니라 근처 값들도) 꺼내서 도마(Cache)에 올리고,
레시피(프로그램, 처리하는 순서와 방법을 제공)에 따라 필요한 재료들만(Register) 올려서
셰프(CPU)가 처리한다.
(자료구조 - 한국외대 컴퓨터전자시스템공학부 신찬수 교수님)
자료를 찾아보다가 우연히 발견했는데, 심지어 파이썬이다..!
출중한 강의력과 인간적인 잡음 그리고 보기 좋은 판서로 진행된다.
따로 메일로 요청하면 수업자료도 보내주시는 것 같다.
쭉 들으면서 정리해볼 생각이다.
혹시라도 애매하거나 틀린 부분이 있으면 집어주세요!
1강 - 자료구조와 알고리즘
자료(data)가 memory에 저장되고, 연산되거나 쓰이는 방식(읽기, 쓰기, 삽입, 삭제, 탐색)들이 자료구조라고 할 수 있다.
그리고 그러한 자료구조들을 통해 입력-> 출력(정답)을 해내는 것이 알고리즘이다.
'최대공약수는 어떻게든 1은 존재하니까, 어떤 막대로 나눠서 구분할 수 있다면
큰 것에서 작은 것을 빼면서 결국 마지막에 남는 큰 덩어리가 최대공약수가 될 것이다.'
대박이네.. 바로 파이썬으로 구현해보았다.
2강 - 알고리즘 시간복잡도1
여러 컴퓨터마다 쓰이는 환경이 다르므로, 가상의 컴퓨터-언어-코드를 기준으로 잡는다.
RAM에서 CPU와 메모리를 통해 기본연산 - 알고리즘을 수행한다.
가상언어를 통해 가상 컴퓨터에서 알고리즘이 수행된다.
-> RAM에서 쓰는 연산들과 제어규칙을 제공해주면 됨
그렇게 작성된 코드가 가상코드다.
무한히 많은 입력을 가정했을 때에 연산의 횟수, 시간은 얼마나 걸릴까?
3강 - 알고리즘 시간복잡도2
가장 많은 연산이 들어가는 케이스를 기준(최악의 케이스)으로 그 연산횟수로 수행시간을 설정한다.
4강 - 알고리즘 시간복잡도 BigO
과제로 prefix-sum(구간 합)을 내주신 걸 보니 직접 그 과제를 찾을 수는 없고, 백준에서 찾아 풀기로 했다.
2042- 구간 합 구하기
(https://www.acmicpc.net/problem/2042)
문제
어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다.
만약에 1,2,3,4,5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 합을 구하라고 한다면
17을 출력하면 되는 것이다.
그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 합을 구하라고 한다면 12가 될 것이다.
입력
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다.
M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다.
그리고 둘째 줄부터 N+1번째 줄까지 N개의 수가 주어진다.
그리고 N+2번째 줄부터 N+M+K+1번째 줄까지 세 개의 정수 a, b, c가 주어지는데,
a가 1인 경우 b(1 ≤ b ≤ N)번째 수를 c로 바꾸고
a가 2인 경우에는 b(1 ≤ b ≤ N)번째 수부터 c(b ≤ c ≤ N)번째 수까지의 합을 구하여 출력하면 된다.
입력으로 주어지는 모든 수는 -2^63보다 크거나 같고, 2^63-1보다 작거나 같은 정수이다.
출력
첫째 줄부터 K줄에 걸쳐 구한 구간의 합을 출력한다. 단, 정답은 -2^63보다 크거나 같고, 2^63-1보다 작거나 같은 정수이다.
-틀린 코드-
?? 트리라는데요?
이 구간합이 아닌건가..? 다음 기회에..