도전하는 일반인

들어가기 전에 앞서 배운 정렬 알고리즘은 직관적이지만 실행 시간의 상한이 다소 높았습니다. 반복되는 작업이 많았기 때문인데요, 지난 강의에서 배운 재귀를 활용하면 정렬 알고리즘을 더 효율적으로 만들 수 있을까요? 학습 목표 재귀를 활용한 병합 정렬을 구현할 수 있습니다. 핵심 단어 병합 정렬 병합 정렬 지난 단원에서 다양한 정렬 방법에 대해서 배웠습니다. 하지만 우리가 아직 공부하지 않은 대표적인 정렬 방법이 하나 더 있습니다. 전화번호부의 분할 정복 탐색처럼 데이터를 반으로 나누어간다는 것과 공통점이 있는 방법인 병합 정렬(합병 정렬)이 있습니다. 병합 정렬은 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방식입니다. 그리고 이 과정은 재귀적으로 구현되기 때문에 나중에..

들어가기 전에 알고리즘을 구현하기 위해 코드를 작성하다 보면 동일한 작업을 반복해야 할 때가 있습니다. 이러한 작업을 함수로 구현하면 코드를 보다 효율적으로 만들 수 있음을 배웠습니다. 하지만 함수 내에서도 동일한 작업이 반복되는 경우는 어떨까요? 이번 강의에서는 함수를 함수 내에서 재사용하는 방법, 즉 재귀적으로 호출하는 방법을 배워 보겠습니다. 학습 목표 함수를 재귀적으로 사용하는 코드를 작성할 수 있습니다. 핵심 단어 재귀 재귀 함수를 사용할 때 어디에서 호출했나요? main 안에서 프로그램을 작성하면서 필요한 순간에 호출하여 사용합니다. 그런데 main 역시 함수라는걸 기억하시나요? main이라는 함수 안에서 또 다른 함수를 사용한 것입니다. 이 사실을 알게 되었을 때, 우리는 함수가 본인 스스로..

들어가기 전에 지금까지의 강의에서 정렬 알고리즘이나 검색 알고리즘을 학습하면서 그 실행 시간의 상한과 하한도 함께 배워 보았습니다. 이번 강의에서는 각 알고리즘들의 실행 시간을 비교해보고, 그 시간을 좀 더 단축시키는 방법이 있을지 알아보겠습니다. 학습 목표 여러 정렬 알고리즘과 검색 알고리즘의 실행 시간을 Big O와 Big Ω로 정의할 수 있습니다. 핵심 단어 Big O Big Ω 여태까지 배운 선형 검색, 이진 검색, 버블 정렬, 선택 정렬의 실행시간은 각각 어떻게 되는지 정리해 보겠습니다. 실행시간의 상한 O(n^2): 선택 정렬, 버블 정렬 O(n log n) O(n): 선형 검색 O(log n): 이진 검색 O(1) 실행시간의 하한 Ω(n^2): 선택 정렬, 버블 정렬 Ω(n log n) Ω(..

들어가기 전에 앞서 배운 버블 정렬은 직관적이지만 O(n^2)의 시간이 소요됩니다. 이 방법이 최선일까요? 이번에는 다른 정렬 알고리즘인 선택 정렬을 배워보겠습니다. 학습 목표 선택 정렬의 원리와 실행 시간을 설명하고 구현할 수 있습니다. 핵심 단어 선택 정렬 선택 정렬 보통 배열이 정렬되어 있으면 정렬되지 않은 배열보다 더 쉽게 탐색할 수 있습니다. 정렬을 위한 알고리즘 중 선택정렬을 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬입니다. 선택 정렬은 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가합니다. 다음과 같은 정렬되지 않은 숫자들을 오름차순 정렬해보도록 하겠습니다. 6 3 8 5 2 7 4 1 먼저 ..

들어가기 전에 어떤 배열이 주어졌을 때, 그 배열이 미리 정렬되어 있다면 훨씬 빠른 속도로 검색이 가능합니다. 정렬하기 위한 방법은 여러가지가 있고, 각각 실행 시간도 다릅니다. 이번 강의에서는 그 중 하나인 버블 정렬을 배워 보겠습니다. 학습 목표 버블 정렬의 원리와 실행 시간을 설명하고 구현할 수 있습니다. 핵심 단어 버블 정렬 버블 정렬 정렬되지 않은 리스트를 탐색하는 것 보다 정렬한 뒤 탐색하는 것이 더 효율적입니다. 정렬 알고리즘 중 하나는 버블 정렬입니다. 버블 정렬은 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법을 말합니다. 버블 정렬은 단 두 개의 요소만 정렬해주는 좁은 범위의 정렬에 집중합니다. 이 접근법은 간단하지만 단 하나의 요소를 정렬하기 위해 너무 많..

들어가기 전에 주어진 배열에서 선형 검색으로 값을 찾는 방법을 알아봅니다. 전화번호부와 같이 배열이 여러개가 있는 경우, 한 배열의 특정 속성값을 찾고 동일한 위치의 다른 배열의 속성값을 출력하는 방법도 배워봅니다. 또, 이를 더 간단하고 확장성있게 구현하는 방법을 배워봅니다. 학습 목표 주어진 배열 또는 구조체에서 선형 검색을 할 수 있습니다. 핵심 단어 선형 검색 구조체 선형 검색 찾고자 하는 자료를 검색하는 데 사용되는 다양한 알고리즘이 있습니다. 그 중 하나가 선형 검색입니다. 선형검색은 원하는 원소가 발견될 때까지 처음부터 마지막 자료까지 차례대로 검색합니다. 이렇게 하여 선형 검색은 찾고자 하는 자료를 찾을 때까지 모든 자료를 확인해야 합니다. 효율성 그리고 비효율성 선형 검색 알고리즘은 정확..

들어가기 전에 우리가 프로그램을 작성한 후에 실행하면 작업이 완료될때까지 어느정도 시간이 소요됩니다. 아주 간단한 프로그램인 경우에는 실행 시간을 걱정할 필요가 없지만, 처리하는 데이터가 많아지고 처리하는 작업이 복잡해질수록 실행 시간은 매우 중요해집니다. 특정 알고리즘을 작성하였을 때 그 실행 시간을 표기하는 방법을 배워보겠습니다. 학습 목표 알고리즘의 실행 시간의 상한과 하한을 표기할 수 있습니다. 핵심 단어 Big O Big Ω 1주차에 아래 그림과 같이 알고리즘을 실행하는데 걸리는 시간을 표현해 봤었습니다. 위와 같은 그림을 공식으로 표기한 것이 Big O 표기법입니다. 여기서 O는 “on the order of”의 약자로, 쉽게 생각하면 “~만큼의 정도로 커지는” 것이라고 볼 수 있습니다. O(..

들어가기 전에 지난시간까지 우리는 메모리의 구조, 자료형, 배열과 같은 기본적인 개념을 익혔습니다. 이번 강의부터는 여태까지 배운 내용을 활용하여 검색이나 정렬과 같은 문제를 푸는 알고리즘을 배워 보겠습니다. 먼저 주어진 배열 속에서 특정 값을 찾는 방법부터 시작해 보겠습니다. 학습 목표 주어진 배열 속에서 특정 값을 찾는 방법을 설명할 수 있습니다. 핵심 단어 선형 검색 이진 검색 배열은 한 자료형의 여러 값들이 메모리상에 모여 있는 구조입니다. 컴퓨터는 이 값들에 접근할 때 배열의 인덱스 하나하나를 접근합니다. 만약 어떤 값이 배열 안에 속해 있는지를 찾아 보기 위해서는 배열이 정렬되어 있는지 여부에 따라 아래와 같은 방법을 사용할 수 있습니다. 선형 검색 배열의 인덱스를 처음부터 끝까지 하나씩 증가..