공부공간

www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 각 정점에서 최대거리 ( x + y = 1000칸 움직임 ) 에 편의점이있거나 현재 정점에서 페스티벌위치까지 갈수있는지 판단하기 위해서 재귀함수를 이용하여 매 정점을 체크해준다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public st..

www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리 www.acmicpc.net 0부터 ~ 최대 Capacity 까지의 수를 이분탐색으로 구하고, 구한 숫자로 유량을 보낼 수 있는지? 확인하는 이분탐색 + bfs 문제 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.ArrayList; impor..

www.acmicpc.net/problem/14889 1717번: 집합의 표현 첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 �� www.acmicpc.net N명이 속한 축구팀을 N/2 N/2씩 나누기위해 비트연산을 이용한다. 0~(1

https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1≤n≤50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 미로의 방문체크를 N^2 으로하면서 최단경로를 Deque로 계산한다. package algorithm; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.StringTokenizer; public class 미로만들기 { public static void m..

https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 시뮬레이션 + 완전탐색 문제.. 동일한 최단거리 중 조건에 맞는 승객을 태우기 위하여 우선순위 큐를 활용한다. 반례로, 한명의 승객의 도착점이 다른 손님의 출발점이 될수 있으므로 VISIT처리시 현재 내위치도 탐색하는 경우를 생각하서 모델링 하면된다! package algorithm; import java.io.BufferedReader; import jav..

https://www.acmicpc.net/problem/16930 16930번: 달리기 진영이는 다이어트를 위해 N×M 크기의 체육관을 달리려고 한다. 체육관은 1×1 크기의 칸으로 나누어져 있고, 칸은 빈 칸 또는 벽이다. x행 y열에 있는 칸은 (x, y)로 나타낸다. 매 초마다 진영이는 www.acmicpc.net NXM맵에서 직선방향으로 K만큼 이동할때에, 목적지까지 갈수있는 최단 시간을 구하는문제이다. 최단시간이고 N,M이 1000이라 BFS로 풀릴것같았다. 먼저, K만큼 1 ) 이동중 범위를 벗어나는경우 2 ) # 벽을 만나는경우 이 두가지의 경우에는 K를 break처리해주었다. import java.io.BufferedReader; import java.io.InputStreamReader..

https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 상어의 움직이는 칸수 ( 최대 3칸 ) 에따라서 DFS를 구현하면 풀리는 문제이다. 매 DFS STEP마다 최댓값을 갱신하여준다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Comparator; import java.util.PriorityQueue; import java.ut..

https://www.acmicpc.net/problem/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문�� www.acmicpc.net 노드간 사이클을 찾는 문제였다. DFS풀이는 바로생각났지만, BFS로 궁금한점이 생겨서 테스트해봤던 문제, 사이클이 존재하면 최단거리로 도달하는 시간만 체크해주면 풀릴거같았다. 예를들어 AAAAA BBBBA AAABA ABABA AAAAA 와 같은 입력에서 어느 A에서 시작하더라도, 같은 시간으로 도달하는 한점이 생긴다 => 사이클이있다. 이 가설?같은거를 증명해보았는데 문제제약조건인..