본문 바로가기

Category

 (129)
알고리즘 | 재귀 ✔ 학습목표 함수를 재귀적으로 사용하는 코드를 작성할 수 있다. 재귀 동일한 작업을 반복할 때는 사용자 정의 함수를 사용하면 보다 효율적으로 코드를 만들 수 있다고 배웠다. 하지만 함수 내에서 동일한 작업이 반복되는 경우에는 어떻게 해야 할까. 본 글에서는 함수를 함수 내에서 재사용하는 방법, 즉 재귀적으로 호출하는 방법을 공부한다. 우리는 이제껏 int main(void){}안에서 프로그램을 작성하고 함수를 호출했다. 그런데 생각해보면 main()도 역시 함수이다. 함수 안에서 또 다른 함수를 사용해온 것이다. 이 사실을 알게 되면 함수가 본인 스스로를 호출해서 사용할 수 있는지에 대한 의문이 생긴다. 답은 할 수 있다 이다. 이를 재귀(Recursion)라고 한다. # ## ### #### #####..
알고리즘 | 병합 정렬 ✔ 학습목표 재귀를 활용한 병합 정렬을 구현할 수 있다. 병합 정렬 병합 정렬(merge sort)은 원소가 한 개가 될 때까지 계속해서 나누다가 다시 합쳐가며 정렬을 하는 방식이다. 합병 정렬이라고도 한다. 이는 분할 정복(divide and ) 알고리즘의 하나이다. 분할 정복은 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음 결과를 모아 원래의 문제를 해결하는 전략이다. 병합 정렬의 단계 병합 정렬은 세 단계로 이루어진다. 1) 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다. 2) 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할한다. 3) 결합(Combine): 정렬된 부분 배열들을 하나의 배열로..
알고리즘 | 정렬 알고리즘의 실행시간 ✔ 학습목표 1. 여러 정렬 알고리즘과 검색 알고리즘의 실행 시간을 Bio O와 Big Ω로 정의할 수 있다. 2. 조건문을 사용해 좀 더 효율적인 알고리즘을 만들 수 있다. 알고리즘의 실행 시간 이제껏 배운 선형 검색(Linear search), 이진 검색(Binary search), 버블 정렬(Bubble sort), 선택 정렬(Selection sort)의 실행시간(시간 복잡도)은 각각 어떻게 되는지 정리해보자. 상한은 다음과 같다. O(1) O(log n) O(n) O(n log n) O(n^2) Linear search o Binary search o Bubble sort o Selection sort o 하한은 다음과 같다. Ω(1) Ω(log n) Ω(n) Ω(n log n) Ω(n^2) L..
알고리즘 | 선택 정렬 ✔ 학습목표 선택 정렬의 원리와 실행 시간을 설명하고 구현할 수 있다. 선택 정렬 선태 정렬(selection sort)은 버블 정렬과 마찬가지로 정렬을 위한 알고리즘 중 하나이다. 선택 정렬에서는 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환한다. 넣을 위치는 이미 정해져있고, 어떤 수를 넣을지 선택한다는 게 특징이다. 선택 정렬은 아래와 같은 의사 코드로 나타낼 수 있다. For i from 0 to n–1 Find smallest item between i'th item and last item Swap smallest item with i'th item 이해를 위해 간단한 GIF를 보자. 선택 정렬은 버블 정렬과 달리 교환 횟수가 ..
알고리즘 | 버블 정렬 ✔ 학습목표 버블 정렬의 원리와 실행 시간을 설명하고 구현할 수 있다. 정렬 어떤 배열이 주어졌을 때, 그 배열이 미리 정렬되어 있다면 훨씬 빠른 속도로 검색이 가능하다. 정렬하기 위한 방법은 여러 가지가 있으며 각각의 효율성도 다르다. 이번 글에서는 그중 하나인 버블 정렬에 대해 공부한다. 버블 정렬 버블 정렬(bubble sort)은 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법을 말한다. 마치 거품이 터지면서(서료 비교 및 교환하면서) 위로 올라가는(옆으로 이동하는) 것처럼 말이다. 이는 접근법이 간단하다는 장점이 있지만, 자칫하면 하나의 요소를 정렬하기 위해 너무 많이 교환하는 낭비가 발생할 수도 있다. 버블 정렬은 아래와 같은 의사 코드로 나타낼 수 있다. Repe..
알고리즘 | 선형 검색 ✔ 학습목표 주어진 배열 또는 구조체에서 선형 검색(linear research)을 할 수 있다. 1) 선형 검색 자료를 검색하는 데는 다양한 알고리즘이 사용될 수 있다. 우리는 그 예시로 선형 검색과 이진 검색을 배웠다. 선형 검색은 원하는 원소가 발견될 때까지 순서대로 보는 방법이다. 본 글에서는 주어진 배열에서 선형 검색으로 값을 찾는 방법을 배운다. 효율성 선형 검색은 정확하지만 효율적이지 못한 방법이다(알고리즘 표기법에서 배운 대로 시간의 상한선이 O(n)이다). 이는 자료가 정렬되지 않거나 그 어떤 정보도 없어 하나씩 찾아야 하는 경우에만 유용하다. * 참고로 검색에 앞서 정렬이 필요한 이유가 이것이다. 정렬은 시간이 오래 걸리고 공간을 많이 차지하지만 매우 큰 데이터를 다룰 경우 시간을 단축..
알고리즘 | 알고리즘 표기법 ✔ 학습목표 알고리즘 실행 시간의 상한과 하한을 표기할 수 있다. 알고리즘의 효율성 프로그램을 작성한 후에 실행하면 작업이 완료될 때까지 어느 정도 시간이 걸린다. 처리하는 데이터가 많아지고, 작업이 복잡해질수록 이 시간은 매우 중요하다. 그래서 알고리즘의 시간 효율성과 공간 효율성(메모리)을 나태 내기 위해 표기법을 사용한다. 두 가지 효율, 즉 시간 복잡도와 공간 복잡도를 나타내는 방법으로는 빅오(Big O), 빅오메가(big Ω),빅세타(big Θ) 표기법이 있다. 강의에서는 빅오와 빅오메가를 다룬다. Big O Big O는 알고리즘 실행 시간의 상한, 쉽게 말하자면 최악의 복잡도를 나타낸다. 복잡도를 비교하자면 다음과 같다. 앞서 배운 검색 알고리즘을 생각해보면 선형검색은 O(n), 이진 검색은 ..
알고리즘 | 검색 알고리즘 ✔ 학습목표 주어진 배열 속에서 특정 값을 찾는 방법을 설명할 수 있다. 배열 본 글에서부터는 이제껏 배운 내용(메모리의 구조, 자료형, 배열 등)을 바탕으로 검색이나 정렬과 같은 문제풀이 알고리즘을 학습할 것이다. 이에 앞서 배열 속에서 특정 값을 찾는 방법을 이해해야 한다. 배열은 한 자료형의 여러 값들이 메모리상에 모여있는 구조다. 컴퓨터는 배열을 볼 때 인덱스 하나하나에 접근하게 된다. 이때 어떤 값이 배열에 들어 있는지 확인하는 데는 정렬 여부에 따라 두 가지 방법이 있다. 선형 검색 선형 검색은 순서대로 하나씩 보는 것이다. 배열의 인덱스를 처음부터 끝까지 하나씩 증가시키며 원하는 값이 들어있는지 확인한다. 50이라는 숫자를 찾는 의사 코드로 예를 들어보자. For i from 0 to n-1..

티스토리툴바