개발기록

*️⃣  개념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 또는 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)를 방문✦ 후위 순회: 하위 트리 모두..

*️⃣  투 포인터 정의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)로 넘어가기 전에 해당 분기를 완벽하게 탐색#..