알고리즘 (40) 썸네일형 리스트형 [백준 2293 : JAVA] 동전1 / Dynamic Programming 개요 dp 문제는 이전의 구한 값을 통해 현재 원하는 값을 도출하는 방식이다. 이 문제에서는 중복만 제거한다면 풀이가 가능하다. 또한, 만들고 싶은 금액을 기준으로 한다. 문제 n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 입력 풀이 dp[] 배열을 선언한다. dp[i] = j 라고 하면, 다음과 같다. i → 금액 j → i원을 만드는데 가능한 경우의 수 dp[i] = dp[i] + dp[i - coin]이다. 문제와 같은 입력이 주어졌을 때 1원 짜리 동전으로 1원 부터 10원.. [백준 7579 : JAVA] 앱 / Dynamic Programming 개요 전형적인 dp문제로 dp배열을 선언하여 풀이할 수 있다. 처음에 문제를 접근 할 때 메모리값을 dp[][] 배열의 인덱스로 잡으면 메모리초과가 난다는 것을 인지하고 비용을 기준으로 잡고 문제에 접근할 것이다. 문제 우리는 스마트폰을 사용하면서 여러 가지 앱(App)을 실행하게 된다. 대개의 경우 화면에 보이는 ‘실행 중’인 앱은 하나뿐이지만 보이지 않는 상태로 많은 앱이 '활성화'되어 있다. 앱들이 활성화 되어 있다는 것은 화면에 보이지 않더라도 메인 메모리에 직전의 상태가 기록되어 있는 것을 말한다. 현재 실행 중이 아니더라도 이렇게 메모리에 남겨두는 이유는 사용자가 이전에 실행하던 앱을 다시 불러올 때에 직전의 상태를 메인 메모리로부터 읽어 들여 실행 준비를 빠르게 마치기 위해서이다. 하지만 스.. [백준 10942 : JAVA] 펠린드롬? / Dynamic Programming 개요 dp를 이용해서 풀이할 수 있다. 1 2 1 3 1 2 1 수열이 주어졌을 때 dp[][]를 선언하고 dp[i][j]에서 i → 검사하고 싶은 시작 인덱스 j → 검사하고 싶은 끝 인덱스 라고 생각하고 접근한다. dp문제는 이전에 구한 dp값을 이용해서 현재 원하는 dp값을 구하는 방식이다. 나는 처음에 문제에 접근할 때 시작 점과 끝을 기준으로 dp값을 구하였다. 하지만 이 문제는 길이가 1일 때 펠린드롬인지, 2일 때 펠린드롬인지 ... 을 통해 dp값을 구하면 쉽게 구할 수 있다. 문제 명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다. 먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다. 각 질문은 두 정수 S와 E로 나타낼 수 있으며, S번째 수부터 E.. [백준 1655 : JAVA] 가운데를 말해요 / PriorityQueue 개요 PriorityQueue를 이용하여 풀 수 있는 문제이다. 해당 자료구조에 대한 이해도가 없는 사람들은 기초 문제부터 풀고 오면 좋을 것이다. 문제를 읽어보면 오름차순 정렬을 했을 때 가운데 인덱스에 있는 값을 찾는 문제이다. https://www.acmicpc.net/problem/11286 불러오는 중입니다... https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연.. [백준 11286 : JAVA] 절대값 힙 / PriorityQueue 개요 이 문제는 백준 11279 최대 힙 문제와 다른 점이 거의 없다. 자세한 사항이 궁금하면 아래 링크를 참조하면 좋을 것 같다. Comparator 인터페이스의 compare메소드만 오버라이딩해주면 문제의 풀이는 끝난다. 2020/01/26 - [알고리즘/백준] - [백준 11279 : JAVA] 최대 힙 / PriorityQueue [백준 11279 : JAVA] 최대 힙 / PriorityQueue 개요 priorityqueue 자료구조를 이용하여 푸는 문제이다. 기존의 queue는 [FIFO] 구조로 First In First Out 구조를 가지고 있다. 식당에 밥을 먹기 위해 가서 줄을 섰을 때 맨 처음 줄을 선 사람이 맨 처음으로.. dragon-h.tistory.com 문제 절댓값 힙은 다.. [백준 1927 : JAVA] 최소 힙 / PriorityQueue 개요 이 문제는 백준 11279 최대 힙 문제와 다른 점이 거의 없다. 자세한 사항이 궁금하면 아래 링크를 참조하면 좋을 것 같다. Comparator 인터페이스의 compare메소드만 오버라이딩해주면 문제의 풀이는 끝난다. 2020/01/26 - [분류 전체보기] - [백준 11279 : JAVA] 최대 힙 / PriorityQueue [백준 11279 : JAVA] 최대 힙 / PriorityQueue 개요 priorityqueue 자료구조를 이용하여 푸는 문제이다. 기존의 queue는 [FIFO] 구조로 First In First Out 구조를 가지고 있다. 식당에 밥을 먹기 위해 가서 줄을 섰을 때 맨 처음 줄을 선 사람이 맨 처음으로.. dragon-h.tistory.com 문제 널리 잘 알려진.. [백준 11279 : JAVA] 최대 힙 / PriorityQueue 개요 priorityqueue 자료구조를 이용하여 푸는 문제이다. 기존의 queue는 [FIFO] 구조로 First In First Out 구조를 가지고 있다. 식당에 밥을 먹기 위해 가서 줄을 섰을 때 맨 처음 줄을 선 사람이 맨 처음으로 식당에 들어가는 것과 같이 입력이 10 20 30 40 50 이 있을 때 출력도 10 20 30 40 50 이 된다고 생각하면 된다. 따라서 stack [LIFO] 과는 반대의 개념이라고 볼 수 있다. priorityqueue는 queue 구조와 비슷하게 생각할 수 있고, 이름처럼 우선순위 큐이다. queue는 First In First Out이라면 priorityqueue는 Comparator 인터페이스의 compare 메소드를 오버라이딩 한 코드에 따라 우선순위가.. [백준 12015 : JAVA] 가장 긴 증가하는 부분 수열 2 / 이진탐색 풀이 개요 이 문제는 [최장 증가수열] LIS (Longest Increasing Subsequence)로 유명한 문제인 것 같다. 이 문제는 두 번째 버전의 문제로 [11053 가장 긴 증가하는 수열 1] 문제가 첫 번째 버전의 문제라고 생각할 수 있다. 첫 번째 버전을 풀지 않았다면 풀고 오는것을 추천한다. ▶ https://www.acmicpc.net/problem/11053 기존의 첫 번째 버전과 차이점은 입력되는 값의 범위이다. 첫 번째 버전보다 입력되는 값의 범위가 1,000 -> 1,000,000으로 변경되었기 때문에 기존의 동적 프로그래밍 방식으로 풀게 되면 O(N^2)이 되어 시간 초과가 나게 된다. 우리는 이분 탐색을 이용하여 O(NlogN)의 시간 복잡도로 풀게 될 것이다. 문제 수열 A가.. 이전 1 2 3 4 5 다음
