알고리즘과 문제해결

(1)

알고리즘과 문제해결

알고리즘 코딩과 디버깅

13강

(2)

1차시

좋은 코드 원칙

학습목표

좋은 코드 작성의 원칙 ^을

이해 할 수 있다.

1

(3)

1

^{간결한 코드 작성}

코드가 짧으면 è 오타 및 단순버그 우려 감소 디버깅 용이

C/C++의 경우 매크로 활용

코드의 논리와 상관 없는 데이터 분리

간결한 코드 작성

1

복잡한 루프문

bool hasDuplicate(const vector<int>& array) { for (int i=0; i<array.size(); ++i)

for (int j=0; j<I; ++j)

if (array[i] == array[j]) return true return false;

}

(4)

1

매크로를 활용한 코드

#define FOR(i,n) for (int i=0; i<(n); ++i)

bool hasDuplicate(const vector<int>& array) { FOR (i, array.size())

FOR (j, i)

if (array[i] == array[j]) return true return false;

}

1

코드와 데이터 분리

string getMonthName(int month) { if (month == 1) return “January”;

if (month == 2) return “Febuary”;

…

return “December”;

}

const string monthName[] = {“January”, “Febuary”, …, “December”}

(5)

1

2차원 배열 크기를 세로 크기, 가로 크기 순서로 일관 표현 while, do-while을 혼용하지 않음

변수의 이름 등을 명확하게 명명

자료를 정규화 è 각도, 시간(시간대), 인코딩

명료한 코드 작성

2

^{라이브러리 사용}

표준라이브러리 사용

자료구조를 직접 구현해서 활용하지 않음 è버그가 존재하거나 성능 저하 위험

표준라이브러리는 오랜 시간 사용되어 검증됨 다른 사람이 코드를 이해하기도 쉬움

(6)

2

^{라이브러리 사용}

코드의 재사용

반복되어 중복적으로 코드를 작성하지 않음

è 문제점이 발견되었을 때 모든 곳을 찾아서 수정해야 함

전체적으로 코드가 간결해짐

다른 사람이 코드를 이해하기도 쉬움

핵심 키워드 이 시간을 통해 꼭 기억해야하는 ‘핵심 키워드’입니다.

좋은 코드 작성 원칙

1

(7)

참고문헌

• https://blog.deming.org/2014/11/minimal-viable-product/

(8)

2차시

자주 하는 실수

학습목표

소스코드 작성 시에 자주하는 실수 사례를 확인 하고 주의할 수 있다.

1

(9)

1

^{배열 관련 실수}

배열 범위 밖 원소에 접근

배열의 크기와 배열 인덱스는 다름

month[12] è month[0], …, month[11]

컴파일시에 발견이 안되고 동작시에 치명 에러

1

다차원 배열 인덱스 순서

배열의 인덱스 순서를 바꾸어 쓰는 경우

동적계획법 등에서 문제 발생 가능

인덱스 순서 등은 프로그램 내에서 동일하게 정의

(10)

2

^{연산 관련 실수}

연산자 우선 순위

시프트 연산자, 비트 연산자 주의

if (b & 1 == 0)

==가 순위가 제일 높음

è if (b&(1==0)) 항상 거짓

2

Off-by-one 오류

계산의 큰 줄기는 맞지만 하나가 모자라거나 많음

100미터 담장에 10미터 간격 기둥은 몇 개? è 11개

< >연산자와 ≦≧ 연산자 혼동

(11)

2

산술 오버플로우

변수에 담을 수 있는 크기 제한

정당한 알고리즘이 예상과 다르게 동작

자료형의 표현 가능한 범위를 벗어나는 경우

2

산술 오버플로우 피해가기

32비트 자료형을 벗어나 결과가 너무 큰 경우

계산 중간 값이 너무 큰 경우도 고려

결과 값이 큰 것으로 예상되면 64비트 자료형 활용

è 32비트를 벗어나는 경우 마지막 32비트만을 저장

(12)

2

예외 처리

예상한 입력 규칙에 들어 맞지 않는 입력

최대, 최소, 0 등 경우의 수를 고려 (경계값 조건)

1

예외 처리

bool isPrime(int n) {

if (n % 2 ==0 ) return false;

for (int i =2; i <n; ++i)

if (n % i ==0) return false;

return true;

}

(13)

3

^{변수 관련 실수}

전역변수와 지역변수

전역변수는 꼭 필요한 경우만 활용

전역변수와 지역변수 명은 다르게 명명

3

전역변수와 지역변수

int g_mode;

void doSomething() { g_mode = 2; }

int main() { g_mode = 1;

doSomething();

if (g_mode == 1) std::cout << "No threat detected.\n";

else std::cout << "Launching nuclear missiles...\n";

return 0;

(14)

3

변수 초기화

변수 초기화를 빼먹게 되는 경우 다른 동작

디버깅에 어려움

3

상수 오타

컴파일러가 잡아주지 못하기 때문에 디버깅 어려움

큰 상수를 잘못 쓸 때 è 100000007

소수점이나 지수 값 등을 잘못 쓸 때

(15)

자주 하는 실수

1

핵심 키워드

자주 하는 실수

(16)

3차시

디버깅과 테스팅

학습목표

테스팅 및 디버깅 의 주요 개념과 특성 을 이해 할 수 있다.

1

(17)

1

^테스팅

컴퓨터가 정확하게 동작하지 않는 것

C

대부분 사람의 실수에 의한 것C

오류는 항상 존재할 수 있음

오류

1

^테스팅

프로그램을 실행하여 명세서에 기록된 내용과 일치 하는지 비교

C

다양한 사용환경의 모든 경우의 수 테스트는 불가능C

효율적인 경우의 수를 가지는 테스트 케이스 중요

테스팅

(18)

1

^테스팅

Validation ^& Verification

고객이 원하는 대로 SW 동작

베타 테스트, 사용성 테스트, 인수 테스트

Validation (확인)

명세서 대로 SW 동작

기능 요구사항, 비기능 요구사항 (단위, 통합 테스트)

Verification ^(검증)

1

^테스팅

프로그램의 내부 구조를 아는 경우에 시행 구조 테스트, 경로 테스트C

프로그래머가 직접 테스트 수행

화이트박스 테스트

(19)

1

^테스팅

프로그램 경험이 필요 없음

C

모든 요구사항과 예상결과가 명세서로 주어짐C

주어진 입력에 의해 결과가 일치하는지 확인

블랙박스 테스트

1

^테스팅

모든 입력에 대해 테스트 불가능 è경우의 수 추출

C

경계선에 있는 값, 경계선 바깥쪽 값C

경계선 안쪽에 있는 값

경계값 분석

(20)

1

^테스팅

경계값 분석 사례

1

^테스팅

(원래 의미) 건물 짓거나 보수할 때 임시 구조물 다른 코드를 개발할 때 활용 하는 임시코드C

코드 테스트 및 결과를 확인할 때 유용

스캐폴딩 Scaffolding

(21)

1

^테스팅

스캐폴딩 사례 소스코드

int main() { while(true) {

int n = rand() % 100 + 1;

vector<int> input(n);

for(int i = 0; i < n; ++i) input[i] = rand();

vector<int> mySorted = input;

mySort(mySorted);

vector<int> reference = input;

sort(reference.begin(), reference.end());

if(mySorted != reference) { cout << "Mismatch!"

2

^디버깅

프로그램의 오류를 정정하여 정상동작 하도록 만듦

C

프로그램을 따라가보며 변수 값의 변동을 모니터링C

프로그램을 만드는데 가장 많은 시간 소요

디버깅 ^Debugging

(22)

2

^디버깅

에러 메시지를 정확하게 파악할 것

C

에러 로그나 디버거를 활용하여 중간 결과를 확인C

오타에 유의 (글꼴 등의 문제도 발생 가능)

디버깅 방법

2

^디버깅

작은 입력에 대해 실행을 확인

단정문(assertion) 활용 è거짓일 때 오류C

계산 중간 결과를 출력 è 반드시 필요한 것만 활용

효율적인 디버깅

(23)

디버깅

1

테스트

2

확장하기 1

프로그래밍을 잘 하는방법

https://medium.com/@ghilbut/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D%E C%9D%84-%EC%9E%98%ED%95%98%EB%8A%94-5%EA%B0%80%EC%A7%80-

%EB%B0%A9%EB%B2%95-1-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%99%80-

%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-

%EA%B3%B5%EB%B6%80%ED%95%98%EA%B8%B0-ebf3a3f79ee2

확장하기 2

SW 테스팅의 필요성

http://eunguru.tistory.com/146

확장하기 3

디버깅 방법

http://studyc.tistory.com/11

(24)

참고문헌

• http://www.parkjonghyuk.net/lecture/2017-2nd-lecture/computational/CT09.pdf

• https://medium.com/@ghilbut/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98

%EB%B0%8D%EC%9D%84-%EC%9E%98%ED%95%98%EB%8A%94- 5%EA%B0%80%EC%A7%80-%EB%B0%A9%EB%B2%95-1-

%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%99%80-

%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-

%EA%B3%B5%EB%B6%80%ED%95%98%EA%B8%B0-ebf3a3f79ee2

• http://eunguru.tistory.com/146

• http://studyc.tistory.com/11

알고리즘과 문제해결