최소 신장 트리(Minimum Spanning Tree) 란?그래프에서 모든 정점에 대해 최소한의 연결만을 남긴 그래프이다. 즉, 간선의 가중치 합이 가장 작은 트리를 뜻한다.사이클이 존재하지 않아야 한다.  최소 신장 트리를 찾는 알고리즘으로는 다음과 같이 두 가지가 있다.1. Prim 알고리즘2. Kruskal 알고리즘  Prim 알고리즘프림 알고리즘은 아래의 방법을 반복한다. 단, 아래 과정을 반복하는 과정에서 사이클이 형성되지 않아야 한다.1. 임의의 정점을 선택하여 하나의 정점을 가지는 최초의 트리를 구성한다. 2. 트리에 포함된 정점과 트리에 포함되지 않은 정점 간의 간선 중, 가장 가중치가 적은 간선을 선택하여 트리에 추가한다.3. 모든 정점이 트리에 포함될 때까지 2를 반복한다. 예시1) ..

DFS 알고리즘이란?DFS(Depth-First Search)란 깊이 우선 탐색이라고도 불리며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.  DFS 알고리즘 작동 과정1. 정점 i를 방문한다.2. 정점 i에 인접한 정점 중에서 아직 방문하지 않은 정점이 있으면, 이 정점들을 모두 스택에 저장한다.3. 스택에서 정점을 삭제하여 새로운 i를 설정하고, 단계 (1)을 수행한다.4. 스택이 공백이 되면 연산을 종료한다 배열 visited[n]을 이용하여, 정점의 방문 여부를 표시한다- visited[i] = True : 방문하였음- visited[i] = False: 방문하지 않음  BFS 알고리즘 작동 예시 0. visited배열 전부 False로 초기화 1. stack에 시작 원소 삽입    2..

BFS 알고리즘이란?BFS(Breadth-First Search)란 너비 우선 탐색이라고도 불리며 그래프에서 시작 노드에 인접한 노드부터 탐색하는 알고리즘이다. 주로 그래프에서 모든 간선의 비용이 동일한 조건에서 최단 거리를 구하는 문제를 효과적으로 해결할 수 있다. BFS 알고리즘 작동 과정1. 정점 i를 방문한다.2. 정점 i에 인접한 정점 중에서 아직 방문하지 않은 정점이 있으면, 이 정점들을 모두 큐에 저장한다.3. 큐에서 정점을 삭제하여 새로운 i를 설정하고, 단계 (1)을 수행한다.4. 큐가 공백이 되면 연산을 종료한다 배열 visited[n]을 이용하여, 정점의 방문 여부를 표시한다- visited[i] = True : 방문하였음- visited[i] = False: 방문하지 않음 그림 1 ..

그래프그래프는 원소를 정점과 간선으로 표현한 것이다. 두 정점이 간선으로 연결되어 있으면 인접하다고 한다. 그래프는 크게 2가지로 표현할 수 있다.  1. 인접 행렬(Adjacency Matrix)인접 행렬이란, 그래프의 연결 관계를 행렬로 표현하여 이차원 배열로 나타내는 방식이다. adg[i][j] = 1 (노드 i에서 노드 j로 가는 간선이 존재할 경우)adg[i][j] = 0 (노드 i에서 노드 j로 가는 간선이 존재하지 않을 경우)  1. 무향그래프  만약 표현하고자 하는 그래프가 방향이 없는 무향 그래프일 경우, 노드 i에서 노드 j로 가는 길이 존재하면, 노드 j에서 노드 i로 가는 길 또한 존재한다. 이러한 특성으로 인해 인접 행렬을 구현하게 되면, 대각 성분을 기준으로 대칭인 성질을 가지게..

Knapsack Problem배낭 문제,Knapsack Problem은 다이나믹 프로그래밍에서 매우 유명한 문제이다. 용량이 K인 배낭에 넣을 수 있는 N개의 물건에 대해 각 물건의 무게 weight와 가치 value가 주어질 때, 배낭에 최대한 가치가 높은 물건들을 담을 수 있는 조합을 찾는 문제이다. 냅색 알고리즘을 나누는 기준담을 수 있는 물건이 나뉠 수 있는가, 없는가? 담을 수 있는 물건이 나누어 질 때 분할가능 배낭문제(Fractional Knapsack Problem) - Greedy 담을 수 있는 물건이 나누어질 수 없을 때 0-1 배낭 문제(0-1 Knapsack Problem) - Dynamic Programming 문제 해결 전략 1. 모든 경우를 탐색하기(Brute Force)N개의..

연쇄 행렬 곱셈i × j 행렬과 j × k행렬을 곱하기 위해서는 i × j × k번 만큼의 곱셈이 필요하다.여러 행렬을 곱할 때, 어떠한 행렬 쌍을 먼저 곱하는지에 따라 연산 횟수가 달라진다.   연쇄 행렬 곱셈 동적 계획식 설계 전략재귀 관계식을 이용하여, 이전 단계의 계산을 이후 단계의 계산에 이용할 수 있다.i와 j사이에 있는 특정 값인 k를 사용하여 정답을 찾아간다연쇄 행렬 곱셈에서는 M[i,j] = min{ M[i,k] + M[k+1][j] + d(i-1)d(k)d(j)} 라는 식으로 문제를 해결하는데,i = j이면 이 자체로 하나의 행렬이므로 행렬곱은 0이고,i  ex) i=i , j=2 일 때 -> k=1 (k는 하나) ex) i=1,j=3 -> k=1,k=2 (k는 두 개)-> 이 때, k..

문제https://level.goorm.io/exam/49101/%ED%99%98%EA%B2%BD%EA%B3%BC-%EC%A5%90-%ED%81%AC%EA%B8%B0%EC%9D%98-%EC%83%81%EA%B4%80%EA%B4%80%EA%B3%84/quiz/1 구름LEVEL난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다.level.goorm.io 문제풀이어떤 정수 X에 대해서 쥐의 몸집 크기가 [X-2,X+2] 구간에 속하는 쥐가 가장 많을 때, 그 중 작은 X값이 대표값이 됩니다몸집이 최대 10만개인데, for문으로 x=1부터 시작해서, 쥐 리스트에 x일 때 범위의 값이 있는지 확인하는건 무조건 시간초과가 뜰 것이라고 생각 (x값 -> 몸집 유무 탐색)역으로, 쥐 리스트에 있는 몸..

문제어떤 쥐가 p[n][m]로 구성된 미로에 있을 때 왼쪽 아래 즉, p[0][0]에서 시작하여 출구가 있는 p[n-1][m-1]에 도달하려고 한다. 단, 이 쥐는 항상 오른쪽 또는 위쪽으로만 움직일 수 있으며 치즈를 최대한 많이 먹으면서 출구로 이동하여야 한다  풀이방법DP를 활용하여, 문제를 간단하게 풀 수 있다. 여기서 A[i][j]를 i행, j열까지 도달했을 때 먹을 수 있는 최대 치즈의 양이라고 정의하면, 다음과 같은 점화식을 사용하여 문제를 해결할 수 있다 A[i][j] = max(A[i][j-1], A[i-1][j]) + A[i][j]현재 위치에서 왼쪽 칸 또는 위쪽 칸 중에서 더 많은 치즈를 먹을 수 있는 경우를 선택하여 현재 칸까지의 최대 치즈 양을 계산이를 모든 칸에 대해 계산하면, 출..