Programming world

3. 동적 계획법 (dynamic programming)


재귀적인 기법은 문제를 간단히 부분 문제로 분할할 수 있고, 부분 문제의 크기의 합을 적게 유지할 수 있는 경우에 유효하다. 그러나, 크기가 n인 문제를 단순히 분할해서 각 부분 문제의 크기가 균형이 맞지 않는 문제로 분할되었을 때에는 재귀적 알고리즘의 복잡도는 아마 지수 함수적으로 증가할 것이다. 이런 경우에는 「동적 계획법」이라는 기법을 이용하면 효율좋은 알고리즘을 설계할 수 있다.
문제를 크기가 적은 부분 문제로 분할한 뒤 부분 문제에 대한 답을 구하기 위해 같은 부분 문제를 몇 번이고 반복해서 해결할 필요가 있는 경우가 있다. 그 때에는 한번 해결한 부분 문제의 해답을 「표」에 기억해 두었다가 필요할 때에 그 표를 참조하게 하면 새로 계산하는데 걸리는 시간을 절약할 수 있게 되어 효율이 좋은 알고리즘을 얻을 수가 있다.
이와 같이 경우에 따라서는 언젠가는 해결하게 될 모든 부분 문제의 해답을 표로 해두는 것이 프로그램을 작성하기 쉬운 경우도 있다. 어떤 부분 문제가 실제로 전체의 문제 해결 과정에서 필요하게 되는지 어떤지는 생각하지 않고 일단 표를 작성하는데, 이와 같이 주어진 문제를 해결하기 위해 부분 문제에 대한 답을 표에 기입하는 기법을 동적 계획법 (dynamic programming) 이라고 한다. 동적계획법이라는 이름은 제어 이론에서 나온 것이다.

본질적으로는 동적 계획법은 모든 부분 문제에 대한 답을 계산하는데, 계산은 크기가 작은 부분 문제로부터 보다 큰 부분 문제로 답을 표에 기록하면서 나아간다. 동적 계획법의 장점은 한번 어떤 부분 문제가 해결되면 답을 기억해 둠으로써 결코 두 번 다시 계산되지 않는다는 것이다. 이 기법은 간단히 예를 보면 쉽게 이해할 수 있을 것이다.

먼저 다음과 같은 n 개의 행렬을 곱하는 문제를 생각하기로 한다. 단, 각 행렬 의 크기는 행, 열로 한다.

       

행렬을 곱하는데 어떤 알고리즘을 이용하더라도 행렬이 곱해지는 순서가 M 을 계산하는데 필요한 연산의 총수에 영향을 미친다.

연산 순서와 연산하는 횟수와의 관계를 보기 위해 다음과 같은 실제적인 행렬 곱셈을 예로 들어보기로 하자.

        

괄호속에 있는 수는 각 행렬 의 치수를 나타낸다. 일반적인 방법을 이용하면 p × q차 행렬과 q × r 차 행렬의 곱셈은 p × q × r 번의 연산을 필요로 하므로, M 을 의 순으로 계산하면 125000 번의 연산이 필요하지만 순으로 계산하면 2200 번의 연산이면 된다. 이들 연산수를 살펴보기 위해 다음과 같은 동적 계획법을 이용하면 된다.

행렬의 곱셈에 필요한 연산수를 최소화하기 위해서는 n 개의 행렬을 곱하는 순서를 모두 체크하면 되지만 이것은 막대한 시간과 노력을 필요로 한다. 그러나, 동적 계획법을 이용하면 복잡도가 O(n³) 의알고리즘을 얻을 수가 있는데, 행렬의 곱셈을 하는데 연산수가 가장 적은 방법을 찾기 위해서는 동적 계획법을 어떻게 이용하는지를 설명하기로 한다.

m_{i, j}가 m_i × M_i+1 × … × M_j 를 계산하는데 걸리는 시간 중에서 가장 적은 시간이라 하고, 이것을 식으로 나타내면 다음과 같다.

        

위의 식에서 첫 번째 항인 m_{i, k} 는 M' = M_i × M_i+1 × … × M_k 를 계산하는데 걸리는 시간 중에서 가장 적은 시간을 나타내고, 두 번째 항인 m_{k+1, j} 는 M″ = M_k+1 × M_k+2 × … × M_j 를 계산하는데 걸리는 시간 중에서 가장 적은 시간을 나타낸다. 단, M′ 는 r_i-1 × r_k 차 행렬, M″ 는 r_k × r_j 차 행렬이다. m_{i, j} 는 모든 k(i  ≤  k  ≤ j - 1) 에 대해 이들 세 항을 합한 값이 가장 적은 값이라는 것을 나타낸다.
이 동적 계획법에 의한 방법에서는 첨자의 값의 차가 적은 순으로 m_{i, j} 를 계산해 간다. 즉, 모든 i 에 대해 m_{i, i} 를 계산하는 것에서부터 시작해서 m_{i, i+1} 과 m_{i, i+2} 순으로 계산한다.

M = M₁ × M₂ × M₃ × M₄ 를 계산하는데 이 알고리즘을 적용하기로 한다. 단, r₀, r₁, r₂, r₃, r₄는 10, 20, 50, 1, 100 이고 m_{i, j} 의 값을 계산한 결과는 다음과 같다. 따라서, 곱셈을 하는데 필요한 최소의 연산수는 2200 이 된다. 

 

그림 7  7 각형과 삼각형 분할의 예

그림 8  삼각형 분할의 예

그림 7 에 7 각형과 각 정점에 대한 (x, y) 좌표를 나타내는데 거리 함수는 일반적인 유클리드 거리로 한다. 그림 7 에서 삼각형 분할의 한 예를 점선으로 나타냈지만 예를들면 그림 8과 같은 삼각형 분할이 있으므로 이것은 최소삼각형 분할이 아니다. 그림 7과 같은 분할의 코스트는 변 (1, 3), (1, 4), (1, 6), (4, 6) 의 길이의 합계
즉, 이고, 그림 8 과 같은 분할 코스트는 변 (1, 3), (1, 4), (1, 5), (1, 6) 의 길이의 합계 즉, =45.16이다.
이 삼각형 분할 문제에 동적 계획법을 적용하기 전에 삼각형 분할이 가지는 두 가지 성질을 정리해 두고, 그들 성질을 알고리즘 설계에 이용하기로 한다. 다각형에는 시계 방향으로 n 개의 정점 v₁, v₂, …, v_n 이 있다고 한다.

[성질 1]  
세 정점 이상으로 구성된 다각형을 삼각형 분할했을 때 다각형의 변과 접해 있는 두 정점은 반드시 하나 이상의 선과 접해 있다. 만일 v_i 과 v_i-1 이 모두 어떠한 선과도 접하지 않는다고 하면, 변 (v_i, v_i-1) 이 에워싸고 있는 영역에는 변(v_i-1, v_i) 과 (v_i+1, v_i+2) 외에 하나 이상의 변이 포함된다. 이렇게 되면 이 영역은 삼각형이 되지 않는다.

[성질 2]
어떤 삼각형 분할에서 (v_i, v_j) 를 선이라고 하면, (v_i, v_k) 와 (v_k, v_j) 가 모두 다각형의 변 혹은 선이 되는 v_k 가 여러 개 존재한다. 그렇지 않으면 (v_i, v_j) 가 삼각형이 아닌 영역을 에워싸고 있는 것이 된다.

다음은 앞의 두 개의 성질을 이용하여 최소삼각형 분할 문제를 해결하는 알고리즘을 설명하기로 한다.

최소삼각형 분할을 하기 위해 우선 인접하는 두 정점 v₀ 과 v₁을 선택한다. 위에 기술한 두 성질은 임의의 삼각형 분할에서 성립하므로 최소의 삼각형 분할에서도 성립한다. 따라서 (v₁, v_k) 와 (v_k, v₀) 가 모두 삼각형 분할에서의 선 혹은 변이되는 정점 v_k 가 존재한다. 이 때, 여러 개의 k 가 존재하면 어느 경우에 어느 정도 좋은 삼각형 분할을 할 수 있는지를 생각해야 하는데 n 개의 정점을 가진 다각형이라면 모두 (n - 2) 개의 선택이 가능하다.

어느 k 를 택하더라도 그로 인해 생기는 부분 문제는 많아야 두 개인데, 그들은 선택한 선의 양쪽 끝에 있는 두 정점을 잇는 원래의 다각형의 변에 의해 구성되는 두 개의 다각형에 대응한다. 예를들면 정점 v₃ 를 선택하면 그림 9에 나타내는 두 개의 부분 문제가 생긴다.

그림 9  v₃ 을 택했을 때의 부분 문제

다음은 그림 9(a), (b) 의 다각형에 대한 최소삼각형 분할을 해야 하는데, 그를 위해서는 또 인접하는 두 정점에서 나오는 선을 모두 생각해야 한다고 여겨진다. 예를들면 그림 9(b) 를 해결하기 위해서 선 (v₀, v₃) 과 같은 부분 문제의 선과 그외의 정점으로 삼각형을 만들어야 한다. 가령 v₄ 를 선택했다고 하면 삼각형 (v₀, v₃, v₄) 와 부분 문제 (v₀, v₄, v₅, v₆) 이 생기고, 이 부분 문제 중에서 원래의 다각형의 선은 하나 뿐이다. 한편, v₄ 가 아니라 v₅ 를 선택하면 부분 문제 (v₃, v₄, v₅) 와 (v₀, v₅, v₆) 이 생기는데 각 부분 문제에 대한 선은 (v₃, v₅) 와 (v₀, v₅) 뿐이다.

일반적으로 정점 v_i 에서 시작해서 시계 방향으로 s 개의 정점 v_i, v_i+1, …, v_i+s-1 로 구성되는 다각형에 대한 최소삼각형 분할을 구하는 문제를 「정점 v_i 에서 시작하는 크기가 s 인 부분 문제」라고 하고, 이후 이를 S_{i, s} 라고 표현하기로 한다. 예를들면 그림 9 (a) 는 S_{0, 4} 이고 그림 9(b) 는 S_{3, 5} 이다. S_{i, s} 를 해결하기 위해서는 다음의 세 경우를 생각할 필요가 있다.

(1) 정점 v_i+s-2 를 선택해서 선 (v_i, v_i+s-1) 및 (v_i, v_i+s-2) 와 변 (v_i+s-2, v_i+s-1) 로 삼각형을 구성하여 부분 문제 S_{i, s-1} 를 해결한다.

(2) 정점 v_i+1 을 선택해서 선 (v_i, v_i+s-1), (v_i+1, v_i+s-1) 과 변 (v_i, v_i+1) 로 삼각형을 구성하여 부분 문제 S_{i+1, s-1} 를 해결한다.

(3) 정점 v_i+k(2 ≤ k ≤ s - 3) 를 선택해서 선 (v_i, v_i+k), (v_i+k, v_i+s-1), (v_i, v_i+s-1) 로 삼각형을 구성하여 부분 문제 S_i,k+1 와 S_{i+k, s-k} 를 해결한다.

크기가 3 이하인 부분 문제를 해결하기 위해서는 아무 것도 하지 않아도 되므로, (1) ~ (3) 을 이용해서 어떤 k(1 ≤ k ≤ s - 2) 를 택해서 부분 문제 S_{i, k+1} 와 S_{i+k, s-k} 를 해결하면 되는데, 부분 문제의 분할을 그림 10 에 나타낸다.

그림 10  S_{i, s} 를 부분 문제로 분할

크기가 4 이상인 부분 문제를 해결하기 위해서는 위의 규칙을 이용해서 얻어지는 재귀적인 알고리즘을 사용하기로 하자. 이 때, 크기가 s 이상인 부분 문제를 해결하기 위한 재귀적 호출수만을 세면 모두 3^s-4 번이라는 것을 나타낼 수 있으므로, 해결해야 할 부분 문제의 수는 s 를 지수로 한 것이 된다. 문제를 분할한 후의 문제의 크기는 이 재귀적인 절차를 해결하는데 필요한 모든 스텝수와 같은데, 주어진 다각형의 정점수가 n 이므로 문제의 크기는 n 의 지수승이 된다.

그러나, 원래의 문제 이외에는 해결해야 할 부분 문제는 n(n - 4) 종류밖에 없다는 것을 알고 있기 때문에 이 해석이 어딘지 이상하다는 것은 금방 알 수 있을 것이다. 그 부분 문제라는 것은 S_{i, s}(0 ≤ i < n, 4 ≤ s(n) 이므로 재귀적인 절차에서는 같은 부분 문제를 여러 번 해결한다는 것이 분명하다. 예를들면 그림 6 ~ 7 에서 선 (v₀, v₃) 을 선택하고 그림 9(b) 의 부분 문제에서 v₄ 를 선택했다고 하면 부분 문제 S_{4, 4}를 해결해야 한다. 그러나, 처음에 변(v₀, v₄) 를 선택했을 때와 처음에 선(v₁, v₄) 를 선택해서 부분 문제 S_{4, 5} 를 해결할 때에 v₁ 과 v₄ 를 정점으로 하는 삼각형을 완성시키기 위해서 v₀ 을 선택해도 역시 같은 부분 문제 v_{4, 4} 를 해결하게 된다.

이로부터 삼각형 분할 문제를 해결할 수 있는 효율이 좋은 방법을 얻을 수가 있다. 모든 i 와 s 에 대해 S_{i, s} 를 삼각형 분할하는데 걸리는 시간 (이후, 이것을 C_{i, s} 로 표현한다) 을 계산하는 표를 만드는 것으로, 이 때 어떤 문제의 해답도 보다 적은 문제의 해답에만 의존하므로 이 표를 크기순으로 메워가면 된다. 즉, 크기 S( = 4, 5, …, n - 1) 에 대해 모든 정점 i 에 대한 문제 S_{i, s}) 의 최소값을 써넣는다. 크기 0 ≤ s < 4 인 문제도 포함해 두면 편리하지만 s < 4일 때 S_{i, s} 의 코스트가 0 이라는 것을 잊어서는 안된다.

여기서 부분 문제를 정하기 위한 C_{i, s}(S ≥ 4) 를 계산하는 식은 다음과 같다.

        C_{i, s} = min{C_{i, k+1} + C_{i+k, s-k} + D(v_i, v_i+k) + D(v_{i +k,} v_i+s-1)}

여기서 D(v_p, v_q) 는 정점 v_p 와 v_q 가 다각형상에서 인접하지 않을 때는 이 두 정점을 연결하는 선의 실이를 나타내고 v_p 와 v_q 가 인접하고 있을 때는 0 으로 한다.

그림 7 에 있는 다각형과 거리를 토대로 하여 0 ≤ i < 6, 4 ≤ s < 6 에 대한 C_{i, s} 를 갖는 표를 다음에 나타냈는데, s < 3 인 행에 있는 값은 모두 0 이다. i = 0 인 열과 s = 7 인 행에 C_{0, 7} 의 값이 들어 있는데 이 값은 같은 행에 있는 다른 값과 마찬가지로 다각형 전체의 삼각형 분할을 나타내고 있다. 왜냐하면, 변(v₀, v₆) 을 보다 큰 다각형의 변이라고 생각해서 그림 7 에 있는 다각형은 큰 다각형의 부분 문제라고 생각하면 된다. 큰 다각형은 v₇ 에서 v₁ 까지의 사이에 여러 개의 정점열을 갖고 있을 것이다. s = 7 인 행은 모두 C_{0, 7} 과 같은 값을 갖는다.

 

2. 균형법


앞에서 설명한 분할 통치법의 예에서는 모두 원래의 문제를 크기가 같은 부분 문제로 분할했는데, 좋은 알고리즘을 설계하기 위한 기본적인 지침 중에 부분문제의 크기가 균등해야 한다는 것이 있다. 이것을 설명하기 위해서 정렬의 예를 사용해서 문제를 균형이 맞지 않는 크기를 가진 부분 문제로 분할한 결과와 같은 크기로 분할한 결과를 비교해 보자. 이 예에서 균형화가 유효하다는 것은 분할 통치법에만 한정된 것이라고 생각해서는 안된다.

n 개의 정수로 구성된 데이터를 크기가 적은 순으로 정렬하는 문제를 생각해 보자. 이 문제를 해결하기 위한 가장 단순한 정렬법은 데이터열을 앞에서부터 차례대로 조사해서 가장 작은 요소를 찾아낸 뒤, 제일 왼쪽에 있는 데이터와 교환하고, 그 다음에는 제일 왼쪽에 있는 데이터를 제외한 데이터열을 앞에서부터 차례대로 조사하여 가장 작은 요소를 찾아낸 뒤, 왼쪽에서 두 번째에 있는 데이터와 교환하는 것을 반복하는 것이다. 이 과정을 나머지 데이터에 대해서도 반복 적용함으로써 n 개의 데이터에 대한 정렬을 할 수 있다.

이 알고리즘에 의해 정렬되는 요소 사이에서 행해지는 비교 횟수를 평가해 보자. 제일 적은 데이터를 정하기 위해서는 n - 1 번 비교를 해야 하고, 두 번째 작은 데이터를 정하기 위해서는 n - 2 번, 그 다음 데이터를 정하기 위해서는 n - 3 번을 비교해야 한다. 전체 비교 횟수는 이들을 합하면 되므로,

        

이 되어 O() 이 된다.

이 정렬 알고리즘은 크기가 다른 부분 문제로 분할하는 분할 통치법을 재귀적으로 적용한 것이라고 볼 수가 있지만 크기 n에 대해서는 효율이 좋지 않으므로 오더상으로 효율이 좋은 정렬 알고리즘을 설계하기 위해서는 부분 문제의 크기를 균등화해야 한다. 크기가 n 인 문제를 크기 1 과 크기 n - 1 인 두 부분 문제로 분할하지 않고, 문제를 크기가 거의 반인 두 개의 문제로 분할해야 하는데, 이것은 앞에서 이미 설명한 합병 정렬이라는 정렬 알고리즘에서 이용되고 있다.

합병 정렬에 대해서는 이미 설명했으므로 알고리즘에 대한 설명은 생략하지만 이미 설명한 바와 같이 이 알고리즘의 복잡도는 O(n log n) 이다.

이와 같이 부분 문제의 크기를 균등하게 함으로써 훨씬 효율이 좋은 알고리즘을 만들 수 있게 된다.

1. 분할 통치법(divide and conquer)


효율이 좋고 알고리즘을 설계하는 기법으로서 가장 널리 사용되고 있는 기법중에 분할 통치법 (divide-and-conquer) 이라는 것이 있는데, 분할 통치법에서는 해결하려고 하는 문제 (크기를 n 이라고 한다) 를 크기가 보다 작은 여러 개의 부분 문제로 분할한다. 단, 이 때 크기가 작은 부분 문제에 대한 답으로부터 원래의 문제에 대한 해답을 쉽게 얻을 수 있게 분할할 필요가 있다. 이 기법에 대해서는 합병 정렬과 2 진 탐색목 등 몇 가지 응용 예를 지금까지 살펴보았다.

우선 문제를 분할하면 어느 정도 효과가 있는지를 예를 통해 살펴보기로 하자.

탁구 대회를 열어서 가장 탁구를 잘 하는 사람과 가장 못하는 사람을 정하려고 한다. 실력이 좋은 사람이 항상 이긴다고 했을 때 몇 번 시합을 하면 되는가를 계산하는 것이 문제이다.

여기서 탁구 대회 참가 인원을 n 명이라고 하자. 이 문제를 해결하기 위해서 스포츠 경기시에 일반적으로 많이 이용하는 「토너먼트법」을 이용하는데, 첫 번째 토너먼트에서는 가장 강한 사람을 결정하고, 그 다음에는 나머지 n - 1명 중에서 마찬가지로 토너먼트법을 이용해서 가장 약한 사람을 정하는 방법을 이용하기로 하자 (그림 1). 그림 1 에서 굵은 선은 시합에서 이긴 사람을 나타내고, × 표시가 있는 것은 진 사람을 나타낸다.

그림 1  탁구 대회

그림 1 과 같은 방법을 이용하는 경우에는 한번 시합을 할 때마다 한 사람씩 대상에서 제외되므로, n 명 중에서 가장 강한 사람을 정하기 위해서는 n - 1 번 시합을 하게 된다. 따라서 이 방법에서 필요한 시합수를 T₁ (n) 이라고 하면,

        

 이 된다.

그러나, 조금만 곰곰히 생각해 보면 그림 1 과 같은 방법을 이용하는 경우에는 불필요한 시합을 많이 한다는 것을 금방 알 수 있다. 첫 번째 토너먼트에서 이긴 사람 (약 n / 2 명) 은 자기가 이긴 상대보다는 강하다는 것은 알고 있으므로 다음 번에 실시하는 토너먼트에는 출전할 필요가 없다. 두 번째 토너먼트전은 첫 번째 토너먼트에서 한번도 이기지 못하고 진 사람만을 모아서 실시하면 되므로, 두 번째 토너먼트에 출전하는 사람수를 k 라고 하면 두 번째 토너먼트전을 운영하기 위해서는 k - 1 번 시합을 하면 된다.

이 방법으로 경기를 할 때의 시합수를 평가히가 위해서는 k 를 구해야 하는데, 이를 위해서는 첫 번째 토너먼트전을 구체적으로 어떻게 행하는지가 문제가 된다. 이 때 전년도 우승자에게 다른 사람이 차례로 한 사람씩 도전하는 방법을 택한다고 하고, 전년도 우승자가 모두에게 이기면 k 의 값은 n - 1 이 된다. 따라서, 이 방법을 이용하더라도 그림 1 의 방법과 같이 2n - 3 번 시합을 해야 한다 (그림 2).

그림 2  비능률적인 경기 운영

그러나 n 명을 거의 반씩 나눠서 첫 번째 토너먼트를 하게 하면 k 의 값은 n / 2 이 된다 (그림 3).

그림 3  능률이 좋은 경기 운영

이 때 계산을 간단하게 하기 위해 n을 짝수라 하고, 이 경우의 시합수를 T₂(n) 으로 하면,

        

이 되어, 그림 1 의 방법보다도 n / 2 - 1 번이나 시합수가 적어진다.

그러면, 이번에는 또 다른 방법을 생각해 보기로 하자.

우선 전체를 반으로 나눠서 각 팀에서 따로따로 최강자와 최약자를 결정한 후, 양 팀의 최장자끼리 시합을 하게 해서 전체의 최강자를 정하고, 최약자끼리 시합을 하게 해서 최약자를 정하면 된다 (그림 4).

그림 4  분할에 의한 최강ㆍ최약자 결정

이 방법을 이용한 경우의 시합수를 T₃(n) 으로 하면,

        

가 된다. 또, 분명히

        

이다. 이 두 식을 이용하면 각 n 에 대해 다음과 같이 되는데, 계산을 간단하게 하기 위해 n = 2p 라고 한다.

        

        

        

        

        

이것을 n 에 대한 일반식으로 나타내면,

       

이 된다.

여기서 설명한 마지막 방법 (그림 4 의 방법) 에서는 우선 전체를 반으로 나눠서 (분할) 각각에 대해 원래와 같은 문제를 해결하고 마지막에 간단한 처리를 해서 전체에 대한 해답을 구한다 (통합). 이와 같이 전체를 분할해서 각각을 따로따로 처리하고 마지막에 통합하는 방법을 「분할 통치법」이라고 한다 (그림 5).

그림 5  분할 통치법의 원리

그림 6  하노이 탑 문제의 초기 상태

분할 통치법의 또 하나의 예로서 하노이의 탑이라는 게임을 생각하기로 하자.

그림 6 과 같이 세 개의 막대 A, B, C 가 있는데, 처음에는 A 라는 막대에 여러 개의 원판이 크기순으로 즉, 어떠한 원판을 보더라도 위에는 그보다 적은 원판이 있고 아래에는 그보다 큰 원판이 놓여져 있다. 이 게임의 목적은 원판을 막대에서 막대로 한번에 하나씩 이동해서 모든 원판을 막대 B 로 옮기는 것이다. 단, 어떠한 경우에도 적은 원판 위에는 큰 원판을 둘 수 없다.
이 게임은 다음과 같은 단순한 알고리즘으로 해결할 수 있다는 것을 알 수 있다. 막대가 삼각형의 형태로 배치되어 있다고 하고 홀수 번째에는 가장 작은 원판을 시계 방향으로 하나만 이동하고, 짝수 번째에는 제일 작은 원판을 제외한 나머지 원판 중에서 이동할 수 있는 것만을 하나 이동한다.
이 알고리즘은 간단하고 정당하지만 왜 정당한지를 금방 알기는 어렵지만 다음과 같은 분할 통치법을 이용하면 정당성도 금방 이해할 수 있을 것이다.

원판 n 장을 A 에서 B 로 이동하는 문제는 크기가 n - 1 인 두 개의 부분 문제로 구성된 것이라고 생각할 수 있다. 우선 n - 1장의 원판을 막대 A 에서 막대 C 로 옮기면 막대 A 에 있던 n 번째 작은 원판 (가장 큰 원판) 을 옮길 수 있는 상태가 되므로 그 원판을 A 에서 B 로 옮긴다.
그리고 나서, n - 1 장의 원판을 막대 C에서 B로 이동한다. n-1장의 원판을 옮기기 위해서는 이 방법을 재귀적으로 사용하면 되는데, 여기서 이동하는 n - 1 장의 원판은 다른 어느 원판보다도 작으므로 이동할 때에 막대 A, B, C 의 제일 윗부분에는 어떠한 원판이 있는지를 생각할 필요가 없다. 실제로 여러 개의 원판이 어떻게 이동하는지는 알기 어렵고, 재귀 호출이 반복되므로 이것을 하나하나 체크하기는 힘들지만, 이 알고리즘의 아이디어는 이해하기 쉽고 정당하다는 것을 증명하는 것도 비교적 쉽다. 일반적으로 이와 같은 분할 통치법을 이용한 알고리즘은 그렇지 않은 알고리즘보다 효율이 좋다.
분할 통치법을 이용해서 알고리즘을 설계할 때에는 문제를 분할하는 방법 및 각 부분 문제에 대한 답을 통합시키는 방법도 고려해야 한다. 특히 부분 문제의 답에서 전체의 문제에 대한 답이 비교적 간단하게 얻어지지 않으면 이 기법은 사용할 수 없는 것이라고 생각해야 한다. 문제의 분할법도 알고리즘의 성능에 영향을 미치기 때문에 중요한다, 대부분의 경우 가능한 균등한 크기로 분할하는 것이 바람직하다.

부분 문제를 해결하기 위해서는 같은 프로시저를 재귀적으로 호출하는 것이 간단하고, 이 재귀 호출은 데이터수가 1 이 될 때와 같이 문제의 답이 분명하게 되는 시점에서 종료하게 된다.

C와 C++는 컴파일시 obj에 함수 이름, 변수 이름 등의 심벌을 기록하는 방식이 다르다.

그래서 C++ 컴파일러에서 C로 작성된 코드를 컴파일 하고자 할 때 사용한다.

C 컴파일러는 함수 이름을 그대로 사용하는 반면 C++ 컴파일러는 그대로 사용하지 않는다.
C++에서 프로그래머가 Func라는 이름으로 함수를 만들어도 이 이름과 동일한 함수를  만들 수 있다.

어떤 Func라는 함수는 정수를 인자로 받고 또 어떤 Func라는 함수는 실수를 인자로 받도록 만들 수 있다.

이렇게 이름이 동일한 여러 개의 함수가 나타날 수 있기 때문에 C++ 컴파일러는 내부적으로 Func라는 이름에다가 인자들의 타입 및 리턴 타입으로 어떤 문자들을 덧붙여서 각 함수들을 구분할 수 있도록 새로운 이름을 만든다.

extern "C"는 C++에서 C 함수를 사용하고자 할 때 컴파일러에게 C 함수라는 것을 알리는 역할을 한다.
이해를 돕기 위해 다음과 같은 프로그램을 예로 들어보자(파일 확장자는 .cpp로 만들어 C++ style로 컴파일한다).
add_1(), fadd_2(), add_3()이 컴파일 된 후 어떻게 이름이 바뀌는지 보면 왜 extern "C" 가 필요한지 알 수 있다.

#include "stdio.h"

int add_1(int a, int b);
float fadd_2(int a, int b);
extern "C" int add_3(int a, int b);

int main()
{
    int a = 2;
    int b = 3;
    int c;
    float fc;

    c  = add_1(a, b);
    fc = fadd_2(a, b);
    c = add_3(a, b);

    return 0;
}

/* -- 시험 삼아 여기를 막는다. --
int add_1(int a, int b)
{
    return a + b;
}

float fadd_2(int a, int b)
{
    return (float)(a + b);
}

int add_3(int a, int b)
{
    return a + b;
}
*/

################### compile/link 결과 ###############################
naver.obj : error LNK2001: unresolved external symbol _add_3
naver.obj : error LNK2001: unresolved external symbol "float __cdecl fadd_2(int, int)" (?fadd_2@@YAMHH@Z)
naver.obj : error LNK2001: unresolved external symbol "int __cdecl add_1(int, int)" (?add_1@@YAHHH@Z)

compile/link하면 위와 같이 link error가 발생한다.
자세히 보면
add_1 -> ?add_1@@YAHHH@Z
fadd_2 -> ?fadd_2@@YAMHH@Z
add_3 -> _add_3
와 같이 compile 과정에서 이름이 바뀐다.
add_1(), fadd_2()는 C++ style의 decorated name으로 바뀐 것이며, add_3()는 prototype에서 extern "C"를 주었으므로 C style로 '_'만 앞에 붙은 것이 차이점이다.

C++는 argument, return value에 따라 이름이 바뀌어 반드시 protype과 일치하는 function이 link된다. argument가 틀린 경우에는 같은 이름의 function이 여러 개 존재할 수 있으며 argument에 따라 적당한 function이 link된다.

C는 단순히 이름 앞에 '_' 만 추가되므로 argument가 틀리던 return value type이 틀리던 link는 될 수 있다. 심하게 잘못되면 compile/link는 되는데 오동작을 할 수도 있다.

C++는 컴파일시 함수 이름을 모두 다른 이름으로 바꿔주기 때문에 C에서 컴파일된 함수를 링크시킬 때는 해당 함수의 선언부 혹은 include 부분에 extern "C"라는 키워드를 사용하여 해당 함수가 C로 컴파일된 함수라는 것을 컴파일러에게 명시적으로 알려줘야 한다.

그런데 이 extern "C" 키워드는 C++에서 사용하는 것이므로 C에서는 사용되지 않는다. 따라서 반대로 C++의 함수를 C에서 사용하고자 한다면 C++ 소스를 컴파일 전에 소스 내에서 사용되는 함수의 선언을 모두
extern "C" 함수선언
이렇게 변환해 주어야 한다.

C에서는 이미 컴파일된 C++ 함수를 호출할 수 없다. 하지만, 만약 이렇게 C++ 소스에서 모든 함수를 extern "C"로 변환한다면 이 함수들은 C++의 함수 특성을 모두 잃게 된다. 즉, 클래스의 멤버 함수가 될 수 없고 인자만 틀리고 함수 이름은 같은 오버로딩 함수가 될 수도 없다.

보통 *.h 파일에 아래와 같이 하여 *.c, *.cpp에서 공용할 수 있는 protype 선언을 한다.

#if defined (__cplusplus)
extern "C" {
#endif

int func1();
int func2();
.
.
.

#if defined (__cplusplus)
};
#endif

참고,
extern "C" aaa();
extern "C" bbb();
는 아래와 같이 블록으로 잡아서 한번만 해주면 된다. 
 
extern "C"
{
    aaa();
    bbb();
}

#define SWAP(x, y) {(x)^=(y)^=(x)^=(y);}

위와같은 SWAP 매크로가 있다.

이제 이 매크로를 한번 풀어 보겠다.

int main()
{

int x = 10;
int y = 20;

printf("X = %d, Y = %d", x, y);

x ^= y ^= x ^= y;  //SWAP(x, y);

printf("X = %d, Y = %d", x, y);

return 0;

}

위과 같이 매크로가 풀릴것인데... 이것을 하나씩 뜯어보면

제일 뒤에것 부터 x ^= y;

이걸 다시 풀어쓰면 x = x^y;

자 그럼 x와 y를 2진수로 풀어 보겠다.

x : 00001010 (10진수 : 10)
y : 00010100 (10진수 : 20)

^모양은 XOR하란 말이므로 위의 두 2진수를 XOR 시키면

x^y = 00011110

그럼 이 값이 x에 들어갔을 것이다.

그럼 다음인 y ^= x;

이것도 다시 풀어쓰면 y = y^x;

x : 00011110
y : 00010100

XOR 시키겠다.

y^x = 00001010

이 값 또한 y에 들어가게 된다.

이제 마지막으로 x ^= y;

풀어보면 x = x^y;

x : 00011110
y : 00001010

XOR 시키겠다.

x^y = 00010100

x에 마지막으로 값이 들어 갔다.

그럼 최종적인 값을 확인해 보겠다.

x : 00010100 (10진수 : 20)
y : 00001010 (10진수 : 10)

자 어떤가...

추가적인 변수 없이 비트연산만으로 SWAP구현이 가능하다.

보기쉽게 코드화 하면

x = x ^ y;
y = y ^ x;
x = x ^ y;

과 같이 쓸 수 있다.


또하나의 방법을 보겠다.

x = x + y;
y = x - y;
x = x - y;

이정도는 +, - 만 할줄 안다면 풀이가 가능하니

풀이는 하지 않겠다...

이처럼 여러가지 방법으로 추가적인 변수 없이 SWAP 구현이 가능하다.

1. C언어와 C++언어의 대표적인 차이

- C++은 기존의 C언어 구성요소를 대부분을 사용하며 거기에 진보된 자료형(Data Type)과 객체지향 프로그래밍 개념을 추가
- C++은 C를 기반으로 만들어졌지만 C와 구별되는 독립적인 언어이고, 많은 면에서 C보다 좋은 언어
- C++은 객체지향 언어(Object Oriented Programming)
   프로시쥬어프로그래밍->구조화된 프로그래밍->객체지향프로그래밍
  : 코드와 데이터를 하나로 묶고(코드/데이터 추상화), 이들 서로가 독립성을 지니도록 하는 경향 (모듈화)
- 소프트웨어 산업의 위기 -> 객체지향언어로 극복

사실 별로 재미있지는 않습니다.

(이강좌는 8bit 마이크로컨트롤러에서 사용하는 것을 기준으로  char은 8bit  int는 16bit 로 가정하고 진행 됩니다. ) 

그래도 중요하고 꼭 알고 넘어가야 하는 문제이기 때문에..

비트연산자에 대해 공부 해 보겠습니다.

비트연산자는

&

| (Shift + \ 입니다. 모음 ㅣ(이),  L(엘)의 소문자, 대문자 I(아이) 가 아닙니다. )

^

~

<<

>>

이렇게 6가지가 있습니다.

어려운것은 없죠?

한가지 알고 넘어가야 할 부분은  << 나 >> 로 이동할때 이동한 만큼의 비트가 버려지고 0으로 채워 집니다.

잘 모르시겠다구요? 그럼 한번 예를 들어 보겠습니다.

unsigned char num=0xFF;

num= num<<4;

num은 얼마가 될까요?? 

바로 0xF0;

2진수로 풀어 보겠습니다.

0xFF==0b11111111 입니다.

0b 1111 1111              을 왼쪽으로 4번 비트 이동 하겠습니다.

0b 1111 1111 0000      입니다. 비게 되는 오른쪽은 0으로 채워집니다.  그리고 빨간 1111은 버려지게 됩니다.

왜 버려지냐구요? 바로 변수 선언을 8bit 로 했기 때문이죠.. 빨간 1111을 저장할 공간이 없기 때문에 버려집니다.

그래서 남은건 0b 1111 0000 == 0xF0

만약 num 가 int 형 이고 초기값이 0x00FF 였다면  어떻게 되었을까요??

그렇죠.. 0x0FF0 이 됩니다.

쉽죠??

그럼 각 연산자들이 어떤 상황일때 자주 쓰이는지 알아 보겠습니다.

먼저

& 연산자

& 연산자는 둘다 1이어야 1이 되기 때문에

1)특정 비트만 0으로 만들고 싶을때

2)특정 비트만 확인 하고 싶을때 (masking)

로 많이 사용됩니다. 

예를 들어 보겠습니다.

1)특정 비트만 0으로 만들고 싶을때

PORTA 에 LED8개가 붙어 있고 모두 켜져 있습니다.(PORTA==0xFF) 

그런데 다른 비트는 건드리지 않고 0번 1번 7번 비트의 LED 만 끄고 싶다면???

PORTA=PORTA & 0x7C;

라고 하면 됩니다.

쓰고 보니 PORTA=0x7C; 라고 하면 되지 않느냐? 라고 물으실 분들을 위해 다른 가정을 하나 더 넣겠습니다.

현재 LED 가 어떻게 켜져 있는지 모르는데 0번 1번 7번 비트의 LED 만 끄고 싶다면??? 그렇다면..

PORTA=PORTA & 0x7C; 이런식으로 & 연산자를 쓰는 것이 다른 비트는 건드리지 않게 됩니다.

2)특정 비트만 확인 하고 싶을때 (masking)

특정 비트만 확인하는 부분은 조건문에서 많이 들어 가는데..

예를 들어 PORTA 에 스위치가 8개 붙어 있는데

PORTA 3번 비트에 달려 있는 스위치가 눌렸는지 판단하고 싶다면?? (스위치는 안눌렀을때 1 눌리면 0으로 가정합니다. )

if((PINA & 0x08) == 0){  ... } 

else 

 이런식으로 사용하게 되면 스위치가 눌렸다면 {  ... }  의 동작을 수행하고 눌리지 않았다면  else 문을 수행 하겠죠??

| 연산자

| 연산자는 둘중 하나라도 1이면 1이 되기 때문에

1)특정 비트만 1으로 만들고 싶을때

로 많이 사용됩니다. 

예를 들어 보겠습니다.

1)특정 비트만 1으로 만들고 싶을때

AVR의 ADC관련 레지스터 중에 ADCSRA 라는 레지스터가 있습니다.

그런데 이 레지스터의 6번 비트를 1로 set 하면 ADC를 시작하라는 명령을 내리는 비트입니다.  다른 비트들은 ADC 관련 설정 값이죠..

만약.. ADC를 시작하고 싶은데 ADC 의 다른 설정은 건드리지 말아야 할때.. 바로 | 를 쓰면 됩니다.

ADCSRA |= 0x40; 이렇게 사용하면 해당 비트만 1로 만들수 있습니다.

포트 출력할때 특정포트만 1로 만들고 싶다면 동일한 방법으로 사용하면 됩니다.

^ 연산자 (XOR 발음 익스클루시브오알 ㅡㅡ;)

두개가 다르면 1이 되기 때문에

1)특정 비트를 토글하고 싶을때

많이 사용됩니다. 

예를 들어 보겠습니다.

PORTA 에 연결된 LED중 0번 비트에 연결된 LED만 켰다 껏다를 반복하고 싶습니다.

그럼 이렇게 코드는 어떻게 작성할까요??

while(1)

{

     PORTA = 0x01;

     delay_ms(1000);

     PORTA = 0x00;

     delay_ms(1000);

}

이렇게 작성해도 되지만  ^ 를 사용하면

while(1)

{

     PORTA ^= 0x01;       

     delay_ms(1000);

}

코드가 간단해 집니다.

PORTA 의 값이 뭐든 다른 비트는 변화 없이 0번 비트만 토글됩니다.

<<, >> 연산자

& 연산자는 둘다 1이어야 1이 되기 때문에

1)두개의 8bit 정수를 합쳐서 int 형 변수에 넣어 줄때  

2)나누기나 곱셈대신 사용할때

예를 들어 보겠습니다.

AVR 에는 10bit ADC 가 있습니다.

ADC 를 하게 되면 10bit 를 8bit씩 나눠 ADCH, ADCL 에 나눠 담기게 됩니다.

10bit 니까 8 , 2나 2 , 8로 나뉘게 됩니다.  (나뉘는 방법은 ADMUX 레지스터 안에 있는 ADLAR 비트에 의해 설정됩니다.)

ADLAR==0 일때 shift 연산자를 이용해서 16비트 변수에 담아 보겠습니다.

원칙적으로 A/D 변환결과를 읽을 때는 ADCL 부터 읽어야 합니다.

unsigned int temp=0x0000;

temp =  ADCL | (ADCH<<8);     //이렇게 써도 됨  temp =  ADCL + (ADCH*256);

ADLAR==1 일때도 한번 해보겠습니다.

unsigned int temp=0x0000;

temp =  (ADCL >>6 )  | (ADCH<<2) ;

벌써 비트 연산자가 막 들어가기 시작하네요...

곱셈이나 나눗셈을 대신 할때는 몇가지 조건이 있습니다.

먼저 정수형만 되고 2의 지수승만 됩니다.   2,4,8,16,32,64,128,256,512,1024 .....

예를 들어보겠습니다.

0x0F 를 <<2 한것과 *4 것을 비교해 보겠습니다.

0x0F 는 10진수로 15입니다.          *4하면 60 이죠

0x0F를  <<2 하면 0x3C 입니다.     십진수로 계산해 보면 60이죠

아래 표를 보면 << 와 *과의 관계가 이해가 되실 겁니다.

>> 와 / 도 마찬가지입니다.

 * 나 / 대신  <<, >> 를 쓰는 이유는 연산하는 속도가 빠르기 때문입니다.

 2,4,8,16,32,64,128,256,512,1024 ... 으로 나누거나 곱할때는 << 나 >> 를 쓰는 연습을 해 봅시다.  

이것으로 비트연산 강좌를 마칩니다. ^^ 모두 열공~

1. 임시 변수 없는 SWAP 매크로

#define SWAP(a, b) {(a)^=(b)^=(a)^=(b);} 


2. 주어진 수가 2의 제곱수(1, 2, 4, 8, 16 등등)인지 검사(출처: flipCode)

inline bool IsPow2(int v)
{
    return (!(v & (v - 1)));
}


3. 0이 아닌 비트들의 개수 세기...(예를 들어 0xf0는 4개..)(출처: flipCode)

8비트용:
v = (v & 0x55) + ((v >> 1) & 0x55);
v = (v & 0x33) + ((v >> 2) & 0x33);
return (v & 0x0f) + ((v >> 4) & 0x0f);

32비트용:
#define g31 0x49249249ul // = 0100_1001_0010_0100_1001_0010_0100_1001
#define g32 0x381c0e07ul // = 0011_1000_0001_1100_0000_1110_0000_0111


v = (v & g31) + ((v >> 1) & g31) + ((v >> 2) & g31);
v = ((v + (v >> 3)) & g32) + ((v >> 6) & g32);
return (v + (v >> 9) + (v >> 1 + (v >> 27)) & 0x3f; 

debugging.doc

I. 디버깅

1. 기본 디버깅 환경

Windows Driver 디버깅을 위해선 다음 그림과 같이 디버깅용 컴퓨터가 더 필요합니다. 디버깅 컴퓨터에는 타겟 컴퓨터와 같은 운영체제가 로딩되어 있어야 하고 디버깅을 위한 프로그램이 필요합니다. 디버깅 프로그램은 DDK에서 제공하는데 자세한 사용법은 도움말을 참조하시기 바랍니다.

Debugger                         Debuggee

위 그림에서 알 수 있듯이 컴퓨터간의 데이터 교환은 RSC-232 직렬 통신을 통해 이루어 지는데 통신에 필요한 케이블은 다음 그림과 같이 만들어 사용하면 됩니다.

2. Windows 2000/XP에서 디버깅 환경

디버깅을 시작하기 이전에 두 컴퓨터간의 통신 속도를 맞춰줘야 하고 타겟 컴퓨터를 디버그 모드 설정 해야 합니다. Windows NT 계열에서는 다음과 같이 boot.ini 파일에 다음과 같이 추가해 주면 부팅 시 디버그 모드로 부팅할 지 일반 모드로 부팅할 지 사용자에게 묻는데 이때 디버그 모드를 선택해 주면 디버그 모드로 부팅하게 됩니다.

[boot loader]

timeout=30 default=multi(0)disk(0)rdisk(0)partition(1)\WINNT

[operating systems]

multi(0)disk(0)rdisk(0)partition(1)\WINDOWS="Microsoft Windows XP Professional" /fastdetect

multi(0)disk(0)rdisk(0)partition(1)\WINDOWS="Microsoft Windows XP Professional" /fastdetect /debugport=com1 /baudrate=57600

통신 속도 설정은 위의 내용을 보면 알겠지만 /debugport는 직렬 케이블이 연결된 포트이고 /baudrate는 통신 속도를 나타냅니다. 여기에 설정된 속도와 Windows 2000 DDK에서 제공하는 디버깅 프로그램에서의 속도를 맞춰주면 됩니다.

다음은 Windbg를 실행하여 환경설정을 하고 디버깅 하는 방법입니다.

1번 방법은 ddk를 설치 시 같이 설치 되는 windbg 실행 방법이고, 2번의 방법은 최신 Windbg6.2.7.4의 실행 방법입니다.  2번의 Windbg6.2.7.4를 사용하는 것이 사용하기에도 쉽고 자세한 디버깅을 할 수 있습니다.

1) 기본 windbg실행

View->Options를 선택했을 때 뜨는 창으로 포트, 속도 및 Flags를 다음과 같이 설정해 주면 됩니다.

참고로 디버그 모드로 부팅하였는데 Windbg에 디버깅에 관련된 아무런 내용도 출력되지 않을 시에는 Windbg에서 디버깅 명령인 ‘Ctrl+C’와 ‘g+ Enter’를 번갈아 눌러 주시면 디버깅 내용이 출력됩니다.

2) Windbg 6.2.7.4

다운 방법: http://www.microsoft.com/whdc/ddk/debugging/installx86beta.mspx 에서

Install 32-bit Beta Version 6.2.7.4 (April 29, 2003) 8.2 MB 를 클릭하여 다운 받으시기 바랍니다.

실행 화면

kernel debugger 실행

속도와 포트 설정

위와 같이 하면 기본적인 디버깅은 설정이 됐습니다.

추가적으로,

File->Symbol File Path

: 드라이버를 컴파일 하면, xxx.pdb파일이 xxx.sys파일과 같이 생성되는데, 이 파일을 등록 해주면, break될 경우( 예) bluescreen) 해당 소스에 line과 함수 명들과 같은 자세한 정보가 출력이 됩니다.

이 xxx.pdb파일을 symbol(심볼) 파일이라고 합니다. 이 파일은 컴파일 된 드라이버 파일에 대해 함수위치와 소스정보에 대해 가지고 있습니다. 그래서 관련 이 파일이 로딩되면, 컴파일 된 소스에 대한 정보(함수들, 소스의 line 정보(소스가 있다면)등…)를 얻을 수 있습니다.

등록방법은 File->Symbol File Path 를 클릭할 경우, 심볼 파일의 경로를 설정하여주면, 해당 경로의 심볼을 로딩하게 됩니다. 심볼이 바뀐 경우에는 Reload를 check해 줍니다.

위 그림을 보면, 심볼이 세미콜론으로 2개가 등록이 되어있습니다.

SRV*c:\websymbols*http://msdl.microsoft.com/download/symbols

: web으로 관련 심볼을 다운받는 것입니다. 예전에 심볼을 미리 다운받아서 위치를 지정해 주었지만, 지금은 필요할 경우 웹에서 직접 다운 받는다. 이 심볼파일 중에는 ndis.sys와 같은 커널 함수들에 대한 심볼들을 포함하고 있어서 커널 소스는 알 수 없어도 함수 이름 등은 알 수가 있습니다.

c:\symbols

: 이 경로는 사용자가 추가해 주는 심볼 파일 경로입니다. 사용자가 컴파일해서 만들어진 심볼파일을 이 폴더에 복사해놓으면 심볼이 로딩됩니다.

아래의 그림은 심볼이 등록되었음을 보여주고 있습니다.

File->Source File Path

소스의 경로를 지정해 줍니다. 소스를 로딩 할 경우, break 지점이 소스 내에 있으면, 해당 소스의 라인에서 “p” 명령어를 치며, 디버깅을 해 나갈 수 있습니다.

View

MFC 에서 디버기을 할 때 메모리, 디스어셈블, 스택 등을 알 수 있듯이 여기서도 알 수 있습니다.

3. 디버깅 명령어

Windows 드라이버의 디버깅은 Windows Visual Studio와는 달리 사용자가 디버깅 명령을 직접 입력하는 방식으로 진행됩니다. 디버깅을 위해선 여러 가지 디버깅 명령어들을 다룰 수 있어야 되는데 디버깅 명령어에 대한 자세한 내용은 DDK 도움말을 참고하시기 바랍니다.

다음은 디버깅에서 많이 사용하는 명령어를 정리한 것으로 이 정도의 명령어로도 간단한 디버깅은 충분히 수행할 수 있을 것이라 생각됩니다.

. !analyze -v

디버기(debugee)가 BlueScreen이 발생하거나, 시스템에 문제가 있을 경우, Windbg 프로그램은 break가 걸리게 된다. 이때 break된 원인을 자세히 알기 위해서 “!analyze -v”명령을 명령줄에 치면, 자세한 정보를 얻을 수 있다.

4. Windows 98에서 디버깅 환경

디버깅을 시작하기 이전에 두 컴퓨터간의 통신 속도와 사용할 포트를 맞춰줘야 하고 디버깅이 시작될 때 타겟 컴퓨터를 디버그 모드 시작해야 합니다. Windows 98 에서는 두 컴퓨터간의 통신 속도를 맞추기 위해서 다음과 같은 절차가 필요합니다.

1) 타겟 컴퓨터에서 해야할 일.

a)       타겟 컴퓨터에 98DDK가 설치되어 있어야 한다.

b)       설치된 경로를 C:\98DDK라고 하면 C:\98DDK\bin\Runwdb98.bat 파일의 내용을 다음과 같이 수정해야한다.

수정전: @wdeb98 %1  /n  /x  /c:2  /r:19200  /f:runwdeb.wrf  ..\win.com

수정후: @wdeb98 %1  /n  /x  /c:1  /r:19200  /f:runwdeb.wrf  c:\windows\win.com

여기서 통신속도(/r)는 사용자가 정해주는 값으로 19200을 사용해도 되고 다른 값으로 사용해도 된다. 하지만 이 값은 반드시 디버거의 Rterm98.exe에서 사용하는 값과 같아야 한다. 디버깅을 하다가 종종 출력되는 내용이 깨지는 경우가 있는데 이럴때는 통신속도를 변경하여 알맞은 속도로 설정해주면 된다. 포트에 해당되는 것은 ‘/c’ 이다. 이 값도 기본적으로 2로 되어있고 그대로 사용하면 된다. 중요한 것은 어떤 포트를 사용하느냐가 아니라 시리얼케이블이 연결된 포트와 /c의 포트와 일치해야한다는 것이다. “/f:runwdeb.wrf”는 심볼파일을 등록할 때 사용하는 파일로 이 부분에 대해서는 ‘c)’에 자세하게 기술하겠다.

c)       C:\98DDK\bin\ runwdeb.wrf의 내용은 아래와 같다.

사용자가 드라이버 소스를 컴파일해서 만들어진 심볼파일을 SnSDrv.sym이라고 하면 위의 그

림과 같이 기입해주고 SnSDrv.sym 파일을 C:\98DDK\bin 에 복사해주면 디버깅시 심볼이 등록

된다.

98DDK에서는 이러한 심볼파일들을 다음과 같이 제공하고 있다.

98SE: 98ddk CD의 \DEBUG_WINDOWS98SE\Retail\

98: 98ddk CD의 \Dbg_sym\Retail\

아래의 그림은 디버깅이 시작될 때 심볼이 등록되었음을 보여주는 화변을 캡쳐한 것이다.

2) 디버깅 컴퓨터에서 해야할 일.

a)       디버깅 컴퓨터에 98DDK가 설치되어 있어야 한다.

b)       C:\98DDK\bin\Rterm98.exe를 실행한다. 다음은 실행한 화면이다.

c)       메뉴에서 “Settings->Options ”를 선택하면 아래와 같은 창이 뜬다.

d)       위의 그림과 같이 설정해주면 타겟 컴퓨터에서 설정한 통신속도와 포트가 일치한다.

e)       ‘확인’을 누른다.

3) 디버깅하기

a)       이제 모든 환경이 설정되었다.

b)       디버깅 컴퓨터에서는 C:\98DDK\bin\Rterm98.exe를 실행한다.

c)       타겟 컴퓨터에는 디버깅하고자하는 드라이버가 설치되어 있어야하고 심볼을 등록해주면 더 자세한 정보를 얻을 수가 있다.

d)       타겟 컴퓨터를 도스모드로 재부팅한다.

e)       C:\98DDK\bin\Runwdb98.bat 파일을 실행하면 디버깅 컴퓨터에 실행된 Rterm98 화면에서 디버깅되는 내용을 확인 할 수 있다.