알고리즘 문제 해결 전략 1 - 문제 해결 시작하기(1~86page)

 

 본 포스팅은 블로거가 개발언어의 개념정리 필요를 위한것입니다.

목차와 차례가 뒤죽박죽이며 오직 블로거의 편의목적을 위해 작성되었음을 알려드립니다. 

- 책의 개관

- 우리나라 개발의 문제점

- 프로그래밍 대회에서 배울수 있는것

- 대회

- 대회준비

- 문제 해결 개관

- 문제 해결 전략

- 코딩의 중요성을 간과하지 말라

- 자주 하는 실수

- 디버깅과 테스팅

- 변수 범위의 이해

- 실수 자료형의 이해

- 더 읽을거리

 

 

 

- 책의 개관

 

 현대의 컴퓨터 과학 교육이 실제 학문이 발전하는 방향의 반대 순서로 이루어져 있기 때문에 응용능력을 기를수 없다.

그래서 '잘하는 사람과 못하는 사람의 생산성이 스무 배'라는 말이 나온다.

결국 이 문제는 직관의 의존하는 문제로 이어지게 된다.

말이 좋아서 직관이지 실제로는 때려 맞추기에 가까운 수준이다.

 

 다익스트라 알고리즘이 생겨난 배경과 이 알고리즘을 설계하는 데 필요했던 결정적 통찰을 얻을수 있게 도와주고 지식을 자신의 것으로 만들어 학문이 생겨난 과정에서 일어난 발견과 깨달음을 학생들이 되짚을수 있어야한다.

 

 

- 우리나라 개발의 문제점

 

 개발방법들은 배워나갈수 있지만 이들을 조합하는방법에 대해서는 배울수 없다. 결국 아까 말한 다시 직관으로 돌아간다. 여기서 말하는 직관이란 근거없는 때려맞추기이다.

 

 

- 프로그래밍 대회에서 배울수 있는것

 

 1. 문제를 해결하는 데에만 집중

 2. 알고리즘을 베껴쓴다고 해결할수없어 원칙들을 이해하고 변형해야 풀수 있기에 이해력이 상승한다.

 3. 정답과 오답이 명확하게 가려짐

 4. 프로그램의 효율성에 미치는 영향 직접 경험가능

 5. 좋은 코드를 작성하는 토대가 마련됨

 6. 고수 프로그래머들이 짠 코드를 직접보고 비교해보며 기준을 잡을수 있음

 

 

- 대회

 

 ACM-ICPC(대학생), TopCoder(실무진들 포함한 대회), Google Code Jam(전세계적 가장 인기있는 대회)

모의고사

 : topcoder, codeforces, uva.onlinejudge

 

 

- 대회준비 

 

 가능한 한 많은 문제 풀기, 채첨사이트 이용(백준, 알고스팟, USACO, 탑코더, ACM-ICPC, Euler, SPOJ)

 팀단위로 참가할 경우 > 디버깅은 항상 눈으로 할수 있도록 연습(디버깅 할 시간,공간제약이 크기때문)

 

 

- 문제 해결 개관

 

 파인만 문제해결법 + How to Solve It의 병합하여서 다음과같은 문제해결과정을 거쳐야함

아래 6단계는 경험에 쌓임에 따라 의식적으로 하지 않아도 수행할수 있지만 초반에는 필요함

1. 문제를 읽고 이해한다.

 -> 문제를 잘못읽는 실수와 성급하게 문제를 유추하지 말기

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

 -> 수학적/전산학적 개념으로 표현, 이 과정을 통해 난이도 상 -> 하로 만들수도 있음

3. 어떻게 해결할지 계획을 세운다. (흔히말해 생각하는것)

 -> 어떤방식, 알고리즘, 자료구조 선택, 시간소요가 제일 큰과정

4. 계획을 검증한다.

 -> 시간과 메모리 사용량 검증

5. 프로그램으로 구현한다.

 -> 알고리즘 구현이 부정확하거나 비효율적인지 확인하면 구현

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

 -> 회고하며 피드백하고 더 나은 해결방법이나 코드는 없었는지 고민

 -> 문제 해결의 결정적이였던 깨달음이나 해법,방식을 오답노트로 작성하기

 

문제를 풀지 못할때

 -> 초보시절에는 너무 많은 시간 소요는 독이 된다.

 -> 왜 문제를 못풀었는지 자세하게 살펴봐야됨

 

 

- 문제 해결 전략

 

 직관보다 -> 체계적인 접근으로 해결하는것이 후에 진짜 직관을 늘릴수 있음

체계적인 접근에는 다음과 같은 방법이 있고

이는 '어떻게 문제를 풀 것인가(How to Solve It)'이라는 문제 해결 분야의 고전에서 나온 전략들을 참고한것

1. 비슷한 문제를 풀어본적이 있는가.

2. 단순한 방법에서 시작할 수 있을까?

 -> 시간, 공간제약없이 무식하게 풀다보면 문제를 푸는 기준이나 힌트를 찾을수 있음

3. 내가 문제를 푸는 과정을 수식화할 수 있을까?

 -> 손으로 풀어보기

4. 문제를 단순화할 수 없을까?

 -> 보통 문제들이 단순한 문제에서 연장된 문제이기 때문에 이 부분을 고려하면 핵심을 파악가능

5. 그림으로 그려 볼수 있을까?

 -> 인간의 사고체계는 기하학적 도형이 더 직관적으로 받아 들여짐

6. 수식으로 표현할 수 있을까?

 -> 숫자로 표현

7. 문제를 분해할 수 있을까?

 -> 더 다루기 쉬운 형태로 문제를 변형(아마 다른 유형으로 생각해볼수 있지 않을까를 말하는건가 싶음) 

8. 뒤에서부터 생각해서 문제를 풀 수 있을까?

 -> 예를들면 사다리 타기에서 거꾸로 올라가면 길을 쉽게 찾을수 있음

9. 순서를 강제할 수 있을까?

 -> 대부분의 경우 답을 만들기 위해 할 수 있는 일들의 순서를 강제화 하기(제약조건을 강제로 추가해보라는뜻)

10. 특정 형태의 답만을 고려할 수 있을까?

 -> 정규화를 하여서 무한한 후보들중에서 유한한 후보들의 집합만을 고려할수있게함

 -> 정규화는 어렵기 때문에 아마 경험을 통하지 않으면 깨닫기 쉽지 않음

 -> 아마 내 생각에 정답이 되는 후보가 하나 있다면 그 후보를 변형시켜서 특징을 잡는다거나 아니면 정답이 되는 후보들의 양극단의 특징점을 잡거나 해당 후보들의 공통적인 특징을 파악한다는 포괄적인 뜻같음

 

 

- 코딩의 중요성을 간과하지 말라

 

당장 빨리 코드를 작성하기 보다 읽기 쉬운 코드를 작성하는것이 중요하다.

상위 입상자들의 코드에서 시간에 쫓겨 작성한 흔적을 찾기란 쉽지 않다.

 

- 좋은 코드를 짜기 위한 원칙

 

1. 간결한 코드를 작성하기

 -> 프로그래밍 대회에서는 전역변수의 광범위한 사용(실무에서는 불가)

 -> 자바,c#에서는 foreach, c++에서는 매크로사용을 권함. 다만 이것은 '흑마법'과 같이 잘 신중하게 사용해야함

2. 적극적으로 코드 재사용하기

 -> 시간이 없다고 해서 코드를 더 알기 쉽게 고치는 데 주저해서는 안 된다.

 -> 대회에서는 하나의 함수가 두가지 일을 수행할수도 있음(실무나 프로그램에서 추구하는 이상적인 일은 아님)

3. 표준 라이브러리 공부하기

 -> 기초적 알고리즘을 직접 작성하는것은 크나큰 실수

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

 -> 한번 검증된 알고리즘이나 코드를 작성하고 이것만을 꾸준히 사용할 필요가 있다.

 -> 아마 자주 사용하는건 조금 형식을 외울필요가 있어보임

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

 -> 변수명, 함수명 명료하게 적기(본인이 가장 많이 하는 실수)

6. 모든 자료를 정규화에서 저장하기

 -> 인코딩, 각도, 세계시간 등 표준으로 정규화할 필요가 있음

7. 코드와 데이터를 분리하기

 -> 예를들어서 월을 표시할때 if문으로 열두자리 작성하지 말고 배열로 작성해서 for문 돌리기

 

 

- 자주 하는 실수

 

1. 배열 범위 밖 원소에 접근

 -> 배열 크기를 정할 때 계산을 신중히 하기

2. 일관되지 않은 범위 표현 방식 사용하기

 -> 구간을 표시할때 닫힌구간(<= i <=), 열린구간( < i < )을 사용하지 말고 반 열린 구간( <= i < )를 사용하기

대부분의 프로그래밍 언어가 이런식으로 표현하고 이는 다음과 같이 세가지 장점이 있음

     1. 공집합을 표현가능 ( 2<=i<2 ) 

     2. 두 구간이 연속한지 확인가능 ( [a,b), [c,d) ) 에서 b=c가 입증되면 a,d는 연속

     3. 구간의 크기 쉽게 확인가능. b-a가 구간의 크기

 -> 그리고 한 가지 방법으로만 범위를 표현할 필요가 있음

3. Off-by-one 오류

 -> 하나가 모자라거나 하나가 많아서 틀리는 코드의 오류들을 모두 가리키는것

 -> 최소 입력이 주어졌을 때 이 코드가 어떻게 동작하는지 확인

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

 -> 상수를 잘못입력해서 틀리는 경우가 많음

 -> 오타를 조심하고 64,32비트 잘 구분하여서 사용

5. 스택 오버플로

 -> 재귀호출사용시 얼마나 깊이가 파악

 -> heap사용

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

 -> 특정배열에 접근하는 위치를 하나로 통일하기

7. 잘못된 비교 함수 작성

 -> 자바의 표준라이브러리는 < 연산 대신에 <= 연산을 비교함수의 모델로 쓰니까 조심

 -> 아직 무슨말인지 정확히 이해는 안감

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

 -> 예를들어서 피보나치수열에서 1과 2는 예외항목인데 출력하는경우

9. 연산자 우선순위 잘못 쓰기

 -> if( b & 1 == 0) 에서 1 == 0 이 &보다 연산 우선순위가 높기때문에 사실상 if( b & ( 1== 0)) 으로 표현한거나 마찬가지 그렇기 때문에 괄호로 적절히 감싸기

10. 너무 느린 입출력 방식 선택

 -> cin 같은 고수준 입출력 방식이 저수준 방식보다 두 배 이상 느린 경우도 심심찮게 볼 수 있음

그렇기 때문에 cin을 사용시 동기화를 끄면 빨라지는데 이때 사용하는 코드는 cin.sync_with_stdio(false)를 수행하면됨

 -> 자기가 사용하는 언어의 어떤 입출력이 지원되고 어느 쪽이 빠른지 미리 점검

11. 변수 초기화 문제

 -> 이전 입력에서 사용한 전역 변수 값을 초기화하지 않고 그대로 사용하는 것

 -> 전역변수 문제인지 확인할때는 똑같은 입력을 여러번 주고 다른결과값이 출력되는것으로 확인가능

 

 

- 디버깅과 테스팅

 

1. 디버거없이 버그를 찾아내는 연습 필요

  1) 오동작할것같은 작은값들 입력

  2) 주어진 조건이 거짓이면 프로그램 종료하는 단언문 선언

  3) 실행되는 중간에 로그찍고 확인하기

2. 스캐폴딩(scaffolding) 사용

 -> 스캐폴딩이란 뼈대를 잡기위해 임시로 사용하는 코드를 말한다.

예제를 랜덤으로 입력하게 해주는 코드를 사용하면 신속하게 빨리 오답을 찾아볼수있다.

시간을 잡아먹을수 있으니 필요한 경우에만 가려서 쓰기

 

 

- 변수 범위의 이해

 

1. 산술 오버플로

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

 -> 대부분의 프로그래밍 언어는 별다른 경고를 해주지 않고 논리의 정확성에만 집중할경우 산술 오버플로우

    1.  너무 큰 결과

        -> 큰 정수를 다룰 때는 항상 변수의 형태에 주의하는 습관

    2. 너무 큰 중간 값

        -> 어떤함수가 axb를 진행후에 나누기를 할때 결과적으로는 int범위내에 있어보이지만

         axb 연산중에 이미 int범위를 초과했을 가능성이 있음

    3. 너무 큰 '무한대' 값

        -> 계산상 편리함을 위해 사용하지만 무한대끼리 더해질경우 오버플로우 발생,

         저자는 987,654,321 을 자주이용한다고함(2^30, 더해져도 오버플로우 안남, 10000000 보다 오타가 눈에 더 잘보          임)

2. 오버플로 피해가기

   1. 더 큰자료형 사용

   2. 연산 순서 바꾸기

   3. 점화식으로 바꿀수 있다면 점화식 사용

3. 자료형의 프로모션

unsigned char a = 17;
short b = -18;
int c = 2;
unsigned int d = 0;

cout << (a+b)* c + d << endl;

// 기대한값 : -2
// 출력값 : 4,249,967,294
// 이유
// (a+b) -> int로 변환
// (a+b)*c -> int로 변환
// (a+b)*c+d -> unsigned int 로 변환됨

   -> 기대한 값과 다른값이 출력됨, c++ 은 다음 프로모션을 가지고 있음

        1. 정수 + 실수 => 실수

        2. 정수+정수 Or 실수 + 실수 => 더 넓은 범위를 갖는 자료형으로 변환

        3. 양쪽이 int보다 작은 정수형일 경우 => int로 변환됨

        4. 부호 없는 정수형 + 부호 있는 정수형 => 부호 없는 정수형

bool isSorted(const vector<int>& seq){
	for(int i = 0 ; i < seq.size() - 1 ; ++i)
    	if(seq[i] > seq[i+1])
        	return false;
    return true;
}

     -> 배열이 비어있을 경우 seq.size() == 0이 되고 - 1을 할경우 2^32 - 1이 되어버림

         1. 예외처리

         2. i를 1부터 시작

 

 -> 자바와 C#은 unsigned 부호에 대해서 고려하지 않아도된다. 자바는 아예 unsigned 삭제해버림

 

- 실수 자료형의 이해

 

int countObvious(int n){
	int same = 0;
    	for(int x = 1; x <= n; x++){
        	double y = 1.0 / x;
        	if(y * x == 1.0)
        	    ++same;
        }
    return same;
}

x/1 * x == 1 이 되는 x를 구하는 코드에서 countObvious(50)을 넣으면 50을 리턴해야하지만 실제로는 49라는 값을 리턴함

 

1. 실수와 근사 값

 -> 컴퓨터가 정수를 표현하는데는 정확하지만 소수를 계산시에는 근사값으로 처리하기에 수학적으로 정확하지 않을수 있음

 

2. IEEE 754 표준

 -> 컴파일러들이 사용하는 실수 표기 방식의 표준

 

2.1 이진수로 실수를 표기

2.2. 부동 소수점 표기법

2.3. 무한대, 비정규 수등의 특수한 값이 존재

 

그리고 위의 세가지로 인하여 어쩔수없이 오차가 발생할수 밖에 없고 이를 해결하기 위해서는

1. 오차한도를 정해놓기

2. 상대오차를 사용하기

3. 코드의 수치적 안정성 파악하기

 

이것들은 매우 까다롭고 많은 시행 착오와 경험이 필요한 항목임

 

3. 실수 연산 아예 하지 않기

root{(x1-x2)^2 + (y1-y2)^2} = r  

-> (x1-x2)^2 + (y1-y2)^2 = r^2 로 변형하여서 풀수있는것처럼 실수연산을 사용하지 않고 정수로만 계산하게끔 우회할수있는 방법을 사용하는것이 중요하다고함

 

 

- 더 읽을거리

CleanCode 라는 책을 앞의 몇장만 읽어보아도 좋은 코드를 짜는법을 알려준다고함