강좌 : 부스트캠프 모두를 위한 컴퓨터과학(cs50 2019)

4. 알고리즘

• ide.cs50.io 사이트 이용

✍정렬

버블정렬

• 두개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬

선택정렬

• 배열 안의 자료 중 가장 작은수(혹은 가장 큰수)를 찾아 첫번째 위치(혹은 마지막위치)의 수와 교환해주는 방식으로 정렬

병합정렬

• 원소가 한개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬

---

✍정렬 알고리즘의 실행시간

Big-O

• O(n²) : 선택정렬, 버블정렬
• O(n log n) : 병합정렬
• O(n) : 선형검색
• O(log n) : 이진검색
• O(1)

Omega

• Ω(n²) : 선택정렬
• Ω(n log n) : 병합정렬
• Ω(n) : 버블정렬 → 상황에 따라서 선택정렬보다 더 빠른 방법이 된다
• Ω(log n)
• Ω(1) : 선형검색, 이진검색

Theta

• Θ(n²) : 선택정렬
• Θ(n log n) : 병합정렬

++ Theta(Θ) : 상한선과 하한선이 같을때

---

✍재귀함수

• 함수가 본인 스스로를 호출해서 사용하는 것
• 오버플로우를 막기위해 반드시 종료조건을 만들어야한다
• 각 함수 호출은 return문에 의해 청산된다 프로그램이 재귀의 마지막에 도달했을 때(여기서는 조건문) 다시 이전의 재귀로 복귀하게 된다
• 재귀 함수 호출보다 앞에 있는 문장은 재귀 함수의 순서대로 실행
• 재귀 함수 호출보다 뒤에 있는 문장은 재귀 함수의 순서의 반대로 실행

완성

중첩루프 사용

#include<cs50.h>
#include<stdio.h>

void draw(int h);
int main(void)
{
    int height=get_int("Height: ");  // 사용자로부터 피라미드 높이를 입력받는다

    draw(height);  // 피라미드 그리기
}

void draw(int h)  // 높이를 입력받아 중첩루프를 통해 피라미드를 출력하는 draw함수 정의
{
    for(int i=1; i<=h; i++)  // 높이만큼 반복
    {
        for(int j=1; j<=i; j++)  // 높이만큼 #의 갯수가 증가하기 때문에 <= 사용
        {
            printf("#");
        }
        printf("\n");
    }
}

재귀함수 사용

#include<cs50.h>
#include<stdio.h>

void draw(int h);
int main(void)
{
    int height=get_int("Height: ");


    draw(height);
}

void draw(int h)
{
    if(h==0)  // 종료조건
    {
        return;
    }

    draw(h-1);

    for(int i=0; i<h; i++)
    {
        printf("#");
    }
    printf("\n");
}