알고리즘 (63) 썸네일형 리스트형 [JAVA]백준_2346_풍선터뜨리기 문제 : https://www.acmicpc.net/problem/2346 2346번: 풍선 터뜨리기 첫째 줄에 자연수 N(1≤N≤1,000)이 주어진다. 다음 줄에는 차례로 각 풍선 안의 종이에 적혀 있는 수가 주어진다. 편의상 0은 적혀있지 않다고 가정하자. www.acmicpc.net 문제 유형 : 구현, 자료구조, 덱 풀이방식 : 문제 유형에는 자료구조, 덱이라 표기되었지만 while문으로 구현 소스코드 package BOJ; import java.io.*; import java.util.*; public class BOJ_2346_풍선터뜨리기_Main { public static void main(String[] args) throws NumberFormatException, IOExceptio.. [JAVA]플로이드-와샬(Floyd-Warshall) 알고리즘 플로이드-와샬? 모든 최단 경로를 구하는 방법, 음의 가중치 간선 가능 방법 Step 1. D[][] : 자기자신으로의 인접이 아니고 갈 수 없는 경로라면 INF Step 2. k 경 i 출 j 도 : 경유지와 도착지가 같거나 출발지와 도착지가 같다면 패스 Step 3. 출발지에서 도착지까지의 가중치의 합이 경유지를 들렸을 때값보다 클 경우 갱신 소스 코드 import java.util.Scanner; public class FloydTest { static final int INF = 9999999; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int[][] D = ne.. [JAVA]백준_1719_택배 문제 : https://www.acmicpc.net/problem/1719 1719번: 택배 명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하�� www.acmicpc.net 문제 유형 : 다익스트라, 그래프 이론 풀이 방식 (1) 다익스트라는 한 정점에서 다른 모든 정점을 찾을 때 사용 => 최단 경로의 최근 노드를 저장하여 dfs로 제일먼저 가야할 노드를 찾음 (2) 플로이드 와샬은 모든 최단 경로를 구하는 방법에 사용됨 => 최근 노드를 저장. 양방향 그래프이므로 최근경로를 거꾸로 뒤집으면 처음 가야할 노드를 찾을 수있음 소스코드1 (다익스트라) package.. [JAVA]다음 순열(NextPermutation) NextPermutation ? - 첫 번째 단계로는 맨 뒤에서부터 탐색하며, 교환할 위치를 찾아야한다. - 뒤쪽부터 탐색하며, i보다 값이 작은 i-1 인덱스를 발견하는 순간이 교환할 위치 i-1이 된다. - 두 번째 단계로는 내가 찾은 i-1 인덱스의 배열 값과, 교환할 i-1보다 큰 위치 j를 찾는 것이다. - 이렇게 찾은 i-1자리와 j의 값을 교환한다. - 마지막으로는, 다음 순열의 사전순의 특징을 위해 i번째 인덱스부터 맨마지막 인덱스의 배열 값을 오름차순으로 바꿔주는 작업이 필요하다. 방법 Step 1. 뒷쪽부터 왼쪽으로 탐색하며 교환이 필요한 위치 찾기 찾은위치가 0이면 이미 내림차순된 순열이므로 다음순열은 없다. Step 2. i-1위치 : 교환이 필요한 위치, i-1위치값과 교환할 뒷쪽.. [JAVA]백준_10836_여왕벌 문제 : www.acmicpc.net/problem/10836 10282번: 해킹 문제 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염�� www.acmicpc.net 문제 유형 : 시뮬레이션 풀이 방식 : 최적화를 해야 시간초과가 안나는 문제 => 입력받고 바로 map에 연산 소스 코드 package BOJ; import java.io.*; import java.util.*; public class BOJ_10836_여왕벌_Main { public static void main(String[] args) throws IOException { // 1. 입력 Buf.. [JAVA]백준_10282_해킹 문제 : https://www.acmicpc.net/problem/10282 10282번: 해킹 문제 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염�� www.acmicpc.net 문제 유형 : 다익스트라 다익스트라 개념 정리 https://kistone.tistory.com/10 풀이 방식 : 인접리스트와 우선순위 큐를 이용한 다익스트라 소스 코드 package BOJ; import java.io.*; import java.util.*; public class BOJ_10282_해킹_Main { public static void main(String[] args.. [JAVA]다익스트라 알고리즘(Dijkstra Algorithm) 다익스트라 알고리즘이란? => 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제 (간선들은 모두 양의 간선이어야 한다) => 정점 A와 정점 B를 연결하는 경로 중 간선들의 가중치 합이 최소가 되는 경로 방법 Step1. 미방문 정점 중 최적 비용이 최소인 것 찾기 Step2. 선택 정점 방문하고 경유지로 고려하여 미방문정점들로 가는 최적비용을 최적화 소스코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class DijkstraTest { public s.. [JAVA]백준_1713_후보추천하기 문제 : https://www.acmicpc.net/problem/1713 1713번: 후보 추천하기 첫째 줄에는 사진틀의 개수 N이 주어진다. (1≤N≤20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대로 � www.acmicpc.net 문제 유형 : 시뮬레이션, 구현 풀이 방식 : 학생 번호를 담는 사진 틀 Frame 리스트와 해당 학생의 추천수의 student 배열을 이용하여 구현 소스코드 package BOJ; import java.io.*; import java.util.*; public class BOJ_1713_후보추천하기_Main { public static void main(String[] args).. 이전 1 ··· 4 5 6 7 8 다음