코딩 테스트/백준
백준 17071 자바 - 숨바꼭질 5 문제
www.acmicpc.net/problem/17071 17071번: 숨바꼭질 5 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 숨바꼭질 5에서는 동생이 움직이며 범위가 50만으로 증가한 조건이 주어집니다. 동생이 움직이기때문에 동일한 시간에 동일한 위치에 있어야만 합니다. 숨바꼭질 문제로 풀게 될 경우 수빈 : 3 → 6 → 12 동생 : 6 → 7 → 9 → 12 수빈은 2초에 12자리에 가서 방문처리를 하게되면 동생이 3초에 12에 도달하면서 12의 방문처리가 되어 있기 때문에 3초를 반환하게 ..
백준 13913 자바 - 숨바꼭질 4 문제
www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 숨바꼭질 문제의 확장으로 이전 위치를 배열에 넣어놓고 stack을 통해서 출력하게 하면 됩니다. 숨바꼭질 문제 - wellbell.tistory.com/64 랑 차이점이 거의 없어서 쉽게 해결할수 있습니다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; imp..
백준 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 - 더 깊이 있는 ..