문제 해결 절차

주민건·2020년 9월 27일
1

문제해결방법론

목록 보기
2/7

제가 어떠한 문제를 만나도 해결할 수 있는 방법을 알려드리겠습니다.

  1. 문제를 적는다.
  2. 생각을 열심히 한다.
  3. 해결책을 적는다.

정말 쉽죠?

무슨 미친 소리냐구요?
사실, 제가 만들어낸 말이 아닙니다. ^^

바로, 미국의 노벨상 수상 물리학자 리처드 파인만이 제시한 문제 해결법 입니다.

  1. Write down the problem.
  2. Think real hard.
  3. Write down the solution.

Feynman Algorithm을 따르면 어떠한 문제라도 해결(?)할 수 있습니다.

참 쉽죠?

컴퓨터를 이용한 문제 해결

컴퓨터로 문제를 해결하기 위해서는 마지막 절차가 필요하죠.

“4. 코드로 짠다.”

그럼 이제 저희는 못 풀 문제가 없을까요?
실제로 못 풀 문제는 없을 겁니다.
하지만, 파인만 알고리즘을 어떻게 활용할지 감이 잡히지 않을 수 있습니다.

  1. 문제를 어떻게 적지?
  2. 생각을 어떻게 열심히 하지?
  3. 해결책을 어떻게 적지?
  4. 코드로 어떻게 짜지?

디테일한 세부 과정들이 어떻게 동작하는지 생각을 해볼 필요가 있습니다.
그리고, 우리가 풀고자하는 알고리즘 문제에 어떻게 적용할지 고민해봐야 합니다.

각각의 절차에서 좀 더 생각해봅시다

문제를 어떻게 적지?

문제를 적는 과정에서 필요한 정보는 문제를 해결하는데에 도움을 주는 내용입니다.
해당 내용들을 파악하고, 정리해서 해결책을 만들어나가야 합니다.

위 과정을 문장으로 정리해본다면,
1. 문제를 정의 혹은 이해합니다.
2. 이해한 내용을 바탕으로 어떠한 상황인지 분석합니다.

문제를 해결하기 위해 필요한 정보는 크게 2가지 입니다.

  • 목표 = 해결할 문제가 무엇인지
  • 상황 = 제한된 조건이 무엇인지, 따라야하는 규칙은 어떤 것인지

문제를 정의내리는 과정은 요구사항이 없을 경우 필요합니다.
목표를 스스로 설정하고, 현재 상황을 관찰하여 기록하는 과정입니다.

알고리즘 문제는 요구사항이 제공되므로, 정의내리는 과정은 불필요합니다.
다만, 정의된 내용을 바탕으로 재정의는 할 수도 있습니다.

문제를 해결하는데에 있어서 필요한 정보를 빠짐없이 적을 때까지 문제를 읽습니다.

3줄 요약,

  1. 문제에서 주어진 목표와 상황을 알아냅니다.
  2. 알아낸 정보를 조합하며, 분석합니다.
  3. 문제를 푸는데 충분한 정보를 얻을때까지 반복합니다.

생각을 어떻게 열심히 하지?

뭐든지 열심히 한다고 잘되는 것은 아닙니다.
잘 하는 것과 열심히 하는 것의 차이는 존재합니다.
(갑자기 때려서 죄송합니다)

그래서 열심히 보다는 잘 하는 방법을 생각해봅시다.

제가 소개시켜드릴 잘 하는 방법은 전재가 존재합니다.

"모든 뛰어난 생각들은 단순하고, 무식한 방법에서 출발한다."

갑자기 한 번에 효율적인 방법을 생각해내는 것은 쉽지않습니다.
아주 무식하고 단순한 생각을 효율적으로 개선시켜나가면서 생각을 발전시켜나가는 방법은 한 방에 떠올리는 것보단 쉽습니다.

창의성도 마찬가지라고 생각합니다.
만약, 그 과정을 보지 못하고 결과만 본 다른 사람에게는 창의적이고 효율적인 생각이 될 수 있겠죠.

잘 생각한다는 것은 천천히 생각을 쌓아나가는, 깎아나가는 것입니다.

컴퓨터 공학의 기초 학문인 자료구조, 알고리즘은 생각을 깎아나가는데에 필요합니다.

해결책을 생각하는데에 필요한 재료로 활용될 것입니다.

각각의 자료구조, 알고리즘들 또한 무식한 생각에서 발전되어온 결과물이라고 생각합니다.
추후 가장 무식한 알고리즘에서 효율적인 알고리즘으로 개선되어가는 모습을 이야기 할 예정입니다.

앞으로의 글에서 많은 사람들이 자료구조, 알고리즘을 설명하는 방식으로 채택한 모듈형 개념 설명이 아닌
하나의 물줄기, 큰 흐름으로 설명할 생각입니다.

2줄 요약,

  • 무식한 방법부터 생각해서 효율적으로 개선시켜나가자.
  • 필요한 도구는 자료구조와 알고리즘이다.

해결책을 어떻게 적지?

생각으로만 실행으로 옮겨지지않겠죠.
생각을 잘 정리해서 실행할 수 있도록 만드는 것이 중요합니다.
또한, 열심히 생각한 해결책이 제한 상황을 만족하면서 문제를 해결하는지 확인하는 과정이 필요합니다.

해결책을 효과적으로 정리하기 위해서는
생각의 단위를 정해서 모듈화를 적절히 하는 과정이 필요합니다.

예를 들어, 정말 큰 케이크를 한 입에 먹을 순 없습니다.
먹을 수 있는 크기 정도로 나눠야 먹을 수 있는거죠.

생각을 모듈화한다는 것은 어떤 말일까요?

목표를 이루기 위한 세부 하위 목표를 설정하는 것이죠.
하위 목표들은 서로가 종속적일 수도 있고, 독립적일 수도 있습니다.
서로가 종속적인 하위 목표들은 순서를 정해서 적어둬야합니다.

목표를 언제까지 나누는 것이 좋냐면,
내가 해결할 수 있는 단위면서 내가 행동으로 옮길 수 있는 단위까지 쪼개는 것이 좋습니다.

처음에는 하위 목표가 많이 존재할 수 있습니다.
계속된 연습을 통해 내가 해결할 수 있는 하위 목표의 크기가 커진다면,
나눠야할 하위 목표의 개수는 줄어들게 되겠죠.

만약 연습을 통해 한 입에 먹을 수 있는 케이크의 크기가 커진다면,
케이크를 몇 조각 쪼개지 않아도 한 입에 먹을 수 있겠습니다.

추천 드리는 하위 목표의 가장 작은 단위는 하나의 행위를 하는 함수를 제작할 수 있는 정도입니다.
각각의 모듈화된 목표(=함수)를 통해 문제를 해결하는 것이죠.

이때 얻을 수 있는 이점은 어떤 생각(=함수)에서 실수했는지 파악하기 쉽습니다.
또한, 각각의 생각(=함수)를 따로 테스트해 볼 수 있음으로 큰 실수를 할 확률이 낮아 집니다.

케이크 = 문제의 최종 목표
케이크 한 조각 = 하위 목표
한 입에 먹을 수 있는 크기 = 행동할 수 있는 단위

생각간의 관계를 살펴봅시다.

하위 목표를 만들고, 각각의 하위 목표의 순서를 인식하고 있는 것이 중요합니다.

A라는 목표를 이뤄야 B 목표를 해결할 수 있는 종속 관계가 존재할 것 입니다.

만약 순서가 필요없을 경우, 문제 해결을 적절히 할 수 있는 순서로 목표를 해결합니다.

케이크도 먹어야하는 순서가 존재합니다.

처음부터 엄청 단 케이크를 먹게되면, 다음으로 먹는 케이크의 맛이 안느껴집니다.

진짜 해결책? 가짜 해결책?

다음으로, 해결책을 검증하는 과정을 살펴봅시다.

열심히, 잘 생각해서 얻은 결과를
이해하고 분석한 문제 정보와 함께 놓고
검토해봅시다.

제한 상황을 빠짐없이 반영하였는지, 목표를 제대로 이룰 수 있는지 확인합니다.
제한 상황들의 관계로 인해 나올 수 있는 모든 상황을 커버할 수 있는지도 알아야합니다.

검증하는 과정을 부실하게 한다면, 이후 모든 행위가 비효율적이게 될 것입니다.
빠진 부분이 없는지 꼼꼼하게 살펴야합니다.
부족한 부분이 발견된다면 조금 더 생각하는 시간을 가져야합니다.

3줄 요약,

  • 생각의 단위를 내가 감당할 수 있을 만큼 쪼갭니다.
  • 쪼갠 생각들의 관계를 보고 절차를 매깁니다.
  • 분석한 문제와 생각해낸 해결책을 1:1 맵핑해봅니다.

코드로 어떻게 짜지?

만약 코드를 작성하기 전의 절차를 완벽하게 했을 경우,
생각을 코드로 옮기는 과정에서만 실수가 발생할 것입니다.

구현 능력이 부족한 부분은
앞서 하위 목표를 쪼갤때 "내가 감당할 수 있을 만큼" 분해하기 때문에
문제되지 않아야 합니다.

만약, 코드 구현에 있어서 힘들다면
덜 정리된 하위 목표를 코드를 작성하면서 연습하는 것도 하나의 방법이 될 수 있습니다.

구현 능력이 어느정도 갖춰진 분들은
하위 목표를 코드로 옮기는 수준에 지나지 않을 것입니다.

2줄 요약,

  • 각각의 하위 목표를 함수로 만듭니다.
  • 각각의 함수 테스트를 진행합니다.

전체 최종 정리

제일 처음에 적었던 단순한 절차를 다시 봅시다.
1. 문제를 적는다.
2. 생각을 열심히 한다.
3. 해결책을 적는다.
4. 코드로 짠다.

해당 절차를 세밀하게 들여다보았습니다.
1-1. 문제의 목표를 파악한다.
1-2. 문제의 제한 상황을 알아냅니다.
1-3. 얻은 정보를 바탕으로 문제를 분석합니다.
2-1. 가장 단순하고 무식한 방법부터 생각합니다.
2-2. 해당 생각을 자료구조와 알고리즘으로 개선시켜나갑니다.
3-1. 하위 목표를 설정합니다.
3-2. 각 하위 목표끼리의 관계를 파악합니다.
3-3. 완성된 해결책과 분석한 문제를 비교합니다.
4-1. 각각의 하위 목표를 함수로 구현합니다.
4-2. 함수단위로 작게 작게 테스트를 진행합니다.
4-3. 실제 문제를 해결하는지 확인합니다.
(실제 문제를 풀게 될 경우 2번과 3번 과정이 혼합되어 일어날 것입니다.)

펼쳐놓은 생각을 키워드 단위로 요약해봅시다.
1. 문제분석: 목표, 상황 분석
2. 방법생각: 무식한 방법부터 적용, 세부 목표 설정 및 관계 파악
3. 제한검토: 시간복잡도, 공간복잡도, 문제 제한 상황에 맞게 동작하는 방법인지
4. 코드구현: 모듈화
5. 함수확인: 유닛 테스트

코딩 테스트의 경우 문제를 해결하는데에 제한 시간이 존재하므로,
모든 절차를 완벽하게 지킬 수 없을 것입니다. 따라서, 적절히 타협을 봐야합니다.

제한 시간을 두고, 문제를 풀어보는 연습을 통해
어디서 자신이 자주 실수하는지 확인하고,
습관을 개선시켜나가는 것이 중요합니다.

그리고 이야기된 절차를 엄격하게 지킬 필요 없이
약간의 왔다갔다는 해볼 수 있을 것 입니다.
소프트웨어공학을 배운 사람이라면
에자일 vs 워터폴 느낌이 들 것 같네요.

자신이 적절히 선택하고 자신에게 맞도록 연습하는 것이 중요합니다.

만약 적힌 절차보다 더 효율적인 방법이 있다면
공유해주시면 감사하겠습니다.

첫 번째 포스팅에서 자신의 생각 흐름을 정리적어보신 분들은
제가 오늘 이야기 해드린 내용과 비교해도 좋고,
자신의 생각을 제가 정리했듯이 여러분 나름대로 정리해보는 시간을 가지시면 좋겠습니다.


(뭔 개소리를 이렇게 길게 썼어?)

자, 같이 해봅시다.

https://www.acmicpc.net/problem/14890

삼성 기출 문제집에 있는 경사로 문제입니다.

1. 문제 분석

목표: 지도가 주어졌을때, 지나갈 수 있는 길의 개수
상황:

  • 지나갈 수 있는 길: 한 행 또는 한 열 전부를 나타내며, 한쪽 끝에서 다른쪽 끝까지 지나갈 수 있어야 함.
  • NxN의 지도
  • 2N개의 길 존재
  • 준비된 경사로의 개수는 무제한
  • 경사로를 놓을 수 있는 경우
    - 경사로는 낮은 칸에 놓으며, L개의 연속된 칸에 경사로의 바닥이 모두 접해야 한다.
    - 낮은 칸과 높은 칸의 높이 차이는 1이어야 한다.
    - 경사로를 놓을 낮은 칸의 높이는 모두 같아야 하고, L개의 칸이 연속되어 있어야 한다.
  • 경사로를 놓을 수 없는 경우
    - 경사로를 놓은 곳에 또 경사로를 놓는 경우
    - 낮은 칸과 높은 칸의 높이 차이가 1이 아닌 경우
    - 낮은 지점의 칸의 높이가 모두 같지 않거나, L개가 연속되지 않은 경우
    - 경사로를 놓다가 범위를 벗어나는 경우
  • 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다.
  • 제한 시간: 2초

2. 방법 생각

목표 재설정
: 지도가 주어졌을때, 한 행 또는 한 열 전부를 한쪽 끝에서 다른쪽 끝까지 지나갈 수 있는 길의 개수

세부 목표
: 경사로를 놓거나 놓지않거나해서 한 행 또는 한 열에서 한쪽 끝에서 다른 쪽 끝으로 갈 수 있는지 확인,
경사로 없이 갈 수 있는 길인지,
경사로를 놓았을 때 갈 수 있는 길인지,
경사로를 놓을 수 있는지,

모든 경우를 보는 무식한 방법
: 경사로를 놓아보면서 한 행이나 열을 훑자

3. 제한 검토

경사로를 놓아보면서 한 행이나 열 훑기 = O(N)
모든 행과 열 선택 = O(2N)
복잡도 = O(N^2)
N은 최대 100 이므로, 제한 시간 내에 해결 가능

4. 코드구현

탐색 시작 위치 잡는 함수
경사로 놓는 함수
한 열이나 행을 검토하는 함수

코드를 짜다가 추가한 생각
추가 상황
: 오르막길, 내리막길

제출하고 틀려서 추가한 코드
반영하지 않은 상황
: 경사로를 놓다가 범위를 벗어나는 경우

코드
#include<stdio.h>

int n,l,data[105][105];

void input(){
  scanf("%d %d",&n,&l);
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      scanf("%d", &data[i][j]);
    }
  }
}

int dx[2]={1,0};
int dy[2]={0,1};
bool check(int idx, int dir){
  int path_size=1;
  int height = dir ? data[0][idx] : data[idx][0];
  int x = dir ? idx:0;
  int y = dir ? 0:idx;
  int down=0;
  for(int i=1;i<n;i++){
    y += dy[dir];
    x += dx[dir];
    if(height==data[y][x]) path_size+=1;
    else{
      if(data[y][x]>height+1) return false;
      else if(data[y][x]<height-1) return false;
      else if(data[y][x]==height+1){
        if(path_size<l) return false;
        if(down==1 && path_size<2*l) return false;
        down=0;
      }
      else if(data[y][x]==height-1){
        if(down==0) down=1;
        else{
          if(path_size<l) return false;
        }
      }
      height=data[y][x];
      path_size=1;
    }
  }
  int prev_y = y-dy[dir];
  int prev_x = x-dx[dir];
  if(down==1 && path_size<l) return false;
  return true;
}

int solve(){
  int cnt=0;
  for(int i=0;i<n;i++){
    cnt+=check(i,0);
    cnt+=check(i,1);
  }
  return cnt;
}

int main(){
  input();
  int result = solve();
  printf("%d",result);
  return 0;
}

다음 시간 예고

본격적으로 알고리즘 얘기를 하기에 앞서서
적으면서 문제를 풀어야하는 이유와
간단한 생각 전략에 대해 알아봅시다.

P.S.

눈치 채신 분들도 계시겠지만,
파인만 알고리즘을 제가 감당할 수 있을 만큼 쪼개는 과정을
제가 설명드린 절차를 재귀적으로 적용해서
설명해드렸습니다.ㅋ.ㅋ

profile
Learning Engineer

0개의 댓글