[CS] TIL 11. 선형 검색, 버블 정렬
- 주어진 배열 또는 구조체에서 선형 검색을 할 수 있어야 한다.
- 버블 정렬의 원리와 실행 시간을 설명하고 구현할 수 있어야 한다.
boostcourse의 모두를 위한 컴퓨터 과학 (CS50 2019) 강의를 듣고 정리한 필기입니다. 😀
1. 선형 검색
오늘은 저번 시간에 배웠던 선형검색에 대해서 좀 더 자세히 배우고자 한다.
1.1 선형검색이란. (전화번호를 찾는 프로그램)
찾고자 하는 자료를 검색하는 데 사용되는 다양한 알고리즘이 있고, 그중 하나가 선형 검색이다. 선형검색은 원하는 원소가 발견될 때까지 처음부터 마지막 자료까지 차례대로 검색하는 것이다. 이렇게 하여 선형 검색은 찾고자 하는 자료를 찾을 때까지 모든 자료를 확인해야 한다. 우리는 저번 시간에 숫자 50을 알고리즘을 통해 찾고자 했다.
#include <cs50.h>
#include <stdio.h>
int main(void)
{
int numbers[6] = { 4, 8, 16, 23, 42};
// 어떤 값을 어떤 인덱스에 할당할지를 안다면, 이런식으로 정적으로 초기화 할 수 있다.
// numbers[0] = 4 ... 이런 식으로 할당하는 것과 완전히 같다.
for (int i = 0; i <6; i++)
{
if (numbers[i] == 50)
{
printf("Found\n");
}
}
printf("Not found\n");
}
위의 코드대로 저장하고 실행하면 Not fount라는 말이 뜰 것이다. 왜냐하면 우리가 저장한 numbers 배열에는 50이 존재하지 않기 때문이다.
자 이제 우리는 [CS]TIL2.컴퓨팅사고(2)에서 언급되었던 전화부에서 이름을 찾는 문제 유형에 접근할 것이다. EMMA를 찾아야 한다.
#include <cs50.h>
#include <stdio.h>
#include <string.h>
int main(void)
{
string names[4] = {"EMMA", "RODRIGO", "BRIAN", "DAVID"};
for (int i = 0; i < 4; i++)
{
if (strcmp(names[i], "EMMA") == 0)
// 문자열은 숫자형과 달리 strcmp라는 함수를 사용한다.
// 이유는 문자열 자체가 배열로, 여러개의 문자로 구성되었기 때문이다.
// strcmp는 두 문자열이 같다면 0을 반환한다.
// 양수를 반환하면 첫 번째 문자열이 알파벳 기준으로 큰 경우이고, 음수면 반대의 경우이다.
{
printf("Found %s\n");
}
}
printf("Not found\n");
}
위 프로그램을 실행하면 Found와 Not found, 두 경우의 결괏값이 나온다. 분명 names라는 배열에 EMMA가 존재함에도 그녀가 있으면서 또, 없다는 결괏값을 도출한다. 왜일까? 이유는 printf("Not found\n");가 마지막에 무조건 출력되기 때문이다.
#include <cs50.h>
#include <stdio.h>
#include <string.h>
int main(void)
{
string names[4] = {"EMMA", "RODRIGO", "BRIAN", "DAVID"};
for (int i = 0; i < 4; i++)
{
if (strcmp(names[i], "EMMA") == 0)
// 문자열은 숫자형과 달리 strcmp라는 함수를 사용한다.
// 이유는 문자열 자체가 배열로, 여러개의 문자로 구성되었기 때문이다.
// strcmp는 두 문자열이 같다면 0을 반환한다.
// 양수를 반환하면 첫 번째 문자열이 알파벳 기준으로 큰 경우이고, 음수면 반대의 경우이다.
{
printf("Found %s\n");
return 0;
}
}
printf("Not found\n");
return 1;
}
해결방법은 다소 간단하다. 리턴값을 지정해주면 된다. 위의 코드에서는 성공은 0, 실패는 1이다. 숫자 자체에는 큰 의미가 없지만, 관습이라고 생각하자. 이렇게 고치고 프로그램을 실행하면, Found라는 값이 도출된다.
자 이제 numbers에서 배운 것과 names를 합쳐서 전화부 프로그램을 만들어보자. 이름이 아닌 찾는 EMMA의 전화번호를 출력하는 프로그램을 만들 것이다.
#include <cs50.h>
#include <stdio.h>
#include <string.h>
int main(void)
{
string names[4] = {"EMMA", "RODRIGO", "BRIAN", "DAVID"};
string numbers[4] = {"617–555–0100", "617–555–0101", "617–555–0102", "617–555–0103"};
//이 때, 전화번호를 문자열로 하는 이유는 '-' 같은 기호가 숫자가 아니라 문자열이기 때문이다.
for (int i = 0; i < 4; i++)
{
if (strcmp(names[i], "EMMA") == 0)
{
printf("Found %s\n", numbers[i]);
return 0;
}
}
printf("Not found\n");
return 1;
}
이제 제대로 실행되는 프로그램을 만들었지만 몇 가지 문제가 있다. 효율적이기 못하다는 것과 사실상 컴퓨터는 names와 numbers가 관계가 있다는 것을 모른다는 것이다. 여기서 names와 numbers가 관계란, names[1]의 번호는 numbers[1]이라는 것을 말한다. 막상 작성할 때는 두 배열의 관계를 알 수 있더라도, 시간이 지나면 컴퓨터뿐만 아니라, 우리도 names와 numbers가 관계가 있다는 것을 모르게 될 것이다.
이것들을 해결하기 위해 우리는 효율성과 비효율성에 대해서 생각해봐야 한다.
1.2 typedef와 구조체
#include <cs50.h>
#include <stdio.h>
#include <string.h>
typedef struct
{
string name;
string number;
}
person;
int main(void)
{
person people[4];
people[0].name = "EMMA";
people[0].number = "617–555–0100";
people[1].name = "RODRIGO";
people[1].number = "617–555–0101";
people[2].name = "BRIAN";
people[2].number = "617–555–0102";
people[3].name = "DAVID";
people[3].number = "617–555–0103";
// EMMA 검색
for (int i = 0; i < 4; i++)
{
if (strcmp(people[i].name, "EMMA") == 0)
{
printf("Found %s\n", people[i].number);
return 0;
}
}
printf("Not found\n");
return 1;
}
우리는 새로운 자료형으로 구조체를 정의해서 이름과 번호를 묶어주었다. 위의 코드를 보면 새로운 키워드와 그 사용법을 알 수 있다.
typedef struct
{
string name;
string number;
}
person;
위 코드에서 처음 쓰인 typedef라는 키워드는 새로운 타입을 정의한다는 말이다. typedef 뒤에 쓰인 구조체(struct)는 C에 미리 정의된 키워드로써 마치 그릇처럼 여러 가지 자료형을 담을 수 있다. 중괄호가 닫히고 마지막 줄에 있는 person은 이 구조체(struct)의 이름을 person으로 정의하겠다는 말이다. 이것을 통해 컴파일러(Clang 혹은 make)에게 int, float, char, bool, string 뿐만 아니라 person이라는 자료형이 있다고 알려줄 수 있다. C언어엔 원래 없었지만 typedef struct를 사용해 만든 것이다. 이 person에는 name과 number이라는 두 가지 정보가 들어가 있다.
int main(void)
{
person people[4];
people[0].name = "EMMA";
people[0].number = "617–555–0100";
people[1].name = "RODRIGO";
people[1].number = "617–555–0101";
people[2].name = "BRIAN";
people[2].number = "617–555–0102";
people[3].name = "DAVID";
people[3].number = "617–555–0103";
// EMMA 검색
for (int i = 0; i < 4; i++)
{
if (strcmp(people[i].name, "EMMA") == 0)
{
printf("Found %s\n", people[i].number);
return 0;
}
}
printf("Not found\n");
return 1;
}
person people[4];이라는 부분은 person이라는 자료형으로 배열을 선언했으며, 그 길이는 4, 각각의 인덱스 안에 있는 요소는 한 사람을 표한다는 것을 알 수 있다. string names[4], string numbers[4] 와 똑같은 문법이다.
그리고 그 아랫줄을 보면 people[0].name, people[0].number, people[1].name, people[1].number, … 정의된 것을 볼 수 있다. person 자료형의 배열을 선언하면 그 안에 포함된 속성값은 .(dot)으로 연결해서 접근할 수 있다. 더 불편하게 느껴질 수 있지만, 이제 모든 정보를 한 번에 묶어서 표현할 수 있다.
person 자료형의 값이 4개가 있고, 각각의 person 안에는 이름(name)과 번호(number)가 들어가 있다. 이제 컴퓨터도 알 것이다. 인덱스 1번의 name과 인덱스 1번의 번호가 서로 관계가 있다는 것을. 이것을 통해 우리가 알 수 있는 것은 이름순으로 정렬을 해도, 이름과 번호의 관계는 그대로 유지된다는 것이다.
만약 인덱스가 아니라, person a; 라는 변수가 있다면, a.name 또는 a.number 이 각각의 이름과 전화번호를 저장하는 변수가 된다. 이렇게 함으로써 더욱 확장성 있는 전화번호부 검색 프로그램을 만들 수 있다.
1.3 질문
Q1. 코드를 간소화 하기 위해서 중괄호를 사용할 수 있을까?
▶ 가능은 하지만, 코드가 더 지저분 해져서 군이 하지 않는다.
Q2. 위 프로그램은 동적인데 정적으로 만들 수 있을까?
▶ GetString과 같은 함수를 사용하면 사용자에게 전화번호의 이름을 부여받아서 동적으로 만들 수 있다.
2. 버블 정렬
선형 검색 알고리즘은 정확하지만 아주 효율적이지 못하다. 이는 리스트의 길이가 n이라고 했을 때, 최악의 경우 리스트의 모든 원소를 확인해야 한다는 점 때문이다. for 루프만 생각해도 이를 알 수 있다. 만약 EMMA가 배열의 맨 뒤에 있었으면 총 4번의 루프가 돌았을 것이다. 50을 찾던 처음의 numbers 배열도 리스트 안에 50이 없어 처음부터 끝까지 루프가 돌았을 것이다.
이렇게 선형 검색의 최악의 상황은 찾고자 하는 자료가 맨 마지막에 있거나 리스트 안에 없는 경우이다. 지금 당장이야 고작 4개의 원소지만, 만약 100만 개의 원소가 있는 리스트라고 가정해본다면 효율성이 매우 떨어진다.
반대로 최선의 상황은 찾고자 하는 값이 리스트의 첫 원소일 때이다. 하지만, 당장 어제의 포스팅에도 적혀 있듯이 프로그래머들은 최선의 경우보다 최악의 경우를 염두해야한다.
이런 점을 고려해서 프로그램을 더 개선해보고자 한다. 2차원 배열의 형태, EMMA의 번호가 첫 번째에 있다고 가정 등등이 있지만, 첫 번째는 필요한 부분이 아니며 코드가 쓸데없이 복잡해질 것이다. 두 번째의 경우에는 EMMA의 번호가 항상 첫 번째일 수는 없을 것이다.
가장 간단한 방법은 검색 전에 정렬하는 것이다. 이름을 사전 순으로 정렬하는 것이다.
정렬은 시간이 오래 걸리고 공간을 더 차지한다. 하지만 이 추가적인 과정을 진행하면 훨씬 빠른 속도로 검색이 가능하다. 정렬하기 위한 방법은 여러 가지가 있고, 각각 실행 시간도 다르다. 정렬 알고리즘 중 하나가 오늘 배울 버블정렬이다. 버블 정렬은 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법이다.
예를 들어 8개의 숫자가 임의로 나열되어있다고 하자,
7, 2, 1, 6, 3, 4, 50
우리가 해야 할 것은 버블정렬을 사용해 정렬되지 않는 숫자들을 왼쪽부터 오름차순으로 정렬하는 것이다. 7과 2를 비교해서 7이 2보다 크면 두 개의 자리가 바꾼다. 이런 식으로 자리를 바꾸다가 7보다 큰 50을 만나면 위치를 바꾸지 않고 가만히 있는다.
7, 2, 1, 6, 3, 4, 50
2, 7, 1, 6, 3, 4, 50 (교환)
2, 1, 7, 6, 3, 4, 50 (교환)
2, 1, 6, 7, 3, 4, 50 (교환)
2, 1, 6, 3, 7, 4, 50 (교환)
2, 1, 6, 3, 4, 7, 50 (교환)
2, 1, 6, 3, 4, 7, 50
이 과정을 끝까지 반복하면 최종적으로 아래와 같이 오름차순 정렬이 될 것이다.
1, 2, 3, 4, 6, 7, 50
이것이 버블정렬이다. 마치 거품이(비교 및 교환이) 터지면서 위로 올라오는 (배열의 옆으로 이동하는) 방식이기 때문에 붙여진 이름이다. (거품이 떠오르듯 7이 왼쪽에서 오른쪽으로 움직이고 6도 왼쪽에서 오른쪽으로 거품처럼 움직일 것이다. 마지막으로 갈수록 빠른 속도로 정렬된다.)
아래와 같이 의사 코드로 나타낼 수 있다.
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개의 값이 주어졌을 때 각 루프는 각각 n-1번, n-2번 반복되므로 ` (n-1)*(n-2) = n²−3n+2 ` 번의 비교 및 교환이 필요하다. 여기서 가장 크기가 큰 요소는 n² 이므로 위와 같은 코드로 작성한 버블 정렬 실행 시간의 상한은 O(n²)이라고 말할 수 있다. 정렬이 되어 있는지 여부에 관계 없이 루프를 돌며 비교를 해야 하므로 위와 같은 코드로 작성한 버블 정렬의 실행 시간의 하한도 여전히 Ω(n²)이 된니다.
