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) 가 주..
알고리즘/백준
보호되어 있는 글입니다.
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..
https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 어떻게 풀어야할지 감도 못잡았던 문제다ㅠㅠㅠ 점수순으로 정렬을 해야할 것 같은데, 그 뒤로는 어떻게 풀어야할지 아이디어가 떠오르지 않았다. 그리디도 아닌 것 같아 그냥 백트래킹으로 구현해봤더니 당연히 시간초과가 발생했다. 결국 풀이 방법을 구글링해봤다 이 문제는 그리디였다....(허무) 날짜를 내림차순으로 내려가며 뽑을 수 있는 최대의 이익을 뽑으면 된다고 한다. 풀이는 다음과 같다 그리디 풀이 class Task { int day; int..
11286 절댓값 힙 - 실버1 https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 절댓값이 작은 순으로 하되, 절댓값이 같다면 작은 게 앞으로 가게 구현하면 될 것 같다 PriorityQueue의 생성자에 Comparator를 넣으면 비교방식을 조정할 수 있을 것이다 첫 번째론 절댓값 기준으로 비교하고 절댓값이 같을 경우 크기기준으로 비교하고 크기도 같을 경우 그냥 1을 return하는 식으로 구현하면 될 듯 풀이 class..
