알고리즘 : Ch.01 First Step

정지인·2025년 10월 13일
알고리즘

학교에서 진행하는 알고리즘 수업을 정리해보려고 한다.

1.1 최대 숫자 찾기

  • 카드의 숫자를 하나씩 비교하면서 본 숫자들 중에서 가장 큰 숫자를 기억해가며 찾기
  • 마지막 카드의 숫자를 본 후에 , 머릿속에 기억된 가장 큰 숫자가 적힌 카드를 바닥에서 집어든다.
  • O(n)
  • 이런 방법을 순차 탐색 ( Sequential Search ) 라고 한다.
    • 즉, 카드를 한 장씩 차례대로 ( 주어진 대로) 읽어 가며 찾는 방법

코드 구현

#include <stdio.h>

void main() {
	int arr[10] = { 1,2,3,4,15,6,7,8,9,11 };
	int tmp = 0;
	for(int i = 0; i < 10; i++) {
		if (arr[i] > tmp ) {
			tmp = arr[i];
		}
	}
	printf("Max is %d\n", tmp);
}

1.2 임의의 숫자 찾기 ( Find Random Number )

  • 배열에서 임의의 숫자를 찾는 알고리즘
  • 최대 숫자 찾기처럼 정한 숫자를 기억하고 바닥에 펼처진 카드를 차례대로 한 장씩 읽으며 숫자와 비교

코드 구현 ( 정한 숫자는 9 )

#include <stdio.h>

void main() {
    int arr[10] = { 1,2,3,4,15,6,7,8,9,11 };
    int num;
    int found = 0;

    printf("찾고 싶은 숫자를 입력하세요: ");
    scanf_s("%d", &num);

    for (int i = 0; i < 10; i++) {
        if (arr[i] == num) {
            printf("배열에 %d가 있습니다. 그 숫자의 위치는 배열의 %d번째에 있습니다.\n", num, i + 1);
            found = 1;
            break;
        }
    }

    if (!found) {
        printf("%d는 배열에 없습니다.\n", num);
    }
}
  • 문제
    • 10장의 카드가 만약 오름 차순으로 미리 정렬되어 있다면 ?
    • 9를 순차탐색으로 찾으면 위로부터 7장의 카드를 읽은 후에나 9를 찾는다. ← 효율 down

그러면 순차 탐색보다 효율적인 방법은 ?

  • 정렬되어 있다는 정보를 어떻게 활용할 수 있을까.
    • 중간에 있는 5와 9를 먼저 비교

이진 탐색 ( Binary Search ) , K 찾기

  • 오름차순으로 정렬
  • 중간 숫자와 K 비교
  • 같으면 탐색 성공
  • K가 작으면 앞부분 반에서 같은 방법으로 K 찾고 , K가 크면 뒷부분 반에서 같은 방법으로 찾는다 ← 재귀탐색

1.3 동전 거스름 돈

  • 물건을 사고 거스름돈을 동전으로 받는다
    • 가장 적은 수의 동전을 받을라면?
    • 어떻게 해야지 가장 적은 수의 동전을 찾을까?
  • 가장 큰 액면의 동전부터 차례로 남은 거스름돈 액수를 넘지 않는 한도에서 ( 욕심 내어) 선택한다
  • 그리디 (Greedy) 알고리즘

코드 구현

#include <stdio.h>

void main() {
    int coin = 0;
    int rest = 730;

    while (rest > 0) {
        if (rest >= 500) {
            rest -= 500;
            coin++;
        }
        else if (rest >= 100) {
            rest -= 100;
            coin++;
        }
        else if (rest >= 50) {
            rest -= 50;
            coin++;
        }
        else if (rest >= 10) {
            rest -= 10;
            coin++;
        }
        else {
            break;
        }
    }
    printf("필요한 동전의 개수: %d\n", coin);
}
  • 주의할 점 : 그리디 알고리즘은 항상 최적의 해를 가져다주진 않는다.

1.4 한붓그리기 ( Eulerian Path )

  • 종이에서 연필을 떼지 않고 그리는 한붓그리기 문제
  • 어느 한 점에서 출발하여 모든 간선을 한 번만 지나서 출발점으로 돌아오되 , 궤적을 그리는 동안 연필이 종이에서 떨어지면 안됨. ( 단, 점은 여러번 방문 가능 )
  • 현재 점으로 돌아오는 싸이클이 있으면 진행한다.
  • 단 , 외길이면 , 즉 , 인접한 점이 하나 밖에 없으면 사이클 체크 없이 인접한 점으로 진행한다.

코드 구현

#include <stdio.h>
#define MAX 10

int graph[MAX][MAX];
int degree[MAX];
int n;

void initGraph() {
    n = 4;
    graph[1][2] = graph[2][1] = 1;
    graph[2][3] = graph[3][2] = 1;
    graph[3][4] = graph[4][3] = 1;
    graph[4][1] = graph[1][4] = 1;
}

void calcDegree() {
    for (int i = 1; i <= n; i++) {
        degree[i] = 0;
        for (int j = 1; j <= n; j++) {
            if (graph[i][j] == 1)
                degree[i]++;
        }
    }
}

void checkEuler() {
    int oddCount = 0;
    for (int i = 1; i <= n; i++) {
        if (degree[i] % 2 == 1)
            oddCount++;
    }

    if (oddCount == 0)
        printf("Eulerian Circuit 가능\n");
    else if (oddCount == 2)
        printf("Eulerian Path 가능\n");
    else
        printf("한붓그리기 불가능\n");
}

void dfs(int u) {
    for (int v = 1; v <= n; v++) {
        if (graph[u][v]) {
            graph[u][v] = graph[v][u] = 0;
            dfs(v);
        }
    }
    printf("%d ", u);
}

void main() {
    initGraph();
    calcDegree();
    checkEuler();
    printf("한붓그리기 경로 (역순): ");
    dfs(1);
    printf("\n");
}

1.5 미로 찾기

  • 오른손 법칙
    • 현 위치에서 한 방향을 선택하고 , 오른손을 벽에 댄다.
    • 그리고 출구가 나올 때 까지 계속 오른손을 벽에서 떼지 않고 계속 걸어간다.

코드 구현

#include <stdio.h>

#define N 7

int maze[N][N] = {
    {1,1,1,1,1,1,1},
    {1,0,0,0,1,0,1},
    {1,0,1,0,1,0,1},
    {1,0,1,0,0,0,1},
    {1,0,1,1,1,0,1},
    {1,0,0,0,0,0,1},
    {1,1,1,1,1,1,1}
};

// 북, 동, 남, 서
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

// 오른손 법칙 미로 탐색
void rightHandMaze(int startX, int startY, int endX, int endY) {
    int x = startX, y = startY;
    int dir = 1; // 시작 시 오른쪽(동쪽)을 바라본다고 가정
    int step = 0;

    while (1) {
        printf("(%d, %d)\n", x, y);
        if (x == endX && y == endY) {
            printf("출구 도착! 총 %d걸음\n", step);
            break;
        }

        // 오른쪽 방향
        int rightDir = (dir + 1) % 4;
        int rightX = x + dx[rightDir];
        int rightY = y + dy[rightDir];

        if (maze[rightX][rightY] == 0) {
            // 오른쪽이 길이면 오른쪽으로 회전 후 전진
            dir = rightDir;
            x += dx[dir];
            y += dy[dir];
        }
        else if (maze[x + dx[dir]][y + dy[dir]] == 0) {
            // 정면이 길이면 그대로 전진
            x += dx[dir];
            y += dy[dir];
        }
        else {
            // 둘 다 벽이면 왼쪽으로 회전
            dir = (dir + 3) % 4;
        }

        step++;
        if (step > 1000) { // 무한루프 방지
            printf("출구를 찾지 못했습니다.\n");
            break;
        }
    }
}

int main() {
    rightHandMaze(1, 1, 5, 5);
    return 0;
}

1.6 가짜 동전 찾기

  • 여러 개의 동전 속에 1개의 가짜 동전이 있음
  • 가짜 동전의 무게는 정상적인 동전보다 약간 가벼움
  • 최소의 양팔 저울을 사용하는 횟수로 가짜 동전을 찾아내기
  1. 동전 1개를 저울 왼편에 올리고 , 나머지 동전을 하나씩 비교
    • 1 ~ (n-1)회
    • 운이 좋으면 1번만에
    • 최악은 가장 마지막에
    • 총 동전 수가 n이라면 n-1번 저울 재야 함.
  2. 동전을 2개씩 짝을 지어 , n/2 짝을 각 각 저울에 달아서 가짜 동전을 찾아내기
    • 1 ~ n/2 회
    • 최악의 경우의 수가 n/2로 감소
  3. 동전 더미를 반으로 나누어 저울 양편에 놓아서 찾기
    • 동전 더미를 반으로 나누어 저울에 달고, 가벼운 쪽의 더미를 계속 반으로 나누어 저울에 단다.
    • 분하뢴 더미의 동전 수가 1개씩이면 마지막으로 저울을 달아 가벼운 쪽의 동전이 가짜
    • 이 알고리즘은 운이 좋을 때가 없다. → 왜냐하면 항상 마지막에 가짜 동전을 찾기 때문이다.
    • 1024개가 있을 때 몇 번 저울에 달아야할까 ? → 10번
    • O(log2n)

1.7 독이 든 술단지

  • 많은 술단지들 중에 독이 든 술단지를 찾아야
  • 가능한 조사하는 신하를 줄이고 싶음
  • 독을 먹으면 일주일 뒤에 죽음
  • 적은 수의 술단지에 대해서 생각해보고 술단지 수를 늘려가며 일반적인 규칙을 찾는게 핵심
  • 만약 술단지가 2개라면
    • 1명의 신하가 한 술단지를 먹고 죽으면 그 술단지에 독이, 죽지 않는다면 다른 술단지에 독이 있다는 것
  • 4개라면 ?
    • 아까와 같은 방법으로 한다면 3명의 신하가 필요하다.
    • 여기서 신하를 3명에서 2명으로 줄일 수 있는 방법은 없을까 ?
    • 문제의 핵심은 신하가 “ 하나의 술단지만 먹으라는 조건은 없었다”
    • 4개의 술단지 중 2개는 A와 B 신하 한명씩 마시고 , 하나는 둘 다 마시게 한다면?
      • 만약 A가 죽는다면 → A가 먹은 술단지에
      • B가 죽는다면 → B가 먹은 술단지에
      • A와 B 모두 죽는다면 → 같이 마신 술단지에
      • A와 B 모두 살았다면 → 먹지 않은 남은 술단지에.
  • 이러한 원리로 문제를 풀어가면 된다.

코드 구현

#include <stdio.h>

int main(void) {
    int N;
    printf("술단지 개수 N을 입력하세요: ");
    if (scanf_s("%d", &N) != 1 || N <= 0) {
        printf("유효한 양의 정수를 입력하세요.\n");
        return 0;
    }

    // 최소 신하 수 k = ceil(log2(N))을 반복문으로 계산
    int k = 0;
    int cap = 1;                 // 2^k
    while (cap < N) { cap <<= 1; k++; }

    printf("\n[요약]\n");
    printf("- 술단지 개수 N = %d\n", N);
    printf("- 최소 신하 수 k = %d (2^%d = %d >= %d)\n", k, k, cap, N);
    if (k == 0) {
        // N == 1인 경우: 신하가 필요 없음
        printf("- 술단지가 1개뿐이므로 신하가 필요 없습니다. 그 1개가 독일 수밖에 없습니다.\n");
        return 0;
    }

    // 신하별 할당표 출력
    // 신하 s(0=LSB)는 (b-1)의 s번째 비트가 1인 배럴을 마신다.
    printf("\n[신하별 할당표]\n");
    for (int s = 0; s < k; s++) {
        printf("신하 %d (비트 %d): ", s, s);
        int first = 1;
        for (int b = 1; b <= N; b++) {
            if (((b - 1) >> s) & 1) {
                if (!first) printf(", ");
                printf("%d", b);
                first = 0;
            }
        }
        if (first) printf("(해당 없음)");
        printf("\n");
    }
    return 0;
}

요약

  • 순차 탐색 ( Sequential Search ) : 주어진 순서에 따라 차례로 탐색

  • 이진 탐색 ( Binary Search ) : 정렬된 데이터에 대해서 중간에 있는 데이터를 비교하여 그 결과에 따라 같으면 탐색을 마치고 , 다르면 작은 쪽 또는 큰 쪽을 같은 방식으로 탐색

  • 동전 거스름돈 문제에서 항상 욕심 내어 가장 큰 동전을 선택 → 그리디 알고리즘

  • 한붓그리기 문제는 오일러 서킷 ( Euler Circuit ) 문제와 같다. 알고리즘의 핵심은 현재 점에서 사이클이 존재하면 진행.

  • 가짜 동전 찾기에서 동전 더미를 반으로 분할하여 저울에 달고, 가짜 동전이 있는 더미를 계속해서 반으로 나누어 저울에 단다. ← 분할 정복 ( Divide And Conquer ) 알고리즘

  • 독이든 술 단지 문제는 2진수를 활용 ( Binary Tree ) 하여 해를 찾는다.

profile
정지인
멋쟁이사자 13기 백엔드
이전 포스트

Algorithm Study : 2weeks - 분할 정복 알고리즘

다음 포스트

알고리즘 : Ch.02 Get Ready

0개의 댓글