[알고리즘] 다익스트라(Dijkstra) 알고리즘 1. 다익스트라(Dijkstra) 알고리즘이란? - 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘 - 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려줌. > 모든 정점을 방문하되, 최단 경로로! - "최단 거리는 여러 개의 최단 거리로 이루어져있다."는 다이나믹 프로그래밍의 특성 반영 > 하나의 최단 거리를 구할 때, 그 이전까지 구했던 최단 거리를 그대로 사용 - 가중치가 양수일 때만 사용 가능하다 2. 알고리즘의 동작 단계 (1) 출발 노드, 도착 노드 설정 (2) 출발 노드를 기준으로 각 노드의 최소 비용 저장 (3) 방문하지 않은 노드 중에서 가장 비용이 적은 노드 선택 (4) 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신 > 간선 비용.. [알고리즘] Greedy Algorithm (탐욕 알고리즘) 1. Greedy Algorithm이란? - Greedy: 탐욕스러운, 욕심 많은 - 탐욕 알고리즘: 선택의 순간마다 당장 눈 앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법 - 최적 해를 구하는 데에 사용하는 근사적인 방법 - 여러 경우 중 하나를 결정할 때마다 그 순간 최적이라고 생각되는 것을 선택하는 방식 > 최종적 해답에 도달 (지금의 선택이 앞으로 남은 선택들에 어떤 영향을 끼칠지 고려 X) - 그 순간에는 지역적으로 최적이라도, 지역적인 최적을 수집한 최종적(전역적)인 답이 최적이라는 보장은 없다. - 탐욕 알고리즘에 적용할 수 있는 문제: 지역적, 전역적 모두 최적! * 간단한 예시 - 문제: 노드에서 가장 합이 높은 방법을 선택하는 방법 - 그리디 알고리즘: 상황에 맞게 가.. [알고리즘] Dynamic Programming(동적 계획법) 1. 다이나믹 프로그래밍이란? - "동적 계획법" - step1. 하나의 큰 문제를 여러 개의 작은 문제로 나눈다. - step2. 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용한다. - 하나의 문제 해결 패러다임 (특정한 알고리즘 X) - 기억하기 프로그래밍 2. 재귀와 DP의 차이? - 일반적인 재귀(Naive Recursion)를 단순히 사용 시, 동일한 작은 문제들이 여러 번 반복 > 비효율적 계산 ex. 피보나치 수열 - 재귀: f(n-1), f(n-2)에서 각 함수를 1번씩 호출 => 동일한 값을 2번씩 구하게 됨 => n 값이 증가함에 따라 호출되는 함수의 횟수는 기하급수적으로 증가 (약 7해) - DP: 한 번 구한 작은 문제의 결과 값을 저장하고 재사용 > 반복 X > 약 200회 .. [Algorithm] 하노이의 탑 알고리즘 (재귀) 💜 하노이의 탑이란? 1) 정의 - 하노이의 탑은 퍼즐의 일종으로, 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있다. 2) 조건 한 번에 한개의 원판만 옮길 수 있다. 가장 위에 있는 원판만 이동할 수 있다. 큰 원판이 작은 원판 위에 있어서는 안 된다 3) 목표 - 세 막대를 왼쪽부터 A, B, C라고 가정하자. - 위 조건에 맞게 모든 원판을 A에서 C로 옮겨야 한다. 💜 어떤 기능을 하는 함수를 구현해야하는가? (문제 정의) - 원반의 이동 횟수를 최소화한다. - 각 원반을 옮기는 모든 순서를 출력한다. => 원반 개수 N개를 입력 받아, 모든 원반을 C막대에 옮기는 모든 과정을 출력한다. .. [프로그래머스] 230701 코딩테스트 연습 1. 덧셈식 출력하기 const readline = require('readline'); const rl = readline.createInterface({ input: process.stdin, output: process.stdout }); let input = []; rl.on('line', function (line) { input = line.split(' '); }).on('close', function () { console.log(`${Number(input[0])} + ${Number(input[1])} = ${Number(input[0]) + Number(input[1])}`); }); 2. 문자열 붙여서 출력하기 const readline = require('readline'); co.. [프로그래머스] 230630 코딩테스트 연습 1. 문자열 출력하기 const readline = require('readline'); const rl = readline.createInterface({ input: process.stdin, output: process.stdout }); // 인터페이스 객체 생성 let input = []; rl.on('line', function (line) { input = line.split(' ').map((data) => { return data }); rl.close(); }).on('close',function(){ console.log(input.toString()); process.exit(); }); 2. a와 b 출력하기 const readline = require('readline'); co.. 이전 1 다음
