코딩 테스트를 위한 자료 구조와 알고리즘 with C++ std::forward_list의 단점 성능상 이유로 마지막에 원소 추가, 역방향 진행, 크기 반환 등을 지원하지 않는다. 빠른 원소 삽입에 적합한 컨테이너는 아니다. std::list STL에서 제공하는 이중 연결 리스트 컨테이너이다. 양방향 반복자를 제공한다. 마지막에 원소 추가, 크기 반환을 지원한다. std::list의 성능 삽입, 삭제 연산시 2개의 포인터를 처리해야 하므로 std::forward_list보다는 시간이 좀 더 걸린다. 크기를 저장하므로 크기 반환은 O(1)에 수행된다. 원소의 삽입 삭제는 O(1)에 수행된다. (삽입할 위치 전의 반복자를 알고 있다는 전제 하에) 특정 위치의 원소를 참조하기 위해서는 반복자를 직접 진행해야 ..
Level 0. 옹알이 (1) 정규 표현식을 이용하여 해결했다. regex_replace 시에 마지막에 regex_constants::format_first_only 파라미터를 주면 첫 번째 매치만 교체할 수 있다. 일치된 문자열을 길이만큼 '_'로 바꾼 후 모든 문자가 '_'로 바뀌었는지 확인하였다. #include #include #include using namespace std; int solution(vector babbling) { int answer = 0; for (string s : babbling) { size_t length = s.length(); vector words = {"aya", "ye", "woo", "ma"}; for (string word : words) s = reg..
코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 임의 접근 반복자(Randon Access Iterator) 특정 위치의 원소에 바로 접근할 수 있는 반복자 vector, array 등에서 사용된다. 순방향 반복자(Forward Iterator) 한 쪽 방향으로만 진행하고 증가 연산만 가능한 반복자 forward_list에서 사용된다. 양방향 반복자(Bidirectional Iterator) 양쪽 방향으로 진행 가능하고 증감 연산을 지원하는 반복자 대부분의 STL 컨테이너에서 지원한다. 반복자의 성능 vector, array에서 next(), prev()는 O(1)에 수행된다. forward_list, list에서 next(), prev()는 선형 시간이 소요된다. std::iterator 앞에..
Level 0. 등수 매기기 평균 점수를 저장하는 벡터1, 역순 정렬된 상태로 저장하는 벡터2를 만들어 해결하였다. 시작 주소부터 원소까지의 거리에 1을 더하면 등수가 된다. #include #include #include using namespace std; vector solution(vector score) { vector answer; vector vec1, vec2; for (const vector& v : score) vec1.emplace_back((v[0] + v[1]) * 0.5); vec2 = vec1; sort(vec2.rbegin(), vec2.rend()); for (const float& average : vec1) answer.emplace_back(find(vec2.begin..
코딩 테스트를 위한 자료 구조와 알고리즘 with C++ std::vector의 단점 중간에 원소를 추가/삭제하는 작업이 O(n)으로 매우 비효율적이다. std::forward_list STL에서 제공하는 단일 연결 리스트 컨테이너이다. 단일 연결 리스트이기 때문에 순방향 반복자만을 지원한다. (그렇기 때문에 std::sort가 아닌 컨테이너 자체적으로 sort 함수를 제공한다.) 메모리나 성능을 극단적으로 최적화해야 하는 경우가 아니라면 std::list를 사용하는 것이 보통이다. std::forward_list의 성능 성능 유지를 위해 O(n) 복잡도의 크기 반환, 중간 원소 접근을 제공하지 않는다. 원소의 삽입은 O(1) 복잡도를 갖는다. (삽입할 위치 전의 반복자를 알고 있다는 전제 하에) std..
Level 0. 평행 두 선분이 평행하다는 것은 기울기가 같다는 뜻이다. 2중 for문을 이용해 조합을 만들고 vector에 기울기를 저장하여 매번 비교하는 식으로 해결했다. 하지만, 2중 for문 안에 find 함수가 있기 때문에 사실상 O(n³)의 복잡도를 갖는다. #include #include #include using namespace std; int solution(vector dots) { vector slopes; for (auto it = dots.begin(); it < dots.end() - 1; ++it) { for (auto jt = it + 1; jt < dots.end(); ++jt) { float x1 = (*it)[0], y1 = (*it)[1]; float x2 = (*j..