본문 바로가기

전체 글

프로그래머스 - 부대복귀(Java) 다익스트라(dijkstra) 문제입니다. 연결 정보가 주어지고, 여러 출발지에서 하나의 목적지 까지로 가는 가중치를 구하는 문제입니다. 무방향 그래프이기 때문에 이를 반대로 생각하면, 하나의 목적지에서 여러 출발지까지 가는 가중치를 구하는 문제로 해석할 수 있습니다. 즉, 하나의 시점에서 다른 노드들로 가는 최소 가중치를 구하는 문제이므로 다익스트라인 것을 알 수 있습니다. 다익스트라 시간 복잡도는 O(VlogV + ElogV)입니다. log500,000의 값이 18.931568569324174이므로, 19로 계산하겠습니다. 500,000*19 + 100,000*19 = 11,400,000 입니다. 이정도면 허용범위 내라고 할 수 있기 때문에, 다익스트라 시간복잡도로 해결할 수 있습니다. [구현 코드] .. 더보기
프로그래머스 - 순위(Java) 플로이드-와샬(Floyd-Warshall) 문제입니다. 플로이드 와샬은 모든 노드가 다른 노드로 갈 때의 가중치를 이차원 배열 형태로 저장하는 알고리즘입니다. 선수 n명과 대진표 일부가 주어졌을 때, 순위를 알 수 있는 선수의 수를 구하는 문제입니다. 플로이드 와샬은 기본적으로 돌아갈 경우가 더 짧으면 돌아가는 형태를 지닙니다. // k를 거쳐서 가는 경우 for (int k = 1; k dis[i][k] + dis[k][j]){ ... } } } } 이 말을 다르게 해석하면, 가중치가 갱신이 될 경우에는 연결된다라는 의미이기도 .. 더보기
프로그래머스 - 가장 긴 팰린드롬 구현 문제입니다. 가장 긴 부분 문자열 부터 시작하여 모든 부분 문자열을 확인해 팰린드롬을 찾으면 됩니다. 처음에 두 개의 반복문 안에 subString으로 문자열을 짜르고 비교하는 코드를 사용했었습니다. String le = str1.subString(0, di); String ri = str1.subString(di+1, n); StringBuilder sb = new StringBuilder(ri); if(le.equals(sb.reverse().toString())){ ... } 예시 코드가 길어지기 때문에 생략했지만, 최소 subString이 네 개는 필요했습니다. subString의 경우 O(N)의 시간이 소요되기 때문에 시간초과가 발생했습니다. 이후 방법은 subString이 아닌 반복문을 .. 더보기
프로그래머스 - 여행경로(Java) dfs 문제입니다. 주어지는 항공권을 모두 사용해서 여행 경로를 만들어야 합니다. 저의 경우 항공권이 주어지면 해당 정보를 Map에 저장했습니다. Map에 저장하면 O(1)로 value를 가져올 수 있기 때문에, 반복해서 찾는 것 보다 더 좋다고 생각했습니다. 추가로 항공권 정보를 Map에 저장할 때, 항공권의 위치를 저장했습니다. 중복해서 항공권을 사용하지 않고 여행 경로를 만들기 위함 입니다. [구현 코드] import java.util.*; class Solution { private static boolean[] visited; private static Map map; private static List ansList; private static class Node{ String city; in.. 더보기
프로그래머스 - 디스크 컨트롤러(Java) 힙 문제입니다. 한 번에 하나의 일만 처리할 수 있는 디스크에 여러 요청이 들어왔을 때, 요청 대기시간의 평균을 가장 짧게 만들어야 합니다. 입력 값과, 스케줄 길이에 따라 정렬을 하게 된다면 O(Nlog(N))으로 문제를 해결할 수 있습니다. 특정 시간을 기준으로 해결할 수 있는 있는 요청을 우선순위 큐에 삽입하여 하나씩 처리하면 됩니다. [구현 코드] import java.util.Arrays; import java.util.Comparator; import java.util.PriorityQueue; class Solution { private static class Job implements Comparable { int s, d; public Job(int s, int d) { this.s = .. 더보기
프로그래머스 - 스티커 모으기2(Java) dp 문제입니다. 원형으로된 배열이 있고, 조건에 맞춰 원소를 뽑아 낼 때의 최댓값을 구하는 문제입니다. 하나의 원소를 뽑아낼 경우 양 쪽에 있는 원소는 뽑아낼 수 없습니다. 때문에 크게 두 가지로 구분될 수 있습니다. 첫 번째 원소를 뽑는 경우(원형이기 때문에, 마지막 원소는 뽑을 수 없습니다.) 첫 번째 원소를 뽑지 않는 경우 특정 위치를 i라고 했을 때에도 두 가지로 구분할 수 있습니다. 현재 위치를 뽑는 경우 : dp[i-2] + sticker[i] 현재 위치를 뽑지 않는 경우 : max(dp[i-1], dp[i-2]) [구현 코드] class Solution { private static int[] dp1, dp2; public static int solution(int sticker[]) { .. 더보기
프로그래머스 - 섬 연결하기(Java) 그리디 문제입니다. 가중치 그래프가 주어졌을 때, 최소 신장 트리를 구하는 문제입니다. 최소 신장 트리는 가중치가 가장 작은 간선부터 선택하고, 선택된 노드들은 유니온-파인드 연산을 통해 중복되지 않게 간선을 연결하는 방법을 사용합니다. [구현 코드] import java.util.*; class Solution { private static int[] parents; public static int solution(int n, int[][] costs) { int answer = 0; Arrays.sort(costs, new Comparator() { @Override public int compare(int[] o1, int[] o2) { return o1[2] - o2[2]; } }); parent.. 더보기
프로그래머스 - 가장 먼 노드(Java) 다익스트라 문제입니다. 노드가 주어지고, 노드의 연결 정보가 간선으로 주어집니다. 가중치가 1인 그래프에서 노드 1을 기점으로 가장 먼 노드의 개수를 구하는 문제입니다. 시점이 주어지기 때문에, 다익스트라를 사용해야 하는 것을 알 수 있습니다. [구현 코드] import java.util.*; class Solution { private static List graph; public static int solution(int n, int[][] edge) { int answer = 0; graph = new ArrayList(); for (int i = 0; i < n + 1; i++) graph.add(new ArrayList()); for (int[] e : edge) { int a = e[0]; i.. 더보기

티스토리툴바