[묘공단] 코딩테스트 스터디 1주차

이직을 한 이후로 면접관으로 들어가기 전 문제 검토 때가 아니면 자료구조/알고리즘 공부를 따로 하지는 않았는데, 좋은 기회로 스터디를 진행할 수 있게 되어서 대학생 때로 돌아간 것처럼 바짝 열심히 해보려고 한다. 목표는 AtCoder 청록색 레이팅인데 그동안 머리가 많이 굳어서 정말 열심히 하지 않으면 쉽지는 않을 것 같다. 그래도 공개적으로 이렇게 적어야 바로 아래 단계까지라도 가능하지 않을까, 화이팅!

이 글은 골든래빗 코딩 테스트 합격자 되기 파이썬 편의 0장 ~ 4장 써머리입니다.

0장. 코딩 테스트를 준비하기 전에

타인의 풀이를 보면 사고의 폭을 넓힐 수 있다

더 나은 시간 복잡도 풀이, 또는 언어의 문법을 잘 활용한 간결한 코드 등
비단 코딩 테스트뿐만 아니라 우리는 다른 사람의 코드를 수없이 보게 될 것이므로 이런 연습을 해두는 것이 좋다

시험 보듯 공부하라

연습을 실전처럼, 실전을 연습처럼
책에서 모의고사를 제공해 주기는 하지만, 조금 더 실전처럼 긴장감을 가지고 연습을 위해서 AtCoder와 같은 플랫폼을 고려해 보자
탑코더나 코드포스도 있지만, 시간대나 난이도를 고려했을 때 AtCoder가 적합하다고 판단됨

1장. 코딩 테스트 효율적으로 준비하기

언어 선택하기

변수 선언, 함수 정의, 컨테이너 자료형 (자료구조), 조건문, 반복문은 대부분의 범용 프로그래밍 언어에서 지원하므로 본인이 가장 자신 있는 언어를 선택
개인적으로는 지원하고자 하는 직군의 범용 언어로 준비하는 것이 안전하다고 생각한다

• Spring 백엔드 엔지니어 -> Java, Kotlin
• 프런트엔드 엔지니어 -> JavaScript
• 머신러닝 엔지니어 -> Python

회사나 면접관 성향에 따라 다르지만, 팀에서 주로 쓰는 언어에 제한을 두는 경우가 간혹 있음

문제 분석 연습하기

다른 좋은 내용들이 많지만, 특히 중요하다고 생각되는 부분이

• 입력값을 분석하라
• 핵심 키워드를 파악하라

드물지만 아주 작은 입력값이라면 불필요한 자료구조/알고리즘보다 하드 코딩이 가능할 때도 있고
입력값에 따라서 우리가 사용할 수 있는 알고리즘이 달라질 수 있으므로 이 부분이 중요하다고 생각된다 (대표적으로 TSP와 같은 문제)
핵심 키워드 역시 문제로부터 힌트를 얻을 수 있으므로 '항상' 문제를 잘 읽는 버릇을 들이자 (e.g., 쌍, 최근 -> Stack 등)

2장. 프로그래머스 완벽 활용 가이드

플랫폼 사용 관련 가이드이므로 생략

3장. 알고리즘의 효율 분석

시간 복잡도는 입력 크기에 대한 연산 횟수의 상한을 의미하며, 낮으면 낮을수록 좋음
빅오 표기법을 기준으로 최고차항만 남겨서 진행
선형 시간 O(N) 기준으로 최대 연산 횟수를 1,000만 정도로 고려해서 알고리즘 선택 및 후보군 압축

4장. 코딩 테스트 필수 문법

저자의 서술 전제가 파이선 기초서 1권을 완독 했다는 가정이므로 중요하다고 생각하는 부분들만 정리함

부동소수점 연산

이진표기를 하므로 실제 예상값과 다른 결과가 나올 수 있음
책에서 제시하는 예제는 0.1을 3번 더하고 0.3을 빼면 사람은 0을 기대하지만 실제로는 그렇지 않음
예전에는 대충 1e-9처럼 적당히 아주 작은 수를 기준으로 close를 체크했었는데
sys.float_info.epsilon을 앞으로는 활용하는 것이 좋겠다
실무에서는 비슷하게 torch.allclose, numpy.allclose 많이 사용

import sys

a = 0.1 + 0.1 + 0.1
b = 0.3
print(a - b)  # 아주 작은 값, 그러나 0은 아님

if abs(a - b) < sys.float_info.epsilon:
    print("a와 b는 같은 값")
else:
    print("a와 b는 다른 값")

리스트

아마 뒤에 나올 것 같지만, 마지막 원소가 아닌 인덱싱으로 값 삭제는 매우 비싼 연산이므로 값 삭제가 빈번하다면 다른 자료구조를 고려

딕셔너리

검색, 삽입, 삭제는 매우 중요하므로 잘 숙지할 것. Walrus 연산자를 잘 활용하면 좀 더 간결한 코드 작성이 가능하다

my_dict = {"apple": 1, "banana": 2, "cherry": 3}

key = "kiwi"    # kiwi is not in my_dict
if val := my_dict.get(key):
    print(f"값: {val}")  # 다시 my_dict.get(key) 또는 my_dict[key] 를 호출하지 않아도 됨
else:
    print(f"{key}가 딕셔너리에 없음")

문자열 추가, 삭제

이뮤터블 객체이므로 추가, 삭제 시 매번 새로운 객체가 생성된다
따라서 + 연산을 여러 번 반복할 것 같다면 join을 사용

# 매번 새로운 객체 생성
string = "He"
string += "llo"

# join 시 한 번만 새로 객체를 만들면 됨
string_list = ["He", "llo"]
result = "".join(string_list)   # Hello