알고리즘 함수 및 코테 꿀팁

최대/최소 값 탐색

• max_element/min_element/minmax_element

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    vector<int> v = {4, 1, 6, 3, 8, 2};

    // 1. max_element: 최댓값의 위치를 찾아줍니다
    auto max_it = max_element(v.begin(), v.end());
    cout << "최댓값: " << *max_it << endl; // 8 출력
    
    // 2. min_element: 최솟값의 위치를 찾아줍니다
    auto min_it = min_element(v.begin(), v.end());
    cout << "최솟값: " << *min_it << endl; // 1 출력
    
    // 3. minmax_element: 최솟값과 최댓값을 한 번에! (구조적 바인딩 활용했어요)
    auto [min_iter, max_iter] = minmax_element(v.begin(), v.end());
    cout << "최댓값2: " << *max_iter << endl; // 8 출력
    cout << "최소값2: " << *min_iter << endl; // 1 출력
}

 

---

특정 조건 만족하는 원소 구하기

• count
  • 단순 값만 비교
• count_if
  • 사용자 조건을 정의할 수 있음

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    vector<int> v = {1, 1, 2, 2, 3, 3};

		// 값이 2인 원소 개수
    int cnt = count(v.begin(), v.end(), 2);
    // 짝수 개수
    int even_cnt = count_if(v.begin(), v.end(), [](int x) { return x % 2 == 0; });

    cout << "값이 2인 원소 개수: " << cnt << endl;
    cout << "짝수인 원소 개수: " << even_cnt << endl;
}

---

STL 활용 복습

• 시간 복잡도 요구 사항 파악
  • 삽입/삭제/탐색을 빈번하게 한다면
    • map/set 또는 unordered_map/unordered_set
  • 가장 큰/작은 값 빈번하게 추출
    • priority_queue
  • 앞에서 빼고 뒤에서 넣기
    • 한쪽 방향 : queue
    • 양쪽 방향 : deque
• 정렬
  • 결과적으로 정렬 상태 필요
    • map, set, sort() 사용
  • 특정 값 범위 찾을 때(정렬 필요)
    • lower_bound, upper_bound
  • k번째 원소에 집중
    • nth_element
• 중복 제거 & 효율적 관리
  • unique + erase 패턴(정렬 필요)
  • set / unordered_set

문제를 처음 접할 때, 입력 크기(N)와 연산 횟수를 파악 후 대략적인 시간 복잡도를 예측해보는 것이 좋음

그리고, 어떤 STL 중 어떤 자료구조가 적합할지 짚어보는 것이 좋음

---

디버깅 & 출력 패턴

• std::distance
  
  • 첫번째 이터레이터와 두번째 이터레이터의 거리(두 개의 차)를 반환

• , std::advance
  • 이터레이터를 원하는 위치로 이동

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    vector<int> v = {1, 2, 3, 4, 5};
    auto it = find(v.begin(), v.end(), 3);
    cout << *it << endl; // 3
    int idx = distance(v.begin(), it); // idx = 2
    advance(it, idx); // it를 2칸 전진 -> 숫자 5를 가리킴
    cout << *it << endl; // 5
}

---

헤더 파일 단일화

• #include <bits/stdc++.h>
  • GCC 전용 헤더로 C++ 표준 라이브러리를 모조리 포함시킴
  • 문제 사이트에 따라 사용 불가할수도 있음

---

효율적 입출력

• ios::sync_with_stdio(false), cin.tie(nullptr)
  • c 표준 입출력과 c++ 스트림을 분리하여 동작하게 하여 버퍼링 효율이 좋아져 입출력이 약간 빨라짐
• \n
  • endl을 사용하면 출력 버퍼가 강제로 flush돼서 느려질 수 있으나 큰 문제에서 반복 출력 할 땐 \n이 선호됨
• getline(cin, string)
  • 문자열 전체를 입력받는 함수
  • 공백이나 탭 같은 구분 문자도 그래도 읽을 수 있음
  • 한줄 통째로 string 에 저장됨

---

코태 노하우

1. 제한 사항과 입력 크기 다시보기

   

   • 입력 크기와 시간제한을 확인하는것이 가장 중요
2. 예외 케이스 챙기기
   • 문제를 풀었을 때 틀렸다면 예외 처리 챙기기
     • 빈 입력, 동일 원소만 존재하는 경우
     • 음수, 0, 최대/최소 값 경계에서 동작
     • 순열, 정렬 문제에서 이미 정렬된 상태로 들어오거나, 역정렬된 상태
   • 이러한 케이스들은 가끔 풀이가 살짝 어긋나면 그대로 틀릴 때가 많음
   • 따라서 테스트를 직접 추가해 돌려보면 빠르게 오류를 잡을 수 있음
3. 빠른 코딩 테스트 제출 사이클
   • 빠르게 초기 코드를 짜서 제출한 뒤 틀렸다면 빠르게 수정하는 방식이 유리할 수도 있음