![]()
https://www.acmicpc.net/problem/1052 1052번: 물병 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번 www.acmicpc.net 알고리즘 유형 수학 그리디 알고리즘 비트마스킹 문제 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번에 K개의 물병을 옮길 수 있다. 하지만, 지민이는 물을 낭비하기는 싫고, 이동을 한 번보다 많이 하기는 싫다. 따라서, 지민이는 물병의 물을 적절히 재분배해서..
![]()
https://www.acmicpc.net/problem/2852 2852번: NBA 농구 첫째 줄에 골이 들어간 횟수 N(1
https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 다익스트라 / BFS 문제입니다. 우선순위 큐를 사용하기 위해 Comparable를 사용했고, bfs에서 초기 설정 및 현재 상태 처리를 담당하고, 범위 체크를 하는 함수를 만들어 문제를 해결했습니다. import java.util.*; import java.io.*; public class Main { static int dirX[] = {0, 0, -1, 1}; static ..
문제링크 https://www.acmicpc.net/problem/18223 18223번: 민준이와 마산 그리고 건우 입력의 첫 번째 줄에 정점의 개수 V와 간선의 개수 E, 그리고 건우가 위치한 정점 P가 주어진다. (2 ≤ V ≤ 5,000, 1 ≤ E ≤ 10,000, 1 ≤ P ≤ V) 두 번째 줄부터 E개의 줄에 걸쳐 각 간선의 정보 www.acmicpc.net 코드 import heapq input = __import__('sys').stdin.readline v,e,p = map(int,input().split()) graph = [[]*(v+1) for _ in range(v+1)] INF = float('inf') for _ in range(e): a,b,c = map(int,input(..
18352번: 특정 거리의 도시 찾기 (acmicpc.net) 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 단순 다익스트라 문제. 늘 풀던 것과는 다르게 거리정보 없이 그냥 1. graph리스트에 방향정보를 저장. dist리스트에 출발노드에서의 거리를 모두 저장 ~다익스트라 이용 : 힙큐모듈이용 q 리스트 생성. 출발노드 저장. dist에 출발노드는 거리 0 저장. while 반복문으로 q 끝날때까지 돌기! q에서 거리정보가장작은애 p..
문제 https://www.acmicpc.net/problem/17835 17835번: 면접보는 승범이네 첫째 줄에 도시의 수 N(2 ≤ N ≤ 100,000), 도로의 수 M(1 ≤ M ≤ 500,000), 면접장의 수 K(1 ≤ K ≤ N)가 공백을 두고 주어진다. 도시는 1번부터 N번까지의 고유한 번호가 매겨진다. 다음 M개의 줄에 걸쳐 www.acmicpc.net 풀이 도시의 개수만큼 다익스트라 계산하면 대략 10억번의 연산이 수행되어 시간초과가 나온다. 모든 도시에서 면접장으로 갈 수 있는 경로가 항상 있음 -> 면접장에서 도시로 향하는 다익스트라 가능 -> 도시의 연결 정보 입력 시 역방향으로 관계 지정해야 함. (도시: arr / 면접장: targets) 다익스트라에서 탐색 할 도시 리스트 ..
https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 1. 문제풀이 위치가 X일 때 X-1 또는 X+1로 이동하거나 2*X의 위치로 순간이동할 경우 1초가 소모된다. 이동 방법은 3가지임을 알 수 있으며 동일한 시간이 소모됨을 확인할 수 있다. 각 방법에 대하여 시간이 1초가 소모되는 가중치가 동일한 상황이므로 너비 우선 탐색을 시행하여 최단 시간을 구한다. 현재 위치에서 각 방법으로 이동 한 결과를 큐에 넣은 ..
문제 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 풀이 일반적인 다익스트라 문제와 비슷하다. dijkstra() 부분은 큰 차이점이 없다. 양방향이므로 graph에 양쪽 모두 추가해주고, 이 부분을 주의해야한다. d1 = dijkstra(1) d2 = dijkstra(v1) d3 = dijkstra(v2) res = min(d1[v1]+d2[v2]+d3[N], d1[v2]+d3[v1]+d2[N])..
![]()
문제 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net Algorithm 다익스트라 문제이다. 문제에서 버스가 왕복하지 않으므로 양방향이 아닌 단방향으로 그래프에 값을 넣어주면 된다. 시작지점을 입력받아 주어진 출발점을 설정하고 다익스트라 알고리즘을 실행해 주면 된다. 문제에서 '출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.'로 제시해주었으므로 시작지점부터 다른 노드들 사이의 최소가중치를 가지고 있는..
![]()
문제: 17608번: 막대기 (acmicpc.net) 17608번: 막대기 아래 그림처럼 높이만 다르고 (같은 높이의 막대기가 있을 수 있음) 모양이 같은 막대기를 일렬로 세운 후, 왼쪽부터 차례로 번호를 붙인다. 각 막대기의 높이는 그림에서 보인 것처럼 순서대로 www.acmicpc.net 코드 코드 설명 위 문제는 막대기를 차례대로 쌓고, 우측에서 보았을 때 볼 수 있는 막대기의 수를 구하는 것이다. 따라서, 마지막에 쌓은 막대기를 기준으로 총 볼 수 있는 막대기의 개수를 계산을 해야하므로, 스택을 사용을 해주었다. 따라서, 차례대로 입력된 막대기의 높이들을 스택에 넣어주었다. 입력을 끝낸 후, 스택을 돌아보면서, 임의의 변수 max에 현재까지의 막대기의 최고 높이를 저장한 후, 더 큰 높이를 가진 ..
![]()
Problem Solution 변수 및 데이터 입력**: `n`, `m`, `k`를 입력받는다. `INF`라는 상수를 사용하여 무한을 나타낸다. `INT_MAX`는 C++에서 정수의 최댓값을 나타내는 상수이다. `graph`는 정점과 간선 정보를 저장하는 2차원 벡터이고 `distance`는 각 정점까지의 최단 거리를 저장하는 배열로 초기값은 모두 무한으로 설정한다. `m`번 만큼 간선 정보를 입력받아 `graph`에 저장하고 각 간선은 시작 노드, 도착 노드, 비용으로 구성한다. `dijkstra` 함수를 정의한다. 우선순위 큐 `q`를 사용하여 노드까지의 최단 거리를 기준으로 노드를 선택하고 알고리즘을 통해 시작 노드로부터 각 노드까지의 최단 거리를 계산하고 `distance` 배열에 저장한다. `d..
![]()
https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 알고리즘 분류 구현 시뮬레이션 문제 로봇 청소기와 방의 상태가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 방은 N*M 크기의 직사각형으로 나타낼 수 있으며, 1*1 크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북 중..
