본문 바로가기

알고리즘107

[Java] 알고리즘 최단경로 (다익스트라) [Java] 알고리즘 최단경로 (다익스트라) 최단 경로 알고리즘 두 노드를 연결하는 가장 짧은 경로를 찾는다 (노드 사이의 간선 마다, 특정 값이 있다) 지도 탐색, 네트워크 다익스트라 출발 노드 기준에서, 다른 모든 노드의 최단 경로를 구할 수 있다 (하지만 가중치 음수 값이 없어야 한다) 다익스트라 알고리즘은, 우선순위 큐를 사용한다 그림으로 대략적인 설명 import java.util.*; public class Dijkstra { static class Node { int to; int distance; Node(int to, int distance) { this.to = to; this.distance = distance; } } public static void dijkstra(int node.. 2023. 7. 10.
20230709 [Java] 문제풀이 20230709 [Java] 문제풀이 [프로그래머스] 요격 시스템 미사일이 떨어지는 개구간이 targets라는 2차원 배열로 주어진다 이 미사일을 요격하기 위해, 필요한 요격 미사일의 개수의 최솟값을 구하는 것이다 일단 각 미사일의 개구간 중, 끝 부분을 기준으로 오름차순으로 정렬을 한다 그렇게 정렬을 하고 난 후에, 현재 공격 받는 미사일의 개구간의 시작점과, 그 전의 공격 받았던 미사일의 개구간의 마지막 지점이 완전히 겹치면, 한번에 요격을 할 수 있다 [3, 6] , [4, 7] : 두 미사일을 한번에 요격할 수 있음 [3, 6], [6, 8] : 두 미사일을 요격하려면 두 개의 요격 미사일이 필요함 [3, 6], [7, 9] : 두 미사일을 요격하려면 두 개의 요격 미사일이 필요함 // ==== .. 2023. 7. 9.
20230707 [Java] 문제풀이 20230707 [Java] 문제풀이 [프로그래머스] 완주하지 못한 선수 완주하지 못 한 선수를 찾는 것이다 참여는 했지만, 끝내지 못 한, 한 사람을 찾으면 된다 참여한 사람들의 이름을 marathon 이라는 HashMap에 넣고, value는 +1을 해준다 같은 이름이 있을 수 있다 completion에서, 이름이 나올때마다, value에 -1을 해준다 동명인이 없으면 모든 value는 하나 빼고 0일 것이다 동명인이 있을 수 있어 -1만 해주는 것이다 0이 아니면 그 사람이 완주를 못 한 선수다 import java.util.*; class Solution { public String solution(String[] participant, String[] completion) { HashMap ma.. 2023. 7. 7.
[Java] 알고리즘 다이나믹 프로그래밍 [Java] 알고리즘 다이나믹 프로그래밍 다이나믹 프로그래밍 큰 문제를 작은 문제로 쪼개서 앞에 저장을 하고, 해결해 나가는 것이다 피보나치 수열 예시) 1, 1, 2, 3, 5, 8, 13, 21 - 이렇게 순서대로 공식대로 계산을 하면서 문제를 해결하는 방식이 있다 (시간이 오래 걸릴 수 있다) f(1) f(2) f(3) f(4) f(5) f(6) f(7) f(8) f(9) f(10) 1 1 2 3 5 8 13 21 34 55 위와 같이 f(10) 까지 저장이 되어 있으면, f(11)을 구할 때 f(1)부터 다시 구하는 것이 아니라 f(9)와 f(10)만 찾아서 더해주면 된다 피보나치 수열을 구할 때에, 재귀를 사용할 때에는, 위와 같이 A zone과 B zone 모두 작동하게 된다 즉 B zone에.. 2023. 7. 6.
20230705 [Java] 문제풀이 20230705 [Java] 문제풀이 신고 결과 받기 k번 이상 신고를 받은 사람은 게시판 이용이 정지된다 한 사람이, 특정한 사람 한 명을 계속 신고해도, 한번 신고한 것과 같다 set을 이용하여, 한 사람이 특정 한 사람을 여러 번 신고 한 것을 없앤다 각 유저가, 신고한 유저 ID 중, 정지된 ID의 개수를 구하는 것 import java.util.*; // 각 유저가, 신고한 유저 ID 중, 정지된 ID의 개수를 구하는 것 class Solution { public int[] solution(String[] id_list, String[] report, int k) { HashSet set = new HashSet(); for (String string : report) set.add(string.. 2023. 7. 5.
20230704 [Java] 문제풀이 20230704 [Java] 문제풀이 [프로그래머스] 숫자 짝꿍 두 개의 숫자가 문자열로 주어진다 두 숫자가 공통으로 가진 숫자들을 모아서 제일 큰 수를 만드는 것이다 110, 11110 이면 110이 있어 110이 가장 큰 숫자다 1234, 123456 에서는 1234가 있고 4321이 가장 큰 숫자다 0~9까지, 각각 숫자들의 개수를 넣으려는 배열을 2개 만들었다 하나는 X 수에 대한 배열 하나는 Y 수에 대한 배열 두 배열을 제일 뒷부분에서 순회하면서, 0이 아닐 경우 겹치니깐 두 배열 중 작은 숫자만큼 문자열에 넣어주면 된다 StringBuffer를 사용할 때에는 .toString() 을 이용하면 문자열로 바꿔준다 import java.util.*; class Solution { public St.. 2023. 7. 4.
20230702 [Java] 문제풀이 20230702 [Java] 문제풀이 [프로그래머스] 덧칠하기 페인트 칠을 하는 것이고, 칠해야 하는 구역 section이 주어지고, 한번에 칠할 수 있는 길이 m이 주어진다 여기서, 페인트 칠은, 칠해야 하는 구역은 무조건 칠해야 하고, 이미 칠해진 곳에 덧칠할 수 있다 max 라는 변수를 만들어서, 페인트 칠을 할 수 있는 마지막 구역을 정해준다 max 안에 들어간 구역들은, 한번에 페인트 칠이 될 수 있는 공간이다 section[i] 2023. 7. 2.
20230628 [Java] 문제풀이 20230628 [Java] 문제풀이 달리기 경주 players 배열은, 경주가 시작할 때에, 선수들이 배치된 순서다 callings는, 선수 이름이 불릴 때마다, 앞에 선수와 순위가 바뀌는 것이다 즉 선수 이름이 불리면, 앞에 선수를 추월한 것이다 처음에는 너무 배열로 하겠다는 생각만 해서, 시간 초과가 나왔다 추후에 map을 사용해서 앞의 선수의 이름, 그리고 등수를 찾으면서, 배열에서 선수의 자리를 바꿔주었더니, 시간 초과를 해결할 수 있었다 import java.util.*; class Solution { public String[] solution(String[] players, String[] callings) { HashMap map = new HashMap(); for (int i = 0;.. 2023. 6. 28.
20230625 Java 문제풀이 20230625 Java 문제풀이 전국 대회 선발 고사 학생 3명을 선발하는 문제이다 문제에서는 학생들의 등수가 담긴 배열과, 학생들의 참여 여부가 담긴 배열이 주어진다 두 개의 배열을 탐색하며, 선발 고사를 참여하는 학생들 중, 높은 등수를 가진 학생들을 고른다 높은 등수부터 10000 * (제일 높은 등수) + 100 * (2번째 높은 등수) + (3번째 높은 등수) 의 식을 구하는 것이다 import java.util.*; class Solution { public int solution(int[] rank, boolean[] attendance) { ArrayList list = new ArrayList (); // number는 등수를 말하는 것 // 즉 등수는 1씩 증가할 것이고, 참가하는 학.. 2023. 6. 25.

티스토리툴바