CS50
CS지식이 전혀 없어서 기초강의로 CS50를 보고 정리.
Computational Thinking
- 2진법
On, Off 표시로 1과 0을 나타냄으로 2진법을 사용.
8bits -> 1byte - ASCII code
문자표현을 위해 정해진 숫자와 문자 약속. (대문자와 소문자 차이는 2^5)
더 많은 문자 나타내기위해 unicode도 사용.
색표현도 마찬가지. RGB로 나타냄.
Algorithms
Input이 output이 되기위해 수행될 명령들의 순서적 나열. (정확성과 효율성 중요)
*의사코드
프로그램 작성시 모듈작동 논리를 표현하기 위한 언어. 일반적인 언어로 코드를 흉내내어 알고리즘을 작성
- 알고리즘 표현법
- Big - O (O)
상한, 찾을 때 걸리는 최댓값, 최악의 경우
- Omega (Ω)
하한, 찾을 때 걸리는 최솟값, 최상의 경우
-
linear search (선형검색)
하나씩 비교하는 검색. 정확하지만 비효율
어떠한 정보도 없을 경우 사용
O(n)
Ω(1) -
Binary search (이진검색)
배열이 정렬되어 있을때 절반값을 조건과 비교하여 검색(조건보다 크거나 작거나)
O(log n)
Ω(1) -
Bubble sort (버블정렬)
거품이 터지면서 위로 올라가듯, 두개 인접값을 비교하면서 위치를 교환하는 방식.
정렬되어있을 때 더욱 효율적이다.
O(n^2)
Ω(n^2) 정렬이 안되어 있을 경우
Ω(n) 정렬시
- Selection sort (선택정렬)
조건의 값을 배열안의 자료중에서 찾고 특정위치로 이동시킨다.
교환횟수는 최소화하지만, 자료비교 횟수는 증가
O(n^2)
Ω(n^2)
- merge sort (병합정렬)
원소가 하나가 될때까지 반으로 나누고 다시 합쳐나가면서 정렬
숫자를 반으로 나누는 데 O(log n), 다시 정렬하는데 O(n)
O(n log n)
Ω(n log n)
Log