알고리즘/개념4 5주차 알고리즘 - 최소신장트리 (MST) - MST : Minimum Spanning Tree - 그래프 상의 모든 노드들을 최소 비용으로 연결하는 방법 : 크루스칼, 프림 노드와 간선정보가 주어졌을 때 최소가 되게 노드들을 한 번만 연결하는 방법 MST 관련 문제들은 내부 알고리즘은 동일. 문제 파악한 후 MST 형태인 것만 떠올면 풀 수 있음 - 크루스칼 (Kruskal) 알고리즘 · 간선 중 최소 값을 가진 간선부터 연결 · 사이클 발생 시 다른 간선 선택 · 주로 간선 수가 적을 때 사용 · O(Elog E) - 간선 정보들을 오름차순 Sorting 작업 필요 - 사이클 발생 체크하는 Union-Find 테이블 초기 : 각 자기 자신으로 초기화 1. 처음에 가장 작은 가중치인 1을 선택해서 1 - 3 노드를 연결하면 3의 부모노드는 연결.. 2023. 8. 10. 5주차 알고리즘 복습 - 다이나믹 프로그래밍 다이나믹 프로그래밍 (Dynamic Programming) DP , 동적 계획법 - 큰 문제를 부분 문제로 나눈 후 답을 찾아가는 과정에서, 계산된 결과를 기록하고 재활용하여 문제의 답을 구함 여기까지는 분할정복인데 여기서 차이가 있음. - 중간 계산 결과를 기록하기 위한 메모리가 필요 - 한 번 계산한 부분을 다시 계산하지 않아 속도가 빠름 * 다른 알고리즘과의 차이점 - 분할정복과의 차이점 : 분할정복은 부분문제가 중복되지 않음 : DP는 부분문제가 중복되어 재활용에 사용 - 그리디 알고리즘과의 차이점 : 그리디는 순간의 최선을 구하는 방식 (최적해) : DP는 모든 방법을 확인 후 최적해 구하는 방식 -> 그 과정에서 중복된 연산을 하지 않음 * 그리디가 DP보다 빠름 (당연함) 반드시 최적해를 구.. 2023. 8. 6. 5주차 알고리즘 복습 - 그리디 매순간 현재 기준으로 최선의 답을 선택해 나가는 기법 - 빠르게 근사치를 계산할 수 있다. - 결과적으로는 최적해가 아닐 수 있다. * 정렬 안 된 상태로 그리디 사용 불가 그리디 알고리즘 적용 조건 : 이 두 가지 만족시 적용 가능 * 최적부분 구조 (Optimal substructure) : 전체 문제의 최적해는 부분 문제의 최적해로 이어짐. * 탐욕적 선택 특성 (Greedy Choice Property) 지금 선택이 다음 선택에 영향을 주지 않음. -> 현재 마주하는 문제가 미래에 영향을 받아 최적이 아니게 바뀌지 않는다 ! 이 개념이 좀 헷갈렸는데 500 100 50 10 같은 완벽하게 그리디 적용할 수 있는 것도 내가 지금 500원을 고르냐 안 고르냐에 따라서 100원의 선택값이 달라지니까 영.. 2023. 8. 6. 5주차 알고리즘 복습 - 투 포인터 배열에서 두 개의 포인터를 사용하여 원하는 결과를 얻는 방법 - 두 개의 포인터 배치 방법 : 같은 방향에서 시작 - 첫 번 째 원소에 포인터 둘 다 배치 : 서로 다른 방향에서 시작 - 첫 번째 원소와 마지막 원소에 배치 다중 for문의 복잡도를 좀 더 선형적으로 풀 수 있다. O(n^2) -> O(n) p1, p2가 자료 n개까지 중첩이 아니라 +로 연산이 됨. 대표문제 : 특정한 합을 가지는 부분 연속 수열 찾기 Main ) 특정한 수열이 주어졌을 때 연속된 부분 수열의 합이 target이 되는 구간의 좌표 시작, 끝 값 찾기 public static int[] twoPointers(int arr[], int target) { int result[] = {-1, -1}; int p1 = 0; int.. 2023. 8. 6. 이전 1 다음 728x90
