c++ 코딩테스트 공부

교재 : 코딩테스트 합격자 되기(c++편)

04장 코딩 테스트 필수 문법 (0828)

• 04-1 프리미티브 타입과레퍼런스 타입

• 정수형

• 부동소수형

• 문자열

• 04-2 STL

• STL

• STL과 자주 사용하는 필수 문법

• 반복자

• 04-3 STL의 컨테이너

• 벡터

• 셋

• 맵

• 정렬되지 않은 셋과 맵

• 04-4 STL의 알고리즘

• count( ) 함수로 횟수 세기

• sort( ) 함수로 정렬하기

• next_permutation( ) 함수로 순열 생성하기

• unique( ) 함수로 중복 정리하기

• binary_search( ) 함수로 이진 탐색하기

• max_element( ), min_element( ) 함수로 최댓값, 최솟값 위치 구하기

• 04-5 함수

• 함수 정의

• 함수 호출

• 04-6 코딩 테스트 코드 구현 노하우

• 조기 반환

• 보호 구문

• [둘째 마당 : 코딩 테스트 완전 정복]

05장 배열 (0830)

• 05-1 배열 개념
• 배열 선언
• 배열과 차원
• 05-2 배열의 효율성
• 배열 연산의 시간 복잡도
• 배열을 선택할 때 고려할 점
• 05-3 몸풀기 문제
• [문제 01] 배열 정렬하기★
• [문제 02] 배열 제어하기★★
• 05-4 합격자가 되는 모의 테스트
• [문제 03] 두 수를 뽑아서 더하기★
• [문제 04] 모의고사★
• [문제 05] 행렬의 곱셈★
• [문제 06] 실패율★★
• [문제 07] 방문 길이★★

06장 스택 (0902)

• 06-1 스택 개념
• 스택의 동작 원리 이해하기
• 06-2 스택의 정의
• 스택의 ADT
• 06-3 몸풀기 문제
• [문제 08] 괄호 짝 맞추기★★
• [문제 09] 10진수를 2진수로 변환하기★
• 06-4 합격자가 되는 모의 테스트
• [문제 10] 괄호 회전하기★
• [문제 11] 짝지어 제거하기★
• [문제 12] 주식 가격★★
• [문제 13] 크레인 인형 뽑기 게임★★
• [문제 14] 표 편집★★★★★

07장 큐 0904

• 07-1 큐의 개념
• 큐에서 데이터가 이동하는 과정 살펴보기
• 큐의 특성을 활용하는 분야
• 큐의 ADT
• 07-2 몸풀기 문제
• [문제 15] 요세푸스 문제★★
• 07-3 합격자가 되는 모의 테스트
• [문제 16] 기능 개발★★
• [문제 17] 카드 뭉치★★

08장 해시 0906

• 08-1 해시의 개념
• 해시 자세히 알아보기
• 해시의 특성을 활용하는 분야
• 08-2 해시 함수
• 해시 함수를 구현할 때 고려할 내용
• 자주 사용하는 해시 함수 알아보기
• 08-3 충돌 처리
• 체이닝으로 처리하기
• 개방 주소법으로 처리하기
• 08-4 몸풀기 문제
• [문제 18] 두 개의 수로 특정값 만들기★
• [문제 19] 문자열 해싱을 이용한 검색 함수 만들기★★
• 08-5 합격자가 되는 모의 테스트
• [문제 20] 완주하지 못한 선수★
• [문제 21] 영어 끝말잇기★
• [문제 22] 전화번호 목록★★
• [문제 23] 할인 행사★★
• [문제 24] 오픈 채팅방★★
• [문제 25] 베스트 앨범★★
• [문제 26] 신고 결과 받기★★
• [문제 27] 메뉴 리뉴얼★★★

09장 트리 0924

• 09-1 트리 개념
• 나무를 거꾸로 뒤집어 놓은 모양의 트리
• 09-2 이진 트리 표현하기
• 배열로 표현하기
• 이진 트리 순회하기
• 포인터로 표현하기
• 인접 리스트로 표현하기
• 09-3 이진 트리 탐색하기
• 이진 탐색 트리 구축하기
• 이진 탐색 트리 탐색하기
• 이진 탐색 트리와 배열 탐색의 효율 비교
• 09-4 몸풀기 문제
• [문제 28] 트리 순회★
• [문제 29] 이진 탐색 트리 구현★
• 09-5 합격자가 되는 모의 테스트
• [문제 30] 예상 대진표★
• [문제 31] 다단계 칫솔 판매★★
• [문제 32] 길 찾기 게임★★★★

10장 집합

• 10-1 집합과 상호배타적 집합의 개념
• 집합의 개념
• 상호배타적 집합의 특성을 활용하는 분야
• 10-2 집합의 연산
• 배열을 활용한 트리로 집합 표현하기
• 유니온-파인드 알고리즘
• 10-3 몸풀기 문제
• [문제 33] 간단한 유니온-파인드 알고리즘 구현하기★★
• 10-4 합격자가 되는 모의 테스트
• [문제 34] 폰켓몬★
• [문제 35] 섬 연결하기★★★

11장 그래프 1005

• 11-1 그래프의 개념
• 그래프 용어 정리
• 그래프의 특징과 종류
• 그래프 구현
• 11-2 그래프 탐색
• 깊이 우선 탐색
• 너비 우선 탐색
• 깊이 우선 탐색과 너비 우선 탐색 비교
• 11-3 그래프 최단 경로 구하기
• 다익스트라 알고리즘
• 벨만-포드 알고리즘
• 11-4 몸풀기 문제
• [문제 36] 깊이 우선 탐색 순회★
• [문제 37] 너비 우선 탐색 순회★
• [문제 38] 다익스트라 알고리즘★★★
• [문제 39] 벨만-포드 알고리즘★★★
• 11-5 합격자가 되는 모의 테스트
• [문제 40] 미로 탈출★★
• [문제 41] 게임 맵 최단 거리★★
• [문제 42] 네트워크★★
• [문제 43] 양과 늑대★★★★★
• [문제 44] 배달★★★
• [문제 45] 경주로 건설★★★★★
• [문제 46] 전력망을 둘로 나누기★★

12장 백트래킹

• 12-1 백트래킹과 백트래킹 알고리즘 개념
• 백트래킹이란?
• 백트래킹 알고리즘이란?
• 유망 함수란?
• 백트래킹 알고리즘 문제에 적용해보기
• N-퀸 문제
• 12-2 몸풀기 문제
• [문제 47] 1부터 N까지 숫자 중 합이 10이 되는 조합 구하기★
• [문제 48] 스도쿠 퍼즐★★★
• 12-3 합격자가 되는 모의 테스트
• [문제 49] 피로도★
• [문제 50] N-퀸★
• [문제 51] 양궁 대회★★
• [문제 52] 외벽 점검★★★★★
• [문제 53] 사라지는 발판★★★★★

13장 정렬

• 13-1 정렬 개념
• 정렬이 필요한 이유
• 삽입 정렬
• 병합 정렬
• 힙 정렬
• 우선순위 큐
• 계수 정렬
• 위상 정렬
• 13-2 몸풀기 문제
• [문제 54] 계수 정렬 구현하기★
• [문제 55] 정렬이 완료된 두 배열 합치기★
• 13-3 합격자가 되는 모의 테스트
• [문제 56] 문자열 내 마음대로 정렬하기★
• [문제 57] 정수 내림차순으로 배치하기★
• [문제 58] K번째 수★
• [문제 59] 가장 큰 수★★★
• [문제 60] 튜플★★
• [문제 61] 지형 이동★★★★

14장 시뮬레이션

• 14-1 시뮬레이션 문제 풀이 노하우
• 시뮬레이션 문제를 푸는 방법
• 행렬 연산
• 좌표 연산
• 대칭, 회전 연산
• 14-2 몸풀기 문제
• [문제 62] 배열 회전하기★★
• [문제 63] 두 행렬을 곱한 후 전치 행렬 만들기★
• [문제 64] 달팽이 수열 만들기★★
• 14-3 합격자가 되는 모의 테스트
• [문제 65] 이진 변환★★
• [문제 66] 롤케이크 자르기★★
• [문제 67] 카펫★★
• [문제 68] 점프와 순간 이동★★
• [문제 69] 캐릭터의 좌표★★

15장 동적 계획법

• 15-1 동적 계획법 개념
• 점화식 세우기와 동적 계획법
• 재귀 호출의 횟수를 줄여주는 메모이제이션
• 최장 증가 부분 수열
• 최장 공통 부분 수열
• 15-2 몸풀기 문제
• [문제 70] LCS 길이 계산하기★★★
• [문제 71] LIS 길이 계산하기★★★
• [문제 72] 조약돌 문제★★★
• 15-3 합격자가 되는 모의 테스트
• [문제 73] 피보나치 수★
• [문제 74] 2 × n 타일링★
• [문제 75] 정수 삼각형★★
• [문제 76] 땅따먹기★★
• [문제 77] 도둑질★★★★★
• [문제 78] 가장 큰 정사각형 찾기★★★
• [문제 79] 단어 퍼즐★★★★

16장 그리디

• 16-1 그리디 개념
• 그리디 알고리즘으로 거스름돈 내어주기
• 그리디 알고리즘이 최적해를 보장하려면?
• 16-2 최소 신장 트리
• 신장 트리란?
• 최소 신장 트리란?
• 16-3 배낭 문제
• 짐을 쪼갤 수 있는 부분 배낭 문제
• 짐을 쪼갤 수 없는 0/1 배낭 문제
• 16-4 몸풀기 문제
• [문제 80] 거스름돈 주기★★
• [문제 81] 부분 배낭 문제★★
• 16-5 합격자가 되는 모의 테스트
• [문제 82] 예산★
• [문제 83] 구명보트★
• [문제 84] 귤 고르기★★
• [문제 85] 기지국 설치★★

_01회 모의고사

• [문제 86] 미로 탈출 명령어
• [문제 87] 택배 배달과 수거하기
• [문제 88] 개인 정보 수집 유효기간

_02회 모의고사

• [문제 89] 110 옮기기
• [문제 90] 쿼드 압축 후 개수 세기
• [문제 91] 없는 숫자 더하기

_03회 모의고사

• [문제 92] 불량 사용자
• [문제 93] k진수에서 소수 개수 구하기
• [문제 94] 거리두기 확인하기

_04회 모의고사

• [문제 95] 코딩 테스트 공부
• [문제 96] 두 큐 합 같게 만들기
• [문제 97] 숫자 게임

_05회 모의고사

• [문제 98] 보석 쇼핑
• [문제 99] 파괴되지 않은 건물
• [문제 100] 로또의 최고 순위와 최저 순위