1. 투 포인터(Two Pointers)란?말 그대로 두 개의 포인터(인덱스)를 사용하여 배열이나 리스트를 효과적으로 탐색하는 기법이다.O(N)의 시간 복잡도를 가짐 2. 주요 유형 2.1. 시작점과 끝점에서 만나는 방식(양끝 조합)주로 정렬된 배열에서 두 수의 합이 특정 K와 일치하는지 찾을 때 사용된다.Pointer 1 (Left): 배열의 시작점에서 오른쪽으로 이동한다.Pointer 2 (Right): 배열의 시작점에서 왼쪽으로 이동한다.동작: 포인터에 위치한 두 요소의 합이 K보다 작으면 Left++, 크면 Right-- 를 수행하며 포인터를 이동한다. 2.2. 같은 방향으로 진행하는 방식(슬라이딩 윈도우)연속된 부분 수열의 합이 특정 값 K를 만족하는지 찾을 때 사용된다. 배열의 정렬이 필요하지..
1. 백트래킹이란?이전까지의 DFS (참고: https://roajava.tistory.com/262)지나가는 길에 표시를 한다. (visited = true)막다른 길을 만나서 되돌아 올 때, 그 표시를 지우지 않는다.결과 : 한 번 지나간 곳은 영원히 다시 못감 백트래킹(Back Tracking)지나가는 길에 표시를 한다. (visited = true)막다른 길을 만나서 되돌아 올 때, 표시한 흔적을 지운다. (visited = false)결과 : 한 번 지나갔던 곳이라도 나왔다면 다시 방문할 수 있음.백트래킹은 DFS + 취소(Undo) 기능이다. 2. 코드 차이DFS의 핵심 로직 예시void dfs(int x, int y) { visited[x][y] = true; // 1. 방문 도장 쾅..
1. 브루트 포스(Brute Force)란?가장 무식한 방법이 가장 확실하고 강력한 정답 이름 그대로 가능한 모든 경우의 수를 하나도 빠짐없이 다 확인해서 정답을 찾아내는 방법의 알고리즘이다.보통 for나 while 반복문, 재귀함수를 사용하여 구현한다.예시: 4자리 자물쇠 비밀번호를 0000 부터 9999까지 모든 경우의 수를 다 대입해보는 것.장점: 정답이 존재한다면 100% 확률로 반드시 찾는다.단점: 데이터가 많으면 시간이 매우 오래 걸린다. 2. 브루트 포스를 사용하는 이유사람이 직접 100만 번의 연산을 하려면 며칠이 걸리지만, 컴퓨터는 1초에 약 1억번의 연산을 처리할 수 있다.즉, 경우의 수가 1억 번 이하라면 브루트 포스를 사용해서 처리하는 것이 더 효율적일 수 있다.그렇기에 코딩테스트..
순서단원명 (Topic)중요도핵심 키워드0시간복잡도 & 기본기★★★★★Big-O, 입출력 속도, 재귀함수 이해1기본 자료구조 (선형)★★★★★배열, 연결리스트, 스택(Stack), 큐(Queue)2완전탐색 & 정렬★★★★☆Brute Force, 구현, 버블/병합/퀵 정렬3탐색 (DFS/BFS)★★★★★그래프 탐색, 미로 찾기, 네트워크4탐색 효율화 (비선형)★★★★☆해시(Hash), 이진 탐색, 투 포인터5탐욕법 (Greedy)★★★☆☆최적 부분 구조, 회의실 배정6동적계획법 (DP)★★★★☆메모이제이션, 점화식, 배낭 문제7고급 그래프★★☆☆☆다익스트라(Dijkstra), MST, 위상 정렬 Step 0. 시간복잡도 & 언어 기본 (Base)왜 가장 먼저인가?코딩테스트의 채점 기준은 "정답인가?"와 "..
먼저, 탐색을 하기 위해서는 지도(Graph)가 필요하다.1. 그래프(Graph)란?점(Node / Vertex): 도시, 사람, 데이터.선(Edge): 도로, 친구 관계, 연결 선. 컴퓨터에게 이 지도를 알려주는 방법은 딱 2가지가 존재한다. 코딩테스트에 있어서는 2번(리스트) 방식을 많이 사용한다. 1.1. 2차원 배열(Adjacency Matrix)방식: 엑셀 표처럼 모든 연결 관계를 1(연결됨)과 0(안됨)으로 표시하는 방법.장점: graph[1][2]가 연결됐는지에 대한 확인이 빠르다.단점: 점이 10,000개라면 표가 너무 커져서 메모리가 터진다. 1.2. 연결 리스트(Adjacency List)방식: 각 점마다 자신과 연결된 애들만 나열한다.장점: 필요한 것만 저장해서 메모리를 절약할 수 있..
먼저, 탐색을 하기 위해서는 지도(Graph)가 필요하다. 1. 그래프(Graph)란?점(Node / Vertex): 도시, 사람, 데이터.선(Edge): 도로, 친구 관계, 연결 선.컴퓨터에게 이 지도를 알려주는 방법은 딱 2가지가 존재한다. 코딩테스트에 있어서는 2번(리스트) 방식을 많이 사용한다. 1.1. 2차원 배열(Adjacency Matrix)방식: 엑셀 표처럼 모든 연결 관계를 1(연결됨)과 0(안됨)으로 표시하는 방법.장점: graph[1][2]가 연결됐는지에 대한 확인이 빠르다.단점: 점이 10,000개라면 표가 너무 커져서 메모리가 터진다. 1.2. 연결 리스트(Adjacency List)방식: 각 점마다 자신과 연결된 애들만 나열한다.장점: 필요한 것만 저장해서 메모리를 절약할 수 있..
1. 우선 순위 큐 개념 파악일반 큐 : FIFO (먼저 들어온 순서대로 먼저 나간다.)우선순위 큐 : 늦게왔어도 우선 순위가 높다면 먼저 나간다.즉, 들어간 순서와 상관없이 우선순위가 높은 데이터가 가장 먼저 나온다. 2. 힙(Heap)이란?우선순위 큐를 구현하는데에 있어서 가장 효율적인 자료구조가 바로 힙이다. 생긴 건 트리(Tree)처럼 생겼는데, 반만 정렬된 상태이다.모양: 트리(Tree)구조. (부모-자식 관계가 있는 구조)특징최소 힙(Min Heap): 제일 작은 숫자가 항상 맨 꼭대기(Root)에 온다. (자바 기본값)최대 힙(Max Heap): 제일 큰 숫자가 항상 맨 꼭대기(Root)에 온다.핵심 원리: 데이터가 들어오거나 나갈 때, 자동으로 대 소를 비교해서 최소값 또는 최대값을 맨 위..
1. 순회란?리스트는 그냥 단순 반복문으로 순회를 하면 끝이지만, 트리는 갈림길(왼쪽/오른쪽)이 있어서, "어떤 순서로 방문할지" 규칙을 정해야 한다. 가장 대표적인 3가지 방법이 존재한다. (루트, 왼쪽, 오른쪽을 언제 방문하는지에 대한 차이) 전위 순회(Pre-order)설명: Root를 먼저 처리하고 자식들에게 간다.순서: Root → Left → Right용도: 트리를 복사할 때 사용한다. (부모를 먼저 만들어야 자식을 붙일 수 있기 때문이다. 쉽게 설명하자면 상위 폴더를 지정해서 그 안에 폴더를 생성할 때처럼..)중위 순회(In-order) (중요함)설명: 왼쪽부터 오른쪽으로 간다.순서: Left → Root → Right용도: 정렬된 순서로 데이터를 뽑을 때 사용된다. (이진 탐색 트리에서 사..
