알고리즘 문제 접근 방법 및 실수 줄이기

알고리즘 문제 해결 전략 책에서 앞부분 개인적으로 요약 정리해 보았습니다.

접근 방법

1. 무식하게 풀 수 있는지 확인합니다. (문제를 일단 푸는게 우선이고, 나중에 회고를 통해서 더 좋은 알고리즘을 찾습니다.)
2. 문제를 수식화가 가능한지 확인합니다.
3. 문제를 부분 문제로 여러개 나누어 계산이 가능한지 확인합니다. (예 : 팩토리얼)
4. 문제에서 주어진 순서에서 반대로 풀수 있는지 계산이 가능한 문제인지 확인합니다. (예 : 사다리타기)

실수 줄이기

1. 일관된 표현방식 사용

반 열린 구간 을 사용하여 실수를 예방습니다. (열린구간, 닫힌구간 등은 사용을 자제합니다.)

low <= i < high // [low, high) 반열린구간

c++ 의 STL 에서 배열 관련 함수중에 아래 함수들이 있습니다.

std::begin // 배열의 첫번째 원소의 포인터를 반환합니다. 
std::end // 배열의 마지막 원소 다음 위치의 포인터를 반환합니다. 

위와 같이 반열린구간으로 선형 자료구조를 다루는 언어들이 많습니다.

장점

• 공집합 표현이 쉽습니다.

  2 <= i < 2 // 이렇게 사용하면 i는 어떠한 수도 될수 없습니다. 
  

• 아래와 같이 두가지 영역이 있을때 연속되어있는지, 겹쳐져있는지, 떨어져있는지 등의 비교가 쉽습니다.

  a <= i < b // 1번 영역
  c <= j < d // 2번 영역
  // b == c 이면 두 영역은 연속되어있는 부분이며, 1번이 2번 앞에 있습니다.
  // a == d 이면 두 영역은 연속되어있는 부분이며, 2번이 1번 앞에 있습니다.
  

• 구간의 크기를 쉽게 알수 있습니다. [a,b)의 구간에 포함된 자연수의 수는 b-a가 됩니다.

  a <= i < b // [a,b) 반 열린 구간 자연수 갯수 : b - a
  a <= i <= b // [a,b] 닫힌 구간 자연수 갯수 : b - a + 1
  a < i < b // (a,b)열린 구간 자연수 갯수 : b - a - 1
  

2. 순서 강제기법

예를 들어 집합의 갯 수를 계산하는 문제가 있다고 가정할때 원소의 순서가 달라서 다른 집합으로 인식하는 것을 예방하는 것입니다. 집합을 갯 수 계산할때 원소가 오름차순으로 정렬되어있는 것만 계산하는 것입니다

{1,2,3}, {2,1,3} // 원소의 순서는 다르지만 같은 집합입니다. 

3. 배열은 전역변수 사용 (StackOverflow 예방)

c++의 경우에는 지역 변수로 선언한 배열이나 클래스 인스턴스가 기본적으로 stack memory를 사용하기 때문에 stack overflow를 조심해야 합니다. 배열 등의 큰 지역 변수를 스택에 잡으면 재귀 호출이 몇 번 없어도 곧장 스택 오버플로가 나기 쉽습니다. 때문에 대부분의 참가자들은 자동으로 heap 영역에 메모리 를 할당하는 STL 컨테이너(vector, list, set, map 등) 를 사용하거나 전역 변수를 사용하곤 합니다.

4. off-by-one error

int[] arr = new int[4]; // a[0] ~ a[3]
for(int i = 0; i <= 4; i++){  // java 에선 out of index 발생함. 
  arr[i] = 123;
}

위에 코드에 버그가 있는데, for 문 조건에 i <= arr.length 이 부분 때문에 마지막에 arr[4] 를 사용하기 때문에 에러가 발생합니다. 이런한 에러에는 테스트할때 최소, 최대값을 생각하면서 코딩하면 실수를 예방할수 잇습니다. (예: arr.length 의 최대 index 는 3입니다. 그리고 a[3], a[9] 까지의 평균을 계산할때 9-3 으로 나누지 않고, 9-3+1 로 나눈 다는 점등이 있습니다.)

참고서적 - 알고리즘 문제해결 전략(구종만)

참고문서 - 알고스팟 문서