PS

백준 1753 - 최단 경로 (다익스트라)

[문제 해결] 다익스트라를 이용한 최단경로 문제이다. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신한다 [Java] import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.StringTokenizer; public class Main { private static boolean visited []; private static int dist[]; private static ArrayList graph = ne..

프로그래머스 - 프렌즈 4블록

https://school.programmers.co.kr/learn/courses/30/lessons/17679 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [문제 해결] 중복되는 4개 블록들을 찾아서 ArrayList에 넣어준다. (4분 탐색) ArrayList에서 삭제할 블록들을 꺼내면서 더미 값 'x' 로 바꾸어 준다. x로 된 값들은 전부 위로 올려주고 x가 아닌 값은 밑으로 내린다 중복 되는 4블록이 없을때 까지 반복 [java] import java.io.BufferedReader; import java.io.IOException; impo..

백준 안전영역 2468 - java

https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net [문제 해결] 해당 지역의 높이만큼 비가오면 해당 지역은 물에 잠긴다 주어진 지역들의 높이 만큼 비가 온다고 가정하고 bfs를 탐색하면 된다. 비가 와서 높이가 4이하인 지역이 모두 잠긴다면 안전 영역이 5가되고 높이가 6인만큼 비가오면 안정영역이 4가 된다. 이렇게 주어진 높이들 만큼 비가 온다고 가정하고 안전 영역의 최대 값을 구하면 된다. import java.io.BufferedReader; im..

자바 - 순열 (permutation)

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int[] arr = {1, 2, 3}; //순열을 만들 배열 int n = arr.length; //배열의 길이 int[] output = new int[n]; //순열 출력을 위한 배열 boolean[] visited..

알고리즘 수업 - 깊이 우선 탐색

https://www.acmicpc.net/problem/24479 24479번: 알고리즘 수업 - 깊이 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net 예제 케이스는 통과하는데 제출하면 틀리시는 분들을 위해 반례 드립니다. 1% ~ 3% 70% [입력] [입력] 6 4 1 5 1 3 2 3 1 2 1 4 1 5 4 6 정답 정답 1 0 0 0 0 1 2 0 4 0 3 [java] import java.io.BufferedReader; import java.io.IOExcep..

백준 - 점프왕 쩰리 (Small) - Java

https://www.acmicpc.net/problem/16173 16173번: 점프왕 쩰리 (Small) 쩰리는 맨 왼쪽 위의 칸에서 출발해 (행, 열)로 나타낸 좌표계로, (1, 1) -> (2, 1) -> (3, 1) -> (3, 3)으로 이동해 게임에서 승리할 수 있다. www.acmicpc.net [문제 해결] 저는 DFS를 이용한 완전 탐색으로 문제를 해결 하는데, BFS로도 문제를 해결하실 수 있습니다. [java] import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { private static int[][]..