본문 바로가기

분류 전체보기383

20230714 [Java] 문제풀이 20230714 [Java] 문제풀이 [백준 17478 Silver - 5] 재귀함수가 뭔가요? 재귀는 함수가, 자기 자신을 호출하는 것이다 (아는데 아직도 어려움...) 일단 count를 1씩 더하면서 num과 같아지면 return을 해준다 (break point) 그 이후에는 System.out.printf("%s라고 답변하였지.", under).println(); 이 파트가 실행이 되는 것이다 어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다. "재귀함수가 뭔가요?" "잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어. 마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지. 그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선.. 2023. 7. 14.
[Java] 알고리즘 최단경로 (플로이드-워셜) [Java] 알고리즘 최단경로 (플로이드-워셜) 플로이드-워셜 다익스트라와 벨만 포드는 하나의 시작점에서 모든 노드들 사이의 거리를 알아냈다면, 플로이드-워셜은 모든 노드들 사이의 최소 거리를 알아낼 수 있다 음수가 있어도 가능하고, 자기 자신에게 가는 것이 만약 0 아래로 떨어지면 음수 사이클이라는 것을 확인할 수 있다 단 3중 for문을 사용하기 때문에 다른 최단 경로 알고리즘에 비해 시간 복잡도가 높다 이 다음에는 갱신할 데이터가 없다 import java.util.*; public class Main3 { static int[][] dist; static int INF = 1000000000; public static void floydWarshall(int nodes, int edge, int[.. 2023. 7. 11.
20230711 [Java] 문제풀이 20230711 [Java] 문제풀이 [프로그래머스] 뒤에 있는 큰 수 찾기 스택을 안 사용하고, 이중 for문을 사용하니깐 시간 초과가 나왔다 스택을 이용하여 뒤에 있는 큰 수를 찾기 위해 스택을 사용할 수 있다 import java.util.*; class Solution { public int[] solution(int[] numbers) { int[] result = new int[numbers.length]; Stack stack = new Stack(); for (int i = 0; i = numbers[i]) { s.. 2023. 7. 11.
[Java] 알고리즘 최단경로 (벨만-포드) [Java] 알고리즘 최단경로 (벨만-포드) 벨만-포드 음수 가중치를 포함해서, 시작 정점에서 다른 정점까지 최단 거리를 구할 수 있다 추가로 벨만-포드 알고리즘을 통해서 음수 사이클 존재의 여부를 알 수 있다 음수 사이클이란, 한 노드에서 다른 노드 사이의 간선이 2개가 존재하고, 왔다 갔는데, 가중치가 오히려 내려가는 것 A, B가 있는데 A -> B 는 8 이고 B -> A 는 -9 라고 하면, A와 B를 오고 가면 -1이 된다 모든 간선을 순회한다!!! import java.util.*; public class Main2 { static class Edge { int from; int to; int distance; Edge(int from, int to, int distance) { this.f.. 2023. 7. 10.
[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.
20230708 [Java] 문제풀이 20230708 [Java] 문제풀이 [프로그래머스] 체육복 체육복을 도난 당한 학생들의 배열과, 여벌이 있는 학생들의 배열이 주어진다 여벌이 있는 학생은, 도난당한 학생에게 체육복을 빌려줄 수 있다 단 도난 당한 학생은, 자신보다 1 아래 또는 1 위에 있는 학생의 체육복을 빌릴 수 있다 여벌이 있지만, 체육복을 도난 당했다면 (그 학생은 다른 학생에게 체육복을 빌려줄 수 없게 된다) 일단 새로운 배열을 만들었다 학생들의 번호를 인덱스로 넣었다 (-1을 해줌) 그리고 값은 -1 : 도난 당함 0 : 자기 자신의 체육복만 있음 1 : 여벌이 있는 학생 그리고 이 배열을 순회하면서, 도난 당한 학생의 index - 1 또는 index + 1의 값이 1이라면 1을 더해준다 더해줬다는 것은, 체육복을 빌렸다는.. 2023. 7. 8.
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] 알고리즘 백트래킹 백트래킹 DFS와 백트래킹이 다른점 DFS는 가능한 모든 경우의 수를 탐색을 한다 (그래서 시간이 많이 걸린다) 백트래킹은 탐색을 하다가, 불필요한 탐색이라고 생각하면, 다른 루트를 탐색을 한다 백트래킹에서는 얼마나 가지치기를 잘 하느냐가 제일 중요하다 용어 유망 (Promising) : 목표의 값이 될 가능성이 있다는 것 가지치기 (Prunning) : 목표의 값이 될 수 있는 가능성이 없어, 해당 노드를 제외 백트래킹 (Backtracking) : 유망하지 않는 쪽으로 가지 않고 다시 돌아오는 것 void dfs(int cnt, int idx) { // 현재까지의 결과, 탐색을 진행할 인덱스 // r개를 선택한 경우 if(cnt == r) { // 결과 처리 후 현재 가.. 2023. 7. 7.

티스토리툴바