1. 그리디(탐욕) 알고리즘이란?결정을 내려야 할 때마다 지금 당장 최선인 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다.나중의 결과는 고려하지 않고, 오로지 현재 시점에서의 지역적인 최적해를 찾아가는 것이 특징. 2. 그리디 알고리즘의 핵심 이론해 선택: 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다.적절성 검사: 현재 선택한 해가 전체 문제의 제약 조건에서 벗어나지 않는지 검사한다.해 검사: 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 그렇지 않다면 1번으로 돌아간다. 3. 대표적인 예시동전 거스름돈 문제: 동전 개수를 최소한으로하여 거스름돈을 주는 문제.예를 들어, 1260원을 거슬러 줘야 하고 동전 단위가 500원, 100원, 50원, 10원이라면..
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)에 온다.핵심 원리: 데이터가 들어오거나 나갈 때, 자동으로 대 소를 비교해서 최소값 또는 최대값을 맨 위..
