개발기록

https://m.blog.naver.com/ndb796/221234424646 23. 다익스트라(Dijkstra) 알고리즘  다익스트라(Dijkstra) 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로(Shortest P...blog.naver.com  https://m.blog.naver.com/ndb796/221234427842?recommendTrackingCode=2 24. 플로이드 와샬(Floyd Warshall) 알고리즘  지난 시간에는 다익스트라(Dijkstra) 알고리즘에 대해 학습했습니다. 다익스트라 알고리즘은 하나...blog.naver.com

*️⃣  개념Greedy: 탐욕스러운, 욕심 많은그리디 알고리즘은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다.항상 최적의 값을 보장하는것이 아니라 최적의 값의 ‘근사한 값’을 목표  *️⃣  그리디 알고리즘 적용 조건1. 탐욕적 선택 속성(Greedy Choice Property): 앞의 선택이 이후의 선택에 영향을 주지 않는다.2. 최적 부분 구조(Optimal Substructure): 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.  *️⃣  그리디 ..

*️⃣ 개념정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법배열 내부의 데이터가 오름차순 또는 내림차순으로 정렬되어 있어야만 사용할 수 있는 알고리즘이다. *️⃣ 탐색 과정변수 3개(low, high, mid)를 사용하여 탐색한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색의 과정이다.  *️⃣ 응용 문제 풀이백준 1654  https://www.acmicpc.net/problem/1654const fs = require('fs');const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');function solution(arr) { const..

https://www.acmicpc.net/problem/2098 ✦ 문제 이해[가장 적은 비용을 들여 도시를 모두 순회하기]1번부터 N번까지의 도시가 있다.도시들 사이에는 길이 있고 길이 없을 수도 있다.외판원은 1번 도시에서 시작해서 모든 도시를 순회한 뒤, 다시 처음 도시로 돌아온다.단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외)이때, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다. [각 도시간 이동 비용 행렬]각 도시간에 이동하는데 드는 비용은 행렬 W[i][j]형태로 주어진다.W[i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다.W[i][i]는 항상 0이다. 경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며..

*️⃣ 개념복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법큰 문제를 작은 문제로 나눈 뒤, 기억하여 푸는 기법(시간 복잡도↓ 공간복잡도↑)1. 알고리즘 기법문제를 해결하기 위해 사용되는 절차적인 방법 또는 계획(EX, 정렬 알고리즘, 검색 알고리즘, 그래프 탐색 알고리즘 등)2. 알고리즘 설계 기법문제 해결을 위해 알고리즘을 설계하는 방법이나 접근 방식. 설계 기법은 알고리즘을 개발하고 구현하는 데 사용되는 전략이나 원칙들을 포함한다.(EX, 분할 정복, 동적 계획법, 탐욕적 알고리즘, 백트래킹 등) *️⃣ DP과 재귀적 호출의 차이점1. 하향식(Top-down) vs 상향식(Bottom-up) 접근재귀적 호출은 주로 하향식(top-down) 접근 방식을 사용한다. 큰 문제를 작은..