CS50-03-Algorithms

https://cs50.harvard.edu/x/2023/weeks/3/

Week 3 Algorithms - CS50x 2023

 

 

linear search

For each door from left to right
	If 50 is behind door
		Return true
Return false
//아래와 같이 의사코드(슈도코드) 작성
For i from 0 to n-1
	If 50 is behind doors [i]
		Return true
Return false

binary search [빠름. 단, 값이 정렬되어 있어야만 함] 

If no doors left
	Return false
If 50 is behind doors [middle]
	Return true
Else if 50 < doors [middle]
	Search doors [0] through doors [middle - 1]
Else if 50 > doors [middle]
	Search doors [middle + 1] through doors [n - 1]

---

 

컴퓨터가 정렬을 하는 방법

1. selection sort 

For i from 0 to n-1
    Find smallest number between numbers[i] and numbers [n-1]
    Swap smallest number with numbers[i]

가장 좌측 값과 배열에서 가장 작은 값을 바꿔주면서 하나씩 맞춰감.

(n-1) + (n-2) + (n-3) ....... + 1

n(n-1)/2

n이 제곱이 되어버려서 데이터가 많아지면 기하급수적으로 시간이 오래걸리고, 이미 sort가 되어있어도 무조건 시간이 똑같이 걸림.

 

2. Bubble sort

두개씩만 비교하면서 진행함. 거품이 떠오르듯 마지막 값부터 차오름.

Repeat n-1 times
    For i from 0 to n-2
        If numbers [i] and numbers[i+1] out of order
            Swap them
    If no swaps
    	Quit

(n-1)(n-1)

최악의 경우 n이 제곱이 되어버림.

그라나 이미 sort가 되어있으면 n번.

https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html

Comparison Sorting Visualization

 

---

블럭쌓기(iteration 반복)

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

void draw(int n);

int main(void)
{
    // Get height of pyramid
    int height = get_int("Height: ");

    // Draw pyramid
    draw(height);
}

void draw(int n)
{
    // Draw pyramid of height n
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < i + 1; j++)
        {
            printf("#");
        }
        printf("\n");
    }
}

 

블럭쌓기 (recursion 재귀)

// Draws a pyramid using recursion

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

void draw(int n);

int main(void)
{
    // Get height of pyramid
    int height = get_int("Height: ");

    // Draw pyramid
    draw(height);
}

void draw(int n)
{
    // If nothing to draw
    if (n <= 0)
    {
        return;
    }

    // Draw pyramid of height n - 1
    draw(n - 1);

    // Draw one more row of width n
    for (int i = 0; i < n; i++)
    {
        printf("#");
    }
    printf("\n");
}

 

 

---

 3.merge sort

 

If only one number
    Quit
Else
    Sort left half of number
    Sort right half of number
    Merge sorted halves

n log n 번 실행.

 

https://www.youtube.com/watch?v=ZZuD6iUe3Pc