개발개발

1. 문제 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 2. 풀이 BFS를 통해 상어의 위치를 이동해가며, 먹을 수 있는 물고기 중 가장 작은 거리를 선택하고 더이상 먹을 수 없는 물고기가 없을 때까지 이 과정을 반복해 답을 구한다. 전체적인 풀이 과정은 아래와 같다. 상어의 위치를 저장하고, 상어의 위치에서부터 탐색을 시작한다. 상어의 위치에서 BFS를 해 상어의 위치를 이동시킨다. 상어가 갈 수 있는 경우는 (1) 상어의 크기보다..

1. 문제 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 2. 풀이 백트래킹을 이용해 풀이한다. 백트래킹을 통해 치킨집을 하나씩 선택하며 총 m개의 치킨집을 선택한다.(backTracking()) 백트래킹을 하기 위해, 방문여부를 나타내는 boolean[] visited을 사용한다. m개의 치킨집을 고른 경우, 도시의 치킨 거리를 구한다(getChickenDist()). 최소 도시의 치킨 거리를 구한다.(Math.min(..

1. 문제 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 2. 풀이 n일에 받을 수 있는 최대 수익을 기억하기 위해 DP 배열을 사용한다. 날짜 범위 내에 일 종료가 가능한 경우(i + time[i]

1. 문제 https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 2. 풀이 오른쪽에서 레이저를 쏘기 때문에 오른쪽으로 시작 할 수 있지만, 그렇게 하면 최악의 경우 N!의 복잡도가 발생할 수 있다. 따라서, stack을 활용해 오른쪽부터 계산한다. 풀이 과정은 아래와 같다. 탑의 위치와 높이를 스택에 모두 저장하기 위해 별도의 클래스를 만든다. 탑의 왼쪽부터 시작한다. while문을 이용해 stack에 있는 탑들을 돌아보며, 현재의 탑 높이가 스택..

1. 문제 https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 2. 풀이 BFS로 풀이했다 (1) n층을 최소한의 버튼을 눌러 도착했을 때의 버튼 누른 횟수를 저장하는 배열(minBtn)을 사용해 정답을 구하고, 중복을 체크하는데 사용한다. (2) 위의 최소 버튼 누른 횟수를 저장하는 배열(minBtn)에서 시작점의 버튼 누른 횟수를 0이 아닌 1로 처리해, 시작점과 처음 도착한 층의 차이점을 만들어 처리한다. (3) 맨 마지막 정답을 처리할때, +1 한 값을..

1. 문제 https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 2. 풀이 BFS를 써서 풀이한다. 처음에는 큐에서 poll 했을때 촌수를 높이는 걸로 처리를 했는데, 그렇게 하면 연결되지 않는(?), 결과에 상관없는 촌수를 계산할 때까지 더하기 처리가 나서 실패했다. 그래서 기준점을 잡아서, 기준점과의 촌수를 계산하는 배열을 따로 만들어 처리했다. 3. 코드 import java.util.Arrays; import java.ut..

1. 문제 https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 2. 풀이 시작점에서 부터 다익스트라로 최단 경로를 구한다. 도착점에서 부터 거슬러가며 최단 경로를 따로 표시한다. k[i][j] = 1; // i~j까지가 최단 경로면 1 원래의 리스트에 간선 중 최단 경로가 아닌 간선만 추가해 리스트 갱신 최단 경로를 뺀 간선으로만 다익스트라를 돌림 3. 코드 import java.io.*; import java.uti..

1. 문제 https://www.acmicpc.net/problem/3176 3176번: 도로 네트워크 첫째 줄에 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N-1개 줄에는 도로를 나타내는 세 정수 A, B, C가 주어진다. A와 B사이에 길이가 C인 도로가 있다는 뜻이다. 도로의 길이는 1,000,000보다 작거나 같은 양 www.acmicpc.net 2. 풀이 처음엔 플로이드 와샬을 써야하는가....? 싶었지만 LCA를 써서 푸는 문제였다. LCA에서는 조상 노드들을 따로 저장하는 배열(parent)가 있는데, 이 때 노드에서부터 2^i번째 노드까지의 최솟값, 최댓값을 저장하는 따로 저장하는 것이 포인트다. 3. 코드 import java.io.*; import java.util.Array..

1. 문제 https://www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 2. 풀이 LCA를 구현하는 문제다. LCA는 최소 공통 조상을 구하는 문제다. LCA를 구현하기 위해 현재 노드의 부모를 2차원 배열에 저장하는 방법과 1차원 배열에 저장하는 방법이 있다. 1) 부모를 2차원 배열에 저장 부모를 2차원 배열에 저장할 경우 첫번째 차원에는 노드의 인덱스가 담기고 두번째 차원에는 노드의 2^i번째 조상 노드가 저장된다. 2) 부모를 1차원 배열에..

1. 문제 https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 2. 풀이 플로이드 와샬을 활용한 문제다. 문제의 예제에서 나온 그래프를 잘 보자. 여기서 순서를 정할 수 있는 노드는 뿐이다. 4보다 큰사람이 , 로 2명이고, 4보다 작은 사람이 , , 로 3명이므로 총 6명 중 나보다 큰 사람 2명, 나보다 작은 사람 3명 => 나는 3등 이라는 결론을 얻을 수 있는 것이다. 즉, 현재 노드가 다른 노드들과 모두 연결되어 있는 경우 순서를 따질 수 ..