Page 16 - 컴퓨팅 사고와 함께하는 파이썬기초부터 인공지능 응용까지 도서 미리보기

CHAPTER 2? 문제 해결과 컴퓨팅 사고 025

2.2.1? 문제 분해

문제 분해(decomposition)는 주어진 문제를 더 작은 문제로 나누는 활동을 의미한다.
물론 문제를 쪼갤 때에는 쪼개져 나온 작은 문제의 해답을 활용해 원래 문제의 해답을
어떻게 구할지 그 방법까지 생각해야 한다. 문제 분해는 크고 복잡한 문제를 효과적으
로 해결할 수 있게 해 준다. 이는 작은 문제가 큰 문제보다 다루거나 해결하기 쉽기 때
문이다. 예를 들어 정수 100개의 합을 구하는 문제보다 정수 50개의 합을 구하는 문제
가 해결하기 쉽다. 이때 100개의 합을 구하는 문제를 50개의 합을 구하는 문제 2개로
나누어서 각 문제의 해답이 산출된다면, 두 문제의 해답을 더하여 원래 문제의 답을
구할 수 있게 된다.

문제 A를 문제 A1과 문제 A2로 나누어 순차적으로 처리·해결하는 방법을 구상했다면,
문제 A를 해결하는 알고리즘은 다음과 같이 구성될 것이다.

① 문제 A를 문제 A1과 문제 A2로 나눈다.
② 문제 A1을 해결한다.
③ 문제 A2를 해결한다.
④ 문제 A1과 A2의 해결 결과를 활용해 문제 A를 해결한다.

단순히 문제 A1과 A2를 순차적으로 해결하기만 하면 문제 A가 해결되도록 문제 A를
분해했다면, 단계 ①과 ④는 생략될 수 있다. 어떤 경우든 문제 A1과 A2 각각에 대한
문제해결 알고리즘을 구상하는 작업이 문제 A에 대한 문제해결 알고리즘을 정의하는
데 있어 핵심 작업이 된다. 문제 분해 작업은 반복 적용될 수 있다. 분해 결과로 설정
된 문제(위의 경우 문제 A1이나 A2)를 다시 분해할 수 있다는 것이다. 분해 결과를 다
시 분해하는 식의 작업을 반복 적용해 다루기 쉬운 작은 크기의 문제를 설정할 수 있
다면, 그런 문제들을 해결하고 그 결과를 활용해 처음에 주어졌던 문제(위의 경우 문
제 A)를 해결할 수 있게 된다. [그림 2-1]에 문제 분해·해결·조합 기법을 적용해 문
제가 해결되는 과정이 제시되어 있다.

[큰 숫자 덧셈 공부] 상황과 관련해 2.1에서 제시한 문제(problem)를 다음과 같이 몇
개의 하위 문제(subproblem)로 분해하고, 그들 각각의 해결책을 조합해 원래 문제의
해결책을 도출해 볼 수 있다.