개념 동적 프로그래밍(DP)은 복잡한 문제를 단순한 하위 문제로 나누어 푸는 방법으로 같은 입력값에 대한 반복되는 호출을 하는 솔루션을 만났을 때 사용합니다. 주어진 문제를 부분 문제로 나누어 각 부분 문제의 답을 계산 후 결과값을 이용하면 원래 문제의 답을 효율적으로 구할 수 있습니다. 💡 다이나믹 프로그래밍은 하나의 문제를 단 한 번만 풀도록 하는 알고리즘으로 구체적인 알고리즘이라긴 보단, 문제 해결 패러다임에 가깝습니다. [ 🤔 탐욕 알고리즘과 다른점 ] 둘 다 최적의 값을 찾는다는 점에서 비슷하지만, 다른 방법으로 찾습니다. 탐욕 알고리즘 전체의 값을 찾기 위해 지역적으로 탐욕적인 선택을 찾음 → 비용이 많이 들며, 전역적으로는 최적의 알고리즘을 보장하지 않을 수 있음 동적 프로그래밍 전체의 값을..
개념 플로이드-워셜 알고리즘은 가중치 그래프에서 모든 최단 경로를 구하는 알고리즘입니다. 한 번 실행하여 모든 노드 간 최단 경로를 구하는데 이때, 최단 경로를 찾기 위해 DP(동적 프로그래밍) 방식을 사용합니다. [ 🤔 다익스트라와의 차이점? ] 다익스트라 : 하나의 정점에서 다른 모든 정점까지의 최단 거리 시작점으로 부터 나머지 정점까지 최단거리 구할 때 사용 음의 가중치 간선이 있으면 사용하지 못 함 프로이드-워셜 : 한 번 실행해 모든 노드 간 최단 경로 각 정점간 최단 경로 구할 때 사용 음의 가중치 간선에서 사용 가능 ✔ 시작점으로부터 각 정점까지 최단 거리만 구할 때 → 다익스트라 ✔ 간결한 소스코드, 간선 수가 많을 떄 → 플로이드-워셜 [ 알고리즘 응용 ] 최단 경로 찾는 방향 그래프 실..
개념 이진 검색 알고리즘은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘입니다. 장점 검색이 반복될 때마다 목표값을 찾을 확률이 두배가 되므로 속도가 빠릅니다. 단점 검색 원리상(중간 값을 찾아야 하기에) 정렬된 리스트에만 사용할 수 있습니다. 알고리즘 과정 배열의 중간 값을 임의의 값으로 선택 중앙 값과 찾고자 하는 값의 크고 작음을 비교 중앙 값 = 찾는 값 : 값을 찾았으니 검색 종료 중앙값 > 찾는 값 : 중앙값 기준 배열의 왼쪽 구간을 대상으로 탐색 중앙값 < 찾는 값 : 중앙값 기준 배열의 오른쪽 구간을 대상으로 탐색 값을 찾거나 간격이 0이 될때까지 반복 리스트에서 검색할 값과 같은 요소 발견한 경우(검색 성공) 검색할 범위가 더 이상 없을 경우(검색 실패) [ 0. 선행조..
