💡깊이 우선 탐색 (DFS) 그래프의 위에서 아래로 가장 깊은 곳을 방문하는 탐색법 한 방향으로 갈 수 있는데까지 가다가 길이 없으면 다시 돌아와 갈 수 있는데까지 가는 방법을 반복 어떤 노드를 방문 했었는지 검사 필요 스택 이나 재귀호출 방식을 사용해 구현 ✔️ 입력값 저장 인접리스트(링크드 리스트) 사용 인접 행렬 사용(2차원 행렬 사용) 큐 사용 1. 각 정점에 연결된 노드를 2차원 배열에 넣어준다. (양방향) ex. 1-2 이면 정점1에는 2를, 정점2에는 1을 넣어준다. 2. 만약 정점을 작은 순으로 탐색하고자 하면 오름차순으로 정렬해준다. 3. 탐색 시작 정점부터 탐색해 나가는데 시작 정점 배열의 size() 만큼 반복문을 돌린다. 4. 한 정점을 탐색한 후 해당 정점에 인접한 방문하지 않은 ..
💡Floyd - Warshall - 모든 노드 ~ 모든 노드 사이의 최단거리를 구하기 위해 사용하는 알고리즘 (다익스트라 알고리즘: 한 노드~ 모든 다른 노드 사이의 최단거리 구함) - D(a,b) = min(D(a,b), D(a,k)+D(k,b)) - step1. 어떤 경유지도 거치지 않고 출반~도착 최단거리 기본 테이블에서 시작 step2. 각 출발~도착 경로에서 다른 노드(경유지)를 들른다고 생각하고 최단거리 구함 만약 경유지를 들르지 않는 것이 더 최단거리면 D(a,b)를 선택해 그대로 유지, 경유지를 들리는 것이 더 최단거리면 D(a,k)+D(k,b) 선택 => 경유지(k) = 1부터 시작해서 4까지 업데이트 step3. 가장 마지막 테이블이 최종 결과 (배열에도 최종 결과가 저장) void f..
💡동적 계획(Dynamic Programming) - 작은 문제부터 해결하여 그 결과를 큰 문제를 푸는데 사용하는 bottom-top 방식의 알고리즘 (분할정복과 반대) 💡이항계수 ✔️ 재귀호출을 사용한 하향식 접근 방식 int bin(int n,k){ if(k==0||k==n) return 1; else bin(n-1,k) + bin(n-1,k-1) - 항의 개수 = 2(n, k) - 1 - bin(n-1,k) 값 => bin(n-2,k-1), bin(n-2, k) 필요 (재귀호출에 의해서) bin(n-1,k-1)값 => bin(n-2,k-1), bin(n-2,k-2)필요 - 위에서 아래로 , 큰문제를 작은문제로 분할하여 계산하는데 위 예시처럼 분할되어 독립적으로 수행되는 특성 때문에 같은 계산을 여러..
💡그래프 - 경로 : 두 노드 사이에 이음선으로 연결된 노드의 나열 - 연결 그래프 - 부분그래프 - 방향성/비방향성 그래프 : - 경로 : - 순환경로 : 💡신장트리 - 연결된 비방향성 그래프에서 순환경로가 없어지도록 이음선을 제거해 구성한 그래프 - 모든 정점을 다 포함하되 순환경로가 존재하지 않는 연결 그래프 💡MST (최소비용 신장 트리) - 신장 트리가 되는 부분그래프 중에서 가중치의 합이 최소가 되는 그래프 - 순환경로X ex) 도로건설, 통신, 배관 - MST를 찾기 위한 알고리즘으로는 무작정 알고리즘, 탐욕적 알고리즘, 프림 알고리즘, 크루스칼 알고리즘 등 존재 무작정 알고리즘 : 모든 경우 다 고려 탐욕적 알고리즘 : 적절한 최적해 선정절차 따라 하나의 이음선 선정(선정) -> 순환경로 ..
