본문 바로가기
반응형

전체 글

코딩테스트-맵과 방향백터 맵(격자) 그래프 탐색과 방향벡터 (dy, dx)격자(행렬) 형태로 주어지는 맵 문제는 코딩 테스트의 단골 유형이다. 이런 문제를 깔끔하게 푸는 핵심 도구가 방향벡터(dy, dx)다. 상하좌우 4방향 이동을 배열 하나로 처리해, 탐색 코드를 간결하게 만든다. (실제 네이버 코테에도 출제된 유형이다.)1. yx 좌표계맵 문제에서는 좌표를 (y, x) = (행, 열) 순서로 쓰는 것을 권장한다. 2차원 배열 접근이 a[행][열] = a[y][x]이기 때문에, 순서를 맞추면 헷갈릴 일이 줄어든다.2. 방향벡터 정의상하좌우 4방향의 좌표 변화량을 두 배열에 담아 둔다.const int dy[] = {-1, 0, 1, 0}; // 상, 우, 하, 좌const int dx[] = { 0, 1, 0, -1};(dy.. 더보기
코딩테스트-인접리스트 인접 리스트(Adjacency List)를 이용한 그래프 표현과 DFS인접행렬이 정점이 많아질수록 메모리를 O(V²)로 잡아먹는 반면, 인접 리스트는 실제 연결된 정점만 저장하기 때문에 메모리 효율이 훨씬 좋다. 실전 코딩 테스트에서 그래프는 대부분 인접 리스트로 푼다.1. 인접 리스트란?인접 리스트는 정점마다 "연결된 정점들"만 목록으로 저장하는 방식이다. 연결되지 않은 정점은 아예 저장하지 않으므로, 간선이 적은(희소) 그래프에서 메모리가 크게 절약된다.2. 연결 리스트 vs 벡터인접 리스트는 개념적으로는 연결 리스트(linked list)지만, 실제 구현에서는 벡터(vector)를 쓰는 것을 권장한다.연결 리스트 : 삽입/삭제는 유리하지만, n번째 요소를 찾으려면 앞에서부터 따라가야 해 O(n)이 .. 더보기
코딩테스트-인접행렬 인접행렬을 이용한 그래프 표현과 DFS 탐색이번 글에서는 인접행렬(Adjacency Matrix)로 그래프의 연결 상태를 2차원 배열로 표현하는 방법과, 이를 이용한 DFS(깊이 우선 탐색) 과정을 정리한다.1. 인접행렬을 통한 그래프 표현인접행렬은 정점 간 연결 관계를 0 또는 1로 나타내는 2차원 배열이다. a[i][j] = 1이면 정점 i와 j가 연결되어 있다는 뜻이다.양방향(무방향) 간선은 a[i][j]와 a[j][i]를 대칭적으로 모두 1로 표시한다.배열 크기는 정점 개수(V)에 맞춰 설정한다.2. 방문 기록 관리 (visited)재귀로 그래프를 탐색할 때, 이미 방문한 정점을 다시 방문하면 무한 루프에 빠진다. 이를 막기 위해 visited 배열로 방문 여부를 기록해 중복 탐색을 방지한다.3... 더보기
코딩테스트-누적합 누적합 (Prefix Sum)누적합은 배열의 앞에서부터의 합을 미리 계산해 두는 기법이다. 한 번 만들어 두면 임의의 구간 합을 O(1)에 구할 수 있어, 구간 쿼리 문제의 기본기가 된다.핵심 점화식p[i] = p[i-1] + a[i]즉 "이전까지의 누적합 + 현재 값"을 계속 더해 나가면 된다.구현#include using namespace std;int main() { int a[6] = {0, 1, 2, 3, 4, 5}; // a[0]은 편의상 0 (1-indexed) int p[6] = {0}; for(int i = 1; i 구간 합 공식: 구간 [L, R]의 합은 p[R] - p[L-1]로 한 번의 뺄셈이면 끝난다. 이것이 누적합의 핵심 이점이다.구간 쿼리, 두 가지 방법구간 합.. 더보기
코딩테스트-중복제거 C++ 벡터에서 중복 요소 제거하는 두 가지 방법{1, 1, 2, 2, 3, 3} 같은 벡터에서 중복을 제거해 1, 2, 3만 남기는 방법을 정리한다. 대표적으로 map을 쓰는 방법과 unique()를 쓰는 방법 두 가지가 있다.방법 1. map 이용하기map은 키(key)가 중복될 수 없다는 성질을 가진다. 이를 이용해 각 값을 키로 등록하면 자연스럽게 중복이 걸러진다. 게다가 map은 키 기준으로 자동 정렬되므로 결과도 오름차순으로 나온다.#include using namespace std;map mp;int main() { vector v{1, 1, 2, 2, 3, 3}; for(int i : v){ if(mp[i]){ // 이미 등록된 값이면 c.. 더보기
메모리와 포인터 메모리와 포인터 — 배열의 포인터 변환 (Array Decay) 결론부터 말하면 int[] 와 int 는 서로 다른 자료형이다. 하지만 배열을 포인터에 담아 쓸 수 있는데, 그 이유가 오늘의 핵심이다.배열은 곧 "첫 번째 주소"배열을 포인터로 받으려면 원칙적으로 같은 자료형으로 선언해야 한다. 그런데 배열 이름 자체가 "첫 번째 원소의 주소"를 반환하는 성질을 가지기 때문에, 아래처럼 포인터에 그대로 대입할 수 있다.#include using namespace std;int main(){ int arr[3] = {10, 20, 30}; int *p = arr; // arr → 첫 번째 원소(arr[0])의 주소로 변환됨 cout 여기서 int *p = arr;가 성립하는 이유는, 배열.. 더보기
* 역참조 연산자 (*)*는 아스테리스크(asterisk)라고 읽는다. C/C++에서 이 기호는 문맥에 따라 세 가지 역할을 한다.* 의 세 가지 역할곱하기 (연산자) — 산술 곱셈. 예: a * b포인터 선언 — 주소를 저장하는 변수 선언. 예: int *p;역참조(Dereference) 연산자 — 포인터가 가리키는 주소에서 값을 꺼낸다. 예: *p역참조 연산자란?역참조 연산자는 포인터를 기반으로, 그 포인터가 가리키는 곳의 실제 값을 꺼내는 역할을 한다.#include using namespace std;int main(){ int a = 10; int *p = &a; // p는 a의 주소를 가리킨다 (선언 시 *) cout 핵심 정리&a : 변수 a의 주소를 얻는다 (주소 연산자).. 더보기
코딩테스트-조합 C++로 조합(Combination) 구현하기 — 그리고 언제 이중 포문 대신 재귀를 쓸까순열(Permutation)이 "순서가 있는 나열"이라면, 조합(Combination)은 "순서 없이 뽑기"다. 예를 들어 {1,2,3}에서 2개를 뽑을 때 (1,2)와 (2,1)은 같은 것으로 본다. 이번 글에서는 재귀로 조합을 구현하고, 왜 이중 포문보다 재귀가 나은 경우가 있는지 정리한다.1. 조합 공식 (nCr)조합의 개수는 다음 공식으로 구한다. n!nCr = -------- r!(n-r)!nCr : 조합의 수n : 집합의 전체 원소 개수r : 뽑을 원소 개수하지만 우리가 필요한 건 "개수"만이 아니라 "실제 조합 목록"인 경우가 많다. 그래서 재귀로 직접 나열해 본다.2. 재귀를 이용한.. 더보기

티스토리툴바