Category Reference

Algorithms

복잡도, 자료구조, 정렬, 탐색, 그래프, 코테 패턴까지 알고리즘의 핵심 이론을 카드형 레퍼런스로 정리합니다.

Search cards

4 cards

Search titles, summaries, tags, and subcategories.

복잡도와 기초

4 cards

복잡도와 기초

시간·공간 복잡도와 Big-O

Big-O를 입력 크기에 따른 성장률로 읽고, 코딩 테스트에서 시간 제한과 메모리 제한을 기준으로 알고리즘을 고르는 방법을 정리합니다.

3n + 10        -> O(n)
2n^2 + 50n    -> O(n^2)
n log n + n   -> O(n log n)

복잡도와 기초

재귀와 스택 프레임

재귀를 자기 자신을 호출하는 함수가 아니라 상태를 더 작은 문제로 넘기는 방식으로 읽고, 기저 조건과 콜 스택 한계를 정리합니다.

int Factorial(int n)
{
    if (n <= 1) return 1;     // 기저 조건
    return n * Factorial(n - 1); // 더 작은 문제
}

복잡도와 기초

코테 문제 접근 전략

입력 크기, 값 범위, 정렬 여부, 그래프 구조, 엣지케이스를 읽고 코딩 테스트 문제의 알고리즘 후보를 좁히는 순서를 정리합니다.

1. 입력 크기와 시간 제한을 본다
2. 값 범위와 자료형을 정한다
3. 정렬 여부, 중복 여부, 그래프 조건을 표시한다
4. 가능한 복잡도 후보를 좁힌다
5. 엣지케이스를 먼저 적고 구현한다
6. 예제보다 작은 직접 케이스로 검산한다

복잡도와 기초

비트 연산 기초

AND, OR, XOR, SHIFT를 비트 단위 조건과 상태 집합으로 읽고, 코딩 테스트에서 자주 쓰는 마스크 패턴을 정리합니다.

int mask = 0;

mask |= 1 << 2;          // 2번 비트 켜기
bool has = (mask & (1 << 2)) != 0; // 2번 비트 확인
mask &= ~(1 << 2);       // 2번 비트 끄기
mask ^= 1 << 2;          // 2번 비트 토글

bool isOdd = (x & 1) == 1;
int doubled = x << 1;
int halved = x >> 1;

Loading category cards

Preparing references and filters for this topic. 이 주제의 레퍼런스와 필터를 준비하고 있습니다.

1. 입력 크기와 시간 제한을 본다 2. 값 범위와 자료형을 정한다 3. 정렬 여부, 중복 여부, 그래프 조건을 표시한다 4. 가능한 복잡도 후보를 좁힌다 5. 엣지케이스를 먼저 적고 구현한다 6. 예제보다 작은 직접 케이스로 검산한다

int mask = 0; mask |= 1 << 2; // 2번 비트 켜기 bool has = (mask & (1 << 2)) != 0; // 2번 비트 확인 mask &= ~(1 << 2); // 2번 비트 끄기 mask ^= 1 << 2; // 2번 비트 토글 bool isOdd = (x & 1) == 1; int doubled = x << 1; int halved = x >> 1;