A-star 알고리즘이란?A* 알고리즘은 최단 경로 탐색 알고리즘으로, 다익스트라(Dijkstra)의 장점과 휴리스틱(Heuristic)을 결합한 방식이다.다익스트라: 실제로 이동한 비용(g(n))을 최소화A-star: g(n) + 미래에 걸릴 비용 추정(h(n)) = f(n)을 최소화즉, $f(n)=g(n)+h(n)$ 다음과 같은 식을 가지게 된다.g(n): 시작점에서 현재까지 온 실제 비용h(n): 현재 위치에서 목표까지의 추정 비용 (휴리스틱)A-star 알고리즘을 사용하는 이유다익스트라는 모든 방향을 탐색하기 때문에 비효율적일 수 도 있다.A-star 는 목표 지향적으로 움직여 불필요한 탐색을 줄이고, 빠르게 경로를 찾아냅니다.휴리스틱 함수란?A*의 핵심은 h(n) 을 어떻게 정의하느냐에 달라진다..

1. 다익스트라 알고리즘이란?최단 경로(Shortest Path) 알고리즘 중 하나.특정 시작 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘이다.음수 가중치가 없을 때만 사용 가능.2. 원리 (Greedy + Priority Queue)매번 가장 가까운 정점을 선택해 확정(visited)한다.해당 정점을 거쳐 다른 정점으로 가는 경로를 최단 거리로 갱신한다.이를 반복하면서 모든 정점의 최단 거리를 구한다.핵심 아이디어:"가장 가까운 정점부터 처리하면, 그 이후에는 더 짧은 경로가 나올 수 없다."3. 알고리즘 과정시작 정점의 거리를 0으로, 나머지는 ∞(무한대)로 초기화.방문하지 않은 정점 중 가장 거리가 짧은 정점을 선택.선택한 정점을 거쳐 갈 수 있는 이웃 정점들의 거리를 갱신.모든 정점..

0-1 knapsack 문제란 배낭에 담을 수 있는 무게에 서로 무게가 다른 값어치의 물건을 담는다고 할 때 가방에 담을 수 있는 최대 값를 계산하는 방법이다.knapsack 문제는 Fractional knapsack 과 0-1 knapsack 두개 가 있는데Fractional knapsack은 쪼개서 일부 선택 가능한 knapsack 문제이고0-1 knapsack : 아이템을 0개 또는 1개만 선택할 수 있는 경우이다.0-1 knapsack 관련 문제를 푸는 이유이 중에서 DP에 대한 개념을 더 잘 이해하기 위해 0-1 knapsack을 고르게 되었다.0-1 knapsack을 그리디로 풀어서는 안되는 이유가방의 무게가 50일때 물건들이 다음과 같은경value : 60 , 100 , 120weight :..

투포인터 알고리즘 이란?배열이나 리스트에서 두 개의 포인터 인덱스를 이동시키면서 문제를 해결하는 방식보통 정렬된 배열에서 구간 합, 조건 만족 여부, 두 원소의 조합 등 을 사용할 때 사용시간 복잡도O(N)기본 원리 예시int[] arr = {1, 2, 4, 7, 11, 15};int target = 15;int left = 0, right = arr.length - 1;while (left 마무리 요약투 포인터 알고리즘은 배열 문제를 풀 때 주로 사용브루트포스 방식을 O(N) ~ O(N log N) 으로 줄여주기 때문에 효율적

플로이드 워셜 알고리즘이란?가중치가 있는 방향/무방향 그래프에서 모든 정점 쌍 사이의 최단 거리를 한번에 구하는 DP 기반 알고리즘음수 가중치 간선은 허용하지만, 음수 사이클이 있으면 최단거리가 정의되지 않는다.시간 공간 복잡도시간 : O(N^3)공간 : O(N^2)핵심 아이디어dist[i][j]=min(dist[i][j], dist[i][k]+dist[k][j]) 해석 : i → j 까지 가는 가장 짧은 값을 출력i → k → j 가 가능하다면 해당 값으로 값을 대체❗반복문의 순서가 중요하다 k → i → j중간 정점으로 1..k만 허용 하는 부분 문제를 누적해야 하므로 이 순서가 무조건 보장 되어야한다.사용 판단 기준N이 중간 규모 대략 N≤500 이고 모든 쌍의 거리 도달성을 한번에 알고 싶을 때,..

LIS (Longest Increasing Subsequence)최장 증가 부분 수열→ 어떤 수열이 왼쪽에서 오른쪽으로 나열되어 있으면 그 배열 순서를 유지하면서 크기가 점진적으로 커지는 가장 긴 부분 수열을 추출 하는 문제1. LIS란?주어진 순열에서 오름차순 을 유지하는 부분 수열 중 가장 긴 수열의 길이를 구하는 알고리즘ex) 수열 = [10, 20, 10 ,30 ,20 ,50] 이 주어졌을때가능한 증가 부분 수열은[10, 20, 30, 50] → 길이가 4[10, 20, 50] → 길이가 3[10, 30, 50] → 길이가 3등등이 생성된다. 이럴 경우 정답이 42. 대표적인 풀이방법풀이방법1 : DP풀이방법2 : 이진 검색 활용DP O(N^2) 풀이 - 기초적인 방법아이디어 : dp[i] = i..