분류 전체보기
-
[알고리즘] 버블 정렬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..
-
[알고리즘] 검색 알고리즘Stage/Computer Science 2021. 5. 29. 00:40
학습 목표 주어진 배열 속에서 특정 값을 찾는 방법을 설명할 수 있다. 0. 인트로 배열은 한 자료형의 여러 값들이 메모리상에 모여 있는 구조이다. 컴퓨터는 이 값들에 접근할 때 배열의 인덱스 하나하나에 접근한다. 만약 어떤 값이 배열 안에 속해 있는지를 찾아보려면 배열이 정렬되어 있는지의 여부에 따라 다른 방법을 사용할 수 있다. 1. 선형 검색 배열의 인덱스를 처음부터 끝까지 하나씩 증가시키면서 방문하여 그 값이 속하는지를 검사하는 것이다. 케비넷에서 숫자 50을 찾기 위해 Eric이 첫번째 사물함부터 마지막 사물함까지 문을 하나씩 차례대로 열어봤던 장면을 떠올려보자. 2. 이진 검색 배열이 정렬되어 있다면, 배열의 중간 인덱스부터 시작해서 찾으려고 하는 값과 비교하여 그 값보다 작은 값이 저장되어 ..
-
[배열] 문자열의 활용Stage/Computer Science 2021. 5. 27. 23:04
학습목표 문자열을 탐색하고 일부 문자를 수정하는 코드를 구현할 수 있다.1. 문자열 탐색 사용자로부터 문자열을 입력받아 한 글자씩 출력하는 코드를 짜야 한다면 간단하게 for문을 이용해 문자열의 인덱스를 1씩 증가시켜나가면 된다. 1.1 문자열이 끝나는 인덱스는 어떻게 알 수 있을까? 해당 인덱스의 문자가 null 종단 문자와 일치하는지 검사하면 된다. for (int i = 0; s[i] != ‘\0’; i++) { ... } strlen() 함수를 사용하면 된다. #include #include #include int main(void) { string s = get_string("Input: "); printf("Output:\n"); for (int i = 0, n = strlen(s); i < ..
-
[배열] 문자열과 배열Stage/Computer Science 2021. 5. 27. 22:50
학습목표 문자열이 C에서 정의되는 방식과 메모리에 저장되는 방식을 설명할 수 있다. 1. 문자열? 문자열(string) 자료형의 데이터는 문자(char) 자료형의 데이터들의 배열이다. string s = "HI!"; 문자열 s는 문자의 배열이기 때문에 메모리상에 아래의 그림과 같이 저장된다. 인덱스로 각 문자에 접근이 가능하다. s[0] = H s[1] = I s[2] = ! s[3] = \0 3번째 인덱스의 '\0' 은 문자열의 끝을 나타내는 null 종단 문자이다.
-
[배열] 배열Stage/Computer Science 2021. 5. 27. 22:49
학습목표 배열을 정의하고 사용하는 방법을 설명할 수 있다. 1. 메모리 C에는 다음과 같은 여러 자료형이 있고, 각각의 자료형은 서로 다른 크기의 메모리를 갖는다. bool: 1byte char: 1byte int: 4byte float: 4byte long: 8byte double: 8byte string: ?byte 컴퓨터에서는 RAM이라는 물리적 칩이 메모리 역할을 한다. 쉽게 생각하면 위 사진에 나와있는 조그만 여러 개의 노란색 사각형이 메모리를 의미하고, 작은 사각형 하나는 1바이트를 의미한다. 2. 배열 배열은 같은 자료형의 데이터를 메모리상에 연속으로 저장하고 이를 하나의 변수로 관리하기 위해 사용된다. #include #include int main(void) { // Scores int ..
-
[배열] 디버깅Stage/Computer Science 2021. 5. 27. 22:46
학습목표 디버깅 하는 여러 방법을 설명할 수 있다. 1. 버그와 디버깅 1.1 버그 버그는 코드에 들어있는 오류이다. 버그로 인해 프로그램 실행에 실패하거나 프로그래머가 원하는대로 동작하게 하는 데 실패한다. 1.2 디버깅 코드에 있는 버그를 식별하고 고치는 과정을 말한다. 디버거라고 불리는 프로그램을 사용하여 디버깅을 하게 된다. 디버거는 프로그램을 특정 행에서 멈출 수 있게 해주기 때문에 버그를 찾는 데 도움이 된다. 프로그램이 멈추는 특정 지점을 break point(중지점)라고 한다. 프로그래머가 프로그램을 한번에 한 행씩 실행할 수 있게 해주므로 프로그램이 수행되는 과정들을 단계별로 파악하는 것이 가능하다.