RuDas의 무능월드

하노이의 탑 알고리즘 예제에서 단골 문제이다. 그만큼 머리를 많이써야하는 알고리즘 중 하나이다. 하노이의 탑 문제를 해결하는 프로그램을 작성할 때 알고리즘을 짜기 위해 머리를 쥐어짤 필요는 없다. 검색창에 하노이의 탑이라고 검색하면 기본적인 규칙과 풀이순서가 제공된다. 문제 다음 규칙을 지키며 막대A에 쌓여있는 원판 b개를 막대C로 옮기는 것이다. 1. 한 번에 하나의 원판만 이동할 수 있다. 2. 맨 위에 있는 원판만 이동할 수 있다. 3. 크기가 작은 원판 위 에 큰 원판이 쌓일 수 없다. 4. 중간의 막대를 임시적으로 이용할 수 있으나 앞의 조건들을 지켜야한다. 다음 사진은 이해를 돕기위한 원판이 3개일 때의 풀이 과정이다. 위 사진을 분석하여 알고리즘을 도출할 수있다. 막대A에서 C로 모두 옮기기..

순환(recursion)이란 알고리즘이나 함수가 자기 자신을 다시 호출하여 문제를 해결하는 기법이다. 문제 정의 자체가 순환적으로 되어 있는 경우에 적합하다. 예) 팩토리얼, 피보나치 수열, 하노이의 탑, 이진탐색 등 반복이란 for문, while문등 흔히 쓰는 반복문을 통한 알고리즘이다. 순환에 비해 수행속도가 빠르지만 순환적인 문제는 알고리즘이 매우 복잡해질 수 있다. 수행속도가 빠르다고 문제해결 속도가 빠른 것은 아니다. 순환으로 10번만에 할 계산은 반복으론 10000번을 해야할 수도 있다. 예제1 팩토리얼 순환 int factorial(int n) { if( n 0; k--) v = v*k; return(v); } 에제2 거듭제곱 순환 double power(double x, int n) { i..

앞으로 자료구조에 대해서 포스팅할 것이다. 그럼 먼저 자료구조란 무엇인가에 대해서 얘기를 해야 할 것이다. 자료구조 우리가 프로그램을 만들 때 처리해야할 자료가 있을 수 있다. 예를 들면 음악프로그램에서의 재생목록이라던지 게임에 접속할 때 보이는 입장 대기열이라던지 하는 것 들이 있다. 단순히 이미 저장되 있는 회원목록이라던가 하는 것들 뿐만 아니라 모든 종류의 '자료'에 대해서 얘기하는 것이다. 우리가 앞으로 다룰 것은 그런 자료들을 어떻게 다룰것인가를 얘기하는 것이다. 스택, 큐, 리스트, 트리 등에 대해 알아보고 어떤 방향으로 활용되는 지에 대해서 알아보겠다.

알고리즘을 짬에 있어서의 방법론이 2가지가 있다. 순차지향 프로그래밍과 객체지향 프로그래밍이다. 프로그래밍을 하다보면 이 두가지의 차이점에 대해서 자연스럽게 이해하게 된다. 하지만 정확히 말로 설명하기가 다소 애매하다. 여기서 이해가 안되도 그냥 넘어가도 상관없다. 순차(절차)지향 프로그래밍 알고리즘의 프로세서가 일련의 절차에 의해 돌아가게 되는 프로그래밍이다. 우리가 c언어를 처음배울 때 예재로 흔히 나오던 알고리즘들이 전부 순차지향적인 프로그래밍이다. 우리가 코딩을 할 때 50줄짜리 코딩을 했다고 가정하자. 그럼 그 프로그램이 돌아가는 순서는 1번줄에서 50번줄까지 순서대로 쭈우욱 실행되게 되는 것이다. 순차지향적 프로그래밍의 가장 큰 단점은 유지보수가 어렵다는 점이다. 프로그램 전체가 한 덩어리이기..