개발기록

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

API가 무엇인가요?

*️⃣ 정의0 또는 1로 표현되는 이진수 연산 방식을 이용하여, 정수의 이진수 표현을 자료 구조로 쓰는 기법 *️⃣ 장점1. 수행 시간이 빠르다. 비트마스크 연산은 bit 연산이기 때문에 대부분 O(1)에 구현된다.비트마스크를 이용하는 경우에는 비트의 개수만큼 원소를 다룰 수 있기 때문에 연산 횟수가 적은 경우에는 속도에 큰 차이가 없지만, 연산 횟수가 늘어날수록 차이가 매우 커지게 된다.  2. 코드가 짧다.다양한 집합 연산들을 비트연산자로 한 줄로 작성할 수 있기 때문에 반복문, 조건문 등을 이용한 코드보다 훨씬 간결한 코드를 작성할 수 있다. 3. 메모리 사용량이 적다.bit가 10개인 경우에는 각 bit당 두 가지 경우를 가지기 때문에 210">210210가지의 경우를 10bit 이진수 하나로 표..

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