[알고리즘] 다익스트라(Dijkstra) 알고리즘 1. 다익스트라(Dijkstra) 알고리즘이란? - 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘 - 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려줌. > 모든 정점을 방문하되, 최단 경로로! - "최단 거리는 여러 개의 최단 거리로 이루어져있다."는 다이나믹 프로그래밍의 특성 반영 > 하나의 최단 거리를 구할 때, 그 이전까지 구했던 최단 거리를 그대로 사용 - 가중치가 양수일 때만 사용 가능하다 2. 알고리즘의 동작 단계 (1) 출발 노드, 도착 노드 설정 (2) 출발 노드를 기준으로 각 노드의 최소 비용 저장 (3) 방문하지 않은 노드 중에서 가장 비용이 적은 노드 선택 (4) 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신 > 간선 비용.. [알고리즘] 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS) 0. 그래프 탐색 문제란? - 어떤 한 그래프와 해당 그래프의 시작 정점이 주어졌을 때, 시작점에서 간선(Edge, E)를 타고 이동할 수 있는 정점(Vertex, V)를 모두 찾는 문제 - 문제 해결법: 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)이 있다. 1. 너비 우선 탐색(BFS)이란? - BFS (Breadth - First Search) - 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법 - 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법 - 깊게(Deep) 탐색하기 전에 넓게(Wide) 탐색하는 것 - 두 노드 사이의 최단 경로 / 임의의 경로를 찾을 때 사용 2. 너비 우선 탐색의 특징 - 직관적 X.. [알고리즘] 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회 .. [프로그래머스] 230922 코딩테스트 연습 소수 찾기 (시간복잡도 고려해서) * 에라토스테네스의 체 : // 에라토스테네스의 체 function solution(n) { var answer = 0; function eratostenes(m) { // 0과 1은 소수에서 제외 let arr = new Array(m+1).fill(true).fill(false, 0, 2); // i*i >>> 11^2가 120보다 큰 경우는 의미가 없다 for(let i=2 ; i*i [프로그래머스] 230921 코딩테스트 연습 1. 약수의 개수와 덧셈 function solution(left, right) { var answer = 0; const cnt_arr = Array.from({length: right-left+1}, () => 0); // 1과 자기 자신은 포함 > 2를 default 값으로 // 약수 개수 구하기 for(let i = left; i [프로그래머스] 230920 코딩테스트 연습 1. 같은 숫자는 싫어 function solution(arr) { var answer = []; answer.push(arr[0]); for(let i=1; i 3진법 만들기 n1 = n.toString(3); // 3진법 뒤집기 n2 = n1.split("").reverse().join(""); // 뒤집은 3진법 > 10진법 만들기 n2 = parseInt(n2, 3); answer = Number(n2.toString(10)); return answer; } 3. 크기가 작은 부분 문자열 function solution(t, p) { let cnt = 0; let arr = [] let len = p.length; let pNum = parseInt(p); for (let i=0; i { if (.. [프로그래머스] 230919 코딩테스트 연습 1. 행렬의 덧셈 function solution(arr1, arr2) { var answer = []; let len1 = arr1.length; let len2 = arr1[0].length; let arr = []; for(let i=0; i [프로그래머스] 230918 코딩테스트 연습 1. 문자열 내림차순으로 배치하기 function solution(s) { var answer = ''; answer = s.split("").sort().reverse().join(""); // 문자열 쪼개기 > 정렬 (오름차순) > 역순 (내림차순) > 문자 합치기 return answer; } 2. 부족한 금액 계산하기 function solution(price, money, count) { var answer = -1; let sum = 0; // 놀이기구 총 비용 계산 for(let i=1; i 0) ? Math.abs(sum-money) : 0; return answer; } 3. 문자열 다루기 기본 function solution(s) { var answer = false; // ** isN.. [프로그래머스] 230915 코딩테스트 연습 1. 가운데 글자 가져오기 * substr(문자열 특정 위치, 가져올 갯수) function solution(s) { var answer = ''; if(s.length%2 == 0) { // 단어의 길이가 짝수 answer = s.substr((s.length-1)/2, 2); } else { // 단어의 길이가 홀수 answer = s.substr(s.length/2, 1); } return answer; } 2. 수박수박수박수박수박수? function solution(n) { var answer = ''; for(let i=1; i [프로그래머스] 230914 코딩테스트 연습 1. 나누어 떨어지는 숫자 배열 function solution(arr, divisor) { var answer = []; arr.sort(function(a, b) { return a-b; // 오름차순 정렬 }) arr.forEach( i => { if(i%divisor == 0) { answer.push(i); } }) if(answer.length == 0) { answer.push(-1); } return answer; } 2. 음양더하기 function solution(absolutes, signs) { let answer = 0; absolutes.forEach( (v, i) =>{ if(signs[i] == true) { answer += v; } else { answer -= v; } }.. [프로그래머스] 230913 코딩테스트 연습 1. 정수 내림차순으로 배치하기 function solution(n) { var answer = 0; let result = 0; // 숫자 분리 후 정렬 result = (n+"").split("").sort().reverse(); // 문자 합치기 (문자열 상태) > join으로 바로 해결 가능! result.forEach(i=> { answer += i; }) // 정수로 형변환 return parseInt(answer); } 2. 하샤드 수 function solution(x) { var answer = true; let num = 0; // 긱 자릿수의 합 (x+"").split("").forEach( i => { num += parseInt(i); }) answer = (x%num == 0) .. 이전 1 2 3 4 5 다음
