정글사관학교 4일차 TIL: 알고리즘 풀이, 문제해결이란 무엇인가

첫날부터 흡사 정글에 있는 듯한 기분을 느끼게 했던 0주차 프로젝트가 끝나고 어제 목요일, 1주차 알고리즘 풀이에 들어섰다. 자료구조/알고리즘 문제를 공부하며 컴퓨팅 사고로 전환하는 것이 앞으로 4주 간의 목적이다. 알고리즘은 연구실에 있던 시절에 취미로 조금씩 풀어봤던 터라(그래봤다 한 30문제 풀었나..) 약간 익숙하긴 했지만 그래봤자 기초 수준이었다. 이번 주에 주어진 문제는 총 36문제. 어제 2시간 + 오늘 하루종일 해서 푼 문제는 25문제였다. 골드바흐의 추측 문제를 제외하면 다 풀기는 했다만 속도가 그렇게 빠르다고 느끼지는 않아 앞으로도 연습이 많이 필요할 것 같다.

 

모든 문제를 리뷰하기보다 풀면서 기억해두면 좋은 스킬 + 좋다고 생각한 문제 리뷰 정도로 진행하려 한다.

 

1. 기억해두면 좋은 스킬

1. input 더 빠르게 받는 방법: stdin.readline() & stdin.readline()이 input()보다 빠른 이유

달팽이 기어오르기 문제(달팽이는 올라가고 싶다)를 풀면서 일반적인 반복문으로 코드를 짰더니 계속 시간 초과가 떴다. 어떻게 속도를 줄일 수 있을까 고민하면서 구글링을 하던 중 알게 된 스킬이다. 문제에서 입력을 받을 때 input()으로 받는 것보다 sys 모듈을 import해서 stdin.readline()을 이용하면 훨씬 더 빠르게 받을 수 있다고 한다.

 

지금 TIL을 적기 전까지는 그냥 그러려니 하면서 무지성으로 갖다 썼는데, TIL 덕분에 왜 stdin.readline()이 더 빠른지, 대체 sys 모듈과 stdin의 정체는 무엇인지 고심하게 됐다.

 

먼저 sys 모듈부터 알아보자. 공식 문서에서는 아래와 같이 소개한다.

 

This module provides access to some variables used or maintained by the interpreter and to functions that interact strongly with the interpreter. It is always available.

이 모듈은 몇몇 변수로의 접근을 제공합니다. 이 변수들은 인터프리터에 의해 유지되거나 사용됩니다. 또한, 이 모듈은 몇몇 함수에도 접근을 허용하는데, 이 함수는 인터프리터와 강하게 상호작용합니다. 이는 항상 가능합니다.

...??

다행히 점프 투 파이썬에서는 친숙하게 설명해준다. "sys 모듈은 파이썬 인터프리터가 제공하는 변수와 함수를 직접 제어할 수 있게 해주는 모듈이다."라고. 말 그대로 인터프리터를 제어하게끔 돕는 친구 정도라고 이해하자.

 

다음은 stdin()에 대한 설명이다. stdin은 standard input의 줄임말이다. (standard output(=stout) 역시 존재한다.) 공식 문서를 살펴보자. "stdin is used for all interactive input (including calls to input());" 설명처럼 stdin은 대화식(=interactive) input과 관련된 모든 것에 사용되는 메소드다. 설명에서처럼 input() 역시 stdin()에 포함되는 거였다..!

 

stdin이 모든 대화식 입력에 사용된다는 말은 즉, 백준 문제를 풀 때 문자열/숫자/리스트 등만 받는 게 아니라 파일을 받거나 이미지를 받는 등 보다 넓은 범위의 입력을 의미한다. 문제를 풀 때는 여기까지 고려하지는 않으니 알아만 놓고 있자.

 

먼저 input()이 어떻게 입력을 저장하는지부터 살펴보자.

 

1. input()이 호출되면 ()안에 인자로 주어진 prompt 문자열을 화면에 출력하고, 프로그램은 사용자의 입력을 기다린다. 이때 표준입력은 키보드에서 받는다.

2. 사용자가 하나씩 키를 누를 때마다 이에 대응하는 데이터가 버퍼에 들어간다.

3. enter 키를 누르면 개행문자(줄바꿈을 말한다. \n 같은 애들)가 입력된다. 개행문자를 받으면 버퍼의 입력이 종료된 것으로 간주한다.

4. 입력된 문자열은 해당 시스템의 콘솔 입출력 인코딩을 사용하여 디코드되어 유니코드 문자열로 변환된다.

5. input() 함수는 변환된 문자열 값을 반환하며 종료한다.

*버퍼(buffer): 데이터를 한 곳에서 다른 한 곳으로 전송하는 동안 일시적으로 그 데이터를 보관하는 메모리의 영역이다.

우리가 흔히 말하는 버퍼링(buffering)은 이 버퍼와 관련되는 개념인데, 버퍼링은 버퍼를 활용하는 방식 또는 버퍼를 채우는 동작을 말한다. 우리가 버퍼링 걸린다고 할 때 버퍼링은 어떤 정보를 전송받는 동안 그 데이터가 버퍼를 채우는(=정보를 버퍼에 저장하는) 과정을 말하며 이게 오래 걸리면 그만큼 기다려야 된다.

영상을 전송할 때는 한 번에 보내면 시간이 오래 걸리니 몇 초 분량만 미리 버퍼링(소량만 버퍼에 저장)하고 나머지는 전송하면서 계속 보낸다. 그래서 영상을 앞으로 당기거나 혹은 전송환경이 불안정해 버퍼링 속도가 보장되지 못할 정도로 인터넷이 느리면 버퍼는 금새 고갈되고 재생 분량이 버퍼를 넘어서 재생이 멈춘다.

 

<출처: 링크1 링크2>

 

 

그러면 stdin.readline()과 input() 함수 간 속도 차이는 어디서 발생할까? 두 함수 간 속도 차이는

1) prompt 출력 여부와

2) 한 번에 읽어오냐(stdin.readline()) vs. 키보드를 하나씩 누를 때마다 저장하냐(input())의 차이에서 온다.

 

특히 2)한 번에 읽어와 버퍼에 저장하는 stdin.readline()가 하나씩 누를 때마다 데이터를 버퍼에 보관하는 input()보다 처리 속도가 빠르다. 즉, 버퍼 사이즈 차이로 입력이 반복될 수록  stdin.readline()이 우위를 가진다.

 

그럼 반대로 입력값에 몇 글자 큰 차이가 없다면 input()이나 stdin.readline()이나 큰 차이는 없다고 봐도 무방하겠다.

 

 

2. 입력 받을 때 숫자로 받기 & 숫자 리스트로 변환하기

위에서 stdin.readline()을 소개했으니 앞으로 입력 관련해서는 전부 stdin.readline()으로 쓸 것이다.

 

입력을 받을 때는 기본적으로 문자열로 받게 되어 있다. 입력값이 문자인지 숫자인지 특수문자인지 모르니 모든 문자 입력에 대한 정보를 담고 있는 유니코드로 변환하기 위해 문자열로 받는 것이다. 이걸 일일이 숫자로 변환하려면 여간 애를 먹는 것이 아니다.

 

하지만 list()와 map()을 이용하면 아주 쉽게 문자열로 들어온 숫자를 숫자로 변환 가능하다.

 

1) 특정 변수에 숫자를 받을 때

 

• 받으려는 숫자가 1개일 때

from sys import stdin

a = int(stdin.readline())

 

• 여러 개의 숫자를 변수로 받을 때

from sys import stdin

a, b = map(int, stdin.readline()) #map() 사용
# map(str, stdin.readline()) => 만약 문자 그대로 받을 거면 str을 사용!

 

2) 리스트에 숫자 그대로 저장할 때

from sys import stdin

#들어오는 문자열이 공백으로 분리되어 있을 때
a = list(map(int, stdin.readline().split())) #list(), map() 사용

 

3. 문자열을 한 글자씩 쪼개서 리스트에 저장하기

list() 함수를 사용하면 아주 간단하게 쪼개기가 가능하다.

 

from sys import stdin

a = list(stdin.readline()) # a= "Hi"

print(a) # a = ['H', 'i']

 

2. 문제해결이란 무엇인가

위에 문제풀이할 때 요긴하게 쓸 스킬을 쭈욱 적어둔 터라 여기까지 읽을 사람이 얼마나 있을 지 모르겠지만.. 사실 오늘 배웠던 것 중에 가장 기억에 남았던 것은 스킬도 문제도 아닌 코치님의 말씀이었다.

 

처음 알고리즘 문제를 접할 때도 잘 이해가 되지 않았던 게 하나 있었다. 대체 문제의 조건을 왜 이렇게 빽빽하게 설정해두는 걸까? 예를 들어 "리스트 순서를 뒤집으세요"라는 문제가 있다고 하면, 리스트의 길이부터 리스트에 들어가는 값의 유형은 무엇인지 등. 다행인지 불행인지 그간 혼자 알고리즘 문제를 풀어볼 때는 케이스 정의가 그렇게 민감하게 다가오지 않았다. 어찌 보면 문제를 정말 잘 만든 것이고 반대로는 그만큼 제한을 잘 걸어둔 덕분에 예외가 무엇인지를 전혀 경험해보지 못했다.

 

시작은 지난 카카오 코테였던 것 같다. 가장 쉬운 난이도 문제를 푸는데 어찌저찌 답을 구현했건만 예외 케이스에 걸려서 결국 풀지 못했다. 꽤나 당황했던 기억이 난다. 그때는 진지하게 코테를 풀려 했다기보다 경험만 해보자는 생각이었어서 당황만 하고 넘어갔는데 그게 이번주 내내 했던 경험에 트리거가 되었다.

 

0주차 프로젝트 때도 마찬가지였다. 로그인을 할 때 사용자가 어떤 짓을 할 지 모르니 예외 케이스에는 무엇이 있을지 일일이 고민해야 했다. 사용자 입장에서는 불편하다거나 혹은 너무 당연하게 여겼던 비밀번호 재확인 기능부터 시작해 뒷단에서 직접 만들어봐야만 깨달을 수 있던 수많은 문제들.

 

코치님께서 오늘 이렇게 말씀하셨다.

코딩 테스트는 문제를 잘 푸는 걸 보려는 게 아니라 어떻게 문제에 접근하는지를 보는 게 목적이다.
'array를 뒤집어 보세요'라는 문제를 냈을 때 출제자가 기대하는 것은 단숨에 빠르게 문제를 푸는 지원자의 모습이 아니라 'array를 새로 만들어도 되나요? 아니면 기존 array를 뒤집나요?'와 같이 지원자가 던지는 질문이다

 

 

모호한 문제를 엄밀하게 만들어나가기 위한 질문의 과정이 코테를 보는 목적이다. 백준과 같이 코테를 연습하는 사이트에서는 이러한 질문을 이미 다 반영해 놓은 엄밀한 문제만 있으니 질문할 틈 없이 어떻게 하면 빠르게 풀 수 있을지에만 전념하게 된다.

 

물론 이왕이면 잘 푸는 게 좋으나, 시키는 대로가 잘 푸는 개발자가 아니라 문제를 만들어낼 수 있는 능력이 있는 개발자인지를 테스트하는 게 코딩 테스트의 목적임을 기억하자. 개발자는 시키는대로 하는 사람이 아니라 문제를 새롭게 정의할 수 있는 사람이어야 하기 때문이다.

 

오늘 푼 문제 중 하나에서 역시 이런 일이 있었다. 위에서 스킬 소개할 때 언급했던 달팽이 문제(달팽이는 올라가고 싶다)였다. 늘상 하던 방식으로 반복문으로 짰더니 시간 초과가 뜨더라. 입력값 조건을 보니 1억이 들어가더라. 짰던 코드의 경우 O(n)이었어서 결국 1억 번 반복해야 하는 문제가 발생하는 게 원인이었다. 조금만 생각해보면 1차 부등식을 이용해 O(1)로 아주 간단하게 문제가 풀린다. 

 

이것이 코테니까 아무 생각없이 반복문부터 짰지만 만약 실제 서비스라고 하면 이렇게 접근해도 됐을까? 무지성 코테 연습에 경각심이 일었던 문제였다. 예외 케이스를 고민하는 게 왜 중요한지 이번 주 내내 뼈저리게 느꼈다. 코테는 열심히 연습하되 무지성 개발자가 되지 말자.