시리즈:수학인듯 과학아닌 공학같은 컴퓨터과학/알고리즘 기초

이 문서는 정말 쉽습니다.

문서의 내용이 너무 쉬워서 오늘부터 프로그래밍 할 수 있을 것 같습니다.

이 문서는 쉽게 알 수 있다 시리즈이며, 집단연구 문서입니다.

이 문서에는 독자적으로 연구한 내용이 들어갑니다. 다른 사람의 의견을 존중하면서 무례하지 않도록 작성해 주시고, 의견 충돌 시 토론 문서에서 토론해 주세요.

들어가기 전

빨간 컵에 칠성사이다가 담겨져 있고 파란 컵에 스프라이트가 담겨져있다. 여기서 파란 컵에 칠성사이다를 넣고 빨간 컵에 스프라이트를 넣을려면 어떻게 해야 될까? 해답은 간단하다. 다른 컵(여기선 노란 컵이라 하겠다.)에 빨간 컵의 칠성사이다를 노란 컵에 붓고 빨간 컵이 비게 되면 파란 컵의 스프라이트를 빨간 컵에 붓고 파란 컵이 비게 되면 노란 컵에 담았던 칠성사이다를 파란 컵에 부으면 된다. 갑자기 노란 컵이 튀어나와서 쌩뚱맞다고 생각하는 사람이 있을 수 있겠지만 다른 컵을 쓰면 안된다고는 안했다. 알고리즘은 문제를 해결하기 위한 것이지 수수께끼나 넌센스 문제가 아니다.

이 이야기가 왜 나왔냐면 프로그래밍을 할 때 아래 소스 처럼 2개의 변수 값을 서로 바꿀 경우 변수 2개 가지고 끙끙 거리지 말고 간단하게 변수 하나 더 사용해서 쉽게 해결하면 되기 때문이다. 이제 제 3의 변수를 쓰지 않고 변수 2개의 값을 맞바꾸는 알고리즘을 생각해보자.

의사코드 펼치기
1 function 바꾸기(첫번째컵, 두번째컵): 2 잠시담아둘컵 ← 첫번째컵 3 첫번째컵 ← 두번째컵 4 두번째컵 ← 잠시담아둘컵 5 end function 6 7 function 지금상황(): 8 파란컵 ← "칠성사이다" 9 빨간컵 ← "스프라이트" 10 바꾸기(파란컵, 빨간컵) 11 print 파란컵 12 print 빨간컵 13 end function

using System;

namespace 사이다컵바꾸기
{
    class Program
    {
        static void Main(string[] args)
        {
            // 빨간 컵과 파란 컵에 칠성사이다와 스프라이트가 담겨져 있다.
            string 빨간컵 = "칠성사이다";
            string 파란컵 = "스프라이트";

            Console.WriteLine("=====바꾸기 전=====");
            Console.WriteLine("빨간컵 : {0}", 빨간컵);
            Console.WriteLine("파란컵 : {0}", 파란컵);

            // 새롭게 준비한 노란 컵
            string 노란컵;

            // 스프라이트를 빨간 컵에 붓기 위해 칠성사이다를 노란컵에 붓는다.
            // 그 다음 파란 컵의 스프라이트를 빨간 컵에 붓는다.
            // 그 다음 노란 컵에 임시로 담아둔 칠성 사이다를 파란 컵에 붓는다.
            노란컵 = 빨간컵;
            빨간컵 = 파란컵;
            파란컵 = 노란컵;

            Console.WriteLine("=====바꾼 후=====");
            Console.WriteLine("빨간컵 : {0}", 빨간컵);
            Console.WriteLine("파란컵 : {0}", 파란컵);
        }
    }
}

여담으로, 위 취소선의 답은 의외로 간단하다. 정수가 저장되어 있는 a와 b가 있을 때, a와 b를 더한 다음 a에 저장한다. 그 다음 a에서 b를 뺀 값을 b에 저장한다. 그 다음 a에서 b를 뺀 값을 a에 저장하면 된다. 숫자가 아니고 객체면? 포인터 주소값을 더하고 빼면... ...

알고리즘의 시간 복잡도

어떤 알고리즘이 실행될 때에 입력과 알고리즘의 실행 시간의 함수 관계를 의미한다. 입력에 따라 알고리즘의 속도가 차이가 난다. 입력되는 숫자의 정렬 작업을 하는 알고리즘 a와 b가 있다고 할 때, 숫자의 개수 등에 따라서 a가 b보다 더 빠르게 정렬 작업을 끝마칠 수도 있고 b가 a보다 더 빠르게 정렬 작업을 끝마칠 수도 있다는 의미이다.

이러한 속도는 알고리즘의 계산 횟수에 따라 달라지는데, 이를 정확히 측정하는 것은 매우 어렵다. 그러므로 보통 이를 나타내는데는 Big-O 표기법으로 대략의 시간을 표시한다. 입력된 자료의 수가 [math]\displaystyle{ n }[/math]일 때 계산 횟수가 [math]\displaystyle{ 3n+4 }[/math]이면 [math]\displaystyle{ O(n) }[/math], [math]\displaystyle{ 2n^3+n^2 }[/math]면 [math]\displaystyle{ O(n^3) }[/math]등으로 나타내는 방식.

너비 우선 탐색

추가바람