목록Algorithm (111)
S E P H ' S
다익스트라 알고리즘(Dijkstra) 그래프에서 여러 개의 노드가 있을 때, 한 노드에서 각 모든 노드 까지의 최단거리를 구하는 알고리즘이다. 다만 '음의 간선' 즉, 가중치가 0보다 작은 값이 아닌 경우에 정상 작동한다. 동작과정을 살펴보면 그리디 알고리즘(매번 비용이 가장 적은 노드를 선택하기 때문)과 다이나믹 프로그래밍(DP) 기법을 함께 사용한다. 이 두 단계를 반복하면서 임의의 노드에서 각 노드까지의 최단 거리를 구하게 된다. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다. (그리디 알고리즘) 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신한다. (다이나믹 프로그래밍) 작동 방식에 대해서 그림으로 알아보자. 그림 1은 주어진 그래프 상태이다. 출발점은 A, 도착점은 E라고 할 때..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 문제를 보자마자 조합이구나가 떠오른게 많이 발전한 것 같다. 조금 어려웠던 점은 data에 주어지는 조건에 맞도록 어떻게 조합을 맞춰나가야 하는지가 잘 떠오르지 않았다. 그래서 가능한 조합을 모두 만든 다음, 그 조합이 data에 주어지는 조건에 부합하는지 확인하도록 했다. 또한 조건에 부합하는 조합이 없다면 0을 출력해야한다. answer를 0으로 초기화 해두고 모든 조건을 확인하고도 answer의 증가가 일어나지 않으면 조건에 맞는 것이 없는 것이다. 그대로 코드를 작성해서 통과할 수 있었다. ..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 처음엔 단순히 dfs를 생각했다가 경우의 수가 많아질 수 있다와 1칸, 2칸 ~ N칸 늘어나게 되더라도 몇 칸마다 채워주는 규칙은 똑같지 않나? 라는 생각에 DP가 떠올랐다. 점화식 구하는 것은 DP 문제 중에 기초 중에 기초였지만 경우의 수를 1,000,000,007로 나누는 것을 DP 배열에 저장할 때 모두 해줘야 했다. 앞으로 저런 제한사항이 있다면 주의해서 과정에 꼭 넣는 것을 빼먹지 말아야겠다. public class 타일링_2xn { public int solution(int n) { i..
17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀 www.acmicpc.net 풀이 시계 방향, 반시계 방향으로 원판을 회전하는 기능 인접수를 찾는 기능 평균을 구해 평균에 따라 원판의 수를 업데이트 하는 기능 회전하는 기능은 쉽게 구현해냈고 인접수를 찾아 없애는 것은 문제의 조건에 따라 인접한 수가 같으면 그 좌표값들을 Set에 Point 객체에 담아 넣었다. 그리고 인접수를 찾는 과정이 모두 끝나면 Set 담긴 객체들의 좌표에 해당하는 곳을 0으로 업데이트 해준 다음 평균값에 따라 계산을 해준 다음 원판의 모든 수의 합을..