알고리즘 실행시간 비교실행시간의 상한O(n²): 선택 정렬, 버블 정렬O(n log n)O(n): 선형 검색O(log n): 이진 검색O(1) 실행시간의 하한 (개선 전)Ω(n²): 선택 정렬, 버블 정렬Ω(n log n)Ω(n)Ω(log n)Ω(1): 선형 검색, 이진 검색 샌프란시스코 대학교 컴퓨터 과학 부서의 비교 정렬 시각화 도구 버블 정렬 개선정렬이 모두 되어 있는 리스트가 주어진다면 어떨까? 원래의 의사 코드Repeat n-1 times For i from 0 to n-2 If i'th and i+1'th elements out of order Swap them실행시간의 하한: Ω(n²)문제: 이미 정렬되어 ..

정렬된 배열이 정렬되지 않은 배열보다 탐색하기 쉽다. 선택 정렬(Selection Sort)은 배열에서 가장 작은 값을 찾아 첫 번째 위치의 값과 교환하는 방식의 정렬이다.교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가한다.동작 원리정렬되지 않은 숫자들을 오름차순으로 정렬해보자.6 3 8 5 2 7 4 11단계:가장 작은 값인 1을 찾는다첫 번째 값인 6과 교환한다결과: 1 3 8 5 2 7 4 62단계:정렬된 1을 제외하고 두 번째부터 가장 작은 값을 찾는다가장 작은 값인 2를 두 번째 값인 3과 교환한다결과: 1 2 8 5 3 7 4 63단계 이후:이 과정을 더 이상 교환이 일어나지 않을 때까지 반복한다최종 결과: 1 2 3 4 5 6 7 8의사 코드:For i from 0 to n-1 ..

정렬되지 않은 배열을 탐색하는 것보다 정렬 후 탐색하는 것이 더 효율적이다.정렬 알고리즘은 여러 가지가 있으며 각각 실행 시간이 다르다. 그중 버블 정렬에 대해 배워보자. 버블 정렬(Bubble Sort)은 두 개의 인접한 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법이다. 단 두 개의 요소만 정렬하는 좁은 범위의 정렬에 집중한다. 이 접근법은 간단하지만 하나의 요소를 정렬하기 위해 너무 많이 교환하는 낭비가 발생할 수 있다. 동작 원리8개의 숫자가 임의의 순서로 나열되어 있다.6 3 8 5 2 7 4 1 오름차순으로 정렬해보자.1. 가장 앞의 6과 3을 비교해 순서를 바꾼다. 2. 6과 8은 순서가 맞으므로 그대로 둔다. 8과 5를 비교해 순서를 바꾼다. 3. 이 과정을 끝까지 수행하면 다음과..

선형 검색(Linear Search)은 원하는 값을 찾을 때까지 처음부터 마지막까지 차례대로 검색하는 방법이다.찾고자 하는 값이 발견될 때까지 모든 자료를 순서대로 확인한다. 효율성선형 검색은 정확하지만 효율적이지 못한 방법이다.최악의 경우찾는 값이 맨 마지막에 있거나 없는 경우길이가 n인 배열에서 n번 실행시간 복잡도: O(n)최선의 경우첫 번째 시도에서 값을 찾는 경우시간 복잡도: Ω(1)선형 검색은 자료가 정렬되어 있지 않거나 추가 정보가 없을 때 유용하다. 무작위로 탐색하는 것보다 순서대로 탐색하는 것이 더 효율적이기 때문이다. 정렬 후 검색하면 더 빠르지만, 정렬 자체에 시간이 오래 걸린다는 문제가 있다. 구현숫자 배열 검색주어진 배열에서 특정 값을 찾는 코드다.#include #include ..

실행 시간프로그램을 실행하면 작업이 완료될 때까지 시간이 소요된다.간단한 프로그램은 실행 시간을 걱정할 필요가 없지만, 데이터가 많고 작업이 복잡해질수록 실행 시간은 매우 중요해진다.알고리즘의 실행 시간을 표기하는 방법을 알아보자.이 그래프는 알고리즘 실행 시간을 표현한 것이다. 문제 크기가 커질수록 각 알고리즘의 실행 시간이 어떻게 증가하는지 보여준다. Big O 표기법이런 그래프를 공식으로 표기한 것이 Big O 표기법이다.O는 "on the order of"의 약자로, "~만큼 커지는" 정도를 나타낸다.O(n):n만큼 커지는 것n이 늘어날수록 선형적으로 증가O(n/2):n이 매우 커지면 1/2은 의미가 없어짐결국 O(n)과 같음 Big O는 알고리즘 실행 시간의 상한(최악의 경우)을 나타낸다.주요 ..

검색 알고리즘메모리 구조, 자료형, 배열과 같은 기본 개념을 활용하여 검색과 정렬 문제를 푸는 알고리즘을 배워보자. 주어진 배열에서 특정 값을 찾는 방법부터 알아보자. 배열은 한 자료형의 여러 값이 메모리상에 모여 있는 구조다. 컴퓨터는 배열의 인덱스를 하나씩 접근한다.어떤 값이 배열 안에 있는지 찾으려면 배열이 정렬되어 있는지에 따라 다른 방법을 사용한다.선형 검색배열의 인덱스를 처음부터 끝까지 하나씩 증가시키며 값을 검사한다.For i from 0 to n–1 If i'th element is 50 Return trueReturn false모든 원소를 순서대로 확인하므로 정렬 여부와 관계없이 사용할 수 있다.시간 복잡도: O(n) 이진 검색배열이 정렬되어 있다면..

명령행 인자란make나 clang 같은 프로그램을 실행할 때 컴파일할 코드 외에도 파일명 같은 추가 정보를 함께 줄 수 있다. 이런 정보를 명령행 인자라고 부르며, 우리가 작성하는 프로그램에서도 명령행 인자를 받을 수 있다. argc와 argvmain() 안에 void 대신 argc와 argv를 정의해보자.#include #include int main(int argc, string argv[]){ if (argc == 2) { printf("hello, %s\n", argv[1]); } else { printf("hello, world\n"); }}argc (argument count):main 함수가 받는 입력의 개수argv (argument ..

문자열 길이 구하기문자열에서 문자를 검색하거나 특정 문자를 바꾸려면 어떻게 해야 할까? 사용자로부터 문자열을 입력받아 한 글자씩 출력하는 프로그램을 만들어보자. for 루프로 문자열의 인덱스를 하나씩 증가시키면 되는데, 문자열의 끝은 어떻게 알 수 있을까?한 가지 방법은 널 종단 문자 \0와 일치하는지 검사하는 것이다.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 st..

문자열은 배열이다지금까지 문자열을 저장하기 위해 string 자료형을 사용했다. '문자열'은 문자가 '나열되어 있다' 또는 '배열되어 있다'는 의미다. C에서 string은 정확히 어떻게 정의되어 있을까? 문자열(string) 자료형은 사실 문자(char) 자료형의 배열이다. 문자 배열string s = "HI!";와 같이 문자열 s가 정의되어 있다고 가정해보자. s는 문자의 배열이므로 메모리상에 다음과 같이 저장되며, 인덱스로 각 문자에 접근할 수 있다.가장 끝의 \0은 널 종단 문자로, 문자열의 끝을 나타낸다. 모든 비트가 0인 1바이트를 의미한다. 2차원 배열여러 문자열이 동시에 선언된 경우를 살펴보자.string names[4];names[0] = "EMMA";names[1] = "RODRIGO"..

메모리와 자료형특정 자료형의 변수를 선언하면 메모리상에 특정 크기만큼 자리를 차지한다. 비슷한 종류의 값을 모아서 저장하려면 어떻게 해야 할까? C의 자료형과 각각의 메모리 크기는 다음과 같다.bool: 불리언, 1바이트char: 문자, 1바이트int: 정수, 4바이트float: 실수, 4바이트long: 더 큰 정수, 8바이트double: 더 큰 실수, 8바이트string: 문자열, ?바이트 컴퓨터 안에는 RAM이라는 물리적 칩이 메모리 역할을 한다.각 사각형이 메모리를 의미하고, 작은 사각형 하나가 1바이트다. 예를 들어 char 타입 변수를 생성하면 한 사각형에 값이 저장된다. 배열배열 선언세 개의 점수를 저장하고 평균을 출력하는 프로그램을 작성해보자.#include #include int main(..