알고리즘 문제 해결 전략 I (1)

알고리즘 문제 해결 전략 I  (1)

프로그래밍은 곧 문제 해결이다. 

 

프로그램이 사용할 수 있는 최대 메모리와 사용자가 답답해 하지 않게 하기 위한 시간제한 유의, 재사용성이 높은 간결한 코드 작성.

 

많은 제약조건과 요구사항을 이해하고 최선의 방법을 찾아내는 능력이 프로그래머에게 필요.

 

파인만 알고리즘

1. 칠판에 문제를 적는다.

2. 골똘히 생각한다.

3. 칠판에 답안을 적는다.

 

◆ 문제 해결 과정을 단계별로 나누는것이 point

 

문제를 적는 단계 = 자신의 언어를 이용하여 재정의

 

어떻게 문제를 풀것인가 에서 문제 해결 과정 정의

 

1. 문제를 이해한다.

2. 어떻게 풀지 계획을 세운다.

3. 계획을 수행해서 문제를 해결한다.

4. 어떻게 풀었는지 돌아보고 개선할 방법이 있는지 찾아본다.

 

프로그래밍 대회를 위한 여섯단계 문제 해결 알고리즘

 

1. 문제를 읽고 이해 

문제를 잘 읽어 파악하는것이 중요

 

2. 문제를 익숙한 용어로 재정의한다.

재정의와 추상화

추상화란 현실세계의 개념을 우리가 다루기 쉬운 수학적 전산학적 개념으로 옮겨 표현

 

3. 어떻게 해결할지 계획

사용할 알고리즘과 자료구조를 선택

 

4. 계획 검증

수행에 걸리는 시간과 사용하는 메모리가 문제의 제한 내에 들어가는지 확인

 

5. 프로그램 구현

구현이 비효율적이거나 부정확하면 프로그램은 동작하지 않는다는것

 

6. 어떻게 풀었는지 돌아보고 개선할 방법 찾기

더 많은 배움을 얻을 수 있다.

 

7. 문제를 풀지 못했을때

한 문제에 너무 매달려있는것도 좋지 않다. 다른 사람의 소스코드나 풀이를 참조

다만 본인이 풀지 못했던 이유와 복기를 통한 접근방법 되새김 필요.

 

체계적인 접근을 위한 질문들

1. 비슷한 문제가 있는가

2. 단순한 방법에서 시작할 수 없는가

3. 풀이과정을 수식화 가능한가

4. 문제를 단순화 할 수 없는가

5. 그림으로 그릴수 없는가

6. 수식으로 표현 가능한가

7. 문제를 분해할 수 있는가

8. 내제된 순서를 바꿔 볼 수 있는가

 

코딩과 디버깅에 관하여

좋은 코드를 짜기위한 원칙

1. 간결한 코드작성

전역변수의 광범위한 사용 자제 등

매크로를 사용한 간결한 코드 작성

 

2. 적극적인 코드 재사용

 

3. 표준 라이브러리 공부 

큐나 스택과 같은 자료구조 혹은 정렬 등의 기초적 알고리즘 검증된 라이브러리의 코드 사용

 

4. 항상 같은 형태로 프로그램 작성

 

5. 일관적이고 명료한 명명법 사용

모호하지 않은 변수명과 함수명 사용

표준라이브러리에서 상요하는 명명규약 사용

 

6. 모든자료 정규화 저장

입력받거나 계산하자마자 곧장 정규화 수행

입력받는 유리수를 약분된 기약분수 표현 (버그방지)

각도를 입력하는 방식 정의

 

7. 코드와 데이터의 분리

 

자주하는 실수

산술오버플로

배열범위밖 원소에 접근

 - 배열의 원소에 접근할 때 해당 인덱스가 배열범위 안에 있는지 확인해주지 않음

일관되지 않은 범위 표현방식 사용

off-by-one 오류

 - 100미터의 담장에 10미터 간격의 울타리 기둥을 세울 때

컴파일러가 잡아주지 못하는 상수 오타

스택오버플로

 - 콜스택이 오버플로해서 프로그램이 강제 종료되는것

 - 대게 재귀호출의 깊이가 깊어진것이 원인

 - 자동으로 힙에 메모리를 할당하는 STL 컨테이너 사용 혹은 전역변수 사용

다차원 배열 인덱스 순서 바꿔 쓰기

 - 참조변수 사용 해결

잘못된 비교 함수 작성

최소, 최대 예외 잘못 다루기

연산자 우선순위 

 - 연산자의 우선순위들을 잘 기억해두거나 괄호로 적절히 감싸는 것 필요

 

너무 느린 입출력방식 선택

 - C++의 경우 gets()를 이용 모든 입력을 문자열 하나로 파싱, cin 등 고수준 입력방식 사용

 - 고수준 입출력방식이 속도저하를 일으킬 수 있다. (변수의 수가 1만개가 넘어간다면 주의)

 

변수 초기화 문제

프로그램의 한번만 실행 및 한번에 여러개의 입력에 대한 답을 처리 요구

 - 전역변수값을 초기화하는 과정이 필요.

예제 입력파일을 두번 반복하여 사용하여 예방 (의존관계때문에 나오는 답들을 체크할 수 있음)

 

디버깅과 테스팅

프로그램 없이 디버깅하는 연습이 필요

1. 단정문의 사용. 주어진 조건이 거짓일 때 오류를 내고 프로그램을 강제 종료시키는 함수 또는 구문을 의미.

2. 프로그램의 계산 중간 결과를 출력

3. 디버거 사용

 

답안을 작성한 이후에는 제출 전 예제 입력을 만들어 가능한 많이 프로그램을 테스트하는것이 좋음.

 

변수 범위의 이해

산술 오버플로

어떤 식의 계싼 값이 반환되는 자료형의 표현 가능한 범위를 벗어나는 경우

무한대를 표현하기 위한 정수값으로 987,654,321 을 사용 (오류가 나도 쉽게 확인)

오버플로 예방 방법

 - 연산 순서의 변경

 - 자료형의 확장

 

자료형의 프로모션

피연산자의 자료형이 다르거나 범위가 너무 작을 때, 같은 자료형으로 변환하여 계산함

이를 프로모션이라고 함

 

사칙연산이나 대소 비교 등의 이항 연산자들은 두개의 피연산자를 가짐

이때 C++에서의 규칙

한쪽은 정수형 한쪽은 실수형일 때 : 정수형이 실수형으로 변환

양쪽 다 정수형이거나 양쪽 다 실수형일 때: 더 넓은 범위를 갖는 자료형으로 변환

양쪽 다 int 형보다 작은 정수형인 경우 : 둘다 int 형으로 변환

부호 없는 정수형과 부호 있는 정수형이 섞여 있을 때 : 부호없는 정수형으로 변환

 

 

 

 

 

 

알고리즘 문제 해결 전략 I 中 

2020.07.06