코딩 테스트
백준 13549 자바 - 숨바꼭질 3 문제
www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 앞선 숨바꼭질 문제와 차이점은 순간이동시 0초가 걸린다는 점이다. 이 때문에 앞서 풀었던 동일 시간에 3가지 방향을 처리하는 방법으로 해결하기 어려워졌다. 그래서 위치와 시간을 가지는 객체를 하나 만들고 처리하게 만들었다. 주의점이라면 3가지 방향으로가능 경우에서 순간이동을 하는 경우를 가장 먼저 계산해야한다는 것이다. 순간이동의 경우 시간이 들지않기 때문에 방문처리를 할 경우..
백준 12851 자바 - 숨바꼭질 2 문제
www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 이 문제는 앞서 풀었던 숨바곡질 문제 - wellbell.tistory.com/64 에서 동일 시간에 대한 중복을 체크하지않는 형태라고 보면된다. 중복은 현재에 대한 것만 중복체크를 하고 next에 관련해서 중복을 체크하지않고 count를 세는 방식인것이다. 현재에 대한 것을 중복 체크하는 이유는 현재를 체크할때 보다 뒤에 나오는 것들은 최소 시간보다 무조건 높기 때문이다...
백준 1697 자바 - 숨바꼭질 문제
www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 이문제는 bfs를 통해서 수빈이를 3가지 경우 모두 움직여보면서 방문처리를 하고 수빈이가 동생의 위치에 방문했을 경우의 시간을 출력하면되는 문제이다. 주의해야할 부분이라면 위치와 시간을 포함하는 자료구조(객체)를 만들지 않는 경우 시간을 잘 관리햐아한다는 것인데 큐가 빌때 까지 돌아야하지만 시간은 큐에 사이즈만큼 돌때마다 늘려야한다. 시간이 0초일때는 시작 지점 1개만 큐에 들어온다 ..
백준 2618 자바 - 경찰차 문제
www.acmicpc.net/problem/2618 2618번: 경찰차 첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5≤N≤1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1≤W≤1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄까지 www.acmicpc.net 처음에 두개의 경찰차의 위치와 사건의 위치를 그리디 알고리즘으로 풀면 될줄알았는데 만약 사건의 위치가 두 경찰차로부터의 거리가 같으면 이라는 생각과 함께 안된다는 걸 깨닫고 dp를 통해서 풀이를 진행했다. dp [x][y] = 첫 번째 경찰차의 위치가 x번째 사건이고 두 번째 경찰차의 위치가 y번째 사건에 있을 때 현재 위치에서 사건을 끝까지 해결할때 까지 이동하는 거리의 합의 최솟값으로 두고 dp..
백준 6549 자바 - 히스토그램에서 가장 큰 직사각형 문제
www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 스택을 통한 풀이로 스택에서 꺼낸 인덱스의 직사각형의 높이가 더 큰 경우 스텍에서 해당 인덱스를 꺼내서 계산 스택에서 꺼내지지 않고 순회가 끝나고도 스택에 있는 경우에 꺼내서 계산 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; impor..
백준 11438 자바 - LCA 2 문제
www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 1. dfs를 통해서 자신의 부모만 구함. 2. 이중 for문을 통해서 조상을 셋팅함 - tmp = ancestor[j][i-1]은 j의 2^i-1만큼 위에 있는 조상 - ancestor[j][i] 는 ancestor[tmp][i-1]; 나의 8(2^3)번째 조상은 나의 4(2^2)번째 조상의 4(2^2)번째 조상이다. 3. 두 노드의 가장 까까운 조상 출력 - 필요할 경우 swap - 더 깊이 있는 ..
백준 2169 자바 - 로봇 조종하기 문제
www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net 첫째 줄은 왼쪽 부터 오른쪽으로 dp를 셋팅하고 나머지는 좌우와 위 중 가장 큰값으로 dp를 만들면됨 다만 좌 & 위, 우 & 위로 구하고 그 중 큰값으로 dp를 셋팅하는 방식으로 해야합니다. 이유는 좌를 계산할때 우가 안되있기 때문에 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; i..
백준 10775 자바 - 공항 문제
www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 그리드를 기본으로 파인드유니온을 통해서 부모가 0 인경우 까지 구하는 방식 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; // 공항 문제 - 10775번 public class Airport { static int G, P; static int result =..