README.md

이것이 취업을 위한 코딩 테스트다 with Python

취업과 이직을 결정하는 알고리즘 인터뷰 완벽 가이드 (2020년 08월 05일 정식 출시)

• 이 저장소는 이것이 취업을 위한 코딩 테스트다 with Python (나동빈 저, 한빛미디어) 전체 소스코드를 포함합니다.
• 본 책은 Python 3.7 문법을 활용하였으나, 추가적으로 Java, C++11 소스코드를 제공합니다.
• 책 내용 및 소스코드와 관련한 궁금한 점은 Issues 탭을 이용하여 남겨주세요.
• 책의 오류 사항을 발견하시면 dongbinna@postech.ac.kr로 보내주시면 감사하겠습니다.
  • 이 경우, 원하신다면 정오표에 독자님의 이름(혹은 아이디)을 함께 기재해드립니다.
• 이 책을 이용해 강의를 진행하시는 교수/선생님/강사/동아리장 님들을 위해 강의용 PPT를 제공합니다. (준비중)
• 전체 동영상 강의는 2020년 8 ~ 9월에 걸친 유튜브 라이브 강의를 진행하고 편집 후에 업로드 될 예정입니다.
• 책 구매 링크: 한빛미디어 / YES24 / 교보문고 / 알라딘

---

대기업 코딩 테스트 문제 적중 관련

• 최근 2021 K사 공채 코딩 테스트 1차 합격 커트라인은 3문제 ~ 3.5문제(부분점수 포함)로 예상됩니다.

• 저자 또한 코딩 테스트에 참여해 보았고, 파이썬만 이용하여 알고리즘 코딩 테스트에 합격할 수 있었습니다.

• 특히 아래 두 문제는 본 책의 파이썬 코드를 참고하여 쉽게 해결할 수 있었습니다.

• 3번 문제 (이진 탐색): 책의 15장 정렬된 배열에서 특정 수의 개수 구하기 알고리즘을 활용하면 쉽게 풀 수 있는 문제였습니다.

  • 파이썬의 bisect_left 함수를 활용합니다.

• 4번 (플로이드 워셜): 책의 9장 미래 도시 문제와 접근 방법 및 아이디어가 사실상 동일한 문제입니다.

  • 특정한 중간 지점을 거쳐 갈 때의 최단 경로 알고리즘으로 볼 수 있습니다.
  • 저자 개인적으로도 이 문제는 보자마자 풀어서 7분 이내로 풀 수 있었습니다.

---

도와주신 분들

• 베타 리뷰어 님들: 김민철, 안수빈, 정한길, 황성호 외 10분
• 백준 온라인 저지(BOJ)의 일부 문제를 사용할 수 있도록 허락해주고, 개인적으로 많은 도움을 주신 최백준 님
• 2019, 2020 K사 문제를 책에 수록할 수 있도록 허락해주신 (주)그렙 프로그래머스
  • PPL: 프로그래머스 알고리즘 문제 풀이 강의

시작하며

• 지은이의 글 및 리뷰어의 글

Part 1 코딩 테스트, 무엇을 어떻게 준비할까?

1장 코딩 테스트 개요

• 코딩 테스트 개념과 배경
• 실습 환경 구축하기
• 복잡도
  • 파이썬 수행 시간 측정 방법
  • 선택 정렬과 기본 정렬 라이브러리의 수행 시간 비교

2장 16~20년 코딩 테스트 기출문제 유형 분석

• 최신 출제 경향과 준비 방향
• 연도별 코딩 테스트 유형 분석

GUIDE: 성공적인 취업을 위한 가이드

• 채용 프로세스
• 기술 면접의 대표적인 유형
• 기술 면접 준비
• 알고리즘 문제 풀이 사이트
• 커뮤니티 사이트

Part 2 주요 알고리즘 이론과 실전 문제

3장 그리디

• 이론
  • 당장 좋은 것만 선택하는 그리디
  • 거스름돈 문제: (Python 3.7 코드 / C++ 코드 / Java 코드)
• 실전
  • 동빈이의 큰 수의 법칙: (Python 3.7 코드 / C++ 코드 / Java 코드)
  • 숫자 카드게임: (Python 3.7 코드 / C++ 코드 / Java 코드)
  • 1이 될 때까지: (Python 3.7 코드 / C++ 코드 / Java 코드)

4장 구현

• 이론
  • 아이디어를 코드로 바꾸는 구현
  • 상하좌우: (Python 3.7 코드 / C++ 코드 / Java 코드)
  • 시각: (Python 3.7 코드 / C++ 코드 / Java 코드)
• 실전
  • 왕실의 나이트: (Python 3.7 코드 / C++ 코드 / Java 코드)
  • 게임 개발: (Python 3.7 코드 / C++ 코드 / Java 코드)

5장 DFS/BFS

• 이론
  • 꼭 필요한 자료구조 기초
  • 탐색 알고리즘 DFS/BFS
  • 스택 구현 예제: (Python 3.7 코드 / C++ 코드 / Java 코드)
  • 큐 구현 예제: (Python 3.7 코드 / C++ 코드 / Java 코드)
  • 무한히 반복되는 재귀함수 예제: (Python 3.7 코드 / C++ 코드 / Java 코드)
  • 재귀함수의 종료 조건 예제: (Python 3.7 코드 / C++ 코드 / Java 코드)
  • 2가지 방식으로 구현한 팩토리얼 예제: (Python 3.7 코드 / C++ 코드 / Java 코드)
  • 인접 행렬 예제: (Python 3.7 코드 / C++ 코드 / Java 코드)
  • 인접 리스트 예제: (Python 3.7 코드 / C++ 코드 / Java 코드)
  • DFS: (Python 3.7 코드 / C++ 코드 / Java 코드)
  • BFS: (Python 3.7 코드 / C++ 코드 / Java 코드)
• 실전
  • 음료수 얼려 먹기: (Python 3.7 코드 / C++ 코드 / Java 코드)
  • 미로 탈출: (Python 3.7 코드 / C++ 코드 / Java 코드)

6장 정렬

• 이론
  • 기준에 따라서 데이터를 정렬
  • 선택 정렬: (Python 3.7 코드 / C++ 코드 / Java 코드)
  • 스와프(Swap): (Python 3.7 코드 / C++ 코드 / Java 코드)
  • 삽입 정렬: (Python 3.7 코드 / C++ 코드 / Java 코드)
  • 퀵 정렬: (Python 3.7 코드 / C++ 코드 / Java 코드)
  • 파이썬의 장점을 살린 퀵 정렬: Python 3.7 코드
  • 계수 정렬: (Python 3.7 코드 / C++ 코드 / Java 코드)
  • 정렬 라이브러리 기본 예제: (Python 3.7 코드 / C++ 코드 / Java 코드)
  • 정렬 라이브러리 키(Key) 기준 정렬 예제: (Python 3.7 코드 / C++ 코드 / Java 코드)
• 실전
  • 위에서 아래로: (Python 3.7 코드 / C++ 코드 / Java 코드)
  • 성적이 낮은 순서대로 학생 출력하기: (Python 3.7 코드 / C++ 코드 / Java 코드)
  • 두 배열의 원소 교체: (Python 3.7 코드 / C++ 코드 / Java 코드)

7장 이진 탐색

• 이론
  • 범위를 반씩 좁혀가는 탐색
  • 순차 탐색: (Python 3.7 코드 / C++ 코드 / Java 코드)
  • 재귀 함수를 이용한 이진 탐색: (Python 3.7 코드 / C++ 코드 / Java 코드)
  • 반복문을 이용한 이진 탐색: (Python 3.7 코드 / C++ 코드 / Java 코드)
  • 파이썬에서 빠르게 입력 받기: Python 3.7 코드
• 실전
  • 부품 찾기
    • 이진 탐색으로 해결: (Python 3.7 코드 / C++ 코드 / Java 코드)
    • 계수 정렬로 해결: (Python 3.7 코드 / C++ 코드 / Java 코드)
    • 집합(Set) 자료형으로 해결: (Python 3.7 코드 / C++ 코드 / Java 코드)
  • 떡볶이 떡 만들기: (Python 3.7 코드 / C++ 코드 / Java 코드)

8장 다이나믹 프로그래밍

• 이론
  • 비효율적인 피보나치 수열 구현: (Python 3.7 코드 / C++ 코드 / Java 코드)
  • 피보나치 수열 (Top-bottom): (Python 3.7 코드 / C++ 코드 / Java 코드)
  • 피보나치 수열 (Bottom-top): (Python 3.7 코드 / C++ 코드 / Java 코드)
• 실전
  • 1로 만들기: (Python 3.7 코드 / C++ 코드 / Java 코드)
  • 개미 전사: (Python 3.7 코드 / C++ 코드 / Java 코드)
  • 바닥 공사: (Python 3.7 코드 / C++ 코드 / Java 코드)
  • 효율적인 화폐 구성: (Python 3.7 코드 / C++ 코드 / Java 코드)

9장 최단 경로

• 이론
  • 가장 빠른 길 찾기
  • 간단한 다익스트라 알고리즘: (Python 3.7 코드 / C++ 코드 / Java 코드)
  • 개선된 다익스트라 알고리즘 (우선순위 큐): (Python 3.7 코드 / C++ 코드 / Java 코드)
  • 플로이드 워셜 알고리즘: (Python 3.7 코드 / C++ 코드 / Java 코드)
• 실전
  • 미래 도시: (Python 3.7 코드 / C++ 코드 / Java 코드)
  • 전보: (Python 3.7 코드 / C++ 코드 / Java 코드)

10장 기타 그래프 이론

• 이론
  • 다양한 그래프 알고리즘
  • 간단한 서로소 집합 알고리즘: (Python 3.7 코드 / C++ 코드 / Java 코드)
  • 개선된 서로소 집합 알고리즘 (경로 압축): (Python 3.7 코드 / C++ 코드 / Java 코드)
  • 서로소 집합을 활용한 사이클 판별: (Python 3.7 코드 / C++ 코드 / Java 코드)
  • 크루스칼 알고리즘: (Python 3.7 코드 / C++ 코드 / Java 코드)
  • 위상 정렬: (Python 3.7 코드 / C++ 코드 / Java 코드)
• 실전
  • 팀 결성: (Python 3.7 코드 / C++ 코드 / Java 코드)
  • 도시 분할 계획: (Python 3.7 코드 / C++ 코드 / Java 코드)
  • 커리큘럼: (Python 3.7 코드 / C++ 코드 / Java 코드)

Part 3 알고리즘 유형별 기출문제

11장 그리디

• 모험가 길드 (핵심 유형): (Python 3.7 코드 / C++ 코드 / Java 코드)
• 곱하기 혹은 더하기 (Facebook 인터뷰 기출): (Python 3.7 코드 / C++ 코드 / Java 코드)
• 문자열 뒤집기 (핵심 유형): (Python 3.7 코드 / C++ 코드 / Java 코드)
• 만들 수 없는 금액 (K 대회 기출): (Python 3.7 코드 / C++ 코드 / Java 코드)
• 볼링공 고르기 (S 기관 입학 테스트): (Python 3.7 코드 / C++ 코드 / Java 코드)
• 무지의 먹방 라이브 (카카오): (Python 3.7 코드 / C++ 코드 / Java 코드)

12장 구현

• 럭키 스트레이트 (핵심 유형): (Python 3.7 코드 / C++ 코드 / Java 코드)
• 문자열 재정렬 (Facebook 인터뷰 기출): (Python 3.7 코드 / C++ 코드 / Java 코드)
• 문자열 압축 (카카오): (Python 3.7 코드 / C++ 코드 / Java 코드)
• 자물쇠와 열쇠 (카카오): (Python 3.7 코드 / C++ 코드 / Java 코드)
• 뱀 (삼성): (Python 3.7 코드 / C++ 코드 / Java 코드)
• 기둥과 보 설치 (카카오): (Python 3.7 코드 / C++ 코드 / Java 코드)
• 치킨 배달 (삼성): (Python 3.7 코드 / C++ 코드 / Java 코드)
• 외벽 점검 (카카오): (Python 3.7 코드 / C++ 코드 / Java 코드)

13장 DFS/BFS

• 특정 거리의 도시 찾기 (핵심 유형): (Python 3.7 코드 / C++ 코드 / Java 코드)
• 연구소 (삼성): (Python 3.7 코드 / C++ 코드 / Java 코드)
• 경쟁적 전염 (핵심 유형): (Python 3.7 코드 / C++ 코드 / Java 코드)
• 괄호 변환 (카카오): (Python 3.7 코드 / C++ 코드 / Java 코드)
• 연산자 끼워 넣기 (삼성): (Python 3.7 코드 / C++ 코드 / Java 코드)
• 감시 피하기 (핵심 유형): (Python 3.7 코드 / C++ 코드 / Java 코드)
• 인구 이동 (삼성): (Python 3.7 코드 / C++ 코드 / Java 코드)
• 블록 이동하기 (카카오): (Python 3.7 코드 / C++ 코드 / Java 코드)

14장 정렬

• 국영수 (핵심 유형): (Python 3.7 코드 / C++ 코드 / Java 코드)
• 안테나 (국내 S 교육 기관 선발 평가): (Python 3.7 코드 / C++ 코드 / Java 코드)
• 실패율 (카카오): (Python 3.7 코드 / C++ 코드 / Java 코드)
• 카드 정렬하기 (핵심 유형): (Python 3.7 코드 / C++ 코드 / Java 코드)

15장 이진 탐색

• 정렬된 배열에서 특정 수의 개수 구하기 (Zoho 인터뷰 기출): (Python 3.7 코드 / C++ 코드 / Java 코드)
• 고정점 찾기 (Amazon 인터뷰 기출): (Python 3.7 코드 / C++ 코드 / Java 코드)
• 공유기 설치 (핵심 유형): (Python 3.7 코드 / C++ 코드 / Java 코드)
• 가사 검색 (카카오): (Python 3.7 코드 / C++ 코드 / Java 코드)

16장 다이나믹 프로그래밍

• 금광 (Flipkart 인터뷰 기출): (Python 3.7 코드 / C++ 코드 / Java 코드)
• 정수 삼각형 (IOI): (Python 3.7 코드 / C++ 코드 / Java 코드)
• 퇴사 (삼성): (Python 3.7 코드 / C++ 코드 / Java 코드)
• 병사 배치하기 (핵심 유형): (Python 3.7 코드 / C++ 코드 / Java 코드)
• 못생긴 수 (Google 인터뷰 기출): (Python 3.7 코드 / C++ 코드 / Java 코드)
• 편집 거리 (Goldman Sachs 인터뷰 기출): (Python 3.7 코드 / C++ 코드 / Java 코드)

17장 최단 경로

• 플로이드 (핵심 유형): (Python 3.7 코드 / C++ 코드 / Java 코드)
• 정확한 순위 (K 대회 기출): (Python 3.7 코드 / C++ 코드 / Java 코드)
• 화성 탐사 (ICPC): (Python 3.7 코드 / C++ 코드 / Java 코드)
• 숨바꼭질 (USACO): (Python 3.7 코드 / C++ 코드 / Java 코드)

18장 기타 그래프 이론

• 여행 계획 (핵심 유형): (Python 3.7 코드 / C++ 코드 / Java 코드)
• 탑승구 (CCC): (Python 3.7 코드 / C++ 코드 / Java 코드)
• 어두운 길 (University of Ulm Local Contest): (Python 3.7 코드 / C++ 코드 / Java 코드)
• 행성 터널 (COCI): (Python 3.7 코드 / C++ 코드 / Java 코드)
• 최종 순위 (ICPC): (Python 3.7 코드 / C++ 코드 / Java 코드)

19장 2020년 상반기 삼성전자 기출문제

• 아기 상어 (삼성): Python 3.7 코드
• 청소년 상어 (삼성): Python 3.7 코드
• 어른 상어 (삼성): Python 3.7 코드

Part 4 부록

부록 A 코딩 테스트를 위한 파이썬 문법

• 자료형
  • 수 자료형
    • 정수형
    • 실수형
    • 수 자료형의 연산
  • 리스트 자료형
    • 리스트 만들기
    • 리스트 인덱싱
    • 리스트 슬라이싱
    • 리스트 컴프리헨션
    • 리스트 관련 메서드
  • 문자열 자료형
    • 문자열 초기화
    • 문자열 연산
  • 튜플 자료형
    • 튜플 초기화
  • 사전 자료형
    • 사전 자료형 초기화
    • 사전에서 키로 검색
    • 사전 자료형 관련 메서드
  • 집합 자료형
    • 집합 초기화
    • 집합 연산
    • 집합 관련 메서드
• 조건문
  • 조건문 예시 1
  • 조건문 예시 2
  • 조건문 예시 3
  • pass 키워드 사용 예시
  • 조건문 한 줄에 쓰기
  • 조건부 표현식
• 반복문
  • while 문법
    • while 문법 예시 1
    • while 문법 예시 2
  • for 문법
    • for 문법 예시 1
    • for 문법 예시 2
    • for 문법 예시 3
    • for 문법 예시 4
• 함수
  • 더하기 함수
  • global 키워드 사용 예시
• 입출력
  • 코딩 테스트에서 입력을 위한 전형적인 코드
  • 공백을 기준으로 적은 수의 데이터 입력
  • readline()으로 빠르게 입력 받기
  • f-string 사용 예시
• 주요 라이브러리의 문법과 유의점
  • 내장 함수
  • itertools
  • heapq
  • bisect
  • collections
  • math
• 자신만의 알고리즘 노트 만들기

부록 B 기타 알고리즘

• 이론
  • 소수 판별: (Python 3.7 코드 / C++ 코드 / Java 코드)
  • 에라토스테네스의 체: (Python 3.7 코드 / C++ 코드 / Java 코드)
  • 특정한 합을 가지는 부분 연속 수열 찾기 (투 포인터): (Python 3.7 코드 / C++ 코드 / Java 코드)
  • 정렬되어 있는 두 리스트 합치기 (투 포인터): Python 3.7 코드
  • 구간 합: (Python 3.7 코드 / C++ 코드 / Java 코드)
  • 순열: Python 3.7 코드
  • 조합: Python 3.7 코드
• 실전
  • 소수 구하기 (핵심 유형): Python 3.7 코드
  • 암호 만들기 (핵심 유형): Python 3.7 코드

부록 C 개발형 코딩 테스트

• 서버와 클라이언트
• REST API
• JSON
• API 호출 실습
  • API 호출 실습 1
  • API 호출 실습 2
  • 회원 정보 처리 실습

부록 D 알고리즘 유형별 문제 풀이

추가 보충 자료

책에서는 자세히 다루지 않지만 독자의 요청으로 추가적으로 제공합니다.

• 트리(Tree)
  • 트리의 순회: (Python 3.7 코드)
• 우선순위 큐 (Priority Queue)
  • 우선순위 큐 라이브러리를 활용한 힙 정렬: (Python 3.7 코드 / C++ 코드)
• 바이너리 인덱스 트리 (Binary Indexed Tree, BIT, Fenwick Tree)
  • 구간 합 구하기: (Python 3.7 코드 / C++ 코드)
• 벨만-포드 (Bellman-Ford) 최단 경로 알고리즘
  • 음수 간선이 포함된 그래프에서의 최단 경로 찾기: (Python 3.7 코드 / C++ 코드)
• 최소 공통 조상 (Lowest Common Ancestor, LCA)
  • LCA 기본: (Python 3.7 코드 / C++ 코드)
  • LCA 심화: (Python 3.7 코드 / C++ 코드)