본문 바로가기

ALGORITHM

 (212)
백준 1647 도시 분할 계획 (Java) 1. 문제 링크 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. MST 문제로 크루스칼 알고리즘을 이용했다. 2. 노드를 가중치 기준으로 정렬한다. 3. 두 집이 연결되어 있지 않다면 연결한다. 4-1. 1번 코드는 전체를 다 연결하고 최대 연결 수까지의 값을 더한 것이다. 4-2. 2번 코드는 전체를 다 연결하고 최댓값 하나만 빼준 것이다. 4. 코드 import java.io.BufferedReader; import jav..
백준 18430 무기 공학 (Java) 1. 문제 링크 18430번: 무기 공학 첫째 줄에는 길동이가 가지고 있는 나무 재료의 세로, 가로 크기를 의미하는 두 자연수 N, M이 주어진다. (1 ≤ N, M ≤ 5) 다음 N개의 줄에 걸쳐서, 매 줄마다 나무 재료의 각 위치의 강도를 나타내 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. DFS 탐색을 통해 만들 수 있는 모든 부메랑의 경우를 찾는다. 2. 방문하지 않은 곳에서 만들 수 있는 4가지 부메랑을 만들어본다. 2-1. 각 부메랑의 조건을 통과하면 방문처리 후 dfs를 진행한다. 2-2. DFS가 끝나고 돌아오면 방문처리를 다시 원래대로 돌려둔다. (다른 경우에 영향 끼치지 않도록) 4. 코드 import java.io.BufferedReader; import..
백준 2156 포도주 시식 (Java) 1. 문제 링크 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. dp로 풀었다. 2. 2번째 잔까지는 3연속을 신경쓰지 않아도 되기에 더한 값을 넣는다. 3. 3번째 잔 부터는 연속 3개가 안되기 때문에 비교하여 더 큰 값을 저장했다. 3-1. 지금잔을 선택하지 않는 경우 3-2. 하나 앞의 잔을 선택하지 않고, 지금 잔을 선택하는 경우 3-3. 두개 앞의 잔을 선택하지 않고, 하나 앞의 잔과 지금 잔을 선택하는 경우 4. 코드 import java.io.Buffe..
백준 12886 돌 그룹 (Java) 1. 문제 링크 12886번: 돌 그룹 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. A, B, C를 입력받고, 만들 수 있는 돌 개수로 2차운 배열을 만든다. 2. 3 그룹의 합이 3의 배수가 아니라면 같은 개수로 나눌 수 없다. 3. DFS 탐색을 진행하며 A, B, C가 같은 개수가 나오는지 확인한다. 3-1. A와 B, B와 C, C와 A를 각 단계에서 전부 비교해보면서 나오는지 확인한다. 3-2. 방문 배열을 통해 작은 값과 큰 값이 나왔었는지 확인하고, 그 값들로 DFS..
백준 14442 벽 부수고 이동하기 2 (Java) 1. 문제 링크 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. 입력을 받고 시작 위치인 0,0에서 부순 벽 개수 0으로 시작한다. 2. BFS로 돌면서 방문 처리를 한다. (해당 위치에서 몇개의 벽을 부쉈는지 확인) 3. size만큼 반복하면서 이동 거리를 더한다. 4. 큐에서 하나씩 뺀다. 4-1. 뺀 위치가 종료 위치라면 끝낸다. 4-2. 아니라면 사방탐색을 진행한다. 4-3. 해당 위치에 벽이 없으면 현재 부순 벽 개수로 ..
백준 2166 다각형의 면적 (Java) 1. 문제 링크 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. 다각형의 면적은 삼각형으로 나눠서 구할 수 있다. 2. 다각형을 이루는 순서대로 주어지기 때문에 반복문을 통해 구했다. 3. 첫번째 점을 기준으로 2개씩 순서대로 고르면서 삼각형의 면적을 구했다. 4. 답이 음수가 나오는 경우가 있어 절댓값으로 출력했다. +) 값의 범위를 생각하면 int가 아니라 long으로 구해야 한다는 것을 주의하자 4. 코드 import java.io.BufferedReader; import java.i..
백준 14620 꽃길 (Java) 1. 문제 링크 https://www.acmicpc.net/problem/14620 14620번: 꽃길 2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다. 진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. 입력받은 칸의 수 중에서 조합으로 3칸을 고른다. 1-1. 전체 칸 수에서 조합으로 뽑은 수를 N으로 나눴을 때 몫이 행, 나머지가 열을 뜻한다. 2. 3칸을 사방탐색하면서 5칸을 방문한다. 2-1. 방문했을 때, 화단을 넘어가거나 방문했을 경우에는 끝낸다. 2-2. 총합이 지금의 최솟값을 넘으면 끝낸다. 3. 다 돌고 최솟값을 출력..
백준 1965 상자넣기 (Java) 1. 문제 링크 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 최장증가수열 개념을 그대로 쓰면 되는 기본적인 문제이다. 2번째 코드는 이진탐색을 이용한 코드이다. 4. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new Buff..

티스토리툴바