다익스트라(Dijkstra) 알고리즘 그래프의 최단 경로를 구하는 알고리즘으로 하나의 정점에서 출발하여 최단 거리를 구하는 알고리즘이다. 탐욕법(Greedy)과 동적 계획법을 사용하는 알고리즘으로, 음의 가중치(음의 값)가 없어야한다. 음의 가중치가 존재하게 되면, 최소 비용의 음의 무한대값이 생성될 수 있으며 그리디 알고리즘을 적용할 수 없다. 인접 행렬로 표현된 그래프의 경우 O(n^2)의 복잡도를 가지며, 우선순위 큐를 사용하여 시간복잡도를 O(m logn)까지 낮출 수 있다. 매커니즘 (1) 방문하지 않은 노드 중 가장 비용이 적은 노드를 선택한다 (그리디) (2) 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신한다 (DP) 예시 https://mag1c.tistory.com/451 [백준 19..
문제 링크 Silver 1 https://www.acmicpc.net/problem/13600 13600번: Fatorial O fatorial de um número inteiro positivo N, denotado por N!, é definido como o produto dos inteiros positivos menores do que ou iguais a N. Por exemplo 4! = 4 × 3 × 2 × 1 = 24. Dado um inteiro positivo N, você deve escrever um programa para determina www.acmicpc.net 풀이 solved.ac를 따라 class만 풀다보니 완전탐색만 너무 많이나와서 실2 ~ 실1기준 DP, 그리디..
문제 링크 Silver 1 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 풀이 최대의 경우의 수를 구하는 탐욕법을 요구하는 문제로 가장 많은 경우를 고려하기 위해 회의가 끝나는 시간으로 오름차순해주었고, 같을 경우 시작 시간으로 오름차순 해주었다. Arrays.sort(discussing, new Comparator() { @Override public int compare(int[] o1, int[] o2) { if(o1[1] == o2[1]) return o1[0] - o2[0]; else return o1[1] - o2[1]; } }); 탐욕법을 구현하..
https://school.programmers.co.kr/learn/courses/30/lessons/181188 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 뭔가 낯설지 않은 문제였는데 예전 단속 카메라문제와 유사했다 아니 똑같았다.. 1. 폐구간 별로 오름차순 정렬을 진행 2. 미사일 좌표는 개구간이라고 했기 때문에 이전 구간의 끝지점과 같을 때에도 answer++처리 개구간 (a,b)일 때, a < x < b인 구간 import java.util.*; class Solution { public int solution(int[][] targe..
https://school.programmers.co.kr/learn/courses/30/lessons/172927# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근방법 idx : minerals배열을 총 반복 돌아야하는 횟수로 나머지가 남을경우 올림처리(ex : 18일때 4번돌아야함) count : 광물 종류별 갯수 (처음에는 List을 활용하여 풀려고 했다) picksum : 총 광물을 캘 수 있는 수량(곡괭이 개수*5) 1. stone곡괭이의 경우의 수는 고려하지 않았다. 다이아, 철 곡괭이가 모두 소진된 후에 작업에 사용할 것이기 때문 2. m..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해당 문제는 프로그래머스에서 탐욕법(Greedy) 카테고리 안에 있는 문제이다. 탐욕 알고리즘은 정리해 두었던 내용이다 ( 링크 ) 문제 풀이 아직 익숙치않은 Comparator 인터페이스로 이중배열인 costs의 값을 cost순으로 오름차순 했다는 것 정도다 Comparator의 사용법은 간단히 정리 해 두었다 ( 링크 ) 알고리즘 활용에 미숙해서인지 모르겠지만 내 생각엔 탐욕법이나 기타 알고리즘들을 사용해서 푼 것 같지는 않다 물론 이게 어떤 알고리즘이라고 한다면 공부를 더 깊게 해야 할 것 같다 1. 섬..
탐욕법(Greedy Algorithm) ※ Greedy : 탐욕스러운, 욕심 많은... 탐욕 알고리즘 : 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법 최적해를 구하는 데에 사용되는 근사적인 방법이다. 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달하지만 그것이 최적이라는 보장은 없다. 탐욕 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다. 탐욕 알고리즘 문제를 해결하는 방법 선택 절차(Selection Procedure) : 현재 상태에서의 최적의 해답을 선택한다. 적절성 검사(Feasibility Check) : 선택된 값이 문제의 조건을 만..