본문 바로가기

ALGORITHM

 (212)
백준 3187 양치기 꿍 (Java) 1. 문제 링크 3187번: 양치기 꿍 입력의 첫 번째 줄에는 각각 영역의 세로와 가로의 길이를 나타내는 두 개의 정수 R, C (3 ≤ R, C ≤ 250)가 주어진다. 다음 각 R줄에는 C개의 문자가 주어지며 이들은 위에서 설명한 기호들이다. www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 모든 곳을 돌면서 방문하지 않은 곳 중 양이나 늑대가 있는 곳에서 양의 수와 늑대의 수를 0으로 초기화하고 BFS 탐색을 한다. 시작 지점을 큐에 넣고 BFS 탐색을 시작한다. 큐에서 뺀 곳이 늑대일 경우 늑대의 값을 증가하고, 양일 경우 양의 수를 증가한다. BFS를 끝내고 다시 왔을 때, 양이 많으면 양만 살아남고, 나머지의 경우에는 늑대만 살아남는다. 4. 코드 import java.io..
백준 16139 인간-컴퓨터 상호작용 1. 문제 링크 16139번: 인간-컴퓨터 상호작용 첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. 누적합을 이용해 길이마다 알파벳 26개의 누적합이 저장된 배열을 만든다. 2. 입력받은 알파벳에서 시작-1과 끝의 값 차이를 출력한다 4. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { public static void main(String[]..
백준 15685 드래곤 커브 (Java) 1. 문제 링크 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. 0세대 드래곤의 위치를 넣은 상태로 드래곤 커브를 시작한다. 2. 지금 위치에서 세대가 끝날 때까지 반복한다. 2-1. 새로운 세대는 기존 세대에서 회전이 필요하기 때문에 회전이 시작되는 부분인 끝점부터 시작점까지 역순으로 넣는다. 2-2. 끝점 기준 시계 방향은 지금 방향의 반시계이므로 주어진 방향과 동일하게 사용하기 때문에 +1한 값을 넣는다. 3. 모든 방향을 다 넣었다..
백준 1915 가장 큰 정사각형 (Java) 1. 문제 링크 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 예전에 올렸던 목장 건설하기와 거의 같은 문제이다. 0은 true로, 1은 false로 저장한다. 0이 나오면 해당위치에서 (-1, 0), (-1, -1), (0, -1)의 dp 중 최솟값을 선택하고 1을 더한 값으로 저장한다. 2-1. 세 좌표는 정사각형의 각 모서리로 포함되는 위치들이다. 2-2. 그 중 제일 작은 값만큼만 만들 수 있고, 지금 자리도 포함할 수 있으니까 1을 더한다. 좌표에서 dp를 구할 때마다 최댓값을 갱신한다. 4. 코드 import java.io.B..
백준 11651 좌표 정렬하기 2 (Java) 1. 문제 링크 11651번: 좌표 정렬하기 2 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 입력받은 x, y를 Point에 넣는다. Comparable를 이용해서 y 좌표가 같을 경우 x 좌표를 비교하게 한다. Point를 넣은 pq가 빌 때까지 빼면서 뺀 값의 x, y 좌표를 출력한다. 4. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputS..
백준 5052 전화번호 목록 (Java) 1. 문제 링크 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. N개의 전화번호를 입력받아 list에 넣는다. 2. list를 정렬한다. (문자열) 3. 비교 문자열보다 길이가 긴 경우에만 앞의 문자열만큼에서 같은지 판단한다. 3-1. 비교 문자열과 동일할 경우 일관성을 유지하지 못해 끝낸다. 4. 비교 문자열을 현재 문자열로 바꾼다. 5. 위의 과정을 반복하고 출력한다. 4. 코드 import java.io.BufferedReader; i..
백준 1303 전쟁 - 전투 (Java) 1. 문제 링크 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 입력이 W와 B 2개로 구성되어 있어서 boolean 배열로 만들었다. 아군의 경우와 적군의 경우를 별도로 탐색했다. 아군인 경우에는 true이면서 방문하지 않은 곳을 탐색 시작으로 한다. bfs에서는 사방 탐색을 진행하는데 범위 안에 있으면서 방문하지 않은 곳을 탐색한다. 큐에서 꺼낸 수만큼이 연결되어 있는 것으로 그 수를 반환한다. sum에 그 수의 제곱만큼씩 더해 위력의 합을..
백준 1461 도서관 (Java) 1. 문제 링크 1461번: 도서관 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. 책의 위치를 입력받으면서 양수인 경우와 음수인 경우를 따로 저장한다. 2. 양수와 음수 리스트를 정렬한다. 3. go 를 이용해서 거리를 구한다. 3-1. 양수, 음수 따로 한다. 3-2. 한 번에 갈 수 있는 M번째마다 이동하는 거리의 2배를 더한다. (갔다 왔다) 4. 위치 중 가장 멀리있는 값을 마지막으로 가기 때문에 결과에서 뺀다. 4. 코드 import java.io.BufferedReader; ..

티스토리툴바