알고리즘 문제 해결 과정

Nov 7, 2022

알고리즘 문제 해결 과정 alpha

• 1. 문제를 읽고 이해한 뒤, 재정의, 추상화 하기
• 2. 문제 해결 계획 세우기
• 3. 문제 해결 검증 하기
• 4. 프로그램 구현 하기
• 5. 회고하기

🗣️ 출처

_ 프로그래밍에서 배우는 알고리즘 문제 해결 전략(구종만 저) 보안 확인 : 외부링크
"https://book.algospot.com/"로 ? _를 참고한 후 내용을 추가한 포스트입니다.

1. 문제를 읽고 이해한 뒤, 재정의, 추상화 하기

문제의 조건과 지문을 읽는다, 이 때 편견이나 성급함으로 잘못 유추하게 되면 치명적이므로 꼼꼼히 읽어야 한다. 의외로 자주 일어나는 실수이다.

이후 문제를 추상화 해야한다.

• 추상화 : 현실 세계 개념을 수학적, 전산학적 개념으로 표현
  이를 통해 간단하고 친숙하게 만들어 적용할 도구를 쉽게 선택할 수 있게 한다.
• 문제에 적힌 명칭들을 간략화된 이름으로 바꿔보자

🧾️ example

관광지 수, 여행 비용 => X 너무 현실 세계 개념

a, b => X 너무 아무 의미 없음

NodeCount, weight => O 간결하고 알고리즘에 맞게 추상화된 변수명

• 간략화된 그림이나 수식 등으로 표현해보자

2. 문제 해결 계획 세우기

문제 해결 방식, 즉, 사용할 알고리즘과 자료구조를 선택

가장 좋은 경우는 여러 경험이 쌓인 후 나타나는 직관이다. 하지만 직관이 떠오르지 않거나 직관으로 풀었을 때 틀린 경우 다음과 같은 체계적인 접근을 시도할 수 있다.

문제 접근 방법

비슷한 문제 찾기

다음의 두 경우, 비슷한 문제의 접근법을 적용가능

🧾️ 알고리즘의 원리를 완전히 이해하고 있어 응용하는 경우

1. 두 도시를 잇는 가장 짧은 경로를 찾는 문제를 푼 경험이 있음
2. 위 문제를 풀기 위한 최단 경로 알고리즘을 완전히 이해하고 있음
3. 알고리즘을 응용하면 가장 긴 구간과 가장 짧은 구간의 길이 차이가 적은 경로를 찾는 문제를 풀 수 있음

🧾️ 해당 카테고리의 문제를 푼 경험이 많음

발생 확률이나 경우의 수 문제의 경우, 십중 팔구는 동적계획법으로 해결 가능하다는 경험을 토대로 접근 가능

따라서 문제가 어떤 카테고리(최적화, 경우의 수, 검색, 등)에 속했는지 찾아내는 능력이 필요하다.

단순한 해결 방법으로 시작하기 : 브루트 포스

만약, 갈피를 잡지 못하겠다면, 비효율적이여도 목표를 이룰 수 있는 단순한 알고리즘을 만들어 보자. 예를 들어 사탕을 모두 나누어 주는 모든 경우의 수를 따지게 만든다던가…

그 이유는

• 종종 충분한 자원과 컴퓨터의 효율로 인해 해결되버리는 경우 있음
• 모든 알고리즘은 단순한 알고리즘을 기반으로 구성된 경우가 많음
  • 가지치기, 효율적인 자료구조로 변경 등
• 앞으로 구현 시도해볼 알고리즘의 성능 기준선이 될 수 있음
  • 어느 정도 더 빠른 알고리즘을 구현해야 하는가?

문제 푸는 과정 수식화 : 급할수록 돌아가기

단순한 해결 방법으로 시작하기 : 브루트 포스 는 가끔 오히려 완전한 발상의 전환이 필요할 때는 역효과를 일으키기도 한다.

이때는 간단한 입력과 경우의 문제를 직접 손으로 풀어보자.(직접 구현 보다 왠만하면 빠르다.)
그리고 해당 방법을 공식화한 알고리즘을 구상하거나 고려해야할 점을 얻어낼 수 있다.

문제 단순화 : 문제를 좀더 쉽게 변형

문제를 좀더 쉬운 변형판을 먼저 풀어보는 방법이 있다.
앞선 문제 푸는 과정 수식화 : 급할수록 돌아가기 와의 차이점은, 쉬운 입력을 이용하는 것이 아니라 문제 자체의 조건과 요구를 변경하는 것이다.

• 변수 수 줄이기, 차원 수 줄이기 등

이를 통해 새로운 직관을 얻거나 간단히 문제를 풀어낼 수 도 있다.

예를 들어 2차원의 문제를 1차원으로 줄이고 푼 뒤, 사실은 1차원 문제 값 2개를 풀어 합하면 답이 나오는 경우가 있다.

그림이나 수식으로 표현해 보기

수학적 능력이 있다면 수식으로 표현하여 알고리즘 전개나 축약 등에 도움이 될 수 있다.

• 동적 계획법의 점화식 등이 대표적

수식으로도 안된다면 인간이 직관적으로 받아 들일 수 있는 기하학적 도형을 이용해볼 수 있다.

• 정수쌍의 경우 좌표 평면에 그려보자.

문제를 더욱 작게 쪼게기

한개의 복잡한 조건을 여러개의 단순한 조건으로 나눌 수 있는 경우가 많다.

단순히 문제 두개가 이어진 형태부터, 특정 알고리즘의 값을 비교하기 위해 다른 알고리즘이 필요한 경우도 존재한다.

순서를 뒤집기

주어진 원소에서 목적을 찾는 것이 아니라, 목적지부터 반대로 향하는 방법 또한 존재한다.

예를 들어 어느 입구에 들어가야 출구로 나갈 수 있는가?에 대한 문제는 모든 입구를 확인하지 않고 반대로 출구로 들어가서 나오는 입구를 확인하면 된다.

순서를 강제하기

주로 순서에 관계없는 수(경우의 수, 필요한 횟수)를 요구하는 문제에 사용되며, 일부분 순서대로 조금씩 수를 구한다는 점에서 스위핑이나 DP와 비슷하다.

순서에 관계없을 경우 수많은 경우의 수가 나오는 경우 순서를 강제하여 경우의 수를 줄일 수 있다.

예를 들어 5X5 게임판에서 각 격자를 누르면 격자의 상하좌우 격자 불이 토글되는 문제에서 모든 격자를 끄는데 필요한 최소 클릭 수를 구하는 문제 등이 있다.

엄밀히 말하면 문제 해결 계획 보다는 알고리즘에 가까운것 같다?

정규화(Canonicalization) 하기

위의 순서를 강제하기 의 연장으로, 우리가 고려해야 할 답들 중 형태가 다르지만 결과적으로는 똑같은 것들을 그룹으로 묶은 뒤, 각 그룹의 대표들만을 고려하는 방법이다.

예를 들어 상단에 격자 토글 문제에서 순서가 다르지만 클릭 하는 부분이 같은 경우의 수는 순서와 관계없이 결과가 같으므로 하나로 묶을 수 있다.

정규화 기법이 문제마다 다르므로 경험이 아주 많아야 한다.

3. 문제 해결 검증 하기

알고리즘이 모든 요구 조건을 정확히 수행하는가?

• 루프 불변성
• 증명 방법들
  메모리와 시간이 제한 내에 들어가는가?
• 시간복잡도, 공간복잡도 참조
• …실전에서는 주먹 구구식 참조

  4. 프로그램 구현 하기

  좋은 코드의 원칙

• 표준 라이브러리의 적극적인 활용
• 디버깅 하기 편한 수준의 적절하고 간결하고 재사용 가능한 코드 작성
• 앞서 설명한 추상화 와 달리, 좀더 직관적이고 규약에 맞는 명명법 적용

🧾️ example

def checkPoint(x,y,cx,cy,cr): # 비직관적, 규약에 맞지 않는 명명법
	pass

def is_in_circle(x,y,circle_x,circle_y,circle_r): #직관적이고 pep8에 맞는 명명법, 결과값 예상 쉬움
	pass

위를 통해 디버그가 용이하고 나중에 읽을때도 이해하기 쉬운 코드를 적을 수 있다. - **데이터의 정규화: 데이터가 여러 형식이 존재할 수 있는 경우 하나로 통일하여 저장하자.**
- 이를 통해 형식 불일치로 인한 버그를 막을 수 있다.
- 되도록이면 함수나 클래스에 데이터가 입력되는 즉시 통일하게 하자.
- 예를 들어, 분수값은 무조건 최대한 기약분수 형태로, 시간은 하나의 형식으로 통일해서 - **코드와 데이터의 분리: 코드의 논리와 상관없는 데이터를 분리**
- 분기문이 줄고, 재사용이 가능하게 됨

🧾️ example

def month_to_month_name(month):# 코드양이 많고 실수가 많으며 재사용 힘든 코드(X)
	if (month==1) return "Jan"
	elif (month==2) return "Feb"
	...
	
def month_to_month_name(month): # 코드 양이 적고 재사용이 쉬운 데이터 분리 코드(O)
	month_names = ["Jan", "Feb", "March"...]
	return month_names[month]

자주하는 실수들

• 산술 오버 플로
  • 변수 표현 가능 범위 주의하기
  • 애매하게 작거나 너무 큰 무한대 값
  • 결과나 중간 값이 너무 큼

🧾️ 산술 오버 플로우 예시

• 최소 공배수 구할 때 분자 크기 주의
• ex) lcm(a, b) = (a * b) / gcd(a, b)
• gcd 값을 구하지 말고 미리 분모 나누기, 이항계수 사용으로 방지

• 배열 범위 밖 원소 접근
  • 특히 0부터 시작하는가, 1부터 시작하는가 주의
  • 일관되지 않은 범위 표현 방식 ex) 0 <= i <= 10 ? 0 < i < 10 ?
  • Off-by-one 오류
    • ex) 100미터 담장에 10미터 마다 울타리 기둥을 세우려면 기둥이 몇개 필요한가? 10개 (X), 11개 (O)
• 상수나 변수 오타: "sucess"(X), "success"(O)
• 연산자 우선 순위: 괄호 활용하기
• 잘못된 변수 초기화
• 스택 오버 플로: 최대 재귀 크기 주의하거나 늘리기
• 잘못된 비교 함수: 특히 객체 간의 비교 시 조심
• 입출력 방식 빠르게 바꾸거나 줄이기
• 실수 연산: 제대로된 비교 함수 만들기, 실수 연산 안하는 조건으로 변경하기

5. 회고하기

자신이 문제를 해결한 과정을 돌이켜보고 개선하는 과정

1. 코드와 함께 자신의 경험을 주석으로 남겨보자
   • 간단한 해법
   • 접근 방식
   • 해법을 찾는데 결정적이었던 깨달음
   • 버그 났던 지점
   • 등
2. 잘 푼사람의 코드 보기
   • 자신의 해법과 비교하여 어느점이 우수한지 구분

     맞춘 경우

     두번째로 풀면서 더우 간결하고 효율적인 코드와 알고리즘을 작성해보고, 같은 알고리즘을 유도할 수 있는 간결한 코드를 작성할 수 있다.

틀린 경우

도저히 못풀겠거나 1시간 이상 고민을 해야했던 경우

1. 오답 요인, 정답에 접근하지 못한 이유를 적자.
   반복되면 실패 원인을 깨달을 수 있다.
2. 다른 사람 코드 복기
   • 나는 왜 이 해답을 떠올리지 못했는가?
   • 왜 이사람 코드가 더 간결하거나 효율적인가?
     단순 코드 복기 보다, 블로그 등에서 풀이 과정을 함께 보면 더욱 좋다.