[알고리즘] Intro

구종만의 '프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략'을 바탕으로 작성했습니다.

프로그래밍 대회

탑코더, ACM-ICPC, 코드포스

알고리즘 문제 페이지

프로그래머스, 백준, 알고스팟, 탑코더

문제 해결 과정

1. 문제의 이해
   문제를 읽고 정확하게 이해하는 과정
   사소한 제약 조건이라도 잘못 이해하면 풀 수 없게 되는 문제들이 흔함.
   알고리즘 문제의 경우 작은 실수라도 오답으로 처리되므로 가장 중요한 단계

2. 재정의와 추상화
   이해한 문제를 본인이 다루기 쉬운 개념을 이용해 자신의 언어로 풀어 씀
   이를 통해 직관적으로 이해하기 쉬워짐
   또한 문제의 추상화를 통해서 문제의 본질만을 남겨두고 축약한다.
   문제의 본질을 어떻게 생각하냐에 따라 문제를 쉽게 만들 수 있음

3. 계획
   어떤 방식으로 풀지를 결정
   사용할 알고리즘과 자료구조를 선택한다.

4. 검증
   구현을 시작하기 전에 계획을 검증한다.
   설계한 알고리즘이 모든 경우에 대해서 요구 조건을 정확히 수행하는지 증명하고
   수행시간과 사용 메모리등이 문제의 제한 내에 들어가는지 확인

5. 수행
   계획을 바탕으로 코드로 구현한다.

6. 회고
   문제를 해결한 과정을 돌이켜보고 개선하는 단계
   문제 해결에는 영향이 없지만 장기적으로 도움을 받을 수 있음
   효과적인 방법으로는 접근 방식, 깨달음, 오답원인 등등을 기록한다.
   
   

문제 해결 전략

많은 문제에 적용될 수 있는 생각부터 정렬

• 비슷한 유형 확인
  형태 혹은 목표가 비슷하거나 관련된 문제를 풀어봤었다면 이전과 비슷하게 접근 방법일 거라 기대할 수 있다.
  하지만 해당 알고리즘을 동작 과정과 원리를 완전히 이해해야지 비슷한 문제에대해서 응용할 수 있다.

• 단순한 방법으로 시작
  이후에 소개될 방법 중 하나인 무식하게 풀기의 방식처럼 시간과 공간 제약을 생각지 않고 문제를 해결할 가장 단순한 알고리즘을 만들어 보는것이다.
  이 전략의 목표는 간단한 문제를 어렵게 푸는 실수를 예방할 수 있다.
  문제가 단번에 풀리지 않더라도 자료구조 또는 계산 중복등을 최적화해서 알고리즘을 개선하는 식으로 문제를 풀 수 있다.
  동적 계획법과 연관이 있다.

• 과정 수식화
  손으로 여러 간단한 입력을 직접 해결 해보는 것이다.
  직접 문제를 해결한 과정을 공식화해서 문제를 풀 아이디어를 얻을 수 있다.

• 문제를 단순화
  주어진 문제를 좀더 쉽게 변형을 한다.
  제약 조건 제거, 계산 할 변수의 수 축소, 다차원 문제를 1차원으로 줄여서 표현하는 등 단순화된 문제의 해법이 원래 문제의 해법에 대한 직관을 제공할 수도, 직접적으로 이용할 수도 있다.

• 그림으로 표현
  해법에 대한 직관을 얻을 수 있도록 문제와 관련된 그림을 그려보는 것
  수의 나열보다 기하학적인 도형을 더 직관적으로 받아들이기 쉽기 때문에
  꼭 기하학을 다루는 문제가 아니더라도 유용하게 쓰일 수 있다.

• 수식으로 표현
  평문으로 쓰여 있는 문제를 수식으로 표현
  수식을 전개하거나 축약하는 등 수학적 조작이 문제를 해결하는데 도움을 줄 수 있다.

• 문제 분해
  더 다루기 쉽도록 제약 조건등을 분해하는 방법
  복잡한 조건을 더 단순한 형태를 갖는 조건의 집합으로 분해함으로써 다루기 쉽게 함

• 뒤에서부터 생각
  문제에 내재된 순서를 거꾸로 바꿔보는 방법
  예시로 사다리타기에서 원하는 것을 선택하려면 아래에서부터 올라와서 확인하는 방법이 가장 빠른 방법이다.

• 순서 강제
  순서가 없는 문제에서 순서를 강제해 문제를 푸는 방법
  답에 영향을 끼치지 않는 순서를 강제한 제약을 스스로 추가함으로써 문제의 접근 방식을 제한해 푸는 경우의 수를 줄일 수 있다.

자주 하는 실수

• off by one
  계산은 맞지만 하나가 모자라거나 많아서 틀리는 오류
  반복문에서 >, < 등의 연산자와 ≥ ≤연산자를 혼동하거나 반 열린 구간과 닫힌 구간을 서로 혼용해 쓴 경우 발생한다.
  방지하는 방법으로는 최소 입력이 주어졌을때 코드의 동작 방식을 생각해보며 프로그램을 짜는 것이다.

• 스택 오버플로
  재귀 호출의 깊이가 너무 깊어져 프로그램이 강제종료되는 오류
  C++의 경우 스택메모리를 사용하기에 오류가 나기 쉽기에 STL 컨테이너를 사용하거나 전역 변수를 사용하는 방법을 쓸 수 있다.

• 최대, 최소 잘못 다루기
  예상한 입력에 대해 예외를 제대로 처리하지 못한 경우
  가능한 입력 중 최소 또는 최대 값을 예외처리 해야 되는 문제가 많으므로 이에 대해 제대로 동작할지를 생각해 오류를 잡을 수 있다.
  예시로 자연수를 입력받을때 소수인지를 판별하는 문제에서
  1과 2는 일반적인 소수의 판별 방식과 조금 다르기에 예외로 두고 처리해야한다.

• 너무 느린 입출력 방식
  텍스트를 입출력하는 방법은 다양하지만 이 방법에 따라 속도의 차이가 발생한다.
  입력으로 받거나 출력해야 할 변수의 수가 만개를 넘어가면 고려해봐야할 사항이다.

• 오버플로
  너무 큰 값을 다룰 때 계산의 중간 과정 혹은 마지막에 결과를 계산할 때 오버플로우가 발생해 값이 달라지는 경우
  제한사항에 얼마를 나눈 나머지를 결과값으로 한다를 보고 힌트를 얻을 수도 있다.
  이에 대해서 큰 자료형으로 캐스팅 하거나 제한사항의 나머지 계산을 중간 과정에도 적용한다.

• 자료형 프로모션
  암시적, 묵시적 형변환이라고도 표현한다.
  대부분의 경우 신경 쓸 필요가 없지만 가끔 알기 어려운 버그를 만들 수도 있다.

시간 복잡도

알고리즘의 속도는 반복문이 지배한다.
상수의 경우 반복 횟수가 커질 수록 그 영향이 적어지기 때문이다.
따라서 대개는 반복문이 수행되는 횟수로 수행시간을 표현한다.

Big-O Notation

주어진 함수에서 가장 빨리 증가하는 항만을 남긴 채 나머지를 다 버리는 표기법

O 표기법은 대략적으로 함수의 상한을 나타낸다.
여기에서 상한이란 N이 커질 수록 가장 빨리 증가하는 항과 나머지를 포함하는 항과 큰 차이가 나지 않기때문에 상한이라 표현한다.

예를 들어 다음과 같은 버블 정렬이 있다면

def bubble_sort(arr):
    for i in range(len(arr) - 1, 0, -1):
        for j in range(i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

N만큼 반복하는 반복문이 두 번 중첩되어 있기에
O(N²)이라 표현한다.

대략 1초당 반복문 수행 횟수가 1억을 넘어가면 시간 제한을 초과할 가능성이 있다.