이시윤 박사님 특강 - 코딩테스트

이시윤 박사님

코딩테스트

코딩 인터뷰

코딩테스트는 왜 하는가?

•   최소한의 문제 해결 능력을 확인하기 위하여

•   1. 문제의 문석과 해결 방안 착안

•   2. 이것을 코드로 구현

코딩테스트와 코딩인터뷰

•   코딩테스트: 코딩 문제를 풀어보게 함. 검증하려는 역량에 따라 문제 종류와 난이도가 달라짐

•   코딩인터뷰: 직무에 필요한 배경지식을 충분히 갖추고 있는지 점검. 생각한 바를 논리적으로 올바르게 전달할 수 있는지 점검. Whiteboard test, live coding 방법 등을 활용

(ex: binary search, 코드를 주고 틀린부분, 어떤 데이터 베이스에 연결해야하는데 객체한번 짜보세요. 한두개 틀린건 문제가 되지 않음. 전체적인 구조. Grepp도 코드를 보면서 코딩테스트 진행. 실제로 이 사람에에 이 일을 맡겼을 때 배경을 갖추고 있는가? 직무에 따라 인터뷰 양식이 많이 달라질 수 있음.

코딩 문제의 (대강의) 종류

•   Implementation 제시된 흐름에 따라 실행하는 코드를 만들도록 요구 (문제에 어떻게 흘러가야하는지 다 알려줌. 알고리즘을 제시되어 있고, 구현만 하면 됨)

•   Algorithm comprehension 문제의 효과적/효율적 해법을 찾아내도록 요구

•   효과적(effect): 얼마나 정확한 답을 낼 수 있느냐

•   효율적(efficiency): 빨리 답을 낼 수 있느냐. 시간복잡도, 공간복잡도 관련

•   현실에서는 효과와 효율이 서로 반비례하는 경우가 있음. 답이 아주 정확하지 않지만 빨리 결과를 도출하는 것을 원하는 경우, 답이 매우 정확하지만 도출까지 시간이 매우 오래 결릴 경우.

•   Competency test 특정한(고난도) 자료구조와 알고리즘을 착안하여 제한시간 내에 문제의 답을 도출하도록 요구

•   기타 특정한 언어 구문 (예: SQL) 을 활용할 수 있는지를 테스트

코딩 테스트에 대한 대비

•   1. 구현 능력 갖추기

•   * 적어도 하나의 프로그래밍 언어 (아이디어를 가지고 구형할 수 있어야함. 강사님 생각엔 파이썬이 코테에 최적)

•   2. 기본적인 자료구조 이해

•   * Array, Stack/Queue, Hash/Map, Tree, Graph,

•   3. 기초 알고리즘(정렬, 선택, 탐색) 및 시간/공간 복잡도에 대한 이해(효율적인 코드)

•   4. 현실 문제를 해결하기 위한 알고리즘 적용 해법 착안 사고훈련

•   5. 제한 시간 내에 오류 없이 코드 작성 및 디버깅할 수 있는 능력 훈련

•   4, 5은 많이 해봐야함. 실기에 가까운 측면이 있음. (몸에 익어야함, 악기연주, 스포츠 연습)

•   코딩테스트 문제를 직접 만들어보는 것도 도움이 됨.

자료구조

•   자료구조: 정보의 표현 방식과 여기에 정의되는 연산들의 집합

•   왜 알아야하나: 문제의 해결에 적용할 수 있는 도구를 갖추어야 하므로

•   자료구조와 알고리즘의 관계: 같은 문제의 해결에 대해서도 어떤 자료구조를 택하는지에 따라 적용할 알고리즘이 달라짐.

알고리즘 공부

•   일일이 외워야 하는 것이 아님

•   그러나 복잡한 문제에 대한 (게다가 현실의 문제를 해결하기 위해 빈번히 적용될 수 잇는) 해결법을 바닥부터 고안해 내기란 쉽지 않음

•   알고리즘 하나하나의 절차와 성질을 암기하는 것이 아니라 그것을 착안하는 생각의 흐름을 따라가는 훈련을 하는 것 (수학 공부를 하는 것과 비슷함)

•   추상화: 문제의 본질을 이해하고 -> “정보의 처리”로 접근할 수 있도록 핵심을 추려내는 능력

•   해법 착안: 코드에 의해 해법을 구현하기 위한 자료구조와 알고리즘의 어휘력이 필요

추상화 + 해법 착안: Problem solving

코드구현: Implementation

난이도가 있을수록 접근 방법이 정해져 있는 많음.

더 높은 난이도로 갈수록: 자료구조와 알고리즘 묶음 2개를 주고 선택에 따라 가점을 주는 식으로 냄.

빠지기 위순 함정

•   코드를 짧게 쓴다고 빠르게 실행되는 것은 아님

•   특히, SW 개발에 있어서는 짧은 코드 != 좋은 코드

•   내가 쓴 코드가 어떻게 실행되는지 이해하고 있는 것이 중요

•   (조금 더 나아가면) 문제의 성질이 어떤 것인지에 대한 이해

예시 1:

•   문제: 이진탐색 알고리즘을 구현하시오.

•   In -> 선형탐색의 문제가 발생

•   L.index(mid) -> 마치 인덱스를 한번에 찾아내는 것처럼 되어있는데, 아님. 이진탐색은 정렬되어 있다는 가정 하에, in, index 매서드는 파이썬은 선형탐색을 따르게 됨.

예시 2:

•   L1.append(y) O(1) 메모리 공간 하나 더 할당해서 이어붙이는

•   L2 = L1 + [y] O(n). L1 이외에 새로운 객체가 생성, 새롭게 L2에 대입됨. (훨씬 느림)

•   L1 == L2 True

후반부.

바둑판 – 돌의 좌표, 2차원 배열을 고려.

다양한 방법을 제안할 수 있음.

문제 중, 테두리를 넘어갔을 때 갈 수 없는지에 대한 판단이 있다. 이 경우 배열 인덱스가 [-1]의 경우, 파이썬은 맨 끝 배열로 인식 이는 bug 발생위험이 있어 주의해야함. (디버그가 어려워짐)

장애물 체크 시, 내 좌표범위가 판 안에 있는가를 판단해야함.

•   벗어나는지에 대한 함수

•   장애물 체크 함수

•   이동 함수

정도로 나눌 수 있는데, 이를 체크하는 함수를 만들어서 return True 식으로 판별한 수 이동시키는 방법이 있다.

강사님은 이에 판을 좀 더 키워서, 테두리를 장애물로 취급하게 되면 벗어나는지에 대한 함수는 고려하지 않고, 장애물 체크 함수만 사용하면 된다. -> 복잡도는 관련 없으나 코드가 편해짐

카카오. 입출차 문제

차 번호가 1만개의 경우로 주어졌지만, 한글까지 들어가게 되면 경우의 수가 늘어남.

핵심은 딕셔너리(해시테이블)을 활용해서 key=차 번호, value=입차 시각으로 하여 출차를 만나게 되면 출차 – 입차로 계산하는 것. 그 외의 요구사항은 살을 붙여나가면 될 것 같다.

강사님 의견:

dict로도 해보고, 배열로도 짜보고, 어떤 차이가 있는지 분석을 한 뒤에, 다른 사람 풀이를 보고 내 코드와 비교를 해보면서 점차 나은 코드를 반영하면 될 것 같다.

강의 진행 중에도 착안에 대한 설명까지만 듣고, 문제를 직접 만들어 풀어보는 것이 많은 도움이 된다고 하셨음.

소프트웨어 엔지니어링 차원에서는 clean code를 짜는 쪽을 훈련해볼 것을 권함.

è 코딩테스트와는 관련이 없지만 실무에 있어서 중요함.

코드인터뷰 시, 과제를 주고 제출을 요구, 또는 실시간으로 문제를 풀게 하는 것을 선호하는지.

è 즉석에서 문제를 보여주고, 알맞은 해법을 떠올리고, 문제풀기 유도.

è 엔지니어링의 경우 커뮤니케이션 능력이 중요. (주로 화이트보드) 어떻게 잘 전달할 것인 것

è 코드를 주고, 이는 무슨 소프트웨어이다. 코드를 짜고 실행해보라. 안좋은 코드를 주고 개선해보라. 등의 코딩 인터뷰가 있음. 코드를 잘 짜는지를 봄.

è 과제를 주고 짜오는 경우, 기능을 주고 요구한 사항을 만족하는 프로그램 (2~4일)을 제출해라. 이 경우, 실무진은 코드 짠거만 봐도 내공이 있는지 판단이 됨. 인터뷰는 아님.