TL;DR

사실 TL;DR을 적고싶지 않았는데, 글이 길어 읽기 힘들 것 같다. 권장하지는 않지만 읽기 귀찮으면 결론으로 점프 ... 🌚

서론

어제 문제를 푸는 접근방법에 대해 질문을 받아서 생각나는대로 일단 답변을 했다. 집에 돌아가면서 생각해보니 잘 설명했는지 의구심이 들어 이 주제에 대해 찾아보기로 했다. 예전 처음 코딩을 시작할 때 문제만 보면 마음이 조급하고 두근거리고 한 번에 동작했으면 좋겠고 에러보는게 두렵고 다음 진도 생각하고 🤣🤣🤣.. 하던게 생각이나서 정리해보고자 한다 ㅋㅋㅋㅋㅋ. 이 글을 읽고있는 사람에게 도움이 됐으면 좋겠다.

지금 작성하는 글은 Udacity의 Intro to Computer Science라는 유튜브 강의에서 How to Solve Problems 부분에 관한 내용이다. 한 가지 문제 예시와 함께 문제 접근법에 대해 설명할 것이다. 하지만 여기서 중요한 점은 문제를 해결하는 접근법에 대한 큰 그림에 주목을 하는 것이다!!

추가적으로, 여기서 사용하는 프로그래밍 언어는 파이썬이지만 다른 언어를 배웠다면 코드를 읽는데 크게 무리가 없을 것 이다. 그리고 번역과 내 생각이 짬뽕되어있다는 점을 인지하기 바란다 😈!!

예시 문제

문제를 해석해보았다!

당신의 생일과 오늘 날짜가 주어졌습니다. 당신의 나이를 "일수(number of days)"로 계산하세요. 윤년에 대해 고려해야합니다. 당신의 생일과 오늘 날짜는 무조건 올바른 형식의 날짜입니다 (그리고 시간역행은 없습니다!). 만약 2012년 1월 1일에 태어났고, 오늘이 2012년 1월 2일이라면, 당신의 나이는 1일입니다.

아따마 길다 😓. 일단 문제에 대해 고민을 해보고 어떻게 생각했는지 적어보고 돌아오길 바란다.

처음해야할 것

문제를 처음 마주했을 때 해야하는 것이 무엇이라고 생각하는가? 코딩하기? 헬프미구글 🤪? 가장 처음해야할 것은 문제를 이해하는 것이다.

컴퓨터를 사용하는 문제 이해하기

알고리즘 문제들은 일반적으로 다음과 같이 구성된다.

1. 가능한 입력 (인풋) 또는 가능한 입력의 집합
2. 입력들 간의 관계
3. 희망하는 출력 (아웃풋)

그리고 입력이 어떤 프로시져(절차)를 거쳐서 출력이 나온다.

여기까지 일반적인 이야기였고 예시 문제에 적용해보도록 하자.

쫄지마!

문제를 보면 정신이 아득해지고 심장의 뛰는 증상 🙀을 겪는 환자들이 있을 것이다 ㅋㅋㅋㅋㅋ. 습~~하~~습~~하~~ 를 통해서 마음의 평정심을 유지하도록 하는게 0순위이다 🌞.

준비가 되었다면 다음으로 넘어가자!

입력은 무엇일까?

문제를 다시 보자!

당신의 생일과 오늘 날짜가 주어졌습니다. 당신의 나이를 "일수(number of days)"로 계산하세요.

물론 여기서 입력은 당신의 생일 과 오늘 날짜 이다. 하지만 실제로 저 두가지만 필요하다면 굳이 프로시져를 만들 이유도 없다. 좀 더 큰 그림으로 바꾸면 입력은 두 개의 날짜이다. 좀 더 정확히 하자면, 첫 번째 날짜와 두 번째 날짜이다.

조건을 다시 보자!

당신의 생일과 오늘 날짜는 무조건 올바른 형식의 날짜입니다 (그리고 시간역행은 없습니다!)

이 조건을 보고 머리가 더 복잡해졌는가? 사실 이런 가이드는 문제를 푸는 사람에게 도움이 된다. 물론 문제를 푸는 것 자체가 귀찮은 일이기 때문에 체감을 못할 수도 있다 ㅋㅋㅋㅋㅋ 😬. 하지만 이런 힌트가 없다면 위의 시간역행까지 구현해야하고 여러가지 형식의 날짜를 입력할 수 있도록 해야해서 코드가 훨씬 복잡해진다!!

위의 조건을 보고 알 수 있는 것은 두번째 날짜가 첫번째 날짜보다 앞선 날짜일 수 없다는 것이다. 그렇다고 하여 그것을 코드에서 체크하지 말라는 것은 아니다. 이미 확정된 조건까지 체크해보며 코딩하는 것을 Defensive Programming 이라 카더라..

추가적으로 미국인이 만든 문제를 번역했기 때문에 위에서 말하는 올바른 형식의 날짜 는 그레고리안 달력 (현재 우리가 사용하는 달력)에 "15 oct 2018" 과 같은 형식임을 인지하고 있어야 한다 💪 !!! (입력은 모두 숫자이니 형식에 걱정하지 말자)

사실 조건이 하나 더 있다!

윤년에 대해 고려해야합니다.

윤년은 2월에 29일이 있는 해이다. 이것의 계산법을 적어볼까 하다가 사실상 코드를 다 알려주는 격이 될 것 같아 그러지 않았다. 실제 코딩을 할 때 검색을 해보면 될 것이다!

믿기지 않겠지만 이정도면 사실 친절한 문제이다. 많은 힌트를 주었기 때문이다. 두어줄 써놓고 "마, 자신있으면 풀어봐라 👎" 하는 식의 문제도 많다.

입력은 어떻게 표현되는가??

알고리즘 문제에서 보통 함수 정의 부분이 이미 제공되는 경우가 많아서 입력이 어떻게 표현되는지 생각해보지 않는 경우가 많다. 하지만 충분히 고민해 볼 만 하다. 왜냐면, 문제를 만드는 사람만 프로그래머가 아니고 당신도 프로그래머이기 때문이다 👅!!

def daysBetweenDates(date1, date2):
def daysBetweenDates(year1, month1, day1, year2, month2, day2):

입력의 표현으로 위의 두 가지 경우가 대표적일 것 같다. 일단 강의에서 두 번째 경우를 택했으니 그대로 따라가보기로 한다.

출력은 무엇일까?

문제를 다시 보자!

당신의 생일과 오늘 날짜가 주어졌습니다. 당신의 나이를 "일수(number of days)"로 계산하세요.

출력은 "나이의 일수" 이다. 하지만 우리는 입력을 이해할 때 "첫 번째 날짜와 두 번째 날짜"로 살짝 general하게 바꿨다. 그렇기 때문에 이에 맞추어 출력도 "첫 번째 날짜와 두 번째 날짜 사이의 일수"로 바꿔준다. 그리고 이것을 리턴해야함을 기억한다.

입출력의 예시를 적어보자!

우리는 이제 입력과 출력을 이해하고 있다. 문제를 풀어볼 때다. 정말 자신이 있다면 바로 코딩을 해도되지만, 입출력에 따른 예시를 적어보는 것도 한 번더 이해하고 가는 좋은 방법이다.

daysBetweenDates(2012, 12, 7, 2012, 12, 7) # 0
daysBetweenDates(2012, 12, 8, 2012, 12, 7) # undefined
daysBetweenDates(2012, 6, 29, 2013, 6, 29) # 365

위의 함수 호출 코드에 입력 예시를 적고 주석에 출력 예시를 적어본 것이다. 파이썬 코드 예제라고 undefined에 신경이 쓰일 수도 있지만 그러지 않기를 바란다. 그냥 적은 것이다!

내가 여기 세 개만 적었다고 세 개만 적어보지 말고 최대한 다양한 경우를 적어보도록 노력했으면 좋겠다 😈.

문제를 풀자!

위의 내용을 보고 코딩을 어떻게 해야할지 감이 오지 않는다면, 다음과 같은 방법으로 생각을 해보는 것도 나쁘지 않다.

사람은 어떻게 이 문제를 해결하는지 생각해본다.

위의 내용을 인지하고 사람이 어떻게 해결하는지 예시를 보자.

예시를 적어보자!

다음을 계산해야한다.

daysBetweenDates(2013, 1, 24, 2013, 6, 29) 

사람은 2013년도 달력을 꺼내서 눈과 손으로 일 수를 셀 것이다.

Jan 24 - 31 	= 7
Feb               28
March             31
April             30
May               31
June 1 - 29 	  29

그리고 계산기를 두들겨서 모두 156일이라는 것을 알 수 있다.

더 어려운 예시

ㅋㅋ 갑자기 연도가 확 늘어났다 😭.

daysBetweenDates(2013, 1, 24, 2024, 6, 29) 

어떤 연도는 356일이고 또 어떤 연도는 366일임을 생각해보게 될 것이다.

Pseudo Code

생각하는 알고리즘을 자신만의 언어를 사용해 개략적으로 적어보는 코드를 Pseudo Code (의사코드)라고 한다. 한 번 직접 적어보길 바란다!

다음은 강의에서 나온 의사코드이다.

days = # of days in months1 - day1
month1 += 1
while month1 < month2:
    days += # of days in month1
    month1 += 1
days += day2
while year1 < year2:
    days += days in year1

이 방법으로 풀어야할까?

의사 코드를 한 번에 완벽하게 적기는 힘든 편이다. 아마도 시행착오가 여러번 있을 것이다. 그러므로 실전 코딩에 들어가기 전에 내가 작성한 의사코드로 풀어보는게 맞을지 심도있게 고민해봐야 한다.

위의 의사코드는 다시 작성되는 편이 좋을 것 같다. 그 이유는, 딱 봐도 좀 복잡해 보인다. 아래와 같이 처리하지 않은 조건들이 많다.

• 같은 월인 조건의 처리
• month2 < month1 조건의 처리
• year2 > year1 조건의 처리
• 윤년의 처리

그런데도 벌써 복잡해버리니 이거 원.. 😥😓.

프로그래머라면, 항상 더 심플한 방법이 있는지 생각해봐야 한다!

간단하게 접근하기!

아래는 좀 더 간단한 알고리즘의 의사코드이다. 사람 손으로 일수를 세듯이 days를 하나씩 늘려주는 코드이다.

days = 0
while date1 is before date2:
    date1 = advance to next day
    days += 1

이 글이 읽기 힘든 당신에게

이 글을 작성하는 나도 힘들다. 하지만 앞으로 나아가고 있다는 사실은 중요하다. 그렇기 때문에 힘을 냈으면 좋겠다 💪!

여기서 하나만 기억하고 다음 섹션으로 갔으면 좋겠다.

작은 단위로 코드를 작성하고, 테스트하고, 작성한 코드가 어떤 일을 수행하는지 정확히 알자!

그래서 진짜 뭐부터 코딩하자고??

드디어 코딩할 것을 결정해볼 때이다. 전체를 한 번에?? 윤년인지 확인?? 매월의 일수 구하기?? 어떤게 가장 간단해보이는가?

사실 첫 번째 날짜의 다음날을 구하는 프로시져를 만드는게 제일 쉽다 (date1 = advance to next day).

nextDay(year, month, day)

다음 날을 구하는 코드를 작성해보자. 일단 모든 달의 일수는 30일이라고 가정한다. 한 번에 정답으로 가려고 하기 보다 점점 정답에 근접해가는 것을 보여주고자 함이다.

def nextDay(year, month, day):
    """
    이 버전은 모든 달이 30일이라고 가정했습니다!
    """
    if day < 30:
    	return year, month, day + 1
    else:
        if month < 12:
            return year, month + 1, 1
        else:
            return year + 1, 1, 1

그리고 이 코드를 원래 작성하려했던 daysBetweenDates() 함수에 적용해보고 답에 근접한 결과를 보도록 해야한다.

일단 pseudo code 부터 수정한다.

days = 0
while date1 is before date2:
    date1 = advance to next day <= nextDay
    days += 1

그럼 다음엔 어떤 코드를 작성해야할까?

dateIsBefore(year1, month1, day1, year2, month2, day2)

이 다음에 작성해야할 프로시져는 date1 is before date2 부분 뿐이다. 생각하는 의사코드를 적어보고 코딩을 해보길 바란다.

def dateIsBefore(year1, month1, day1, year2, month2, day2):
    """
    year1-month1-day1이 year2-month2-day2 보다
    앞선 날짜면 True 아니면 False를 리턴한다.
    """
    if year1 < year2:
    	return True
    if year1 == year2:
    	if month1 < month2:
       	    return True
        if month1 == month2:
            return day1 < day2
    return False

daysBetweenDates(year1, month1, day1, year2, month2, day2)

의사 코드안에 필요한 프로시져를 모두 작성했으니 의사 코드를 프로시져로 코딩해본다.

def daysBetweenDates(year1, month1, day1, year2, month2, day2):
    """
    year1-month1-day1과 year2-month2-day2 사이의 일수를 리턴한다.
    입력은 그레고리안 달력의 유효한 날짜이며 첫번째 날짜는 두번째 날짜보다 크지 않다고 가정한다.
    """
    assert not dateIsBefore(year2, month2, day2, year1, month1, day1)
    days = 0
    while dateIsBefore(year1, month1, day1, year2, month2, day2):
        year1, month1, day1 = nextDay(year1, month1, day1)
        days+=1
    return days

첫 번째 날짜가 두 번째 날짜보다 크지 않다고 가정했지만 Defensive Programming을 위해서 체크를 해야한다. assert not dateIsBefore(year2, month2, day2, year1, month1, day1) 코드가 존재하는 이유이다.

Real World Problem

우리는 한 번에 풀기 힘든 예제 문제를 지금까지 모든 달이 30일까지 라는 가정을 통해 정답에 근접한 코딩을 했다. 그렇다고 정답은 아니다. 위에서 배운 나름의 룰들을 적용해서 직접 풀어보고 돌아오길 바란다.

답안

강의에서 제공해준 생각과 답안이다.

강의에서 추천하는 풀이 순서

1. 항상 30을 리턴하는 daysInMonth(year, month)를 작성한다.
2. daysInMonth(year, month)를 사용하여 nextDay(year, month, day)를 수정한다.
3. nextDay(year, month, day)를 테스트한다.
4. daysInMonth(year, month)를 윤년을 생각하지 않고 달에 따라 올바른 일수가 나오도록 수정한다.
5. nextDay(year, month, day)를 테스트한다.
6. isLeapYear(year)으로 윤년인지 아닌지 확인하는 코드를 작성한다.
7. isLeapYear(year)를 테스트한다.
8. daysBetweenDates(...)의 모든 테스트 케이스를 통과해보록 한다.

isLeapYear(year)

def isLeapYear(year):
    if year % 400 == 0:
        return True
    if year % 100 == 0:
        return False
    if year % 4 == 0:
        return True
    return False

daysInMonth(year, month)

def daysInMonth(year, month):
    if month in [1, 3, 5, 7, 8, 10, 12]:
        return 31
    if month == 2:
        if isLeapYear(year):
            return 29
        else:
            return 28
    return 30

nextDay(year, month, day)

def nextDay(year, month, day):
    if day < daysInMonth(year, month):
    	return year, month, day + 1
    else:
        if month < 12:
            return year, month + 1, 1
        else:
            return year + 1, 1, 1

dateIsBefore(year1, month1, day1, year2, month2, day2)

def dateIsBefore(year1, month1, day1, year2, month2, day2):
    if year1 < year2:
    	return True
    if year1 == year2:
        if month1 < month2:
       	    return True
        if month1 == month2:
            return day1 < day2
    return False

daysBetweenDates(year1, month1, day1, year2, month2, day2)

def daysBetweenDates(year1, month1, day1, year2, month2, day2):
    assert not dateIsBefore(year2, month2, day2, year1, month1, day1)
    days = 0
    while dateIsBefore(year1, month1, day1, year2, month2, day2):
        year1, month1, day1 = nextDay(year1, month1, day1)
        days+=1
    return days

test()

def test():
    test_cases = [((2012,1,1,2012,2,28), 58), 
                  ((2012,1,1,2012,3,1), 60),
                  ((2011,6,30,2012,6,30), 366),
                  ((2011,1,1,2012,8,8), 585 ),
                  ((1900,1,1,1999,12,31), 36523),
                  ((1600,1,1,2017,12,31), 152671)]

    for (args, answer) in test_cases:
        result = daysBetweenDates(*args)
        if result != answer:
            print("Test with data:", args, "failed")
        else:
            print("Test case passed!")

이제 test() 함수를 실행해보길 바란다!

드디어 결론

여기까지 읽어봤다면 글을 작성한 사람으로서 매우 기쁘다!! 위에 적은 문제 풀이 스타일이 무조건 정답이라 할 수는 없지만 다른 방법론들과 비교했을 때 큰 틀에서 벗어나지는 않을 것이다.

예시 문제를 지금 당장 풀기 힘들었어도 괜찮다. 서론에서 말한 문제를 해결하는 접근법에 대한 큰 그림을 생각했으면 좋겠다. 그리고 앞으로 수많은 문제를 만나게 될 여러분에게 조그마한 도움이 되었길 바란다.

다시 읽기 부담스러운 글이니 대강이나마 순서를 요약해본다.

0. 문제를 만나서 흥분하거나 쫄지않기!
1. 입력이 무엇인지 정확히 이해하기!
2. 출력이 무엇인지 정확히 이해하기!
3. 최대한 다양한 입출력 예시 써보기!
4. 손으로 의사코드 쓰기!
5. 더 간단한 방법이 있나 생각하기!
6. 큰 문제를 작은 문제로 나누어 점진적으로 코딩하고 테스팅하기!