들어가며
코딩테스트를 준비하면서 책을 하나 샀습니다. 이정표 없이 사이트에서 문제만 푸는 것은 좀 비 효율적인 것 같아서 저에게 방향을 제시해 줄 것이 필요하다고 생각해서 구매했는데 나쁘지 않은 것 같습니다. 완전 정독까지 파이팅~!
코딩 테스트를 준비하기 전에
합격자가 꼭 되고 싶은 여러분
- 타인의 풀이를 보면 사고를 넓힐 수 있다.
- 나만의 테스트 케이스를 추가하는 건 좋은 알고리즘을 생각할 때 도움이 된다.
아는 것과 모르는 것을 명확하게
- 첫 번째, 기록하라.
- 두 번째, 시험 보듯 공부하라.
- 세 번째, 짧은 시간 공부해서는 절대 코딩 테스트를 통과할 수 없다.
- 네 번째, 나만의 언어로 요약하라.
코딩 테스트 효율적으로 준비하기
문제 분석 연습하기
- 첫 번째, 문제를 쪼개서 분석하라.
- 두 번째 제약 사항을 파악하고 테스트 케이스를 추가하라.
- 세 번째, 입력 크기를 분석하라.
- 네 번째, 핵심 키워드를 파악하라.
스택 - 쌍이 맞는지
- 최근- 무언가를 저장하고 반대로 처리
- 데이터의 조합이 균형
- 알고리즘이 재귀
- 최근 상태 추적큐 - 순서대로
- ~대로 동작하는 경우
- 스케줄링
- 최소 시간- 특정 조건에 따라 시뮬레이션
- 시작 지점부터 목표 지점까지 최단 거리깊이 우선 탐색 - 모든 경로 - 메모리 사용량이 제한적일 때의 탐색
- 백트래킹 문제를 풀 때너비 우선 탐색 - 최적
- 레벨 순회
- 최소 단계
- 네트워크 전파- 시작 지점부터 최단 경로나 최소 횟수를 찾아야 할 때 백트래킹 - 조합
- 순열
- 부분 집합- 조합 및 순열 문제
- 특정 조건을 만족하는 부분 집합최단 경로 - 최단 경로
- 최소 시간
- 최소 비용
- 트래픽
- 음의 순환
- 단일 출발점 경로- 다익스트라 : 특정 지점에서 나머지 지점까지 가는 최단 경로
- 벨만-포드 : 음의 순환 탐지, 음의 가중치를 가진 그래프에서 최단 경로 - 다섯 번째, 데이터 흐름이나 구성을 파악하라.
의사 코드로 설계하는 연습하기
- 첫 번째, 세부 구현이 아닌 동작 중심으로 작성하라.
- 두 번째, 문제 해결 순서로 작성하라.
- 세 번째, 충분히 테스트하라.
알고리즘의 효율 분석
시간 복잡도란?
시간 복잡도란 알고리즘의 성능을 나타내는 지표로, 입력 크기에 따른 연산 횟수를 의미한다.
시간 복잡도의 우선순위
다음 순서대로 시간이 오래 걸린다.
| 1 | n! | 팩토리얼 |
| 2 | 2^n | 지수 |
| 3 | n^2 | 2차 |
| 4 | n log n | 1차 * 로그 |
| 5 | n | 1차 |
| 6 | log n | 로그 |
| 7 | 1 | 상수 |
시간 복잡도를 코딩 테스트에 활용하는 방법
코딩 테스트 문제에는 제한 시간이 있으므로 문제를 분석한 후에 빅오 표기법을 활용해서 해당 알고리즘을 적용했을 때 제한 시간 내에 출력값이 나올 수 있을지 확인해 볼 수 있다. 컴퓨터가 초당 연산할 수 있는 최대 횟수는 보통 1억 번이지만, 코딩 테스트의 문제 제한시간은 여유 있게 지정된 것이니 초당 1000~3000만 정도로 고려해야 한다. 예를 들면 제한 시간이 1초인 문제는 연산 횟수가 3000만이 넘는 알고리즘을 사용하면 안 된다. 알고리즘 별로 가능한 최대 연산 횟수 n은 다음과 같다.
| O(n!) | 10 |
| O(2^n) | 20 ~ 25 |
| O(n^3) | 200~ 300 |
| O(n^2) | 3000 ~ 5000 |
| O(n log n) | 100만 |
| O(n) | 1000 ~ 2000만 |
| O(log n) | 10억 |
코딩 테스트 필수 문법
빌트인 데이터 타입
빌트인 데이터 타입이란 헤더 파일 없이 사용할 수 있는 기본 내장 데이터 타입을 말한다.
int, float, double, bool, char, 배열, …
문자열
#include <string>
using namespace std;
int main()
{
string str1;
string str2 = "Hello";
string str3(str2);
string str4(str2, 0, 3); // 부분 복사 "He"
string str5(10, '*'); // 반복 문자열 "**********"
return 0;
}
문자열 찾기
// find(타겟 문자열)
// find(타겟 문자열, 탐색 시작 인덱스)
// 찾으면 시작 인덱스, 못 찾으면 npos 반환
// 시간복잡도 O(n)
string str = "Hello";
size_t pos1 = str.find("He"); // 0
size_t pos1 = str.find('o'); // 4
size_t pos1 = str.find("World"); // npos
size_t pos1 = str.find("l", 3); // 3
문자열 추가, 수정
// 추가는 +, += 사용
// 수정은 [], replace(시작위치, 없앨 개수, 새로운 문자열) 사용
string str = "Hello";
string str1 = "World";
string str2 = str + str1;
str2 += "!"; // HelloWorld!
str2[0] = 'Y'; // YelloWorld!
str2.replace(5, 5, Blue); // YelloBlue // 5번 인덱스부터 5개 문자를 Blue로 대체
STL
standard template library는 C++에서 제공하는 템플릿 기반의 표준 라이브러리다.
STL과 자주 사용하는 필수 문법
- 상수 레퍼런스 : const T&, T&
- auto : auto num = 10;
- range based for : for(int num : array) { … }
- iterator : begin(), end(), rbegin(), rend()
컨테이너
코딩 테스트에서는 벡터, 셋, 맵, 우선수위 큐를 자주 다룬다.
벡터
배열과 유사한 컨테이너이다. 데이터를 순차적으로 저장하고, 인덱스를 통해 특정 위치의 원소에 쉽게 접근한다.
#include <vector>
using namespace std;
int main()
{
vector<int> v1;
vector<int> v2 = {1, 2, 3};
vector<int> v3(4, 3); // {3, 3, 3, 3}
vector<int> v4(v3); // 복사
// 2차원 벡터
vector<vector<int>> v5;
vector<vector<int>> v6(3, vector<int>(4)); // 3 * 4 벡터
vector<vector<int>> v7(3, vector<int>(4, 10)); // 10으로 채워진 3 * 4 벡터
vector<vector<int>> v8 =
{
{1, 2, 3},
{4, 5, 6}
}; // 2 * 3 벡터 초기화 리스트
return 0;
}
벡터의 원소 변경
// 변경
// 시간 복잡도 O(1)
vector<int> vec = {1, 2, 3, 4, 5};
vec[2] = 4; // 1, 2, 4, 4, 5
// 삽입
// 앞에서 삽입, 삭제는 O(n). 비 효율적이다. deque를 사용하는것이 나음.
// 뒤에서 삽입, 삭제는 O(1)
vec.push_back(6); // 1, 2, 4, 4, 5, 6
vec.pop_back(); // 1, 2, 4, 4, 5
// insert(주소, 값) 주소에 삽입하고 뒤로 밀어냄
// erase(주소) 주소에 있는 값을 삭제하고 앞으로 당김
vec.insert(vec.begin(), 0); // 0, 1, 2, 4, 4, 5
vec.earse(vec.begin()); // 1, 2, 4, 4, 5
셋
중복을 허용하지 않고 저장된 데이터를 자동으로 정렬하는 컨테이너이다. 집합이라 하기도 한다.
#include <set>
using namespace std;
int main()
{
set<int> s1;
set<int> s2 = {3, 1, 3, 2, 5}; // 1, 2, 3, 5
set<int> s3(s2);
return 0;
}
셋에서 원소 탐색
// find(target); 찾으면 원소의 위치, 못 찾으면 end() 반환
auto iter = s2.find(3); // 3의 주소
cout << *iter; // 3
셋의 삽입과 삭제
// 삽입, 삭제 둘다 O(log n)
// insert(), erase(), erase는 원소, 원소의 주소 둘 다 올 수 있음
s2.insert(7);
s2.erase(3);
맵
맵은 키와 값을 쌍으로 갖는 컨테이너이다. 키와 값의 쌍을 entry라고 하면 STL에서는 std::pair로 표현한다. 검색, 삽입, 삭제는 O(log n). 셋과 마찬가지로 중복이 허용되지 않는다. 키를 통해 값을 찾는다.
#include <map>
using namespace std;
int main()
{
map<string, double> salaries;
map<string, double> grade =
{
{"John", 3.7},
{"Emma", 4.1}
};
return 0;
}
맵에서 특정 키에 접근
// []연산자, find 메서드 사용한다.
// []를 통해 값에 접근할 때 값이 없으면 맵에 추가를 한다. 추가하고 싶지 않다면 find를 사용.
grade["John"] = 3.5; // 수정
grade{"James"] = 4.5; // 추가
auto iter = grade.find("James");
cout << iter->first << iter->second; // James4.5
맵의 삽입과 삭제
// 삽입은 [] 또는 insert 메서드 이용.
// 삭제는 erase() 메서드, 키 값 또는 주소를 넘긴다.
// 삽입
salaries.insert(make_pair("John", 100));
salaries.insert({"Emma", 200});
salaries["Tom"] = 300;
//삭제
salaries.erase("Tom");
정렬되지 않은 셋과 맵
정렬이 필요하지 않을 때 사용하면 성능을 높일 수 있다. 삽입, 삭제 탐색이 O(1)이다.
#include <unordered_set>
#include <unordered_map>
using namespace std;
int main()
{
unordered_set<int> us;
us.insert(1);
us.insert(2);
us.insert(3);
us.insert(4);
for(int num:us)
cout << num << endl; // 출력이 1, 2, 3, 4로 보장되지 않는다.
unordered_map<int, int> um;
um[1]=1;
um[2]=2;
um[3]=3;
um[4]=4;
for(const suto& pair : um)
cout << pair->first << " : " << pair->second << endl;
// 출력의 순서가 보장되지 않는다.
STL의 알고리즘
count() 함수로 횟수 세기
#include <algorithm>
// count(begin, end, target); // target이 [begin, end) 에서 몇번 나타나는지 반환
vector<int> vec = {1, 4, 3, 4, 5, 4, 5};
int ret = count(vec.begin(), vec.end(), 5); // 2
sort() 함수로 정렬하기
sort 함수는 다음과 같이 오버로딩 되어있다.
- sort(begin, end)
- sort(begin, end, 비교 함수)
사용자 정의 자료형을 정렬할 때는 비교 함수를 넘겨준다.
#include <algorithm>
using namespace std;
int main()
{
vector<int> v = {4, 2, 5, 3, 1};
// 오름차순 정렬
sort(v.begin(), v.end());
// 내림차순 정렬
sort(v.rbegin(), v.rend()); // 역방향 반복자 사용
// 비교함수는 첫 번째 인자가 조건에 맞을 때 참이 되도록 정의한다.
// 예를 들어 오름차순 이라면 [](int a, int b){ return a < b; }
// a가 작을 때 참이 되는 비교함수를 넘겨준다.
// 참고로 비교함수가 false일 때 두 값을 바꾼다.
sort(v.begin(), v.end(), [](){ return a<b; }); // 람다를 비교함수로 넘김
return 0;
}
next_permutation() 함수로 순열 생성하기
시작 반복자와 끝 반복자를 받아서 가능한 모든 순열을 생성하는 함수이다. 가능한 순열이 있으면 true, 더 이상 불가능 하면 false를 반환한다. 실제 범위 내 원소들의 위치가 변경된다. 시간복잡도는 O(n * n!)이다.
#include <algorithm>
int main()
{
vector<int> v = {1, 2, 3};
do
{
for(int i:v)
cout << i << " ";
cout << endl;
} while(next_permutation(v.begin(), v.end()));
return 0;
}
next_permutation 함수는 초기에 오름차순으로 정렬된 상태로 사용해야 한다. 만약 정렬되지 않은 상태로 시작하게 되면 그 부분부터 다음 순열로 넘어가게 된다. 그러면 앞쪽의 순열은 출력되지 않는다.
unique() 함수로 중복 정리하기
vector<int> v = {1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5};
auto newEnd = unique(v.begin(), v.end()); // 1, 2, 3, 4, 5, (newEnd)2, 3, 3, 4, 4, 5, 5
for(auto it = v.begin(), it~= newEnd; ++it)
cout << *it << " ";
cout << endl;
binary_search() 함수로 이진 탐색하기
시작 반복자, 끝 반복자, 찾을 값, 세 개의 인자를 받아서 탐색을 수행하고 있으면 true 없으면 false를 반환한다. 시간복잡도는 O(log n). 원소가 정렬되어 있어야 작동한다.
vector<int> v = {1, 2, 3, 4, 5};
cout << binary_search(v.begin(), v.end(), 4) << endl; // 1
cout << binary_search(v.begin(), v.end(), 7) << endl; // 0
max_element(), min_element() 함수로 최댓값, 최솟값 위치 구하기
시작 반복자와 끝 반복자를 인자로 받고 최댓값, 최솟값의 위치를 반환한다. 시간복잡도는 O(n).
vector<int> v = {1, 3, 5, 2, 4, 6};
auto maxIt = max_element(v.begin(), v.end());
auto minIt = min_element(v.begin(), v.end());
cout << *maxIt << " " << *minIt << endl; // 6 1
코딩 테스트 코드 구현 노하우
조기 반환 early return
double total_price(int quantity, double price)
{
double total = quantity * price;
if(total > 100)
return total * 0.9; // 조기 반환
return total;
}
보호 구문
로직을 진행하기 전 예외 처리 코드를 추가한다.
double get_avg(const vector<int>& arr, int N)
{
if(arr.empty())
return -1;
if(N==0)
return -1;
...( 평균 계산 )
return result;
}
마치며
아직 책의 본격적인 내용을 시작하지 않았지만 앞부분 만으로도 책이 꽤나 마음에 들었습니다. 실전에서 자주 쓰는 문법위주로 설명하고 혼자 알고리즘 문제를 풀 때 이해가 안 되었던 것이 몇 가지 해결되었습니다. 책을 열심히 보고 공부한다면 저도 알고리즘 고수가 될 수 있겠죠? 파이팅~!
'알고리즘 > 코딩 테스트 합격자 되기 C++ 편' 카테고리의 다른 글
| [코테] 해시 (0) | 2024.10.19 |
|---|---|
| [코테] 스택, 큐 (0) | 2024.10.12 |
