알고리즘 문제 해결 전략 : (1) 문제 해결 시작

다양한 분야의 개발자가 존재하지만, 이런 분야 간의 차이를 뛰어넘는 좋은 개발자의 조건이 존재할까?
Algorithm 소스 GIT

문제 해결

• 문제 해결 능력 이란? 제약 조건과 요구사항을 이해하고 최선의 방법을 찾아내는 능력

• 공부 순서

️ 장 번호	장 제목 ️
3	문제 해결 전략
4	알고리즘의 시간 복잡도 분석
6	무식하게 풀기
7	분할 정복
8	동적 계획법(DP)
18	선형 자료 구조
19	큐와 스택, 데크
21	트리의 구현과 순회
22	이진 검색 트리
23	우선순위 큐와 힙
27	그래프의 표현과 정의
28	그래프의 깊이 우선 탐색(DFS)
29	그래프의 너비 우선 탐색(BFS)
30	최단 경로 알고리즘

• 대회 준비를 위한 조언
  • 가능한 많은 문제 풀기 : 중요한 주제를 먼저 공부한 후, 가능한 많은 문제를 풀어보는게 좋다.
  • 온라인 사이트 이용 & 프로그래밍 대회 참가

문제 해결 개관

문제 해결 과정

모든 문제를 해결할때 단계별로 접근하는 것이 좋다.

1) 문제를 읽고 이해한다. * 조급한 마음에 문제를 대충 읽거나 유추하는 우를 범하지 말자.

2) 문제를 익숙한 용어로 재정의한다. * 문제를 자신의 언어로 만들자. 즉 추상화를 하자. * 문제의 본질을 파악한후 재 정의하자.

3) 어떻게 해결할지 계획을 세운다. * 해결 방안에 대해 강구하자.

4) 계획을 검증한다. * 알고리즘의 효율성(시간복잡도, 공간복잡도 등) 분석과 알고리즘의 정당성 증명을 하자.

5) 프로그램으로 구현한다. * 최대한 간단하게 구현하도록 노력하자.

6) 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아본다. * 맞춘 문제는 배운점을 정리하고, 틀린 문제는 오답 원인을 꼭 확인하자.

초보 시절에는 일정 시간이 지나도록 문제를 못풀때는 다른 사람의 소스 코드나 풀이를 참조 하는것이 좋다.

문제 해결 전략

• 직관과 체계적인 접근(힘드니까 아래 처럼 따라해 봐라)을 통해 문제를 해결 해라.
• 비슷한 문제를 풀어본 적이 있던가?
  • DP, DFS, BFS 등과 같이 비슷한 방식과 표준 알고리즘을 대입하자.
  • 허나, 동작 과정과 원리를 완전히 이해하지 못하면 조금만 변형되면 망한다.
• 단순한 방법에서 시작할 수 있을까?
  • ex) 완전탐색 으로 시작해서 중복 탐색(DP)이 되는 부분 혹은 탐색을 할 필요가 없는 부분을 삭제하여 시간복잡도를 줄인다.
• 내가 문제를 푸는 과정을 수식화 하자!
  • 손으로 문제를 풀어보자
• 문제를 단순화 하자!
• 문제를 분해해 보자!
  • 복잡한 조건을 단순한 형태의 여러개로 나눠서 생각하자.
• 뒤에서 부터 생각해서 풀수 있을까?
  • 결과에서 부터 역으로 올라갔을때 쉽게 풀리는 문제들이 존재한다.
  • ex) 사다리 타기
• 순서를 강제해서 생각해보자!
  • 사고를 도와주기 위한 도구로 나만의 제약을 걸어두고 생각하자.
  • ex) 탐색순서를 왼쪽에서 오른쪽으로만
• 특정 형태의 답만을 고려할 수 있을까?
  • 순서를 강제하는 기법의 연장선인 정규화(canonicalization)기법

코딩과 디버깅에 관하여

코딩의 중요성을 간과 말라

보통 알고리즘을 해결한 후에는 사용된 코드를 재사용할 일이 거의 없지만(점수 반영에도 상관 없다.), 실력 향상을 위한 방법은 읽기 쉬운 코드를 작성하는것 이다.

좋은 코드를 위한 원칙

• 간결한 코드 작성하기
  • 전역변수 사용
• 적극적으로 코드 재사용하기
  • 중복 코드들 클래스를 활용하여 분리
  • 함수를 활용한 역할 분할(한 함수는 한가지 일만 수행한다.)
• 표준 라이브러리 공부하기
  • 큐,스택 과같은 자료구조 혹은 정렬 등을 직접 작성하는 것은 멍청한 짓
  • 기본적인 표준 라이브러리 파악 : 언어의 문자열, 동적 배열, 스택, 큐, 리스트, dict/map, 정렬 등은 알아 두자 알고리즘에 필요한 JAVA 표준 라이브러리는 따로 정리하겠다.
  • 항상 같은 형태로 프로그램 작성하기
    • 본인만의 검증된 코딩방식을 만들어 두자
  • 일관적이고 명료한 명명법 재사용하기
    • 함수명, 변수명 등을 의미있게 만들자(디버깅시 힘들다)
    • ex) bool isInsideCircle(~)
  • 모든 자료를 정규화해서 저장하기
    • 각도 같이 애매한 값들(-330도, 30도 | 시간)은 본인만의 표준을 만들자
  • 코드와 데이터를 분리하기
    • 상하 좌우 움직이기
      int[] moveDx = {-1,-1,1,1}
      int[] moveDy = {1,-1,1,-1}

자주 하는 실수

• 산술 오버플로
• OutOfIndex
• 일관되지 않은 범위 표현 방식 사용
• 스택 오버플로
  • 재귀 호출시 스택 최대 크기 고려 해야함 -> Solution :전역변수 사용
• 다차원 배열 인덱스 miss
• 잘못된 비교함수 작성(대,소)
• 최소, 최대 예외 잘못 다루기
  • 최솟값, 최댓값의 상황을 고려하기
• 연산자 우선순위 잘못 쓰기
  • 모르겠으면 그냥 괄호 써..
• 너무 느린 입출력 방식 선택 언어마다 빠른 입출력이 있다. 숙지하자
• 변수 초기화 문제
  • 입력 예제의 수를 먼저 주는 문제들이 있는데, 계산 다시하게 될때 init 잊지말자

디버깅과 테스팅

디버거 없이 디버깅 하는 연습을 꼭 해야한다. 이게 가능하기 위해서는 Clean 한 코드를 짜는것은 필수 적이다.(변수 명명, 간결성, 함수/클래스 활용)

• 디버깅 Tips
  • 작은 입력값에 대해 제대로 실행되나 확인
  • 단정문(assertion) 사용
    • 단정문 : 잘못된 상황에서 프로그램을 강제로 종료 시키는 구문
  • 프로그램 중간마다 계산결과 출력 : 내 예상과 비교 스캐폴딩(scaffolding)-임의의 값들을 대입하는 프로그램을 만듬.. 개인전 대회에서는 무리 같다.

변수 범위의 이해

• 산술 오버플로 고려
  • 너무 큰 무한대 값으로 987,654,321 사용 - 오타 염려 적다.
  • 오버플로 피하기 : 형변환 해주기, 연산 순서 바꾸기
• 자료형의 프로모션
  • 자동으로 형변환 되는 상황에서 오류가 생길수 있다.

실수 자료형의 이해

• 실수 연산의 어려움
  • 1/10 * 3과 3/10은 다르다 - 이진법(부동 소수점)으로 계산을 하게되어 근사값으로 표현 하게 된다.(1/10 * 3 = 0.30000000000000004)
• 실수 비교하기
  • 절대 오차 : 차이가 일정 수치보다 작으면 같다고 본다. (abs(a-b) <1e-10 )
  • 상대 오차 : 오차 한도를 미리 정할수 없을때 사용. (abs(a-b)<=1e-8*max(abs(a),abs(b)) )
  • 둘다 사용하는게 좋겠다.

---

• Previous
  책 소개
• Next
  알고리즘 문제 해결 전략 : (2) 알고리즘 분석 - 시간 복잡도-1

---