본문 바로가기

분류 전체보기

 (102)
[백준] 2217번: 로프 문제링크 : https://www.acmicpc.net/problem/2217 문제풀이 각 로프의 최대 중량이 아래와 같다고 하면, 1) 5짜리 로프를 선택, 최대 5만큼의 중량이 걸린다고 하면, 세 로프로 들 수 있는 최대 중량은 5 X 3 = 15가 된다. 2) 8짜리 로프를 선택, 최대 8만큼의 중량이 걸린다고 하면, 5짜리 로프로는 들 수 없다. (최대가 5이므로) 따라서 8, 13짜리 로프에 각각 8씩 걸리게 되어 최대 중량은 8 X 2 = 16이 된다. 3) 13짜리 로프를 선택, 최대 13만큼의 중량이 걸린다고 하면, 5와 8짜리 로프는 사용할 수 없다. 따라서 13짜리 로프로 들 수 있는 최대 중량은 13 X 1 = 13이 된다. 따라서 이 경우 최대 중량은 2번으로 도출된 16이 된다. ..
[백준] 11812번: K진 트리 문제링크 : https://www.acmicpc.net/problem/11812 문제풀이 처음엔 DFS로 풀으려고 했는데, 부모노드까지 갔다가 되돌아 오는 작업이 생각보다 복잡했다. LCA 알고리즘 분류에 속한다고 적혀있어서 알고리즘을 찾아보았다. LCA 알고리즘이란 공통 조상을 찾는 알고리즘을 말한다. 즉 입력받은 각 두 노드가 공통된 조상을 가질 때 까지 이동한 거리를 합하면, 두 노드 사이의 거리가 된다. 그러면 먼저 각 노드의 부모 노드를 구해야 하는데, 부모 노드의 번호는 다음 공식으로 구할 수 있다. 이 공식을 이용하여, 두 노드의 부모가 같아질 때 까지 거리를 증가시키면 된다. 위와 그림과 같은 경우 거리는 4가 된다. 7 → 2 → 1 (거리 : 2) 8 → 3 → 1 (거리 : 2) --..
[백준] 1057번: 토너먼트 문제링크 : https://www.acmicpc.net/problem/1057 문제풀이 문제에서 라운드마다 번호가 1부터 다시 매겨진다고 했던 것이 힌트인 것 같다. 테스트 케이스를 예로 들면, 8번 9번은 라운드가 끝날 때 마다 아래와 같이 번호가 바뀐다. 8 → 4 → 2 → 1 9 → 5 → 3 → 2 결국 김지민과 임한수의 번호가 같게 되면, 그 라운드에서 대결을 하게 된다. 서로 대결을 하지 않는 경우 -1을 출력하라고 해서 while문에 조건을 어떻게 추가해야 하나 고민했는데.. 김지민과 임한수는 서로 대결하기 전까지 항상 이긴다는 조건이 있으므로, 대결을 하지 않는 경우는 없는 것 같다. 소스코드 package baekjoon; import java.io.BufferedReader; impo..
[백준] 1149번: RGB거리 문제링크 : https://www.acmicpc.net/problem/1149 문제풀이 처음엔 주어진 테스트 케이스를 보고도 이해가 잘 안갔는데, 동적 계획법으로 풀 수 있는 문제였다. 문제와 같은 경우, 아래와 같이 칠을 하면 최솟값 96이 나온다. 집 a부터 차례로 색을 칠한다고 하면, 칠할 수 있는 경우는 아래와 같다. b집을 빨강으로 칠한다고 하면, 옆집인 a는 초록 또는 파랑으로 칠할 수 밖에 없다. 따라서 b를 빨강으로 칠했을 때 최소비용은 a를 초록으로 칠했을 때 드는 비용, a를 파랑으로 칠했을 때 드는 비용 중 최소 비용을 더한 값과 같다. 마지막 집 c를 빨강으로 칠했을 때 최소비용은 색칠한 칸들의 네가지 경우 중 가장 최소비용을 더한 값과 같다. 따라서, i번째 집에 오기까지 최소비용..
[백준] 2562번: 최댓값 문제링크 : https://www.acmicpc.net/problem/2562 문제풀이 데이터를 입력받을 때마다 그 값이 최댓값인지 비교해서 저장해놓은 후 출력한다. 소스코드 package baekjoon; import java.io.*; public class P2562 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int max = 0; int index = 0; for (int i = 0; i < 9; i++) { int num = Integer.parseInt(br.readLine()); if (num ..
[백준] 2164번: 카드2 문제링크 : https://www.acmicpc.net/problem/2164 문제풀이 처음엔 규칙을 찾아서 풀으려고 했는데, 이 문제는 Deque를 사용해서 푸는 문제가 맞는 것 같다. 문제에 나온 순서대로 값 추가 / 삭제를 하면 된다. Deque : https://manzoo.tistory.com/83 소스코드 package baekjoon; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Deque; public class P2164 { public static void main(String[] ar..
[자료구조] Deque Deque이란? (Double-ended Queues의 줄임말. 디큐라고 발음하는 줄 알았는데 덱 / 데크라고 한다.) 스택과 큐를 합쳐놓은 자료구조라고 생각하면 쉽다. 앞과 뒤에서 삽입/삭제가 가능하다. Java에서 사용법 1. 선언 Deque deque = new LinkedList(); Deque deque = new ArrayDeque(); Deque를 구현할 때 보통 LinkedList와 ArrayDeque를 사용한다. (성능차이) - 양 끝의 데이터를 add / remove할 때 : ArrayDeque > LinkedList - 반복 작업에서 현재 요소를 삭제할 때 : ArrayDeque < LinkedList 참고 : https://stackoverflow.com/questions/61631..
[LeetCode] 4번: Median of Two Sorted Arrays 문제링크 : https://leetcode.com/problems/median-of-two-sorted-arrays/ 문제풀이 두 배열을 합쳤을 때 중간 값을 출력하는 문제이다. 홀수 개 일 때는 중간 값 출력, 짝수 개 일 때는 중간 두 값의 평균을 출력한다. 문제를 보니 병합정렬이 생각나서 그 방식을 떠올리며 문제를 풀었다. 1) nums1과 nums2의 길이를 더한 만큼의 크기로 배열을 생성한다. 2) 각 배열의 첫번째 값, nums1[0]과 nums2[0]를 비교한다. 더 작은 값을 nums 배열에 넣는다. 3) 이전 작업에서 nums1[0] 값을 넣었으므로, 다음 값을 비교한다. nums1[1]과 nums2[0]을 비교해 더 작은 값을 nums 배열에 넣는다. (이하반복) 4) 2~3 작업을 반..

티스토리툴바