병합 정렬(Merge Sort)은 원소가 한 개가 될 때까지 계속 반으로 나누다가 다시 합쳐나가며 정렬하는 방식이다.이 과정은 재귀적으로 구현된다.동작 원리다음 숫자들을 오름차순으로 정렬해보자.7 4 5 2 6 3 8 1 1단계: 분할숫자들을 반으로 계속 나눈다.7 4 5 2 | 6 3 8 17 4 | 5 2 | 6 3 8 17 | 4 | 5 2 | 6 3 8 1 원소가 한 개가 될 때까지 나눈다.7 | 4 | 5 | 2 | 6 | 3 | 8 | 1 2단계: 병합이제 작은 숫자가 먼저 오도록 병합한다.숫자 1개씩 병합:4 7 | 2 5 | 3 6 | 1 8 숫자 2개씩 병합:4 7과 2 5를 병합: 2와 4 비교 → 2, 4와 5 비교 → 4, 7과 5 비교 → 5, 7 남음2 4 5 7 | 1 3 6 ..

알고리즘을 구현할 때 동일한 작업을 반복해야 할 때가 있는데 이를 함수로 구현하면 코드를 효율적으로 만들 수 있다. 그렇다면 함수 내에서도 동일한 작업이 반복되는 경우는 어떻게 해야 할까?함수를 함수 내에서 재사용하는 방법, 즉 재귀적으로 호출하는 방법을 알아보자.재귀란지금까지 우리는 main 안에서 프로그램을 작성하면서 필요한 순간에 함수를 호출했다. main도 함수이므로 함수 안에서 또 다른 함수를 사용한 것이다. 함수 안에서 다른 함수를 호출하는 것처럼, 자기 자신을 호출할 수도 있는데 이를 재귀(Recursion)라고 부른다. 반복문으로 피라미드 그리기피라미드 모양을 출력하는 코드다.#include #include void draw(int h);int main(void){ int height..

알고리즘 실행시간 비교실행시간의 상한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..