본문 바로가기

java98

[백준 - Java] 1504번 : 특정한 최단 경로 문제 www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 설명 백준 1753번 최단 경로 문제를 응용하면 되는 문제이다. 📌 다익스트라 알고리즘에 대해 더 알고싶다면 아래 포스팅을 참고해주세요! [Java] 다익스트라 (Dijkstra) 최단 경로 알고리즘 전체 코드 import java.util.ArrayList; import java.util.Arrays; import java.util.PriorityQueue; .. 2021. 3. 20.
[백준 - Java] 1916번 : 최소비용 구하기 문제 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 설명 다익스트라 알고리즘을 이용하면 쉽게 풀 수 있는 문제다. 📌 다익스트라 알고리즘에 대해 알고 싶다면 아래 포스팅을 확인해주세요. [Java] 다익스트라 (Dijkstra) 최단 경로 알고리즘 전체 코드 * 무한대를 처음엔 Integer.MAX_VALUE로 했는데 오버플로우가 나는지 채점 중 런타임 에러가 났다ㅠㅠ 무한대 값을 Integer.MAX_VAL.. 2021. 3. 16.
[백준 - Java] 1261번 : 알고스팟 문제 www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 설명 처음엔 BFS로 최단 거리로 가면 되려나?라고도 생각했지만, 기존의 BFS로는 풀 수 없는 문제이다. 최단 거리도 필요 없고, (0, 0) 정점에서 부터 너비 우선 탐색을 해나가며 벽을 더 적게 부수는 방법으로 (M, N)까지 나아가야한다. 이를 위해서 기존의 Queue가 아니라 Deque를 사용했다. Deque는 Queue의 앞 뒤로 값을 삽입할 수 있다. Deque의 앞쪽을 .. 2021. 3. 16.
[백준 - Java] 6087번 : 레이저 통신 문제 www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 설명 2020 카카오 인턴십 문제로 나왔던 경주로 건설과 비슷한 문제이다. 자세한 설명은 경주로 건설 포스팅을 참고해주세요. [프로그래머스 - Java] 경주로 건설 (2020 카카오 인턴십) 경주로 건설은 직선, 코너 도로마다 비용이 부과되는데 둘을 적절히 사용해 가장 적은 비용으로 경주로를 건설해야 한다. 레이저 통신도 마찬가지이다. 레이저를 쏘는데 거울을 가장 적게 쓰는 방법으로 C에서 다른.. 2021. 3. 15.
[Java] 다익스트라 (Dijkstra) 최단 경로 알고리즘 다익스트라 (Dijkstra) 알고리즘 하나의 시작 정점으로부터 모든 다른 정점까지의 음의 가중치가 없을 때 최단 경로를 찾는 알고리즘 다익스트라 알고리즘에서 음수 간선이 존재하면 안 되는 이유 다익스트라 알고리즘의 각 단계 먼저 집합 S를 시작 정점 v로부터의 최단경로가 이미 발견된 정점들의 집합이라고 하자. 다익스트라 알고리즘에서는 시작 정점에서 집합 S에 있는 정점만을 거쳐서 다른 정점으로 가는 최단거리를 기록하는 배열이 반드시 있어야 한다. 이 1차원 배열을 distance라고 한다. 시작 정점을 v라 한다면 distance[v] = 0이고, 다른 정점에 대한 distance값은 시작 정점과 해당 정점 간의 가중치 값이 된다. 가중치 인접 행렬을 weight라 하면 distance[w] = wei.. 2021. 3. 12.
[백준 - Java] 10836번 : 여왕벌 문제 www.acmicpc.net/problem/10836 설명 매일매일 애벌레를 키우면 무조건 시간 초과가 난다!! 1,000,000 최대 백만일까지 애벌레를 키울 수 있기 때문!! 잘 생각해보면 매일 애벌레를 키워할 필요가 없다! 제일 왼쪽 열과 제일 위쪽 행의 애벌레만 주어지는 N날 동안 주어지는 0, 1, 2로 키우고, 나머지 (1, 1) ~ (M, M) 애벌레들은 N날이 지난 후, 문제의 조건 2에 따라 자신의 왼쪽(L), 왼쪽 위(D), 위쪽(U)의 애벌레들 중 가장 큰 사이즈로 키워진 애벌레의 크기로 바꿔주면 됨! 매일매일 키워보는 거나 제일 왼쪽 위쪽 다 키우고 적용하는 거나 둘은 같다! 그러니 다 키우고 적용하는게 훨 시간을 줄일 수 있다. * Scanner써서 입력받거나 println으.. 2021. 3. 3.
[백준 - Java] 11967번 : 불켜기 문제 www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net 설명 data-make.tistory.com/577 [BOJ] 11967.불켜기(완탐).java #. Problem https://www.acmicpc.net/problem/11967 * The copyright in this matter is in BOJ #. Resolution Process 1. Read and understand problem 2.. 2021. 3. 1.
[백준 - Java] 8972번 : 미친 아두이노 문제 www.acmicpc.net/problem/8972 8972번: 미친 아두이노 요즘 종수는 아두이노를 이용해 "Robots"이라는 게임을 만들었다. 종수는 아두이노 한대를 조정하며, 미친 아두이노를 피해다녀야 한다. 미친 아두이노는 종수의 아두이노를 향해 점점 다가온다. www.acmicpc.net 주절주절... 어떻게 하면 최적으로 문제를 풀 수 있을까 고민을 많이 했던 문제다. 미친 아두이노가 파괴되었나 안되었나 상태 변수를 만들어 관리하기도 했었고, 반례를 생각하지 못한 코드를 짠 경우도 있었고 (ex. 2개 이상의 미친 아두이노가 같은 칸으로 이동하는 경우) 같은 칸으로 이동할 경우 이전에 이동한 아두이노를 미리 움직여서 보드판이 뒤죽박죽으로 나오기도 하고... 맵을 지웠다. 다시 썼다. 복.. 2021. 3. 1.
[백준 - Java] 2638번 : 치즈 문제 www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net 문제 조건 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것으로 가정한다. 그러므로 이 공간에 접촉한 치즈 격자는 녹지 않고 C로 표시된 치즈 격자만 사라진다. 그러나 한 시간 후, 이 공간으로 외부 공기가 유입되면 오른쪽 그림과 같이 C로 표시된 치즈 격자들이 사라지게 된다. 파란색으로 칠해진 부분이 외부 공기, 빨간색으로 칠해진 부분이 치즈 내부의 공기이다. 모눈종이의 맨 가장자리에.. 2021. 2. 27.
[백준 - Java] 2156번 : 포도주 시식 문제 www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 설명 백준 2597번 계단 오르기와 비슷하게 DP (Dynamic Programing) 동적 계획법으로 풀 수 있는 문제다. [백준 - Java] 2579번 : 계단 오르기 하지만 계단 오르기완 다르게 하나 더 고려할 점이 있다. 바로 와인을 먹지 않는 경우 역시 고려해야 한다는 것이다. 일단 그 경우를 제외하고 생각해보자. 먼저 와인은 3잔 연속 먹을 수 없다. 따라서 현재 와인을 먹을 수 있는 경우는 1.. 2021. 2. 25.
반응형

티스토리툴바