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에 저장한다 양수값이 하나도 없다면 ..
이전글 https://fladi.tistory.com/329 [JAVA] 백준 sorting - 실버모음 1181 단어 정렬(실버5) https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 fladi.tistory.com 1302 베스트설러(실버4) https://www.acmicpc.net/problem/1302 1302번: 베스트셀러 첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 ..
1181 단어 정렬(실버5) https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 저번에 풀었던 문제다! (2달전 쯤) 중복된 단어는 하나만 남기고 제거해야한다는 것에서 set냄새가 난다 정렬을 해야하는 set이라면 treeset을 사용하는 게 좋을 것 같다 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br...
