본문 바로가기

Algorithm

 (13)
[Algorithm] TSP(Traveling Salesman problem, 외판원 순회 문제) 📌 TSP(외판원 순회 문제)란?N개의 도시가 있고, 어떤 도시에서 출발해 모든 도시를 한 번씩만 방문한 뒤, 다시 출발 도시로 돌아오는 최소 비용 경로를 찾는 문제조건:모든 도시는 정확히 한 번 방문마지막에 출발 도시로 복귀경로의 총 비용(또는 거리)을 최소화 ⚠️ 단순 접근: 순열 완전탐색모든 방문 순서를 나열해서 최소 비용 경로를 찾는 방법도시 수가 N일 때 가능한 경로 개수: (N-1)! (출발 도시 고정)문제점: N이 조금만 커져도 경우의 수 폭발 (N=10 → 9! = 362,880) ✅ 효율적인 접근: DP(Top-Down) + 비트마스킹핵심 아이디어: "지금까지 방문한 도시 집합"과 "현재 도시"만 알면, 남은 최소 비용을 계산 가능dp[cur][visited] = 현재 cur 도시에 있..
[Algorithm] 유니온 파인드 (분리 집합) 🧱 유니온 파인드(Union-Find)란? 서로 연결되어 있는 것들을 하나의 그룹(집합)으로 묶어서 관리하는 방식 A와 B가 연결됨 → 한 그룹으로 묶음B와 C가 연결됨 → A, B, C가 같은 그룹이 됨D는 따로 떨어져 있음 → D는 또 다른 그룹 🧠 왜 필요한가? 분리 집합(Disjoint Set)을 효율적으로 관리하는 자료구조로, "두 원소가 같은 그룹에 속해 있는지 확인"하고, "두 그룹을 합치는 연산"을 빠르게 처리하기 위해 사용된다. 서로 연결되어 있는지(예: 네트워크, 여행 가능 여부) 확인하는 문제에서 자주 등장연결 여부를 탐색하지 않고도 한 번의 Find로 판별 가능 ✅ 유니온 파인드의 핵심 기능 2가지find(x)x가 속한 집합의 대표(root)를 찾는다.이때, 경로 압축을 이용해 ..
[Algorithm] 누적합 구간의 합을 매번 단순하게 구하면 O(N × M)의 시간복잡도가 발생한다.이를 누적합(Prefix Sum) 배열을 활용하면 O(1)에 구간 합을 구할 수 있어 효율적인 처리가 가능하다. 🧩 누적합(Prefix Sum)이란?prefixSum[i]는 1번째 수부터 i번째 수까지의 총합이다.따라서, i번째 수부터 j번째 수까지의 합은 다음과 같이 계산된다.prefixSum[j] - prefixSum[i - 1] 예를 들어, [1, 3] 구간의 합은 prefixSum[3] - prefixSum[0]으로 계산된다. ⚠️ 주의사항: ArrayIndexOutOfBoundsException 방지 prefixSum[] 배열을 계산하기 위해서는 기존 배열 arr[]을 이용해 다음과 같이 계산해야 한다.prefixSum[..
[Algorithm] 플로이드 개념MST → 모든 노드를 잇는데 드는 최소 비용다익스트라 → 한 노드에서 다른 모든 노드까지 가는 최소 비용플로이드 → 모든 노드에서 다른 모든 노드까지 가는 최소 비용노드 j에서 노드 i로 가는 비용 배열 만들기 → 초기값: INF간선 값을 비용 배열에 반영모든 노드에 대해 해당 노드를 거쳐서 갈 때 비용이 작아지는 경우 값 갱신!거치는 노드, 시작 노드, 끝 노드 각각 V번 for문 돌기 때문에 시간복잡도는 O(V^3)연습 문제 - 백준 11404번 플로이드5141 2 21 3 31 4 11 5 102 4 23 4 13 5 14 5 33 5 103 1 81 4 25 1 73 4 25 2 4첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 ..
[Algorithm] 다익스트라 🧠 개념MST(최소 신장 트리): 모든 노드를 잇되 총 간선 비용이 최소인 트리 구조 생성 → 네트워크 전체를 연결할 때 유리다익스트라(Dijkstra): 한 노드에서 다른 모든 노드까지 가는 최소 비용을 구하는 알고리즘 → 단일 출발 최단 경로 다익스트라는 가중치가 있는 방향 그래프에서도 사용 가능하며, 음수 가중치가 없는 경우에만 올바르게 작동한다. 💡 문제 파악 포인트 다음과 같은 문장을 보면 다익스트라임을 빠르게 판단해야 한다. "한 정점에서 모든 정점으로의 최단 거리""출발 노드 하나가 주어지고 모든 노드까지의 거리 구하기""방향 그래프, 가중치 있음, 음수 없음" 🧩 알고리즘 동작 방식 거리 배열을 모두 무한대로 초기화 (distance[] = Integer.MAX_VALUE)시작 노드의..
[Algorithm] MST 개념MST (Minimum Spanning Tree)Spanning Tree: 모든 노드가 연결된 트리MST: 최소 비용으로 모든 노드가 연결된 트리 → 모든 노드를 잇는데 최소 비용이 뭐야?!푸는 방법: Kruskal, PrimKruskal: 모든 간선 중 작은 것부터 연결Prim: 현재 연결된 트리에 이어진 간선 중 가장 작은 것을 추가예를 들어 다음과 같은 Spanning Tree가 있을 때,Kruskal: 간선 1 → 간선 2 → 간선 3 → 간선 4는 이미 연결되어 있으므로 pass → 간선 5 → 간선 6은 이미 연결되어 있으므로 passPrim: 노드 1에 연결된 간선 중 가장 작은 간선 1 추가 → 현재 트리에 연결된 간선 2, 3 중 가장 작은 간선 2 연결 → 간선 3, 4, 5 중 가..
[Algorithm] DP 개념DP(Dynamic Programming)이전의 값을 재활용하는 방법예시) 1 ~ 10 숫자 중, 각 숫자와 이전 값들을 더한 값 구하기1은 1, 2는 1+2=3, 3은 1+2+3=6 ...이런 경우, 이전 값을 재활용하여 시간을 단축시킬 수 있다.이중 for문으로 구현 → O(N^2)DP는 for문 한 개 → O(N)DP에서 가장 중요한 것은 바로 "이전 값을 활용하는 식" 점화식! (예를 들면, Ai = Ai-1 + Ai-2)점화식을 미리 세우고 코드를 짜는 것이 중요하다.어떻게 해야 할지 막막하지만 처음에는 그냥 해보자! 그러면 규칙이 자연스럽게 보일 것이다.연습 문제 - 백준 11726번9첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)55첫째 줄에 2×n 크기의 직사각형을 채우는 방법의..
[Algorithm] 그리디 개념"때로는 당장 눈앞의 최선이 최고의 결과를 가져온다."현재 차례의 최고의 답을 찾는 문제그런데 현재 최고의 답이 나중에 최선이 아닐 수도 있다.따라서, 현재 최고의 답이 나중에 최선이 되는 이유를 찾아야 한다. → 연습 중요!이유를 증명하기 어려우면 반례가 있는지 찾아본다.예를 들어, 1, 20, 30, 40원의 동전이 무한개 주어졌을 때 50원을 만드는 최소 동전의 개수를 구한다고 가정하자.큰 금액의 동전부터 차감하게 된다면 40, 1 * 10로, 총 11개가 필요하다.하지만, 최소 개수는 30, 20 총 2개이다.이런 식으로 반례가 있는지 찾아본다.연습 문제 - 백준 11047번10 4200151050100500100050001000050000 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10..
[Algorithm] 이진 탐색 (이분 탐색) 🧠 이진 탐색이란?정렬된 수열에서 원하는 값을 빠르게 찾기 위한 탐색 알고리즘이다.기본적으로 정렬의 성질(이전 값보다 이후 값이 크다)을 이용해 탐색 범위를 절반으로 줄이면서 탐색한다. ⏱️ 시간 복잡도는?기본 탐색: O(N)배열을 처음부터 끝까지 순차 탐색이진 탐색: O(log N)배열의 중앙값을 기준으로 절반씩 버리며 탐색 ✔️ 간단한 예시 [1, 2, 3, 4, 5]에서 5를 찾는다고 가정하자.기본 탐색:1 → 2 → 3 → 4 → 5 → 찾음이진 탐색:5는 중간값 3보다 큼 → 탐색 범위를 [4, 5]로 줄임중간값 4보다 큼 → 탐색 범위를 [5]로 줄임 → 찾음 📌 핵심 코드int binarySearch(int[] arr, int target) { int left = 0; int ..
[Algorithm] 투 포인터 개념각 원소마다 모든 값을 순회해야 할 때(O(N^2)) "연속하다"는 특성을 이용해서 처리하는 방법 → 시간복잡도: O(N)두개의 포인터(커서)가 움직이면서 계산처음부터 생각하기는 어려우니 쉬운 방법부터 생각해보자. (완전 탐색 시도 → 시간 초과.. → 연속한가? → 투포인터!)연습 문제 - 백준 2559번10 23 -2 -4 -9 0 3 7 13 8 -3 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 위한 연속적인 날짜의 수이다. K는 1과 N 사이의 정수이다. 둘째 줄에는 매일 측정한 온도를 나타내는 N개의 정수가 빈칸을 사이에 두고..
[Algorithm] 시뮬레이션 개념각 조건에 맞는 상황을 구현하는 문제 (지도, 배열에서 이동하면서 탐험하는 문제)별도의 알고리즘 없이 풀 수 있으나, 구현력이 중요하다.매 시험마다 1문제 이상 무조건 출제된다.연습 문제 - 백준 14503번3 31 1 01 1 11 0 11 1 1 첫째 줄에 지도의 크기(N * M)가 주어지고, 둘째 줄에 로봇 청소기의 좌표 (r, c)와 바라보는 방향 d가 입력된다.(d가 0인 경우 북쪽, 1인 경우 동쪽, 2인 경우 남쪽, 3인 경우 서쪽을 바라보고 있는 것이다.)지도에서 0은 청소되지 않은 칸, 1은 벽이다. 이때 로봇 청소기는 다음과 같이 작동한다.현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.현재 칸의 주변 4칸 중 청소되지 않은 빈칸이 없는 경우,바라보는 방향을 유지한 채로 한..
[Algorithm] 백트래킹 개념모든 경우의 수를 확인해야 할 때 (ex. 순열)for문으로는 확인이 불가한 경우 (depth가 달라질 때)순열을 예로 들어보자.3개의 수 중에서 2개를 뽑아야 한다면 이중 for문으로 풀 수 있다.하지만 뽑는 개수가 정해지지 않은 경우(M, N) for문의 깊이가 달라져야 하기 때문에 for문으로는 풀 수 없다.이럴 때 사용하는 것이 바로 백트래킹이다.연습 문제 - 백준 15649번4 2 다음과 같이 자연수 N과 M이 입력 들어왔을 때, 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 구해야 한다.1 21 31 42 12 32 43 13 23 44 14 24 3 1. 아이디어1부터 N 중에 하나를 선택한 뒤,다음 1부터 N 중에 하나를 선택할 때, 이미 선택한 값이 아닌 경우 선택M개를 ..
[Algorithm] BFS, DFS BFS와 DFSBFS(Breadth First Search, 너비 우선 탐색)DFS(Depth First Search, 깊이 우선 탐색)BFS, DFS는 그래프 탐색의 한 방법이다.그래프 탐색은 어떤 것들이 연속해서 이어져 있을 때 모두 확인하는 방법을 말한다.그래프는 Vertex(어떤 것)와 Edge(이어져 있는 것)로 이루어져 있다.BFS는 자기 자식들을 우선으로 탐색한다.그 뒤 자식의 자식들을 탐색하게 된다.DFS는 자기 자식의 자식을 우선으로 탐색한다.자식이 더 이상 없다면 부모로 올라와서 다음 자식의 자식을 탐색하게 된다.BFS - 아이디어한 Vertex에 연결된 Vertex를 찾는다.찾은 Vertex를 큐에 저장한다.큐의 가장 첫 Vertex를 뽑아서 반복한다.BFS - 시간복잡도O(V+E)B..

티스토리툴바