C 프로그래밍은 매우 도전적인 작업이다. 도전의 이면에 철저한 준비와 체계적인 노력 프로그래머의 개성이 잘 드러난다. 자신의 아이디어와 스타일을 구사할 공간이 매우 넓다. 도전의 이면에 철저한 준비와 체계적인 노력 ‘정리되지 않은 생각을 가지고 키보드를 두드리는’ 잘못을 피하라. 물 붓고 라면 넣고 끓이면 죽이 된다. 문제 해결 절차를 지켜라. 반드시 문제 이해  논리적인 생각으로 알고리즘 설계  C 코딩 이 절은 세 가지 문제를 가지고 문제 해결 연습 2.2 최대 공약수 구하기 2.4 배열 분할 2.5 도형 그리기

2.1 문제 해결 과정 문제를 자동 해결하는 지능적인 컴퓨터는 아직 없다. 프로그래머는 명령문과 실행 순서를 일일이 지정해야 한다. 이 과정을 컴퓨터 프로그래밍이라 한다.

전형적인 문제 해결 과정 프로그래머의 능력 = ‘논리적인 사고’ + ‘적절한 언어로 표현’ 그림 2.2의 절차를 지켜라.

2.2 문제 1: 최대 공약수 최대 공약수 (GCD): 두 정수가 공통으로 갖는 가장 큰 약수

2.2.1 우직한 생각 예제 2.1이 사용한 규칙 알고리즘으로 정리하면, 알고리즘 [2.1]은 ‘스케치’ 버전: 바로 코딩하기 어려움 기본 연산이 아니라 복잡한 연산을 사용하기 때문

또 다른 규칙 규칙2의 손 시뮬레이션 (손으로 단계를 따라가 봄)

규칙2를 알고리즘으로 정리하면, 알고리즘 [2.2]가 사용하는 연산 라인 2의 !과 &&은 not과 and 라인 2에서 나누어 떨어짐은 조건 m%T==0으로 구현

알고리즘 [2.2]를 C 코딩하면,

알고리즘 [2.2]의 계산 효율 라인 9, 10, 12, 13, 18: 단 한번 수행 라인 15-16의 수행 회수가 계산 시간을 좌우함 경우에 따라 다름 m=12, n=24인 경우 푸프 0번 수행 m=56056, n=14157인 경우 14157-143번 수행 계산 효율 나쁨

연습 문제

2.2.2 유클리드의 생각 기원전 300년경의 그리스 수학자 유클리드의 규칙 (유클리드 호제법) 손 시뮬레이션 해보면, m=56056, n=14157인 경우 5번의 루프로 답 찾음 매우 효율적

유클리드 규칙을 알고리즘으로 정리하면, break 문은 루프 탈출

알고리즘 [2.3]을 코딩하면,

함수로 다시 코딩하면, 다음 슬라이드에서 계속 …

함수로 다시 코딩하면,

연습 문제

2.3 언어 규칙과 알고리즘을 ‘표현하는’ 도구 머리 속의 생각을 정확하게 표현할 줄 알아야 한다. 컴퓨터의 기본 명령어는 의외로 단순 알고리즘이 기본 명령어만 사용한 경우 C 코딩이 쉽다. 복잡한 명령이 있는 경우 (초보에게는) 코딩이 까다롭다.

복잡한 명령문과 기본 명령문 고수는 복잡한 명령문을 가지고 바로 C 코딩할 수 있다. 초보는 아래와 같은 과정을 거쳐야 한다.

의사 코드와pseudo code C 코드 의사 코드: C 코드는 아니지만 그에 가까움 스케치 버전: 복잡한 명령어 포함됨 상세 버전: 기본 명령어만 사용 C 코드: C 언어로 기술된 프로그램 소스 프로그램 또는 소스 코드라고도 부름 초보는 아래 순서대로 하는 것이 현명하다. 스케치 코드  상세 코드  C 코딩

2.4 문제 2: 배열 분할 배열에 담긴 수를 기준보다 작은 것과 큰 것으로 구분 작은 것은 기준의 왼쪽으로 큰 것은 오른쪽으로 재배치하는 문제

2.4.1 배열 실제 응용에서 수십~수백만 개의 데이터를 다루는 경우 성적 처리, 매출액 정리, 국세청의 세금 정리, 쇼핑몰의 고객 관리 등 평균과 분산 계산, 정렬 등의 문제 발생 배열을 사용해야 함 그림 2.3: type은 int, array_name은 score, array_size는 1000 첨자는 0~999까지임

배열 접근 n 개 요소를 갖는 배열의 경우 첨자는 0~n-1 유효한 첨자 사용은 프로그래머의 몫 (프로그램이 자동 검사하지 않음) 접근 예

배열에서 최대와 최소 구하는 프로그램 배열의 크기는 미리 지정되어야 한다. 보통 충분히 큰 용량 지정 (메모리 낭비 요인)

함수 버전 배열과 그 속에 담긴 데이터 개수를 매개 변수로 줌 매개 변수에서 1차원 배열의 크기는 생략 가능

연습 문제

2.4.2 배열 분할 퀵 정렬이 사용하는 연산 (퀵 정렬은 5.4절에서 공부)

배열 분할 문제를 어떻게 풀까? 아래 그림에서 실마리를 …

시작은 어떻게?  i=0, j=1 끝낼 때 기준 요소는 어디로?  기준 요소 A[0]과 A[i] 교환 다음 슬라이드에서 계속…

알고리즘으로 정리하면,

for 문으로 바꿔 쓰면, 알고리즘 [2.4]와 논리적으로 같다.

C로 코딩하면, 실제 분할하는 부분은 다음 슬라이드에 …

실제 분할하는 부분은 라인 16-23 매우 간결하지 않은가!

연습 문제

2.5 문제 3: 도형 그리기 도형 그리기로 규칙 도출  알고리즘 정리  C 코딩 연습을 또 해 보자. 단순한 직사각형과 약간 복잡한 다이아몬드 ******* * * * * * * * * * * * * *

2.5.1 직사각형 그리기

알고리즘이 간단하므로 스케치 코드를 바로 C 코딩하면, 실제 그리는 부분은 다음 슬라이드에 …

연습 문제

2.5.2 프로그래밍 스타일: 경계 조건과 예외 조건 프로그램 [2.7]의 경계 조건과 예외 조건에서의 동작은? 경계 조건은 height=0, 1, 또는 2일 때 예외 조건은 height가 음수 또는 화면 길이보다 클 때 경계 조건과 예외 조건의 적절한 처리는 매우 중요하다. 그렇지 않으면 은행이 망하고, 비행기가 추락할 수 있다.

경계 조건과 예외 조건을 적절히 처리하는 버전 이하 생략 …

연습 문제

2.5.3 다이아몬드 그리기 1 bbb* 2 bb*b* 3 b*bbb* 4 *bbbbb* 5 b*bbb* 6 bb*b*

다이아몬드 그리기 규칙

알고리즘으로 정리하면,

C 코딩하면, 실제 그리는 부분은 다음 슬라이드에 …

연습 문제

연습 문제