본문 바로가기

백준 PS일지

 (101)
[백준/Swift] 11404: 플로이드 PS일지. 문제 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 간단한 문제 요약 n개의 도시가 있다. 한 도시에서 출발하여 다른 도시에 도착하는 m개의 버스가 있다. 각 버스는 사용시 필요한 비용이 있다. 모든 도시 쌍에 대해서 도시 A -> B로 가는 최단 경로를 구하시오!! 고려해야 할 사항 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다!! 문제에서 주여졌습니다. 즉, 문제 input에서 A -> B로 가는 비용 10 을 입력 받았는데 A -> B로 가는 비용 5 를 추가로 입력 받을 수 있다는 것입..
[백준/Swift] 1504: 특정한 최단 경로 문제 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 간단한 문제 요약 방향성 없는 그래프가 주어진다. 1->N 정점으로 최단 거리로 이동하려고 한다. 이때 문제에서 주어진 임의의 두가지 정점은 반드시 통과해야 한다. 물론 한번 이동했던 정점, 간선을 다시 이동할 수 있다.(최단 경로로 이동한다는 전제하에) 1 -> N까지 최단 경로를 갈 때 반드시 임의의 두 정점 v1, v2를 거쳐 최단 경로를 가는 경로 길이를 출력 해야한다. 고려해야 할 사항 v1 -> v2로..
[백준/Swift] 1927 : 최소힙 문제 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 간단한 문제 요약 배열에 자연수를 넣는다. 입력값이 0이 나오면 배열에서 가장 작은 값을 출력하고 제거한다. 만약 배열에서 가장 작은 값을 출력 후 제거해야 하는데 비어있다면 0을 출력한다. 문제 풀이, 느낀점 배열은 heap을 사용해서 따로 만들지 않았다. 매 입력마다 0일 때 heap에 원소가 있는지 없다면 0을 있다면 heap에서 pop된 값을 출력해 나가면 된다. 추가로 print()함수를 매번 쓰는 것 보다 string으로 저장..
[백준/Swift] 1261: 알고스팟 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 간단한 문제 요약 시작 (1,1) 탈출 칸 (N,M). 시작 칸에서부터 미로를 탈출해야 한다. 벽이 있는 경우 벽을 부수면서 탈출해야 하는데 벽을 최소한으로 부숴서 탈출 지점까지 도착해야 한다. 문제 풀이, 느낀 점 문제 선정은 다익스트라 파트에서 골랐다. 당연히 힙을 구현했고 힙을 이용해서 풀었다. 한 가지 낯설었던 것은 기존에 다익스트라 문제는 지점을 지날 때 가중치 값이 주어지는데 이 문제는 가중치가 없었다. 그래서 이전에 방문했던 칸..
[백준/Swift] 4482 : 녹색 옷 입은 애가 젤다지? 문제 (링크) 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 간단한 문제 요약 '도둑루피' 라는 검정색 루피를 획득하면 소지한 루피가 감소한다. N*N의 동굴에는 도둑 루피로 가득하다. 젤다는 [0][0]위치에 있고 출구는 맨 아래칸 [N-1][N-1]로 이동해야한다. 동굴의 각 칸은 도둑 루피가 있다. 잃는 금액을 최소로 해서 동굴의 출구로 이동해야 한다. 한번에 한 칸 이동할 수 있다. 고려해야 할 사항 도둑 루피 크기가 K인 특정 칸을 지나면 K루피를 잃는 다는 뜻 시작점 [0][0]..
[백준/Swift] 1238 : 파티/ 우선순위 큐 개념 정리, 최소 힙 개념 with 라이노님 Heap 정리 문제 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 간단한 문제 요약 각 마을에는 한명의 학생이 살고 있습니다. n명의 학생은 x번 마을에 모여 파티를 합니다. 이때 m개의 도로는 단 방향입니다. i 비용을 들여 도로를 지나갑니다. 고려해야 할 사항 N, M, X 입력은 1 부터입니다.. (X제약을 못봐서 계속 X위치를 다르게 구했다는..ㅠㅠ) 문제 풀이, 했갈렸던 점 x번을 제외한 마을 학생들은 각자가 갈 수있는 모든 마을에 대해 최단 경로를 구한 후 x일때의 최단 경로를 저..
[백준/Swift] 6087 : 레이저 통신 보호되어 있는 글입니다.
[백준/Swift] 2933: 미네랄 백준 2933 미네랄 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net BFS 문제 입니다. 간단한 문제 요약 두 사람이 동굴(R,C크기) 양쪽에 서서 번갈아가면서 막대기를 던집니다. 맨 처음 좌 -> 우 그 다음 우-> 좌 의 반복으로 던집니다. 미네랄 "x" 에 맞을 경우 미네랄이 파괴가 되는데 분리된 클러스터(땅과 닿지 않거나, 땅과 연결된 클러스터로 부터 분리된 경우)인 경우 중력에 의해 바닥으로 떨어집니다. 떨어지는 동안 클러스터 모양은 변하지 않습니다. 고려해야 할 사항 막대기는 특정 높이를 유지하며 날라간다. 이..

티스토리툴바