여러 정렬 알고리즘과 검색 알고리즘의 실행 시간을 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) Ω(n) Ω(log n) Ω(1): 선형 검색, 이진 검색 여기서 버블 정렬을 좀 더 잘 할 수 있는 방법을 알아보겠습니다. 만약 정렬이 모두 되어 있는 숫자 리스트가 주어진다면 어떨까요? 원래 의사 코드는 아래와 같습니다. Repeat n–1 times For i from..

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

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

주어진 배열 또는 구조체에서 선형 검색을 할 수 있습니다. 선형 검색 구조체 선형 검색 찾고자 하는 자료를 검색하는 데 사용되는 다양한 알고리즘이 있습니다. 그 중 하나가 선형 검색입니다. 선형검색은 원하는 원소가 발견될 때까지 처음부터 마지막 자료까지 차례대로 검색합니다. 이렇게 하여 선형 검색은 찾고자 하는 자료를 찾을 때까지 모든 자료를 확인해야 합니다. 효율성 그리고 비효율성 선형 검색 알고리즘은 정확하지만 아주 효율적이지 못한 방법입니다. 리스트의 길이가 n이라고 했을 때, 최악의 경우 리스트의 모든 원소를 확인해야 하므로 n번만큼 실행됩니다. 여기서 최악의 상황은 찾고자 하는 자료가 맨 마지막에 있거나 리스트 안에 없는 경우를 말합니다. 만약 100만 개의 원소가 있는 리스트라고 가정해본다면 ..

알고리즘의 실행 시간의 상한과 하한을 표기할 수 있습니다. Big O Big Ω 아래의 그림은 알고리즘을 풀때 찾는 시간 복잡도를 나타낸다. 위와 같은 그림을 공식으로 표기한 것이 Big O 표기법입니다. 여기서 O는 “on the order of”의 약자로, 쉽게 생각하면 “~만큼의 정도로 커지는” 것이라고 볼 수 있습니다. O(n) 은 n만큼 커지는 것이므로 n이 늘어날수록 선형적으로 증가하게 됩니다. O(n/2)도 결국 n이 매우 커지면 1/2은 큰 의미가 없어지므로 O(n)이라고 볼 수 있습니다. 주로 아래 목록과 같은 Big O 표기가 실행 시간을 나타내기 위해 많이 사용됩니다. O(n^2) O(n log n) O(n) - 선형 검색 O(log n) - 이진 검색 O(1) Big O가 알고리즘 ..

선형 검색 이진 검색 배열은 한 자료형의 여러 값들이 메모리상에 모여 있는 구조입니다. 컴퓨터는 이 값들에 접근할 때 배열의 인덱스 하나하나를 접근합니다. 만약 어떤 값이 배열 안에 속해 있는지를 찾아 보기 위해서는 배열이 정렬되어 있는지 여부에 따라 아래와 같은 방법을 사용할 수 있습니다. 선형 검색 배열의 인덱스를 처음부터 끝까지 하나씩 증가시키면서 방문하여 그 값이 속하는지를 검사합니다. 아래 의사코드와 같이 나타낼 수 있습니다. For i from 0 to n–1 If i'th element is 50 Return true Return false 위의 의사코드에 대한 설명은 50이 리스트에 있는지 없는지 하나씩 순서대로 찾는 것이다. 배열이 정렬되어 있지 않을 때 유용하다. 일반적인 완전탐색이다...

스택, 큐, 딕셔너리의 원리와 구조를 설명할 수 있습니다. 스택 큐 딕셔너리 우리가 여태껏 배운 배열, 연결 리스트, 해시 테이블, 트라이 외에도 많은 자료 구조들이 있습니다. 또는 위의 자료 구조를 기반으로 해서 문제를 해결하는데 적합한 새로운 자료 구조를 만들 수도 있습니다. 아래와 같이 세 가지의 대표적인 자료 구조를 간단하게 알아보겠습니다. 큐 큐는 메모리 구조에서 살펴봤듯이 값이 아래로 쌓이는 구조입니다. 값을 넣고 뺄 때 ‘선입 선출’ 또는 ‘FIFO’라는 방식을 따르게 됩니다. 가장 먼저 들어온 값이 가장 먼저 나가는 것이죠. 은행에서 줄을 설 때 가장 먼저 줄을 선 사람이 가장 먼저 업무를 처리하게 되는 것과 동일합니다. 배열이나 연결 리스트를 통해 구현 가능합니다. 스택 반면 스택은 역시..

문자열의 길이가 일정한 경우 이 문자열들을 저장하고 관리하는데 최적의 자료 구조는 무엇일까요? 연결 리스트, 트리, 또는 해시 테이블이 최선의 방안이 될 수 있을까요? 이번 강의에서는 ‘트라이’라는 자료구조에 대해 알아보겠습니다. 트라이의 원리와 구조를 설명할 수 있습니다. 트라이 ‘트라이’는 기본적으로 ‘트리’ 형태의 자료 구조입니다. 트라이는 retrieval 의 줄임 말이다. 특이한 점은 각 노드가 ‘배열’로 이루어져있다는 것입니다. 예를 들어 영어 알파벳으로 이루어진 문자열 값을 저장한다고 한다면 이 노드는 a부터 z까지의 값을 가지는 배열이 됩니다. 그리고 배열의 각 요소, 즉 알파벳은 다음 층의 노드(a-z 배열)를 가리킵니다. 아래 그림과 같이 Hermione, Harry, Hagrid 세 ..