week01

알고리즘 주차 시작

 

기초적인 입 출력, 반복문 문제를 풀고 크게 재귀,  정렬, 완전탐색, 분할 정복, 이분 탐색의 문제들을 풀었다.

배운 지식을 이야기 하기 전에 한주동안 배운 방법론은 해야할 과제가 많고 시간이 부족하다면, 해결하는데 사용되는 기반 지식 혹은 이미 해결한 사례를 빨리 익히고 넘어가고 나중에 활용하는 것이다.

예를 들어 하 문제들은 공부를 하고 푸는데도 오래걸린다면 그냥 답을 보고 내것이 될때 까지 빨리 익히고 난이도가 높은 문제에서 어떻게 활용할지 고민하는데 시간을 쓰자

 

컴퓨터 사고로의 전환

우리의 과제는 알고리즘 문제를 쭉 푸는 것이지만 이번 주차의 이름은 '컴퓨터 사고로의 전환' 이다.

왜 이런 이름이 붙었는지는 문제를 풀면서 깨닫게 되었다. 어떤 문제를 풀때 우리 사람은 간단하게 계산을 해내지만 사실은 머릿속에서 임시 변수들을 만들어 생각을 저장하고 어떤 순서로 사고를 해나갈지 본능적이고 직관적으로 해나간다. 하지만, 이것을 컴퓨터로 옮길때 문제가 발생한다. 컴퓨터는 한번에 한가지 계산밖에 못해내고 당장 주어진 순서로 계산하기 때문이다. (아직 내가 아는 지식에선 그렇다.)

 

그래서 어떤 문제를 풀때 내가 하는 생각을 정말 단순한 하나의 단위로 쪼개봐야한다.

 

예를 들어

1 + 1

을 계산한다 치자

 

우리는 주어진 1 + 1 문자중 제일 첫번째 문자를 읽고 그다음 연산자를 읽고 계산할 준비를 한다. 그다음 숫자 1을 보고 계산한 값인 2를 떠올린다. 이를 풀어서 보면

1. 주어진 문자열에서 맨앞 한 문자 씩 꺼내서 본다.
2. 연산자를 만나기 전까지 숫자를 기억한다. ( temp_1 = 1, 와같이 변수에 저장해서 기억해둔다.)
3. 연산자를 만나면 어떤 명령(함수)을 수행할지 기억하거나 호출한다. (우리 머리속에 있는 덧셈(a, b) 함수를 꺼내 쓴다)
4. 연산자를 만났으면 다음 숫자를 기억한다. ( temp_2 = 1, 처럼 피 연산자를 변수에 저장한다.)
5. 조회가 끝났으면 지금까지 쌓인 정보를 바탕으로 명령을 수행한다.

이를 코드로 옮겨보면

string_input = ['1', '+', '1']   # 주어진 문자열 // 사람은 문자를 받아 읽는다.

result = 0			# 사람은 필요할때 변수를 생성하지만 컴퓨터는 미리 생성해줘야한다
temp_1 = 0
operator = ''
temp_2 = 0

read_one = 0
for next_letter in string_input:		# 문자를 끝까지 읽을때 까지 반복한다.
    if next_letter.isdigit():   # 숫자인지 확인 // 우리 사람은 본능적으로 타입변환을 한다.
        if read_one == 0:
            temp_1 = int(next_letter)   # 첫 번째 숫자 저장
            read_one = 1
        else:
            temp_2 = int(next_letter)   # 두 번째 숫자 저장
    else:
        operator = next_letter   # 연산자 저장

if operator == '+':
    result = sum(temp_1, temp_2)   # 덧셈 수행

print(result)

파이썬으로 실행해보면 2가 출력된다!

 

컴퓨터는 얼마동안 반복할지, 무엇들을 기억해놔야할지 미리 알려줘야한다. 사람처럼 수행하면서 유동적으로 그때그때 변수를 생성하고, 반복을 알아서 중단하기 힘들다!

 

먼저 사람처럼 생각한 것을 단계별로 잘 쪼개서 작성해보고 이 과정에서 기억해야 할것들이 무엇이고 어떤 순서로 기억될지 파악해보자. 그러면 어떠한 변수를 어떤형태로 (스택, 큐 혹은 단순히 값만 저장할건지) 미리 선언해둘지 알수있을 것이다. 또, 반복을 했다면 내가 어떤 조건을 만났을 때 반복을 그만두었는지 (우리가 문장을 읽을땐 다음 문자가 없다면 우리는 한글자씩 읽는 반복을 멈춘다.) 여러 경우의 수가 있는 문제인데 본능적으로 안되는 계산을 쳐냈을때의 조건 (집에 빨리가고 싶다면, 우리는 여러 갈래길중 계속 짧은 길을 선택하는걸 반복한다) 등을 잘 정리하면 반복문과 그것을 종료하는 조건을 알아낼 수 있을 것이다.

 

마치며,

지금 week02 를 진행하면서 글을 작성하였는데 생각을 쪼개서 잘 정리하더라도 컴퓨터의 언어로 옮기는 것은 참 어렵다. 컴퓨터는 우리가 생각한 순서의 반대의 순서로 작성해줘야하는 느낌적인 느낌이 있다.