[Algorithm] 코딩 테스트 준비

🟩 학습 목표

• 코딩 테스트 문제를 해결하기 위한 올바른 마음가짐과 메타인지 전략을 습득한다.
• C++에서 입출력 속도를 비약적으로 높여주는 최적화 코드의 원리를 이해한다.
• 시간 복잡도개념 ($O(N)$)  을 바탕으로 제한 시간 내에 정답을 도출하는 도구(알고리즘) 선택 기준을 세운다.

 

🟧 1. 공부를 시작하기 전 : 메타인지와 기록의 힘

---

🟦 앎과 모름의 경계 명확히 하기

• 무조건 기록하기 : 문제를 풀지 못했더라도 내가 어디까지 생각했는지, 왜 이 방법이 맞다고 생각했는지 한글로 적어둔다. 나중에 정답과 비교할 때 가장 큰 자산이 된다.
• 실전처럼 연습하기 : 타이머를 켜고 정해진 시간 안에 최대 점수를 내는 훈련을 통해 실전 긴장감에 대비한다.
• 나만의 언어로 요약하기 : 공부가 끝난 뒤 아무것도 보지 않고 오늘 배온 내용을 한글로 요약할 수 있어야 진짜 내 지식이 된다.

 

🟧 2. 분석과 설계 : 키보드보다 머리를 먼저 쓰기

---

🟦 문제 분석과 쪼개기

• 전체 시간의 50~60%는 분석에 투자한다. 커다란 문제를 아주 작은 동작 단위로 쪼개어 생각하면 로직을 세우기 훨씬 쉬워진다.
• 제약 사항 체크 : 입력값의 범위를 보고 "컴퓨터가 얼마나 힘들지" 미리 예상해야 한다. 100만 개의 데이터를 $O(N^2)$으로 처리하면 무조건 시간 초과가 발생한다.

🟦 C++ 입출력 최적화 비기

• ios::sync_with_stdio(false); : C++과 C언어 입출력의 동기화를 끊어 C++ 독자적인 속도를 확보한다. 단, 이 코드를 쓰면 printf/scanf를 섞어 쓰면 안 된다.
• cin.tie(NULL); : 입력과 출력 사이의 연결 고리를 끊어, 화면 출력(플러싱) 때문에 입력을 기다리는 시간을 줄인다. 대량의 데이터를 읽어야 하는 코딩 테스트에서 필수적이다.

 

🟧 3. 알고리즘 도구 상자와 시간 복잡도

---

🟦 상황별 추천 알고리즘

문제의 키워드	추천 도구 (알고리즘/자료구조)	주요 용도
최근 데이터, 괄호 짝	스택 (Stack)	뒤로 가기, 거꾸로 처리
순서대로 처리	큐 (Queue)	시뮬레이션, 대기열
최단 거리, 최소 단계	너비 우선 탐색 (BFS)	미로 찾기, 최단 경로
모든 경우의 수 탐색	깊이 우선 탐색 (DFS)	모든 경로 추적
최단 경로 (가중치)	다익스트라 (Dijkstra)	지도 앱 최단 거리

🟦 빅오($O$) 표기법과 시간 제한

• 컴퓨터는 1초에 약 $10^8$번(1억 번) 연산이 가능하다. 안전하게 $3 \times 10^7$번 정도의 계산을 목표로 설계한다.
• $O(N)$ : 데이터가 1,000만~3,000만 개일 때 적합하다.
• $O(N \log N)$ : 데이터가 100만 개일 때 정렬 등을 수행하기 적합하다.
• $O(N^2)$ : 데이터가 2,000~5,000개 수준일 때만 사용 가능하다.

 

🟧 4. 실전 연습 : 주식 시장 최고 수익 찾기 (그리디)

---

🟦 문제 분석 및 의사코드(Pseudocode) 작성

• 데이터 개수 $N$이 100만 개이므로 $O(N^2)$은 탈락이다. 데이터를 한 번만 훑는 $O(N)$으로 설계해야 한다.
• 의사코드 설계 :

1. C++ 입출력 속도 향상 코드를 적는다.
2. 날짜 수 N을 입력받는다.
3. 가장 싼 가격(minPrice)을 매우 큰 값으로, 최대 이익(maxProfit)을 0으로 초기화한다.
4. N번 동안 날짜별 주가를 돌며 현재 가격이 minPrice보다 낮으면 갱신한다.
5. 그렇지 않으면 현재 가격 - minPrice를 계산해 maxProfit을 최대 이으로 갱신한다.
6. 최종 최대 이익을 출력한다.

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    int minPrice = 10001;
    int maxProfit = 0;

    for (int i = 0; i < n; i++) {
        int currentPrice;
        cin >> currentPrice;

        if (currentPrice < minPrice) {
            minPrice = currentPrice;
        } 
        else if (currentPrice - minPrice > maxProfit) {
            maxProfit = currentPrice - minPrice;
        }
    }

    cout << maxProfit << "\n";
    return 0;
}

 

🟧 핵심 요약 및 주의사항

• 기록의 습관 : 정답을 맞히는 것보다 내 사고 과정을 데이터베이스화하는 것이 실력 향상의 지름길이다.
• 설계 우선주의 : 의사코드를 한글로 먼저 작성하면 문법 고민 없이 로직의 구멍을 먼저 찾을 수 있다.
• 시간 복잡도 계산 : $10^8$ 규칙을 항상 머릿속에 두고, 내 설계가 시간 제한 안에 들어오는지 빅오 표기법으로 검증해야 한다.