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..
2161 카드1 - 실버5 https://www.acmicpc.net/problem/2161 2161번: 카드1 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 길이가 7이라면 7+6+5+...+2+1 = (7+1)*7/2 길이의 배열을 만드는 방법도 사용할 수 있고 큐를 사용할 수 있다. 정수는 1000까지니까 최대 (1000+1)*1000/2 = 500500 길이의 배열이 만들어질 것이니까.. 큐를 사용하는 게 좋을 것 같다! 큐를 이용한 풀이 class Main { public static void main(String[]..
2605 줄 세우기 - 브론즈2 https://www.acmicpc.net/problem/2605 2605번: 줄 세우기 점심시간이 되면 반 학생 모두가 한 줄로 줄을 서서 급식을 탄다. 그런데 매일 같이 앞자리에 앉은 학생들이 앞에 줄을 서 먼저 점심을 먹고, 뒷자리에 앉은 학생들은 뒤에 줄을 서 늦게 점심을 www.acmicpc.net 리스트의 인덱스를 사용하여 풀어도 될 것 같고, 스택으로 원하는 만큼 뽑고 삽입해도될 것 같다 두 방법 모두로 풀어보겠다! 리스트 풀이 class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader..
24416 알고리즘 수업 - 피보나치 수 1 - 브론즈1 https://www.acmicpc.net/problem/24416 24416번: 알고리즘 수업 - 피보나치 수 1 오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍 www.acmicpc.net 그냥 하라는대로 따라가면 된다. 의사코드만 잘 구현하면 될듯 dp가 재귀호출보다 성능이 좋다는 걸 알려주려는 듯 하다 한 번 구한 값을 재활용하는 dp와 달리 필요할 때마다 계속 값을 구해야하는 재귀호출이 훨씬 성능이 나쁜 것을 알 수 있음 풀이 class Main { static int cnt1 = 0; static int ..
Dynamic programming(동적계획법)이란? 1950년대 Richard Bellman에 의해 개발된 알고리즘 패러다임 복잡한 문제를 더 간단한 하위 문제로 분해하여 단순화하는 것을 의미 간단한 문제의 해를 구하고, 이를 이용하여 복잡한 문제를 푼다 동적계획법 문제는 두 가지 특성을 가진다 1. 최적의 하위 구조 최적화 문제에 대한 솔루션이 해당 하위 문제에 대한 최적 솔루션의 조합으로 얻어낼 수 있다 작은 문제로 큰 문제를 해결할 때 사용되는 관계가 존재하고, 이를 함축적 순서라고 한다 2. 중첩되는 하위 문제 동적계획 알고리즘은 분할 정복 알고리즘과 구분된다 분할 정복 알고리즘은 해결이 어려운 문제를 분할하여 문제를 해결한다는 점에서 동적계획법과 비슷하지만 차이점이 존재한다. 동적계획법은 하위..
2467 용액 - 골드5 https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 이전에 비슷한(같은) 문제를 푼 적이 있는데, 그 때는 포인터 2개를 이용하여 문제를 풀었다 이번에는 이진탐색으로 풀어보려고 한다 산성과 알칼리 용액 모두 합쳐 오름차순 정렬한다 알칼리 용액들을 하나씩 빼면서 배열에서 내 절댓값과 가장 가까운 값을 찾는다 [작음, 작음, (같거나)큼, 큼, 큼, ...] 이런 꼴로 나올 것이기 때문에 lowerbound를 구해준다 l..
어느정도 이진탐색 기본기를 다진 것 같으니 활용을 열심히 해보자! 2512 예산 - 실버2 https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 처음부터 배정이 가능한 경우 -> 예산의 최댓값 출력 배정 불가능 경우 -> 상한액 출력 그냥 상한액을 이진탐색으로 찾는다고 생각하면 되겠다 배정이 가능하면 오른쪽을 탐색, 배정이 불가능하면 왼쪽 탐색 [가능, 가능, 가능, 불가능, 불가능, ...] 이런식으로 나올 것이니 upperbound값을 구하..
정렬관련 골드 문제를 풀다 이진탐색을 구현하는 연습이 부족하다는 걸 느꼈다. (start와 end 인덱스를 어디를 잡아야할 지 헷갈렸음) 그래서 이번 기회에 이진탐색 문제 몇 개를 풀어보려고 한다! 공부할 수록 공부해야할 게 늘어나는 것 같다 ㅎㅎ 이진탐색이란? 리스트를 두 부분으로 나눠 필요한 부분에서만 탐색하도록 제한하여 원소를 찾는 방법이다 ex) [ 1 2 3 4 5 6 7 8 9 ] 와 같이 오름차순으로 정렬된 리스트가 있고 3을 찾아야한다 일단 1~9번째 원소의 중간인 5를 본다 5는 3보다 크니 탐색범위를 1~4로 줄인다 1~4번째 원소의 중간인 2를 본다 2는 3보다 작으니 탐색범위를 3~4로 줄인다 .. 이 과정을 반복하여 3을 찾아냄 이진탐색을 위해서는 정렬이 필수적이며, 평균적으로 순..
실버문제를 어느정도 풀어봤으니 이제 sorting 관련 골드 문제를 풀려고한다! https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 10억까지 정수로 나타내지고, 합은 최대 20억정도가 될 수 있으니 int값에 저장할 수 있음 처음 생각한 풀이(시간초과) 음수값을 저장하는 배열과 양수값을 저장하는 배열을 만들어 정렬한다 인덱스로 비교비교하면서 차이가 0에 가까운 애를 result에 저장한다 양수값이 하나도 없다면 ..
