알고리즘 문제타입 별 개념 정리

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

1장 그리디

• 이론
  • 당장 좋은 것, 눈앞에 보이는 것만 선택하는 그리디
  • 항상 최적의 결과를 도출하는 건 아니지만 어느정도 최적의 해에 근사한 값을 빠르게 구할 수 있다.
  • 또한 ‘특정한 상황’에 있어서 그리디 알고리즘이 최적의 해를 보장할 수도 있다. (언제나 그리디 알고리즘 조건을 충분히 만족하는지 검증해야 한다)
  • 거스름돈 문제: C++ 코드 / Java 코드)
• 실전
  • 동빈이의 큰 수의 법칙: C++ 코드 / Java 코드)

    동빈이의 큰수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰수를 만드는 방법이다. 단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다.

  • 숫자 카드게임: C++ 코드 / Java 코드)

    숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오. https://www.acmicpc.net/problem/10815

  • 1이 될 때까지: C++ 코드 / Java 코드)

    어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다.

but 최적의 해를 보장하지 못하는 경우가 더 많아 다이나믹 프로그래밍(Dynamic Programming)등의 기타 알고리즘 기법을 적용해야 하기도 한다.

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장 정렬

• 이론

  • 기준에 따라서 데이터를 정렬 이후에 차근차근 구현해보겠지만, 각 알고리즘마다 최상과 평균 시간복잡도와 안정성은 어느정도 알고있는 것이 좋다.

    (참고로 Shell Sort의 경우 /가 나눗셈을 의미하는게 아니라 갭 시퀀스(gap sequence)에 따라 시간복잡도가 달라진다. 그래서 'gap sequence가 좋은 경우' / 'gap sequence가 나쁜 경우' 이렇게 보면 된다. 자세한 내용은 shell sort를 다룰 때 말해드리겠다.)

  • 선택 정렬: (C++ 코드 / Java 코드)

    n ( n + 1) / 2. [+1, /2 과 같은작은 연산은 빼고 계산한다]

    선택 정렬의 시간 복잡도는 **O(n^2) 이다

  • 버블 정렬: C++ 코드 / Java 코드)

    삽입정렬이나 선택정렬과 같은 O(N2) 의 시간복잡도를 갖는다 하더라도 거품정렬의 교환횟수가 평균적으로 더 많기 때문에 실질적으로는 삽입, 선택 정렬보다 더 많은 시간이 걸린다

    만약 여러분이 정렬 알고리즘에서 거품정렬을 배울 때 이렇게 swap에 대한 flag변수를 두지 않는다면, 최선의 경우에도 O(N2)의 시간 복잡도를 갖기 때문에 반드시 확인해보는 것이 좋다.

    버블 정렬의 시간 복잡도는 **O(N^2) 이다

  • 스와프(Swap): (C++ 코드 / Java 코드)

  • 삽입 정렬: (C++ 코드 / Java 코드)

    삽입 정렬은 데이터를 '비교'하면서 찾기 때문에 '비교 정렬' 이며 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 않기 때문에 '제자리 정렬(in-place sort)' 이기도 하다.

    정확히는 데이터를 서로 교환하는 과정(swap)에서 임시 변수를 필요로 하나, 이는 충분히 무시할 만큼 적은 양이기 때문에 제자리 정렬로 보는 것

    시간 복잡도 O(N^2) 실제로는 삽입정렬이 연산이 가장 적게 일어남. 거의 정렬된 상태에서는 어떤 알고리즘보다도 빠르다

  • 퀵 정렬: ( C++ 코드 / Java 코드)

    평균 시간 시간복잡도 O(N * log N), 최악 시간 복잡도 O(N^2) → 이미 정렬이 거의 되어 있는 경우

  • 기수 정렬

    정렬 알고리즘의 한계 O(n log n)을 넘어설수 있는 알고리즘. but 적용할 수 있는 범위가 제한적이다. 범위는 데이터의 길이에 의존함, 정렬하고자 하는 데이터의 길이가 동일하지 않은 데이터는 정렬 불가(기존 정렬 알고리즘에 비해 기수 정렬 알고리즘은 좋은 성능 내는것이 불가능하단 말)

    LSD방식(덜 중요한 숫자부터 정렬하는 방식) 주로 이 방식을 이야기 함, MSD방식 ( 중요한 숫자부터 정렬) 정렬이 끝나야 결과확인 가능, 정렬이 완료되었는지 확인하는 과정이 필요해 메모리를 더 사용하게 된다. 시간 복잡도 O(n)

  • 계수 정렬(카운팅 정렬): (C++ 코드 / Java 코드)

    최대값에 해당하는 값을 size로 하는 임시 배열, 정렬하고자 하는 값들이 몇 개씩인지 파악하는 임시 배열을 만들고 그 배열을 기준으로 정렬함. index부터 시작하여 누적된 값으로 배열을 변경. 여기서의 index가 정렬하고자 하는 value가 되고 value는 정렬되었을 때의 index가 된다. 시간복잡도 O(n)

  • 정렬 라이브러리 기본 예제: (C++ 코드 / Java 코드)

  • 정렬 라이브러리 키(Key) 기준 정렬 예제: (C++ 코드 / Java 코드)

• 실전
  • 위에서 아래로: (C++ 코드 / Java 코드)
  • 성적이 낮은 순서대로 학생 출력하기: (C++ 코드 / Java 코드)
  • 두 배열의 원소 교체: (C++ 코드 / Java 코드)

7장 이진 탐색

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

8장 다이나믹 프로그래밍

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

9장 최단 경로

• 이론
  • 가장 빠른 길 찾기
  • 간단한 다익스트라 알고리즘: (C++ 코드 / Java 코드)
  • 개선된 다익스트라 알고리즘 (우선순위 큐): (C++ 코드 / Java 코드)
  • 플로이드 워셜 알고리즘: (C++ 코드 / Java 코드)
• 실전
  • 미래 도시: (C++ 코드 / Java 코드)
  • 전보: (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 코드
• 어른 상어 (삼성):

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 기타 알고리즘

• 이론

  • 소수 판별: (C++ 코드 / Java 코드)

  • 에라토스테네스의 체: (C++ 코드 / Java 코드)

    임의의 자연수에 대해, 그 자연수 이하의 소수(prime number)를 찾아 주는 방법(특정 자연수 이하의 합성수는 모두 지워지고 소수들만 남는 것)

  • 특정한 합을 가지는 부분 연속 수열 찾기 (투 포인터): (C++ 코드 / Java 코드)

  • 구간 합: (C++ 코드 / Java 코드)

• 실전
  • 소수 구하기 (핵심 유형): 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++ 코드)