1편 알고리즘 문제 풀이를 위한 전략

문제를 풀면서 무엇이 부족한지 모르기에 좀 더 절차적으로 접근

1. 알고리즘 문제 해결을 위한 전략

1) 문제를 읽고 이해하기

- 문제가 원하는 바를 완전히 이해

- 사소한 제약조건, N값의 범위, 메모리 크기

2) 문제를 익숙한 용어로 재정의 = 재정의와 추상화

- 문제를 직관적으로 이해하기 위한 발판

- 문제의 본질만 남기고 축약 => 어떤 부분을 추상화할 것인를 선택하는 작업, 문제를 재정의하는 방법들에 대한 고찰

3) 계획 세우기

- 문제를 어떤 방식으로 해결할지, 사용할 알고리즘과 자료구조 선택

※ 문제 해결 전략 => 체계적인 접근

- 비슷한 문제를 풀어본 적이 있는가? => 원리를 이해하고 변형할 수 있는 능력

  문제의 목적을 보고 적절한 접근법을 선택하기 위해서는 문제를 분류(최적화, 경우의 수, 검색 등)하고, 각 알고리즘들이 어느 경우에 사용될 수 있는지

- 단순한 방법 => 점진적으로 개선점을 찾아가는 방법

- 수식화

- 문제를 단순화

- 그림으로

- 문제를 분해

- 뒤에서 부터 시작

- 순서를 강제

- 특정 형태의 답만 고려(답이 여러개가 나올 수 있는 경우)

4) 계획 검증하기

- 빅오, 메모리

5) 계획 수행하기

- 구현에서 유의점과 좋은 프로그램 작성

※ 좋은 코드 짜기

- 간결한 코드 - 전역변수(대회 한정)

- 코드 재사용 - 모듈화 : 항상 깔끔하게 작성하고 그것이 습관이 되도록 노력

- 표준 라이브러리 공부

- 항상 같은 형태로 프로그램 작성 - 행열, 범위, for 등

- 일관적이고 명료한 명명법 사용

- 자료를 정규화 - 각도, 시간, 분수 등 : 정규화는 프로그램이 자료를 입력 받거나 계산하자마자 바로 시행하는 것이 좋음

- 코드와 데이터 분리

  fig1 코드 처럼 데이터를 코드 안에 넣기 보다는 fig2 처럼 논리와 상관없는 데이터는 상수화

string getMonthName(int month){
   if (month == 1) return "January";
   if (month == 2) return "February";
   ...
   return "December";
}

<fig1>

const string monthName[] = { "January", "Fabruary", ..., "December" };

<fig2>

코드와 상관없는 데이터 부분은 따로 분리. 맵에서 움직일 수 있는 위치 보다 움직일 수 있는 상대좌표를 이용하는 것이 좋음

단, 오타 조심

※ 자주하는 실수

- 산술 오버플로우

  int를 벗어나는 큰 결과 또는 중간값 : 자료형을 변경, 중간값의 수식을 변경하여 초과하지 않도록 함

  무한대 - 987654321 : 2^30에 가까운 수로 어느 정도의 수가 더해지더라도 오버플로우가 안생김

  자료형의 프로모션 - 보통 부호있는 값과 없는 값이 계산될 때 : 특히 벡터의 사이즈는 부호없는 size_t를 반환함

  실수 연산 - 안쓰는게 제일 좋음. 써야 한다면 값을 늘려서 정수형으로 변환. 그것도 안되면 그냥 크게 잡는게 좋음(부동 소수점의 유효숫자)

- Out of Index

- 상수 오타

- 스택 오버플로우 - C++의 경우 지역 변수로 선언한 배열이나 클래스 인스턴스가 스택을 사용하기 때문에 조심. 그냥 전역이 제일 좋음

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

- 최대, 최소 예외

- 연산자 우선순위

- 변수 초기화 - 입력 예제를 똑같은걸 두번 쓰면 어느 정도 피할 수 있음

- 계산 중간 결과를 출력하는 것이 디버깅을 덜 돌리게 함

6) 회고하기

- 문제를 풀 때마다 코드와 함께 자신의 경험을 기록

- 문제의 간단한 해법 + 어떤 방식으로 접근했는지 + 문제 해결을 위한 결정적 깨달음

- 오답 원인

=> 나중에 읽으면서 그때 뭘 배웠는지 되새김. 문제들 간의 공통 해법 등 파악하는데 좋음

- 다른 사람의 코드

다음 2편은 빅오에 대해

- 해당 내용은 종만북에서 가져옴 -

- 알고리즘 문제 해결 전략 1편 중 -

- 저작권 문제시 삭제하겠습니다 -