구현

코딩 테스트에서 구현이란? 

머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다.

우리가 알고리즘 문제를 접하게 되면, 일단 문제를 읽고 어떻게 풀어나갈지 생각한다.

머릿속으로 어떤 식으로 문제 풀이하면 되겠다라는 생각이 드는 것도 중요하지만,

가장 중요한 것은 그 풀이 방식을 프로그래밍 언어로 정확히 구현할 수 있어야 하는 것이다.

이를 위해, 해당 프로그래밍 언어에 대한 문법을 정확히 알고 있어야 바로바로 해결할 수 있다.

(이를 위해, 현재 공부하고 있는 파이썬 관련 문법도 복습하는 차원에서 정리해보려고 한다.)

 

구현 유형의 문제는 풀이는 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 의미한다.

많은 경험자들은 '알고리즘은 설계했는데 구현이 먼저 풀 수 있는 문제가 없을 때 푸는 게 좋다'라고 말한다.

개발을 할 때 프로그래밍 언어의 문법에 능숙하고 코드 작성 속도가 빠른 사람을 '피지컬이 좋다'라고 이야기하는데, 

구현 유형의 문제들이 이러한 '피지컬'을 요구하는 문제라고 볼 수 있다.

 

그래서 본인과 같이 코딩 테스트와 새로운 언어 공부를 시작한지 얼마 안된 사람들에게는 이러한 유형에서 익숙치 않아 어려움을 많이 겪을 수 있지만, 경험을 쌓다보면 점차 '피지컬'이 상승할 것이다.

 

본 교재(이것이 취업을 위한 코딩테스트이다. with 파이썬)에서는 완전 탐색과 시뮬레이션 유형을 구현 유형에서 함께 다루고 있다.

완전 탐색은 모든 경우의 수를 주저 없이 다 계산하는 해결 방법을 의미하고

시뮬레이션은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행하는 유형을 의미한다.

 

 

 

 

상하좌우

문제 : 교재 110p 참고

 

해당 문제는 일련의 명령에 따라서 개체를 차례대로 이동시킨다는 점에서 시물레이션 유형으로 분류되며 구현이 중요한 한 문제 유형이다. (다만, 다른 교재나 문제풀이 사이트에서는 다르게 일컬을 수 있다.)

 

나의 풀이

풀면서도 느꼈다. 이거 아닌데;;;;

일단 코드를 설명하자면, A에 리스트 형태로 문자들을 입력받고, for문을 통해서 리스트 내의 문자가 각각 R, L, U, D와 일치한다면, 해당 문자에 대한 좌표 이동 값을 계산 및 저장 후 출력했다.

문제 난이도는 쉬운 편이지만, 이런 접근 방식을 의도해서 문제를 출제하지 않았을 것이라는 생각을 계속했다.

그럼에도 뭔가 딱히 떠오르는게 없어서 일단 이대로 마무리하고, 해설을 참고했다.

 

 

해설을 참고한 뒤의 코드

내 생각이 맞았다.

해설 코드에서는 L, R, U, D 의 문자들을 하나의 리스트에 저장해두었고, 문자에 따라서 좌표와 계산될 값들을 추가로 dx, dy 리스트에 저장하고, for문으로 문자값을 확인할 때마다, 리스트에서 적절한 값들을 가져와서 계산하였다.

이 코드가 훨씬 간결하고, 보기 좋았다. 

그리고 본인이 놓친 부분도 존재했다. 해설 코드 23번째 줄에서 이동하게될 좌표에 대한 범위도 확인해주었다.

본인은 이 부분을 고려하지 않았다. 나의 완벽한 실수다.

교재의 입력 예시만 성공했다고 다 확실한 코드가 아니다.

(입력 예시가 많아서 테스트를 많이 해볼 수 있으면 더 좋을 거 같다.)

 

 

 

시각

문제 : 교재 113p 참고

 

이러한 유형은 완전 탐색 유형으로 분류된다. 

완전 탐색 알고리즘은 가능한 경우의 수를 모두 검사해보는 방법이다.

완전 탐색 알고리즘은 비효율적인 시간 복잡도를 가지고 있으므로 데이터 개수가 큰 경우에는 정상적으로 동작하지 않을 수 있다. 그래서 일반적으로 알고리즘 문제를 풀 때는 확인해야 할 전체의 데이터의 개수가 100만개 이하일 때 완전 탐색 을 사용하면 적절하다.

 

 

이번 교재를 공부하면서 처음으로 문제를 풀지 못했다....

에러가 나기보다는 계속해서 출력값이 다르게 나왔다.

 

첫 번째는 시, 분, 초에서 3이 들어가는 경우를 다 계산을 하려고 했다.

분, 초는 0~59이기 때문에, 3이 포함되는 숫자들의 개수가 정해져있다.

중요한 것은 입력값에 따라 시에 3이 포함되는지 결정이되고 이에 따라 결과값도 달라지기 때문에, 입력값에 따라 다르게 계산하도록 분류를 하였다.

두 번째는 모든 경우의 수에서 3이 포함되지 않는 경우의 수를 제외시켜 계산하려고 했다.

이 역시 분, 초에서 제외되는 숫자들은 정해져있고, 입력값(시)에 따라 결과값이 달라진다.

 

문제를 풀면서, 이 방법 역시 뭔가 출제자의 의도에 벗어난 접근 방식이라고 생각을 했고, 심지어 원하는 결과값이 나오지 않아, 계속 문제의 원인을 찾다가 결국 해설을 참고하게 되었다.

 

 

해설을 참고한 뒤의 코드

처음 해설 코드를 보았을 때, 너무 허무했다. 

너무나도 단순한 문제였고, 이를 증명하듯이 코드량 또한 매우 짧았다. 

너무 복잡하게 생각하지 말고, 쉽게 접근을 해봤어야 했는데,,,

단순히 입력값(시) 만큼 반복해서 해당 분, 초 범위(0~59) 내에서 문자 '3'이 존재할때마다, 횟수를 증가 시켜주는게 끝이었다.

그리고 반복문이 많아서, 이게 효율적인 코드가 맞나?라는 생각을 잠시 했지만, 00시00분00초~23시59분59초 사이의 모든 경우의 수는 86,400가지 밖에 존재하지 않기 때문에, 시간 제한 부분에서 크게 문제될 것이 없다.

 

이전에 다뤘던 다른 코드에서는 반복문을 통해, 의미없는 연산을 얼마나 수행할지 알 수 없기 때문에, 시간 제한 문제를 고려하며 최대한 효율적으로 코드를 작성하려고 했지만, 이러한 '시각' 관련 문제는 경우의 수가 정해져 있기 때문에 그럴 걱정이 없다... 또 한번 배우고간다.

 

 

 

왕실의 나이트

문제 : 교재 115p 참고

 

해당 문제는 앞에서 다룬 '상하좌우' 문제와 비슷하다.

 

나의 풀이

난이도는 쉬웠다.

위에서 언급한 것과 같이, 앞서 다룬 상하좌우 문제와 흡사하였고 어느 정도의 노하우를 알고 문제에 접근해서 그런지 해설과 조금 표현의 차이만 있을 뿐, 접근 방식은 거의 동일하였다.

각 입력값들은 문자로 입력됐기 때문에, 각각 정수형으로 변환을 하고, 나이트의 위치에서 움직일 수 있는 모든 경우의 수를 계산할 수 있도록 추가로 리스트 형태로 계산할 값들을 만든 뒤, 반복문을 통해 나이트가 이동한 모든 경우의 좌표값을 구하고, 해당 값이 범위내에 존재하면 count를 증가시켜주는 방식으로 접근하였다.

 

그런데 해설 코드를 보면서 궁금한 점이 생겼다.

 

 

해설을 참고한 뒤의 코드

문자를 정수값으로 변환하는 과정에서 ord()함수를 사용하는 것은 본인과 동일하지만, ord()로 변환한 뒤에 추가로 앞에int를 붙여서 정수형으로 변환하는 연산을 추가로 하였다. 

ord()를 사용하면, int형으로 변환이 자동으로 된다고 알고 있었다. 그래서 혹시 몰라 print문을 통해서 type검사를 했지만, 역시나 int형이 출력되었다.

이 부분에서 뭔가 특별한 이유가 있는지 궁금하다. 혹시 내가 모르고 지나치는 부분이 있을지 모르니까

 

 

 

게임 개발

문제 : 118p 참고

 

전형적인 시뮬레이션 문제이다. 별도의 알고리즘을 요구하기보단 문제 내용을 성실히 구현만 하면 풀 수 있는 것이 특징이다. 다만, 문제가 길고 제대로 이해한 상태로 소스코드를 만들어가는 과정이 완전 쉽지만은 않을 것이다.

따라서, 이러한 문제들을 반복적으로 풀어가며 '피지컬'을 상승시킬 필요가 있다.

 

 

나의 풀이

 

문제 난이도는 평이한 편이지만, 주어진 조건을 충족시키기 위해 여러 제약들이 존재하기 때문에, 다뤄줘야할 경우의 수들이 여러 존재하였고, 주석을 적어두다 보니 코드가 좀 길어졌다.

코드를 짜면서, 이렇게 일일이 조건 만들어주는게 맞는건가 싶은 생각이 들었지만, 이런 유형은 어쩔수 없는 것 같다.

 

일단 코드 설명을 하자면, 입력값을 토대로, game_map이라는 리스트를 적절한 크기로 생성하고, 입력값들을 리스트에 삽입한다. 문제 조건에서 방향 전환을 반시계방향으로 한다고 정해졌기 때문에, 북을 0으로 기준잡고, 북, 동, 남, 서 순으로 리스트 순서를 정한 뒤, 각 방향으로 이동함에 따라 계산될 값들을 리스트에 저장하였다.

 

그리고 while문에서 만약 앞으로 이동할 것으로 예상되는 좌표가 game_map의 범위에서 벗어난다면, break문으로 while문을 빠져나오고, 범위를 벗어났다는 문구와 함께, 현재 위치 좌표를 출력한다. (이 부분은 문제와 관련없이, 그냥 본인이 예외처리를 확인하고자 임의로 넣었다.)

그렇지 않은 경우는, 이제 2가지 case로 나뉘는데, 앞으로 이동할 것으로 예상되는 좌표의 값이 0(육지)이면, 이동을 한다는 의미로, 현재 좌표를 해당 좌표로 수정해주고, 왼쪽으로 회전했다는 의미로 d값을 계산해준다.

그렇지 않고, 앞으로 이동할 것으로 예상되는 좌표가 바다이거나 이미 가본 좌표라면, 제자리에서 왼쪽으로 회전만하고, 다시 while문의 처음 단계부터 시작한다. 

만약 한바퀴를 회전할 때까지 이동할 수 있는 좌표가 없는 경우는, 제자리에서 뒤로 이동하고 다시 이전의 단계를 수행한다. 만약 뒤로 이동할 때, 해당 좌표가 1(바다)라면, 이동하지말고 while문을 종료한 뒤, 현재 좌표를 출력한다.

 

 

해설을 참고한 뒤의 코드

접근 방식에서는 나의 코드와 크게 다르진 않았다.

차이점이 있다면, 일단 방향 전환 부분을 함수를 통해 구현한 부분 이를 위해 global 키워드를 사용한 점과 리스트에 값을 삽입하는 방식 정도에서 차이가 있는 것 같다.

 

그리고 해설 코드에는 따로 index 범위를 벗어나는 것에 대한 예외를 처리하는 부분이 존재하지 않았는데, 

필자는 실무의 코딩은 예외를 고려해서 코드를 짜야 하지만, 코딩 테스트는 입력값이 주어지는 경우가 대부분이므로, 이런 예외처리를 고려하지 않고 빠르게 코드를 작성하는데 목표를 두어야 한다고 설명하였다.

 

이는 따로 index 범위를 벗어나는 error를 크게 의식하지 않고 코드를 작성해도 된다는 의미인건가?

 

 

 

느낀점

계절학기 첫 수업날이라 그런지, 아직까지는 여유가 있어서 글을 남긴다. 쉬운 문제였지만, 처음으로 문제 1개를 해결하지 못하였다는 점에서, 좀 반성하게 되었다. 빠르게 교재를 공부하고, 반복하여 '피지컬'을 빨리 키우고 싶다.

그리고, 위에서도 언급하였지만, int(ord('?')) 부분과 index 범위 관련해서는 아직 궁금중을 해결하지 못했다.

책을 훑어봤을 때, 필자에게 질문도 남길 수 있다는데, 찾아보고 질문해야겠다.

혹시 이 글을 보고 있고, 이에 해답을 알고 계시는 분은 답글 부탁드립니다.

 

 

 

만약 이 글을 읽고 있는 사람이 존재한다면, 어떠한 피드백 환영입니다.

 

블로그 작성코드 부분이든, 글의 내용이든, 블로그 관련된 것이든 부족하고나 수정이 필요한 부분이 눈에 보인다면, 피드백 부탁드립니다.