개발기록

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) 접근 방식을 사용한다. 큰 문제를 작은..

🌲 트리의 개념트리는 노드로 이루어진 자료 구조이다.트리는 하나의 루트 노드를 갖는다.루트 노드는 0개 이상의 자식 노드를 갖고 있다.그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있다.노드(node)들과 노드들을 연결하는 간선(edge)들로 구성되어 있다.그래프의 한 종류로, 사이클이 없는 하나의 연결 그래프이다. 트리의 개념 자세히 알아보기 ➔ https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html 🌲 이진트리각 노드가 최대 2개의 자식을 갖는 트리 🌲 이진트리 순회(Tree Traversal)✦ 전위 순회: 뿌리(root)를 먼저 방문✦ 중위 순회: 왼쪽 하위 트리를 방문 후 뿌리(root)를 방문✦ 후위 순회: 하위 트리 모두..

*️⃣  투 포인터 정의1차원 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가면서 원하는 값을 찾을 때 까지 탐색하는 알고리즘리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리*️⃣  투 포인터 동작 방식left(l), right(r) 이나 start(s), end(d) 으로 포인트의 이름을 붙임처음에 start=end=0 이고, 조건은 항상 두 포인터들의 관계는 start 2개의 포인터는 현재 부분 배열의 시작(start)과 끝(end)을 가르킨다.*️⃣  투 포인터 알고리즘 문제의 유형포인터 2개가 같은 방향으로 진행하는것포인터 2개가 양끝에서 시작하여 반대로 진행하는 것포인터 하나는 한쪽 방향으로만 진행하고, 다른 포인터는 양쪽으로 이동하는 것  *️⃣  슬라..

*️⃣ 그래프는 여러 개의 노드(node)와 이들을 연결하는 간선(Edge)으로 이루어진 자료구조이다. 그래프트리방향성방향/무방향 그래프방향 그래프순환성순환/비순환비순환루트 노드존재하지 않음존재노드간 관계성부모, 자식 관계 없음부모, 자식 관계  *️⃣ 그래프 탐색하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것시작점에서 간선(Edge, E)을 타고 이동할 수 있는 정점(Vertex, V)들을 모두 찾는 것그래프 탐색 알고리즘에는 흔히 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있디. *️⃣  깊이 우선 탐색(Depth-First Search, DFS): 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색#..