전체 글170 DP 문제 맛보기 (카드 구매하기 1,2) https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net [DP 문제 풀기전] - 작은 문제를 일단 풀어본다. - 그 사이에 반복되는 문제가 있는지 살펴본다. - 그 다음 문제를 풀때, 반복되는 것을 전 문제 것을 차용한다. [ 접근법 ] i장의 카드 값을 저장하는 배열(arr)과 i장의 최대 구입비를 저장하는 배열(dp)를 설정한다. 1장을 구매하는 방법은 다음과 같다. - 1장 구입 (= 0장의 최대 구입비 (dp[0]) + 1장 구입(arr[1])) 2장.. 2022. 12. 19. 한 문장에서 반복되는 문자열 중 가장 짧은 문자열 찾기 BOJ 26266] 비즈네르 암호 해독 문제 중 S E O U L S E O U L S E O U L... 이런 문자열에서 반복되는 문자열 중 가장 짧은 문자열은 SEOUL이다. 다음을 찾기 위해 KMP 알고리즘을 차용 https://blog.naver.com/ndb796/221240660061 30. KMP(Knuth-Morris-Pratt) 알고리즘 이번 시간에 다루게 될 알고리즘은 KMP 알고리즘으로 대표적인 문자열(String) 매칭 알고리즘입... blog.naver.com for (i = 1; i < size; i++) { if (v[j] == v[i]) { start = i; while (i < size && v[j] != v[i]) { j++; i++; } if (start == j) { .. 2022. 12. 18. 후위 표기식 계산하기 [ 후위 표기식 이란? ] 일반적으로 우리가 사용하는 중위 표기식과 달리 연산자를 뒤쪽에 배치하는 표기식을 의미한다. (중위 표기식) 1+2*3/2 (후위 표기식) 12+*32/ 후위표기식을 구하기 위해 우리는 Stack을 이용한다. 이때문에 컴퓨터는 후위 표기식의 연산속도가 더 빠르다라고 알고 있다. [ 중위 -> 후위 ] - 우리가 신경써야할 것은 부호를 어떻게 배치하나 이다. - 피연산자는 순서대로 출력하고, 부호에 의해 괄호 및 우선순위가 결정된다. [ 원리 ] - stack에 연산자를 제외한 부호를 넣어준다. - 만약 *나/가 오게되면 기존에 stack에 있던 같은 우선순위의 부호들(*, /)를 출력 및 pop해주고 자신을 push한다. - 만약 +나-가 오게되면 이미 자신보다 우선순위가 높은 .. 2022. 12. 16. BOJ 17299] 오등큰수 [ 접근법 ] - 오큰수 문제와의 차이점이라면 등장 횟수를 추가로 저장해야한다는 것이다. - 등장 횟수를 따로 저장하는 것 이외에 그대로 진행하면 된다. [ 주의 사항 ] - 등장횟수와 값을 저장하는 배열 두가지를 혼동하지 말자. - stack과 결과값에는 순서를 저장해두자! [ 코드 ] 더보기 #include #include #include #include #include using namespace std; stack s; int arr[1000001]; //num[i]의 등장횟수 int num[1000001]; //i번째 원소의 값 int res[1000001]; //v에는 오등큰수의 순서가 정리 int main() { ios_base::sync_with_stdio(false); cin.tie(NU.. 2022. 12. 15. BOJ 17298] 오큰수 [ 접근법 ] - 오른쪽 수열에서 자신보다 큰 수중 가장 작은 값을 구하는 것이기 때문에 stack을 이용하자. - 하나하나 비교하는 o(n*n)는 수가 100000에 달하기 때문에 다른 방법을 모색해야 된다. - 왼쪽에 있는 수열의 오큰수는 무조건 오른쪽의 있는 수열보다 작거나 같다. - 그렇기 때문에 만약 다음 수열이 자신의 오큰수가 아니라면 stack에 저장해두고 다음 수열의 오큰수가 등장하면, 그때 stack을 pop하면서 해당 오큰수가 stack에 저장된 오큰수가 맞나 확인을 한다. - 만약 오큰수가 아니라면 -1을 저장한다. [ 주의사항 ] - 결과 저장배열에 수열 순서대로 저장해야 순서가 뒤죽박죽 되지 않는다. - 시간이 1초라고 해서 이중반복문이 등장하면 안되는 것이 아니다! - 마찬가지로.. 2022. 12. 15. BOJ 1874] 스택 수열 [ 문제 이해 ] 입력 값 예) 3 5 1 2 4 - 1부터 n까지의 수를 순서대로 스택에 넣는다. (+출력) 스택 : 1 2 3 - 위를 하다 입력된 값과 같아지면 그 수를 스택에서 제거한다 (-출력) 스택 : 1 2 (3제거) 스택 : 1 2 4 (5제거) 이런 식으로... - 위 과정을 몇번해서 스택이 비워지고, 해당 수열이 완성되는 지 총 횟수를 출력한다 - 만약 위 과정을 진행하다 수열이 만들어지지 않으면 NO를 출력한다. [ 접근법 ] 1. 스택에 1부터 1씩 증가하면서 스택에 넣는다. 2. 입력받은 값이 스택의 top 과 같아지면 스택을 pop()한다. 3. 1,2 과정을 반복하다 스택이 비워지면 종료 4. 만약 위 과정 중 스택이 입력값이 스택의 topp()보다 크면 "NO" 를 출력하고 .. 2022. 12. 13. 이전 1 ··· 25 26 27 28 29 다음
