Stage
-
[메모리] 메모리 주소Stage/Computer Science 2021. 5. 31. 22:25
학습 목표 16진법을 읽고 쓸 수 있다. 메모리 주소에 접근하고 값을 받아오는 코드를 C로 작성할 수 있다. 1. 16진수(Hexadecimal) 컴퓨터과학에서는 숫자를 10진수나 2진수 대신 16진수로 표현하는 경우가 많다. 왜??? 당연히 10진수나 2진수 대신 16진수로 표현할 경우에 장점이 있기 때문인데, 그 이유를 알아보자. 1.1 10진수를 16진수로 바꾸기 우리가 생활하면서 사용하는 10진수와 16진수를 비교해보면 이유를 바로 알 수 있다. 10진수 255를 2진수로 바꾸면 11111111과 같다. 컴퓨터는 2진수를 사용하기 때문에 255를 11111111로 표현해야하지만, 너무 길다. 255뿐만 아니라 모든 데이터를 2진수로 표현해야 한다고 가정하면 너무 길어진다. 이를 16진수로 한번 표..
-
[알고리즘] 병합 정렬Stage/Computer Science 2021. 5. 29. 00:53
학습 목표 재귀를 활용한 병합 정렬을 구현할 수 있다. 1. 정렬 알고리즘 대표적인 정렬방법 중 하나이다. 전화번호부에서 mike를 찾기 위해 절반을 나눠서 탐색해나갔던 분할 정복 탐색처럼 데이터를 반으로 나누어간다는 공통점이 있다. 병합 정렬은 원소가 한 개가 될 때까지 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방식이다. 2. 예시 임의로 나열된 8개의 숫자를 오름차순으로 정렬해보자. 7 4 5 2 6 3 8 1 먼저 숫자를 반으로 나누자. 7 4 5 2 | 6 3 8 1 나눠 놓은 덩어리를 한번 더 나눠보자. 7 4 | 5 2 | 6 3 8 1 또 나누자. 7 | 4 | 5 2 | 6 3 8 1 원소가 한 개가 남았으므로 더 이상 나눌 수가 없다. 두 숫자를 작은 숫자가 먼저 오도록 병합하자. 4..
-
[알고리즘] 재귀Stage/Computer Science 2021. 5. 29. 00:53
학습 목표 함수를 재귀적으로 사용하는 코드를 작성할 수 있다. 1. 재귀? main에서 필요할 때 다른 함수들을 호출해서 사용했던 상황을 떠올려 보자. 생각해보면 main도 함수인데 main이라는 함수 안에서 다른 함수를 호출해서 사용한 것이다. 그렇다면 함수가 본인 스스로를 호출해서 사용할 수 있을까? -> YES. 이를 재귀(Recursion)라고 부른다. 2. 피라미드를 출력하자 # ## ### #### #include #include void draw(int h); int main(void) { int height = get_int("Height: "); draw(height); } void draw(int h) { // 높이가 0이라면 (그릴 필요가 없다면) if (h == 0) { return..
-
[알고리즘] 정렬 알고리즘의 실행시간Stage/Computer Science 2021. 5. 29. 00:52
학습 목표 여러 정렬 알고리즘과 검색 알고리즘의 실행 시간을 Big O와 Big Ω로 정의할 수 있다. 1. 실행시간 정리 1.1 실행시간의 상한 O(n^2): 선택 정렬, 버블 정렬 O(n log n) O(n): 선형 검색 O(log n): 이진 검색 O(1) 1.2 실행시간의 하한 Ω(n^2): 선택 정렬 Ω(n log n) Ω(n): 버블 정렬 Ω(log n) Ω(1): 선형 검색, 이진 검색 #이 파트는 이해 못해서 문제 다 틀렸다. 구글링 해서 자료 보강하고 추가 해놓을 것.
-
[알고리즘] 선택 정렬Stage/Computer Science 2021. 5. 29. 00:50
학습 목표 선택 정렬의 원리와 실행 시간을 설명하고 구현할 수 있다. 1. 정렬 알고리즘 정렬 알고리즘 중 하나인 선택 정렬은 배열 안에 나열된 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬이다. 선택 정렬은 교환 횟수를 최소화하지만 각 자료를 비교하는 횟수는 증가한다. 2. 예시 정렬되지 않은 숫자 8개가 있다. 이 숫자들을 오름차순으로 정렬해보자. 6 3 8 5 2 7 4 1 숫자들을 끝까지 탐색하면서 제일 작은 수를 찾는다. 6 3 8 5 2 7 4 1 가장 작은 값과 현재 리스트의 첫 번째 값을 교환한다. 1 3 8 5 2 7 4 6 1은 이제 정렬이 되어 있으니 제외하고, 두 번째 숫자부터 탐색하면서 또 제일 작은 수를 찾..
-
[알고리즘] 버블 정렬Stage/Computer Science 2021. 5. 29. 00:49
학습 목표 버블 정렬의 원리와 실행 시간을 설명하고 구현할 수 있다. 1. 정렬 알고리즘 정렬되지 않은 리스트를 탐색하느 것보다 정렬한 뒤 탐색하는 것이 더 효율적이다. 정렬 알고리즘 중 하나인 버블 정렬은 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법을 말한다. 2. 에시 숫자 8개가 임의의 순서로 나열 되어 있다. 6 3 8 5 2 7 4 1 이 숫자들을 오름차순으로 정렬하기 위해 버블 정렬을 이용해보자. 3 6 8 5 2 7 4 1 3 6 5 8 2 7 4 1 바로 다음에 있는 숫자와 비교해서 정렬을 해나가면 아래와 같이 정렬이 된다. 3 6 5 2 7 4 1 8 오름차순으로 정렬이 되지 않았기 때문에 다시 처음으로 돌아가서 같은 작업을 반복한다. 3 5 2 6 4 1..
-
[알고리즘] 알고리즘 표기법Stage/Computer Science 2021. 5. 29. 00:44
학습 목표 알고리즘 실행 시간의 상한과 하한을 표기할 수 있다. 1. Big O 표기법 알고리즘을 실행하는 데 걸리는 시간은 아래 그림과 같다. 이 그림을 공식으로 표기한 것이 Big O 표기법이다. O 는 "on the order of"의 약자이고, 쉽게 생각하면 "~만큼의 정도로 커지는" 것이라고 볼 수 있다. O(n)은 n만큼 커지는 것이므로 n이 커지면 선형적으로 증가한다. O(n/2)도 결국 n이 매우 커지면 1/2은 큰 의미가 없어지므로 O(n)이라고 볼 수 있다. 예를 들어, 우리가 푸는 문제가 계속 커져서 저 선들을 더 큰 화면에 담기도록 축소해서 보기 위해 x축과 y축을 늘려보자. 노란 선과 빨간 선은 아주 가까워질 것이고, 계속 축소하다보면 두 선은 결국 거의 같아 보일 것이다. 1.1..