본문 바로가기

알고리즘146

20230719 [Java] 문제풀이 20230719 [Java] 문제풀이 [백준] 2667 단지번호붙이기 1과 0으로 된 정사각형의 행렬이 주어진다 1은 아파트, 0은 빈공간 아파트는 동서남북으로 연결이 되어 있다 아파트의 수와, 각 아파트의 크기를 구하면 된다 apartNum 에 아파트의 수를 저장했다 그리고 apartments에는 아파트의 크기들을 넣었다 (나중에 sort으로 정렬을 한 후 오름차순으로 출력을 했다) 물론 0은 출력하면 안 됨 import java.util.*; public class baekjoon2667 { static int[][] map; static int[] dr = {-1, 0, 0, 1}; static int[] dc = {0, -1, 1, 0}; static int[] apartments = new in.. 2023. 7. 19.
20230718 [Java] 문제풀이 20230718 [Java] 문제풀이 [백준] 1260 DFS와 BFS 예전에 파이썬으로 풀었던 문제를 자바로 풀어보았다 DFS와 BFS를 구현하는 것이다 여기서 만약에 자식 노드, 즉 다음 정점의 개수가 1개 이상일 경우, 제일 작은 것부터 탐색을 한다 즉 모든 자식 노드들을 오름차순으로 정렬을 해주면 된다 import java.util.*; public class baekjoon1260 { public static void dfs(int[] visited, ArrayList matrix, int start) { System.out.print(start + " "); visited[start] = 1; for (int i = 0; i < matrix.get(start).size(); i++) { if .. 2023. 7. 18.
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.

티스토리툴바