코딩 테스트 개요 및 파이썬 문법 정리

• 2022/05/15
• 12-minute read

참고 원본 - 코딩 테스트 출제 경향 분석 및 파이썬 문법 부수기

Table of Contents

• 코딩 테스트
  • 코딩 테스트 ?
  • 온라인 저지
  • 코딩 테스트용 언어
  • 개발형 코딩 테스트용 언어
  • 코딩 테스트 준비를 위한 환경
  • 팀 노트
  • 출제 경향
  • 알고리즘 성능 평가
  • 알고리즘 설계 Tip
  • 알고리즘 문제 해결 과정
• 파이썬 문법
  • 자료형
  • 입출력
  • 조건문
  • 반복문
  • 함수
  • 람다 표현식
  • 유용한 표준 라이브러리

코딩 테스트란?

• 자동 채점 시스템을 도입하여, 문제 해결 능력 평가 시험
• 큰 회사의 채용 시스템에 주로 사용
• 작은 회사 또는 지원자의 수가 적은 경우는 개발형 코딩 테스트도 가능
  • 개발형 코딩 테스트 : 요구 사항과 개발 프로그램의 내용을 설명하고, 실제 개발처럼 진행
• 온라인과 오프라인으로 나뉨
  • 온라인: 문제 풀이를 공유하지 않는 선에서 인터넷 사용 가능
  • 오프라인: 제공되는 환경만을 사용하며, 인터넷 사용 불가능
• 테스트를 여러 단계로 진행하는 경우
  • 1차는 온라인, 2차는 오프라인 등이 될 수 있음
  • 2차에 개발형 코딩테스트도 가능

코딩 테스트 준비를 위한 온라인 저지

• 해외 사이트
  • 코드 포스
  • 탑 코더
  • 릿 코드
  • 코드 셰프
• 국내 사이트
  • 백준 - 기출 문제가 많음
  • 코드 업 - 초급 문제가 많음, 기초 다지기 및 처음 시작하기에 좋음
  • 프로그래머스 - 기출문제 많음
  • SW Expert Academy

일반 코딩 테스트를 위한 언어

• C, C++, Python 정도가 우수한 대표적
• C, C++: 메모리 관리 및 전체적인 자유도가 높음
• Python: 다양한 라이브러리가 제공되며, 기본 자료형이 우수
• 시간이 없다면, 가장 익숙한 언어가 좋음
• 새로운 것을 배울 시간이 있다면, Python이 가장 좋은 선택

개발형 코딩 테스트 언어

• 압도적으로 Python이 우수
• 개발형 코딩 테스트: 실제 Application 구현 또는 해커톤 방식을 사용
• 개발형 코딩 테스트 특성 상, 실제 수행 시간이 그렇게 중요하지 않은 경우가 많으며, API 등을 사용할 일이 많으므로, Python이 상대적으로 유리 (Request library, Json library 등이 standard에 포함되어 있음)

코딩 테스트를 위한 환경

• 온라인 개발 환경
  • 리플릿
  • 파이썬 튜터
  • 개발환경 구축에 많은 시간을 들일 필요 없음
  • 언제든 같은 환경에서 진행이 가능
• 오프라인 개발 환경
  • Pycharm
  • 코딩 테스트 특성 상, 프로젝트 관리 보다는 하나의 파일로 작성 및 제출하는 경우가 많으므로, 굳이 오프라인 환경을 고집할 이유는 없음
  • 대표적으로 Pycharm이 파이썬 사용 시에는 좋음
• C++
  • Dev-C++
  • 가장 간결하고, 간단하게 설치해서 사용이 가능

소스 코드 관리

• 자주 사용하는 알고리즘 코드를 library화 하는 것이 좋음
• 팀 노트
  • 팀 노트: 알고리즘 문제 해결을 위한 자신만의 알고리즘 노트
• 점점 비슷한 코드가 증가하므로, 기록 및 재사용을 위해 관리하는 것이 좋음

출제 경향

• 약 2 ~ 5시간 정도 진행
• 쉬운 난이도의 문제에서는 그리디 알고리즘이 가장 많이 나오며 약 20%를 차지
• 구현 및 BFS/DFS가 각각 33%, 21% 로 일반적으로 많이 나옴
• 다이나믹 프로그래밍이 8%로 그나마 많이 나오는 편임
• 그 외 정렬, 이진 탐색, 그래프 이론, 최단 경로 알고리즘이 출제

삼성 전자

• 완전 탐색, 시뮬레이션, 구현, BFS/DFS 주로 출제
• 2문제 중 2문제 다 맞춰야 합격 가능

카카오

• 구현, 이진 탐색, 자료 구조, 그리디 주로 출제
• 7문제 중 3~4문제 정도 맞춰야 합격 가능
• 카카오 기술 블로그에서 기출 문제 해설 확인 가능

라인

• 탐색, 구현, 문자열, 다이나믹 프로그래밍, 그리디 주로 출제
• 5문제 중 2~3문제 정도 맞춰야 합격 가능

알고리즘 성능 평가 방법

• Time-Complexity: 입력 크기에 대한 처리 시간 분석
• Space-Complexity: 입력 크기에 대한 메모리 사용량 분석
• 복잡도는 낮을수록 좋은 알고리즘
• Big-O Notation
  • 알고리즘 처리 속도를 표현하는 방식
  • 입력 크기 N에 대한 처리 횟수를 나타내는 방식
  • 최종 처리 횟수 중 가장 빠르게 증가하는 항만 남김
  • $N –> \inf$ 일 때를 가정하고 표현
  • $3N^3 + 5N^2 + 1,000,000 \rightarrow O(N^3)$
  • $O(1) > O(logN) > O(N) > O(NlogN) > O(N^2) > O(N^3) > O(2^n) > O(N!)$
  • 1중 for문 $\rightarrow O(N)$
  • 2중 for문 $\rightarrow O(N^2)$

알고리즘 설계 Tip

• 연산횟수 5억번 기준
  • C언어: 1~3초 (평균 2초)
  • Python: 5~15초 (평균 10초)
  • CPython 보다 PyPy로 제출하는 것이 유리할 때가 있음
  • $N=5000, N^3=125,000,000,000$
  • 1250억 / 5억 = 250
  • $250 \times 10 == 2500$초
• Python일 경우, 1초에 약 2000만번 정도 처리하다고 가정하면 쉬움
• 시간 제한이 1초인 문제
  • $N<500 \rightarrow O(N^3)$ 까지 사용 가능
  • $N<2000 \rightarrow O(N^2)$ 까지 사용 가능
  • $N<100,000 \rightarrow O(NlogN)$ 까지 사용 가능
  • $N<10,000,000 \rightarrow O(N)$ 까지 사용 가능
  • 절대적인 것은 아님

알고리즘 문제 해결 과정

1. 문제 읽기, 컴퓨터적인 사고를 통해 문제 쪼개기 (Divide)
2. 복잡도 분석 (요구 사항 확인)
3. 아이디어 찾기 (문제 풀이를 위한 아이디어)
4. 소스코드 설계 및 코딩

• 대부분의 문제는 핵심 아이디어를 캐치한다면, 간결하게 소스코드가 작성 가능한 형태
• 수행 시간 측정을 위해 time module 활용

  import time
  start_time = time.time()
  # =================
  # 실제 동작 부분 삽입
  # =================
  used_time = time.time() - start_time
  print(used_time)
  

자료형

• 정수형 - Int
  • 양수, 음수, 0을 표현 가능
  • 대부분의 코딩 테스트에서 사용
• 실수형 - Float
  • 소수점 아래의 숫자가 있는 데이터
  • .을 붙이면 자동으로 실수형으로 정의
  • 0.0 = 0.
  • 0.7 = .7
  • 위와 같이 사용 가능
  • 지수 표현 방식
    • 유효숫자e지수 로 사용할 수 있으며, ${유효숫자} \times 10^{지수}$ 를 의미
    • float_number = 1e9 $\rightarrow 1000000000$
    • 임의의 큰 수를 나타낼 수 있음
    • 최단경로 알고리즘에서 도달할 수 없는 Node에 대해 INF로 설정할 수 있지만, 가능한 최대값이 10억이라면, 1e9로 표현 가능
  • 실수형 사용시 주의 사항
    • 컴퓨터는 정확한 실수 값을 저장할 수 없는 경우가 많음

    a = 0.3 + 0.6
    print(a == 0.9) # False
    

    • 위와 같은 상황을 방지하기 위해, round() 함수 사용

    a = 0.3 + 0.6
    print(round(a, 1) == 0.9) # True
    

    • round(입력, 자리 수)
    • round(123.456, 2) $\rightarrow 123.46$
  • / 사용 시, 무조건 결과 값이 실수형으로 반환된다는 점을 주의
• 리스트 - List
  • C의 배열, Linked List와 유사
  • C++ STL Vector와 유사
  • data = [] 또는 data = list()로 초기화 가능
  • data[0] 또는 data[-1] 등으로 접근 가능 (0부터 시작, 역순은 -1부터)
  • 리스트 인덱싱
    • 특정 원소에 접근하는 것
  • 리스트 슬라이싱
    • 연속적인 위치의 값을 가져오는 것
    • data[2:5] $\rightarrow$ 2~4번째 원소를 가져오는 것 (5가 아닌, 4임을 주의)
  • 리스트 컴프리헨션
    • 대괄호 안에 조건문 및 반복문을 사용하여 리스트 초기화
    • data = [i for i in range(10)] $\rightarrow$ [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    • data = [i for i in range(20) if i % 2 == 1] $\rightarrow$ [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
    • data = [i * i for i in range(1, 10)] $\rightarrow$ [1, 4, 9, 16, 25, 36, 49, 64, 81]
    • 2차원 list 초기화 시 유용하게 사용 가능
      • N $\times$ M 크기 초기화 예시
      • data = [[0] * m for _ in range(n)] (for문 내부에서 값을 사용하지 않을 경우, _ 처리 가능)
      • data = [[0] * m] * n (이렇게 쓰면 문제 발생)
  • append()
    • data.append(10)과 같은 형태로 사용
    • 리스트 맨 뒤에 값을 삽입
    • $O(N)$의 복잡도를 가짐
  • sort()
    • data.sort()와 같은 형태로 오름차순 정렬 가능
    • data.sort(reverse=True)와 같은 형태로 내림차순 정렬 가능
    • $O(NlogN)$의 복잡도를 가짐
  • reverse()
    • data.reverse()와 같은 형태로 순서를 반대로 변경 가능
    • $O(N)$의 복잡도를 가짐
  • insert()
    • data.insert(3, 20)과 같은 형태로 3번째 위치에 20이라는 값 삽입 가능
    • $O(N)$의 복잡도를 가짐
  • count()
    • data.count(3)과 같은 형태로 3이 리스트 내부에 몇개 있는지 확인 가능
    • $O(N)$의 복잡도를 가짐
  • remove()
    • data.remove(3)과 같은 형태로 3을 하나 삭제 가능
    • $O(N)$의 복잡도를 가짐

  # remove() 사용 없이, 리스트에서 특정 값 모두 삭제
  data = [1, 2, 3, 4, 5, 6]
  remove_set = {3, 5} # 집합
  
  result = [i for i in data if i not in remove_set]
  

• 문자열 - String
  • data = "" 또는 data = ''으로 초기화 가능
  • 문자열 간의 더하기 가능

  data = 'hello' + ' ' + 'world'
  print(data) # hello world
  

  • 문자열과 정수형 사이의 곱셈 가능

  data = 'a' * 10
  print(data) # aaaaaaaaaa
  

  • 문자열은 중간의 하나의 값만 변경할 수 없음 (Immutable)
  • 인덱싱 및 슬라이싱은 가능 (특정 위치 접근 및 중간 부분만 가져오기)
• 튜플 - Tuple
  • 리스트와 유사하지만, 값의 변경이 불가능
  • data = ()로 초기화 가능
  • list에 비해 메모리 공간이 효율적
  • Tuple 사용이 적합한 경우
    • 서로 다른 데이터를 묶어서 관리해야할 때
      • 최단 경로 알고리즘 - 비용과 노드 번호를 묶어서 관리
    • Hashing 키 값으로 사용해야할 때
      • list의 경우 중간에 값이 변경될 수 있어서 부적합
    • list에 비해 메모리가 효율적이어야 하는 경우 사용
• 사전 - Dictionary
  • key, value를 쌍으로 가지는 자료형
  • key는 중간에 변경이 불가능
  • Hash Table을 사용하므로, 접근 및 수정 시 복잡도가 $O(1)$
  • key값만 필요한 경우 dict.keys()
  • value값만 필요한 경우 dict.values()
  • keys(), values() 모두 반환 형태가 dict.list이므로, 사용을 위해서는 list로 변환 필요
  • key는 변경 불가능한 값을 사용해야하며, 이를 통해 value에 접근 가능
• 집합 - Set
  • 데이터의 중복이 없으며, 순서가 없는 자료형
  • 데이터의 존재 여부 확인 시 매우 유용
  • 다른 list 또는 문자열로 초기화 가능
  • data = set(other_list) 또는 data = set(other_string) 형태로 사용 가능
  • data = set() 또는 data = {a, b, c}로 초기화도 가능
  • 데이터 조회 및 수정에 복잡도 $O(1)$
  • 합집합 result = set_a | set_b
  • 교집합 result = set_a & set_b
  • 차집합 result = set_a - set_b
  • 새 원소 추가, 삭제 시
    • data.add(5)
    • data.update([5, 6])
    • data.remove(3)
  • 순서가 없으므로, 인덱싱 불가능
  • 집합의 원소는 변경 불가능한 값을 써야하며, 원소를 통해 접근 가능

기본 입출력

• 표준 입력
  • input()
    • 한 줄의 문자열을 입력으로 받는 함수
    • data = input()
  • map()
    • list의 모든 원소에 각각 특정한 함수를 적용하는 함수
    • result = map(int, data)
  • 위 두 가지를 합쳐서 입력을 받을 수 있음
    • input_list = list(map(int, input().split()))
    • a, b, c = map(int, input().split())
  • 더 빠르게 입력 받는 법
    • sys.stdin.readline() 사용
    • 이렇게 입력을 받으면, 마지막에 줄바꿈 기호가 추가되어서 입력 받아짐
    • 입력 받은 데이터에 rstrip() 함수를 적용하면 됨
    • 이진 탐색, 정렬, 그래프 관련 문제에서 꽤나 자주 사용

    import sys
    data = sys.stdin.readline().rstrip()
    

• 표준 출력
  • print()
    • () 안의 내용을 출력
    • 출력하려는 내용을 , 로 구분해서 띄워쓰기로 출력 가능
    • 사용 시, 기본적으로 마지막에 줄바꿈이 포함됨
    • 이를 방지하려면 print("hello", end=" ")와 같은 식으로 설정하여 줄바꿈 비활성화
  • f-string
    • Python 3.6 버전 이상에서 사용 가능
    • 문자열 내부에 특정한 변수를 포함해서 출력할 때 사용

  name = "Jackson"
  print(f'제 이름은 {name}입니다.') # 제 이름은 Jackson입니다.
  

조건문

• Python은 코드 블럭을 들여쓰기로 지정
• if, elif, else 키워드를 사용

a = 10
if a < 10:
    print("a는 10보다 작습니다.")
elif a > 10:
    print("a는 10보다 큽니다.")
else:
    print("a는 10입니다.")

• 조건부분에 사용하는 비교 연산자
  • a == b $\rightarrow$ a와 b가 같다면 True, 다르다면 False
  • a != b $\rightarrow$ a와 b가 다르다면 True, 같다면 False
  • a > b $\rightarrow$ a가 b보다 크다면 True, 작거나 같다면 False
  • a < b $\rightarrow$ a가 b보다 작다면 True, 크거나 같다면 False
  • a >= b $\rightarrow$ a가 b보다 크거나 같다면 True, 작다면 False
  • a <= b $\rightarrow$ a가 b보다 작거나 같다면 True, 크다면 False
• 조건부분에 사용하는 논리 연산자
  • A and B $\rightarrow$ A와 B가 모두 True라면 True, 둘 중 하나라도 False라면 False
  • A or B $\rightarrow$ A와 B가 모두 False라면 False, 둘 중 하나라도 True라면 True
  • not C $\rightarrow$ C가 True라면 False, C가 False라면 True
• list, 문자열 등과 사용하는 방법
  • x in data $\rightarrow$ data내부에 x라는 값이 포함되어 있다면 True, 없다면 False
  • x not in string_data $\rightarrow$ string_data내부에 x라는 문자가 포함되어 있다면 False, 없다면 True
• pass
  • 특정 조건부의 동작 부분을 추후에 구현하고 싶을 때 사용
• 조건문 간소화
  • 조건에 대해 동작하는 내용이 한 줄이라면 조건문 간소화 가능

  if a > b: result = True
  else: result = False
  

• 조건부 표현식
  • 조건을 확인해서 특정 변수에 값을 입력 가능

  result = "Success" if Score >= 80 else "Fail"
  

• 수학적 표현 방법도 사용 가능 (3 < data < 5)

  a = 4
  if 3 < a < 5:
      print("a는 3보다 크고, 5보다 작습니다.")
  else:
      print("a는 3보다 작거나 같고, 5보다 크거나 같습니다.")
  

반복문

• while, for문 사용 가능
• 일반적으로 while보다 for가 간결
• list, tuple, dictionary 등에 순차 접근 가능
  • for i in list_data
  • for i in tuple_data
  • for i in dictionary_data
• range()함수를 사용하여 특정 범위의 숫자 사용 가능
  • for i in range(50) $\rightarrow$ 0 ~ 49
  • for i in range(1, 10) $\rightarrow$ 1 ~ 9
  • for i in range(1, 10, 4) $\rightarrow$ 1, 5, 9
• continue()함수를 사용하여, 남은 실행 부분을 넘기고, 다음 반복 시작 가능
• break()함수를 사용하여, 반복문 바로 탈출 가능
• for문 내부에 for를 또 사용하여, 중첩 반복문 가능

함수

• 특정 기능을 묶는 것
• 소스 코드 반복을 줄일 수 있음
• 내장 함수
  • Python에 기본적으로 제공되는 함수
  • print(), input() 등
• 사용자 정의 함수
  • 개발자가 직접 정의하여 사용하는 함수
• 매개변수(parameter)
  • 함수 내부에서 사용할 변수
• 반환 값(return value)
  • 함수에서 처리된 결과

  def function_name(parameter1, parameter2, parameter3):
      # ==========================
      #       실제 동작 부분
      # ==========================
      return return_value
  

• 사용 시, parameter 순서 직접 지정 가능

  def sum(a, b):
      return a + b
  
  result = sum(b=3, a=10)
  

• global 키워드
  • 함수 내부의 변수가 함수 밖의 변수를 사용하고 싶을 때 사용

  a = 0
  def plus_one():
      global a
      a += 1
  

• 반환 값은 여러 개 반환도 가능

  def operator(a, b):
      return a + b, a - b, a * b, a / b
    
  result = operator(1, 2) # (3, -1, 2, 0.5)
  a, b, c, d = operator(2, 2)
  # a = 4, b = 0, c = 4, d = 1.0
  

람다 표현식

• lambda 입력: 출력 형식으로 사용
• lambda a, b: a + b
• 함수를 입력으로 받는 또 다른 함수의 입력으로 넣을 때 유용하게 사용

  array = [('홍길동', 50), ('이순신', 32), ('아무개', 74)]
  print(sorted(array, key=lambda x: x[1])) # [('이순신', 32), ('홍길동', 50), ('아무개', 74)]
  

  list1 = [1, 2, 3, 4, 5]
  list2 = [6, 7, 8, 9, 10]
  result = list(map(lambda a, b: a+b, list1, list2)) # [7, 9, 11, 13, 15]
  

유용한 표준 라이브러리

• 내장함수
  • 기분 입출력, 정렬 등 많은 내용을 포함
  • sum() $\rightarrow$ 입력 값들의 총합
  • min() $\rightarrow$ 입력 값들 중 최소값
  • max() $\rightarrow$ 입력 값들 중 최대값
  • eval() $\rightarrow$ 문자열로 수식 입력 시 결과 반환
    • result = eval("(3+5)*7") $\rightarrow$ 56
  • sorted() $\rightarrow$ 반복 가능한 객체를 입력, 정렬해서 출력
    • reverse=True 입력 시, 내림차순 정렬 가능 (기본 오름차순)
    • key= 입력하여, 특정 속성을 기준으로 정렬 가능
• itertools
  • 반복되는 형태의 데이터 처리 시 유용
  • 순열, 조합 라이브러리가 유용하게 사용됨 (완전 탐색 시)
  • 순열: n개에서 r개 선택해서 일렬로 줄세우기(‘AB’ != ‘BA’)
  • 조합: n개에서 r개 순서 상관없이 뽑기 (‘AB’ == ‘BA’)
  • 모든 경우의 수 예측 및 이를 통해 모든 경우를 고려하는 방법의 사용 가능 여부 확인 가능
    • 경우의 수 > 10,000,000 ~ 100,000,000 일 경우, 완전 탐색 사용 불가능 (시간 초과)

  from itertools import permutations
  data = ['A', 'B', 'C']
  result = list(permutations(data, 3))
  print(result) # [('A', 'B', 'C'), ('A', 'C', 'B'), ('B', 'A', 'C'), ('B', 'C', 'A'), ('C', 'A', 'B'), ('C', 'B', 'A')]
  

  from itertools import combinations
  data = ['A', 'B', 'C']
  result = list(combinations(data, 2))
  print(result) # [('A', 'B'), ('A', 'C'), ('B', 'C')]
  

  • 중복 순열 & 중복 조합

  from itertools import product
  data = ['A', 'B', 'C']
  result = list(product(data, repeat=2))
  print(result) # [('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'B'), ('B', 'C'), ('C', 'A'), ('C', 'B'), ('C', 'C')]
  

  from itertools import combinations_with_replacement
  data = ['A', 'B', 'C']
  result = list(combinations_with_replacement(data, 2))
  print(result) # [('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'B'), ('B', 'C'), ('C', 'C')]
  

• heapq
  • 힙 자료구조 제공 (최단 경로 알고리즘 등, 우선 순위 큐 기능 구현 시 사용)
• bisect
  • 이진 탐색 기능 제공
• collections
  • 덱(deque), 카운터(Counter) 자료구조 제공
  • Ccounter는 특정 값의 등장 횟수를 셀 수 있음

  from collections import Counter
  data = ['r', 'b', 'g', 'g', 'b', 'b']
  cnt = Counter(data)
  print(cnt['b']) # 3
  print(cnt['r']) # 1
  print(dict(cnt)) # {'r': 1, 'b': 3, 'g': 2}
  

• math
  • 수학적 기능 제공
  • 팩토리얼, 제곱근, 최대공약수(GCD), 삼각함수 등 제공
  • 최대 공약수 및 이를 이용한 최소 공배수 계산 가능

  from math import gcd
  def lcm(a, b):
      return a * b // gcd(a, b)
  print(gcd(14, 21)) # 7
  print(lcm(14, 21)) # 42