https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 처음에는 수학적으로 풀고싶다고 생각했는데 쉽지않아서 그냥 탐색하는 식으로 풀기로 했다 bfs로 풀기로함. 이유는 다음과 같다 한 번 부으면 무조건 다 부어야함 물통은 3개 밖에 없음 붓다보면 나올 수 있는 케이스가 그렇게 많지 않을 것이다 또한 부피가 최대 200임 -> 정말 많지 않을듯 내 풀이 class Case { int A; int B; int C; public Case..
알고리즘
https://www.acmicpc.net/blog/view/9 세그먼트 트리 (Segment Tree) 글이 업데이트 되었습니다. https://book.acmicpc.net/ds/segment-tree 문제 배열 A가 있고, 여기서 다음과 같은 두 연산을 수행해야하는 문제를 생각해봅시다. 구간 l, r (l ≤ r)이 주어졌을 때, A[l] + A[l+1] + .. www.acmicpc.net 이 글을 참고하여 세그먼트 트리를 공부하였습니다 2042 구간 합 구하기 - 골드1 https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주..
보호되어 있는 글입니다.
백준 2565 전깃줄 문제가 너무 안풀려 구글링을 하다 LIS 알고리즘을 접하게 되었다. 브루트포스든 datastructure든 dp든 계속 파고들면 새로 배워야할 알고리즘이 보이는 것 같다. (브루트포스->백트래킹, datastructure->union-find, dp->LIS...) 공부가 끝이없다! ㅎㅎ 최장 증가 부분 수열(LIS: Longest Increasing Subsequence) 알고리즘이란? 원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하는 최대길이의 부분수열을 구하는 문제다. 예를 들면 다음과 같은 수열이 있다 6 2 5 1 7 4 8 3 이 수열에서 최장증가 부분수열은 2578 이다. LIS 풀이법 LIS 문제를 푸는 방..
2096 내려가기 - 골드5 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 작은 문제가 바로 보이는 문제! 그냥 배열을 내려가면서 가능한 최대값, 최솟값을 구하면 될 것 같다 마지막 줄에 도착했을 때 최댓값 3개중 가장 최대인 값/ 최솟값 3개 중 가장 최소인 값이 답 class Value { int min; int max; public Value(int min, int max) { this.min = min; this.max = max; } } publi..
11660 구간 합 구하기 5 - 실버1 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 그냥 지정된 범위의 합을 구하면 될 것 같아 이중 for문을 사용하여 더해봤다 -> 시간초과남ㅠ 아이디어가 떠오르지 않아서 구글링을 해봤다 이 문제는 누적합을 이용하는 문제였다! 애초에 값을 저장할 때 누적합을 저장했다 처음에는 행마다 따로 누적합을 구하는 방식을 사용함 xMin, yMin, xMax, yMax가 ..
배낭문제와 비슷한 류의 문제를 풀어봤는데, dp문제가 많이 약하다는 걸 알아냈다! 배열을 종이에 그리지 않으면 헷길리고, 문제를 제대로 풀 수 없는게 슬펐다. 그래서 손으로 그리지 않아도 머릿속으로 떠오르도록 많이 풀어 익숙해지려고 한다. 10844 쉬운 계단 수 - 실버1 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net dfs로도 풀릴 것 같다 -> 시간초과남 ㅜ dp로 풀어야겠다고 생각했지만 아이디어가 떠오르지 않아 구글링을 해봤다 풀이 설명 (dp가 진짜 참신한 것 같다. 이렇게 푸는 게 너무 신기하고 재밌다) 행은 1자리수 ~ N자리수 열은 어떤 자리..
1351 무한 수열 - 골드5 https://www.acmicpc.net/problem/1351 1351번: 무한 수열 첫째 줄에 3개의 정수 N, P, Q가 주어진다. www.acmicpc.net 일반적인 재귀방식은 시간이 너무 많이 들 것 같아 고민을 해봤다 재귀방식으로 필요한 값들을 일단 찾음 이미 구한 값들은 map으로 저장하여 다시 계산하지 않도록 함 class Main { private static Map map = new HashMap(); private static int p; private static int q; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(n..
이전 글(Union-Find 정리 글) https://fladi.tistory.com/348 [JAVA] Disjoint Set과 Union-Find 알고리즘(백준 1717 집합의 표현) 서론 백준 1717번 문제를 몇 시간동안 못풀어서 결국 구글링을 해봤는데, 이 문제는 Union-find알고리즘을 써야한다는 걸 알게되었다. Union-Find 알고리즘을 처음 접했을 땐 너무 참신해서 짜릿했다! fladi.tistory.com 이전에 Union-Find 알고리즘에 대해 공부했다 활용문제를 조금 더 풀고싶어 비슷한 문제를 풀어보려고 한다! 4195 친구 네트워크 - 골드2 https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진..
2841 외계인의 기타 연주 - 실버1 https://www.acmicpc.net/problem/2841 2841번: 외계인의 기타 연주 첫째 줄에 멜로디에 포함되어 있는 음의 수 N과 한 줄에 있는 프렛의 수 P가 주어진다. (1 ≤ N ≤ 500,000, 2 ≤ P ≤ 300,000) 다음 N개 줄에는 멜로디의 한 음을 나타내는 두 정수가 주어진다. 첫 번째 www.acmicpc.net 스택문제이다 기타줄에 따른 프렛을 스택으로 저장하면 될 것 같다 나보다 큰 프렛이 스택의 peek에 저장되어있다면 계속 뺀 후 나를 추가시키면 될듯 풀이 class Main { public static void main(String[] args) throws Exception { BufferedReader br = n..
