코딩 테스트 합격자 되기 (c++) 편 정리

01 코딩 테스트 효율적으로 준비하기

01-1 언어 선택하기

01-2 문제 분석 연습하기

1. 문제를 쪼개서 분석하라
2. 제약 사항을 파악하고 테스트 케이스를 추가하라
3. 입력값을 분석하라
4. 핵심 키워드를 파악하라
5. 데이터 흐름이나 구성을 파악하라

핵심 키워드

-	키워드	설명
스택	쌍이 맞는지 최근	무언가를 저장하고 반대로 처리해야할 때 데이터의 조합이 균형을 이뤄야 할 때 알고리즘이 재귀 특성을 가질 때 최근 상태 추적
큐	순서대로 ~대로 동작하는 경우 스케쥴링 최소 시간	특정 조건에 따라 시뮬레이션 할 때 시작 지점부터 목표 지점까지 최단거리
깊이 우선 탐색	모든 경로	메모리 사융량이 제한적일 때의 탐색 백트래킹 문제를 풀 때
너비 우선 탐색	최적 레벨 순회 최소 단계 네트워크 전파	시작 지점부터 최단 경로나 최소 횟수를 찾아야 할 때
백트래킹	조합 순열 부분 집합	조합 및 순열 문제 특정 조건을 만족하는 부분 집합
최단 경로	최단 경로 최소 시간 최소 비용 트래픽 음의 순환 단일 출발점 경로	다익스트라: 특정 지점에서 나머지 지점까지 가는 최단 경로 벨만 포드: 음의 순환 탐지, 음의 가중치를 가진 그래프에서 최단 경로

01-3 의사코드로 설계하는 연습하기

1. 세부 구현이 아닌 동작 중심으로 작성하라
2. 문제 해결 순서로 작성하라
3. 충분히 테스트 하라

02 프로그래머스 완벽 활용 가이드

03 알고리즘의 효율 분석

시간 복잡도	최대 연산 횟수
O(N!)	10
O(2^N)	20 ~ 25
O(N^3)	200 ~ 300
O(N^2)	3,000 ~ 5,000
O(N log N)	100만
O(N)	1,000 ~ 2,000 만
O(log N)	10억

04 코딩 테스트 필수 문법

04-1 빌트인 데이터 타입

• 정수형: int, long, long long
• 실수형: float, double (float: 4byte, double: 8byte)
• 형변환: static_cast<타입>(변수), (타입)변수
• 문자열: string

// 문자열 선언 및 초기화
string str1; // 문자열 선언
string str2 = "hello"; // 문자열 초기화
string str3(str2); // 문자열 복사
string str4(str2, 0, 3); // 문자열 부분 복사
string str5(10, '*'); // 문자열 10개 '*'로 초기화

// 문자열 탐색
string str = "Hello, C++ World!";
size_t pos1 = str.find("Hello"); // "Hello"의 위치를 찾음
size_t pos2 = str.find('C'); // "C"의 위치를 찾음

size_t start_index = 2;
size_t pos3 = str.find("Hello", start_index); // 시작 인덱스부터 "Hello"의 위치를 찾음

size_t pos4 = str.find_first_of("Python"); // 존재하지 않는 문자 찾기, string::npos값 반환 (ex> 18446744073709551615)  

// 문자열 추가, 수정
string str  = "APPLE";
str += " PIE"; // 문자열 추가
str[0] = 'A'; // 문자열 수정
str.insert(0, "I LOVE "); // 문자열 삽입
str.erase(0, 2); // 문자열 삭제
str.replace(0, 5, "I HATE "); // 문자열 대체

04-2 STL

• 참조값 전달(&를 사용하여 변수의 주소를 전달) vs 주소값 전달(*을 사용하여 포인터를 전달)
• auto 문법: C++11부터 도입된 키워드로, 컴파일러가 변수의 타입을 자동으로 추론하여 결정하는 기능
• 순방향 반복자, 역방향 반복자

04-3 STL의 컨테이너

• vector

  // 선언
  vector<int> v1; // int형 벡터 선언
  vector<int> v2(10); // 크기가 10인 int형 벡터 선언
  vector<int> v3(10, 5); // 크기가 10이고 모든 원소가 5인 int형 벡터 선언
  vector<int> v4(v3); // v3를 복사하여 v4를 선언
  vector<int> v5(v3.begin(), v3.end()); // v3의 모든 원소를 복사하여 v5를 선언
  vector<int> v6 = {1, 2, 3, 4, 5}; // 초기화 리스트를 사용하여 벡터 선언
  // 2차원 벡터 선언
  vector<vector<int>> v7(3, vector<int>(4)); // 3x4 크기의 2차원 벡터 선언
  vector<vector<int>> v8 = {\{1, 2, 3\}, \{4, 5, 6\}}; // 초기화 리스트를 사용하여 2차원 벡터 선언
  // 벡터 원소 추가, 삭제
  v.push_back(10); // 벡터의 끝에 10을 추가
  v.pop_back(); // 벡터의 끝 원소를 삭제
  v.insert(v.begin() + 2, 20); // 벡터의 2번째 위치에 20을 추가
  v.erase(v.begin() + 2); // 벡터의 2번째 원소를 삭제
  

• set

  // 선언
  set<int> s1; // int형 set 선언
  set<int> s2 = {1, 2, 3}; // 초기화 리스트를 사용하여 set 선언
  set<int> s3(s2); // s2를 복사하여 s3를 선언
  // set 원소 추가, 삭제
  s.find(2); // 2가 있는지 탐색 s.find(2) == s.end()이면 2가 없다
  s.insert(4); // 4를 추가
  s.erase(2); // 2를 삭제
  s.clear(); // 모든 원소 삭제
  s.size(); // set의 크기
  s.empty(); // set이 비어있는지 확인
  

• map

  // 선언
  map<int, string> m1; // int형 키와 string형 값을 가지는 map 선언
  map<int, string> m2 = {\{1, "one"\}, \{2, "two"\}}; // 초기화 리스트를 사용하여 map 선언
  map<int, string> m3(m2); // m2를 복사하여 m3를 선언
  map<int, string> m4(m2.begin(), m2.end()); // m2의 모든 원소를 복사하여 m4를 선언
  // map 원소 접근
  m[2]; // 2에 해당하는 값을 찾음, 없으면 기본값 "" 반환
  m.at(2); // 2에 해당하는 값을 찾음, 없으면 예외 발생
  m.find(2); // 2가 있는지 탐색 m.find(2) == m.end()이면 2가 없다
  // map 원소 추가
  m.insert(make_pair(3, "three")); // 3: "three"를 추가
  m.insert({4, "four"}); // 4: "four"를 추가
  m[5] = "five"; // 5: "five"를 추가
  // map 원소 삭제
  m.erase(2); // 2를 삭제
  

• unordered_map, unordered_set: 해시 테이블을 사용하여 원소를 저장하는 컨테이너, 정렬되지 않음 (탐색 속도가 빠름)

04-4 STL의 알고리즘

// count
int result = std::count(v.begin(), v.end(), 5); // v에서 5의 개수를 세기
// count_if
int result = std::count_if(v.begin(), v.end(), [](int x) { return x > 5; }); // v에서 5보다 큰 원소의 개수를 세기
// find
auto it = std::find(v.begin(), v.end(), 5); // v에서 5를 찾기, it가 v.end()가 아니면 5가 있음
// sort
std::sort(v.begin(), v.end()); // v를 오름차순으로 정렬
std::sort(v.begin(), v.end(), std::greater<int>()); // v를 내림차순으로 정렬 
// reverse
std::reverse(v.begin(), v.end()); // v를 역순으로 정렬
// unique
std::vector<int>::iterator it = std::unique(v.begin(), v.end()); // v에서 중복된 원소를 제거, it는 중복 제거 후 마지막 원소를 가리킴
v.erase(it, v.end()); // 중복 제거된 원소를 벡터에서 삭제
// remove
std::vector<int>::iterator it = std::remove(v.begin(), v.end(), 5); // v에서 5를 제거, it는 제거된 원소의 마지막 원소를 가리킴
v.erase(it, v.end()); // 제거된 원소를 벡터에서 삭제
// max_element
auto it = std::max_element(v.begin(), v.end()); // v에서 최대 원소를 찾기, it이 v.end()가 아니면 최대 원소가 있음
// min_element
auto it = std::min_element(v.begin(), v.end()); // v에서 최소 원소를 찾기, it이 v.end()가 아니면 최소 원소가 있음

04-5 함수

04-6 노하우

• 조기반환: 코드 실행 과정이 함수 끝까지 도달하기 전에 반환하는 기법
• 보호구문: 본격적인 코드 실행 전에 예외조건을 검사하여 실행을 중단하는 기법

05 배열

05-1 배열 개념

// 배열 선언
int arr1[] = {1, 2, 3, 4, 5}; // 원소: 1, 2, 3, 4, 5 / 크기: 5
int arr2[5] = {1, 2, 3}; // 원소: 1, 2, 3, 0, 0 / 크기: 5
int arr3[5] = {}; // 원소: 0, 0, 0, 0, 0 / 크기: 5
int arr4[5]; // 원소: 쓰레기값 / 크기: 5

// 2차원 배열 선언
int arr5[3][4] = { // 3행 4열 배열
    {1, 2, 3, 4}, // 0행
    {5, 6, 7, 8}, // 1행
    {9, 10, 11, 12} // 2행
}; // 원소: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 / 크기: 3x4

05-2 배열 효율성

• 접근: O(1)
• 삽입, 삭제: O(N)

06 스택

06-1 스택 개념

• 스택은 LIFO(Last In First Out) 구조로, 가장 나중에 들어온 데이터가 가장 먼저 나가는 구조
• 스택은 주로 함수 호출, 괄호 검사, 후위 표기법 변환 등에서 사용됨
• 스택은 배열이나 연결 리스트로 구현할 수 있음

06-2 스택 ADT

• 연산: isFull(), isEmpty(), push(ItemType item), pop()
• 상태: top, data[MAX_SIZE]

06-3 문제

• 괄호 짝 맞추기 / 10진수 -> 2진수 변환 / 괄호 회전하기 / 짝지어 제거하기 / 주식 가격 / 크레인 인형뽑기 / 표 편집

07 큐

07-1 큐 개념

• 큐는 FIFO(First In First Out) 구조로, 가장 먼저 들어온 데이터가 가장 먼저 나가는 구조
• 큐는 주로 프로세스 스케줄링, 너비 우선 탐색(BFS) 등에서 사용됨

07-2 큐 ADT

• 연산: isFull(), isEmpty(), push(ItemType item), pop()
• 상태: front, rear, data[MAX_SIZE]

07-3 문제

• 요세푸스 문제 / 기능 개발 / 카드 뭉치

08 해시

08-1 해시 개념

• 해시 함수를 사용해서 변환된 값을 인덱스로 삼아 키와 값을 저장해서 빠른 데이터 탐색을 제공하는 자료구조

08-2 해시 함수

• 나눗셈법
• 곱셈법
• 문자열 해싱

08-3 충돌 처리

• 체이닝
• 개방 주소법(선형 탐사, 이차 탐사, 이중 해싱)

08-4 문제

• 완주하지 못한 선수 / 영어 끝말잇어 / 전화번호 목록 / 할인 행사 / 오픈 채팅방 / 베스트앨범 / 신고 결과 받기 / 메뉴 리뉴얼

09 트리

09-1 트리 개념

• 계층 구조를 표현하는 용도로 사용되는 자료구조.
• 트리는 노드와 간선으로 구성되며, 루트 노드에서 시작하여 자식 노드로 이어지는 구조

09-2 이진 트리 표현하기

• 배열 표현: 부모 노드와 자식 노드의 인덱스를 이용하여 표현, 부모 노드의 인덱스가 i일 때, 왼쪽 자식 노드는 2i + 1, 오른쪽 자식 노드는 2i + 2 (탐색 시간 복잡도 O(N))
• 연결 리스트 표현: 각 노드가 자식 노드를 가리키는 포인터를 이용하여 표현, 각 노드는 왼쪽 자식과 오른쪽 자식을 가리키는 포인터를 가짐 (탐색 시간 복잡도 O(log N))

09-3 이진 트리 탐색하기

• 균형 이진트리: 모든 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하인 트리
• AVL 트리: 이진 탐색 트리의 일종으로, 각 노드에 높이 정보를 저장하여 균형을 유지하는 트리
• 레드-블랙 트리: 이진 탐색 트리의 일종으로, 각 노드에 색 정보를 저장하여 균형을 유지하는 트리

09-4 문제

• 트리 순회 / 이진 탐색 트리 구현 / 예상 대진표 / 다단계 칫솔 판매 / 길 찾기 게임

10 집합

10-1 집합과 상호배타적 집합의 개념

• 집합: 순서와 중복이 없는 원소들을 갖는 자료구조
• 상호배타적 집합: 교집합이 없는 집합 관계

10-2 집합의 연산

유니온 파인드 알고리즘

• union: 두 집합을 합치는 연산
• find: 특정 원소가 속한 집합을 찾는 연산
• path compression: find 연산을 수행할 때, 부모 노드를 직접 자식 노드로 연결하여 트리의 높이를 줄이는 기법
• union by rank: union 연산을 수행할 때, 두 집합의 높이를 비교하여 더 작은 쪽을 더 큰 쪽에 붙이는 기법

// 경로압축과 랭크를 사용해서 연산 비용을 줄일 수 있다.
int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]); // 경로 압축
    }
    return parent[x];
}

void union(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
}

10-3 문제

• 간단한 유니온-파인드 알고리즘 구현하기 / 포켓몬 / 섬 연결하기

11 그래프

11-1 그래프 개념

• 정점과 간선으로 이루어진 자료구조
• 구현 ?

인접 행렬	인접 리스트
메모리 사용량이 많음	메모리 사용량이 적음
특정한 정점 간의 간선 존재 여부를 확인하기 쉬움	특정한 정점 간의 간선 존재 여부를 확인하기 어려움

11-2 그래프 탐색

• 깊이 우선 탐색(DFS): 스택을 사용하여 구현 / 재귀적으로 구현 가능

  모든 가능한 해를 찾는 백트리킹 문제 / 그래프의 사이클을 감지해야 하는 문제 / 최단 경로를 구하는 문제가 아닐 때

• 너비 우선 탐색(BFS): 큐를 사용하여 구현 / 레벨 순회

  최단 경로를 구하는 문제

방문 처리시점 차이:

• DFS: 스택에 푸시할 노드는 방문 예정인 노드이므로 팝할 때 처리
• BFS: 큐에 푸시할 노드는 방문 예정인 노드이므로 푸시할 때 처리

11-3 그래프 최단 경로 구하기

• 다익스트라 알고리즘: 가중치가 있는 그래프에서 최단 경로를 구하는 알고리즘 (음의 가중치가 없는 그래프에서만 사용 가능)
• 벨만 포드 알고리즘: 음의 가중치가 있는 그래프에서 최단 경로를 구하는 알고리즘
• 플로이드 워셜 알고리즘: 모든 정점 쌍 간의 최단 경로를 구하는 알고리즘

11-4 문제

• 깊이 우선 탐색 순회 / 너비 우선 탐색 순회 / 다익스트라 알고리즘 / 벨만 포드 알고리즘 / 미로 탈출 / 게임 맵 최단 거리 / 네트워크 / 양과 늑대 / 배달 / 경주로 건설 / 전력망을 둘로 나누기

12 백트래킹

12-1 백트래킹 개념

• 해가 될 가능성이 없는 곳에서는 되돌아가고, 가능성이 있는 곳으로만 진행하는 탐색 기법
• 조합, 순열, 부분 집합 문제를 해결하는 데 유용
• 유망함수: 해가 될 가능성이 있는지 판단하는 함수

12-2 문제

• 1부터 N까지 숫자 중 합이 10이 되는 조합 구하기 / 스도쿠 퍼즐 / 피로도 / N-Queen / 양궁 대회 / 외벽 점검 / 사라지는 발판

13 정렬

13-1 정렬 개념

• 삽입 정렬 / 병합 정렬 / 힙 정렬 / 위상 정렬 / 계수 정렬

우선순위 큐

• 우선순위 큐는 힙을 기반으로 구현된 자료구조로, 우선순위가 높은 원소가 먼저 나오는 큐
• 최대 힙과 최소 힙으로 나뉨 (힙으로 구현하는 것이 효율적)

priority_queue<int> pq; // 최대 힙
priority_queue<int, vector<int>, greater<int>> pq; // 최소 힙
pq.push(10); // 10을 추가
pq.pop(); // 가장 큰 원소를 삭제
int top = pq.top(); // 가장 큰 원소를 가져옴
int size = pq.size(); // 원소 개수를 가져옴
bool empty = pq.empty(); // 비어있는지 확인
priority_queue<int> pq(vec.begin(), vec.end()); // 반복자를 사용하여 우선순위 큐 초기화

13-2 문제

• 계수 정렬 구현하기 / 정렬이 완료된 두 배열 합치기 / 문자열 내 마음대로 정렬하기 / 정수 내림차순으로 배치하기 / K번째 수 / 가장 큰 수 / 튜플 / 지형 이동

14 시뮬레이션

14-1 시뮬레이션 문제 풀이 노하우

14-2 문제

• 배열 회전하기 / 두 행렬을 곱한 후 전치 행렬 만들기 / 달팽이 수열 만들기 / 이진 변환 / 롤 케이크 자르기 / 카펫 / 점프와 순간 이동 / 캐릭터의 좌표

15 동적 계획법

15-1 동적 계획법 개념

• 큰 문제를 작은 문제로 나누었을 때 동일한 작은 문제가 반복해서 등장하는 경우
• 점화식 구현: 재귀 + 메모이제이션
• 최장 증가 부분 수열 (LIS)
• 최장 공통 부분 수열 (LCS)

15-2 문제

• LCS 길이 계산하기 / LIS 길이 계산하기 / 조약돌 문제 / 피보나치 수 / 2*n 타일링 / 정수 삼각형 / 땅따먹기 / 도둑질 / 가장 큰 정사각형 찾기 / 단어 퍼즐

16 그리디

16-1 그리디 개념

• 최적 부분 구조를 가지는 문제 : 부분해를 포는 과정이 최적해를 구하는 과정과 일치
• 그리디 선택 속성 : 선택 과정이 다른 과정에 영향을 미치지 않음

16-2 최소 신장 트리(MST)

• 신장 트리 중 가중치 합이 최소인 트리
• 프림 알고리즘: 시작 정점에서부터 인접한 정점 중 가장 가중치가 작은 간선을 선택하여 트리를 확장하는 방식
• 크루스칼 알고리즘: 모든 간선을 가중치 순으로 정렬한 후, 가장 작은 간선부터 선택하여 사이클이 생기지 않도록 트리를 확장하는 방루

다익스트라 vs 최소 신장 트리

• 다익스트라: 시작 노드에서 각 노드까지 가는데 필요한 간선의 가중치 합을 최소로
• 최소 신장 트리: 모든 노드를 연결하면서 모든 간선의 가중치 합을 최소로 (간선의 개수 = 정점의 개수 - 1)

16-3 배낭 문제

• 배낭 속 짐의 무게와 가치가 주어졌을 때, 배낭에 담을 수 있는 최대 가치를 구하는 문제

-	부분 배낭 문제	0/1 배낭 문제
특징	짐을 쪼갤 수 있음	짐을 쪼갤 수 없음
접근법	그리디 알고리즘	동적 계획법

16-4 문제

• 거스름돈 주기 / 부분 배낭 문제 / 예산 / 구명보트 / 귤 고르기 / 기지국 설치