![](http://i1.daumcdn.net/thumb/C148x148/?fname=https://blog.kakaocdn.net/dn/WJhj3/btqG3DDHCLl/tfmZCmYXjkpQCd8wCdSqfk/img.png)
https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} � www.acmicpc.net 동적계획법 C++ 이번엔 감소하는 부분 수열이다. 접근 방법 가장 긴 증가하는 부분수열에서 감소하는 부분수열로 바뀌었을 뿐이다. 비교할때 이 점을 유의해서 비교하면 된다. 소스코드 #include using namespace std; int main(){ int n; cin >> n ; int num[n]; int le..
![](http://i1.daumcdn.net/thumb/C148x148/?fname=https://blog.kakaocdn.net/dn/bL3JPo/btqGZILllRo/fOiY1GOF7hL4GqDIUThhU1/img.png)
https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수� www.acmicpc.net 동적계획법 C++ 이번엔 가장 큰 증가하는 부분 수열의 합 구하기 접근 방법 지난번 풀었던 가장 긴 증가하는 부분 수열과 로직이 유사하다. 차이점은 우선 합을 저장해야한다는 점과 가장 긴 부분 수열의 경우 부분 수열이 성립할 경우 길이가 1만 증가했지만 이번엔 합이어서 본인의 수 만큼 증가하므로 비교할 때 이 부분을 주의해야 했다. 소스..
![](http://i1.daumcdn.net/thumb/C148x148/?fname=https://blog.kakaocdn.net/dn/cJVjKF/btqGK51WU0v/lMfQq5mthOKcyDc0pQcDkk/img.png)
https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 동적계획법 C++ 쉬운계단수 구하기 접근방법 1~8까지는 괜찮은데 0,9가 문제였다. 그래서 0,9 경우를 따로 계산하고 우선 기본적인 접근은 n번째 자리에 오는 0부터9까지의 숫자의 갯수를 저장하는 배열을 사용한다. 0의 개수는 이전 자리의 1의 개수 1~8(i)의 개수는 이전 자리의 i-1의 개수 + i+1의 개수 9의 개수는 이전 자리의 8의 개수 그리고 마지막에 n번째 자리에 오는 0~9의 개수를 모두 더한 값을 출력한다. 처음엔 마지막에 값을 더할때 나머지 계산을 안하고, 1~8의 경우를 저장할 때 i..
![](http://i1.daumcdn.net/thumb/C148x148/?fname=https://blog.kakaocdn.net/dn/cX8ZFc/btqGNCYns1l/Jo4gS3rtkKKFxXRqsbLKF0/img.png)
https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 동적계획법 C++ 가장 긴 증가하는 부분 수열을 구하는 문제 접근 방법 DP라서 뭔가 2중 for문은 안될 것 같다고 생각하다가 최대 N이 1000이고 제한시간이 1초면 2중 for문도 되겠다 싶어서 그렇게 구현했다. 이번에도 각 인덱스 까지의 최대길이를 갖고 있는 배열을 사용했다. 다만 2중 for문을 사용해야 했던 ..
![](http://i1.daumcdn.net/thumb/C148x148/?fname=https://blog.kakaocdn.net/dn/bkFIg6/btqGDPRYSI0/2kcAtvCkfjwk8NlFGnMkN1/img.png)
https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 동적계획법 C++ 계단 오르기 문제와 로직이 동일해보여서 풀기 시작했는데 닮은듯 달랐다. 계단오르기와 차이점은 우선 두칸이상 건너뛸 수 있다. (근데 사실상 세칸이상 건너뛰는 경우는 없다. 가운데 하나를 먹어야 이득이니까) 그리고 꼭 마지막 주스를 먹어야할 필요가 없다. (최종 값을 출력할때 n-1칸과 n-2칸의 값을 비교해서 출력해야함) 차이점은 두갠데 그래서 많은 것이 추가됐다.. 접근방법은 계..
![](http://i1.daumcdn.net/thumb/C148x148/?fname=https://blog.kakaocdn.net/dn/cGClVZ/btqGAUZujx3/9SkJDPhGaztAJbNf9GcBtK/img.png)
https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 동적계획법 C++ 문제는 위에 사진 참고 (설명 매우 귀찮다 딱히 요약할 것도 없응께) N의 범위는 1부터 10^6 까지 접근방법 n개의 정수 배열을 사용한다. 배열에는 해당 수가 1이 되는데에 필요한 연산의 최소 횟수가 저장된다. 1: 0회, 2: 1회, 3: 1회까지 미리 저장해두고 4부터는 [ 1을 뺀 수의 연산 최소횟수 + 1 , 3으로 나눈 값의 연산 최소횟수 + 1 (3으로 나누어질때만), 2로 나눈 값의 연산 최소횟수 + 1 (2로 나누어질때만) ] 이 중 가장 작은 값을 해당 인덱스의 배열에 저장..
![](http://i1.daumcdn.net/thumb/C148x148/?fname=https://blog.kakaocdn.net/dn/YKWmj/btqGvdzlpkb/YyKPdZrkxsM6UkJrBKAua1/img.png)
https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 동적계획법 C++ 연속으로 세칸을 오를 수 없고 / 그림처럼 한 칸 혹은 두 칸씩 오를 수 있다. 각 계단 마다 점수가 배정돼있고 위의 규칙을 지키면서 그 점수의 합이 최대가 되는 경우 최댓값을 출력하기 접근방법 이 문제도 작은 부분에서의 최댓값을 구해가면서 풀었다. 각 칸에서의 최댓값을 저장하면서 갱신해갔다. 해당 칸에서 그 전칸의 최댓값, 그 전전칸의 최댓값을 비교해가면서 저장해간다. 너무 추상적으로 썼는..
![](http://i1.daumcdn.net/thumb/C148x148/?fname=https://blog.kakaocdn.net/dn/bDPudW/btqGuM8BjAe/6UJbFJjYfgEC7e0XBjLqbk/img.png)
https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최� www.acmicpc.net 동적계획법 C++ 숫자 트리에서 숫자들의 합이 최대가 되는 경로 구하기(최댓값 출력) 접근방법 전형적인 DP 상향식 풀이로 풀었다. 가장 밑 행부터 모든 숫자에 대해 해당 자리까지의 최댓값을 저장해가면서 값을 갱신한다. 예를들어 위의 사진에서 4번째 행 첫번째 자리 2에서 최댓값을 가지려면 4,5중 5를 선택해야하니까 원래 2가 있던 자리에 2+5 = 7을 저장한..
![](http://i1.daumcdn.net/thumb/C148x148/?fname=https://blog.kakaocdn.net/dn/ddarrF/btqGjfjAH7q/9E76ZVax7rGTqnJKPYpHV0/img.png)
https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 스택 C++ 처음에 문제 이해를 못해서 이해하는데 시간이 좀 걸렸다. 1부터 n까지의 수가 연속된 수라는 점을 이해하면 된다. 1부터 n까지의 수가 섞여있는 수열이 주어지고 나는 1,2,3,4,...,n 까지의 수를 순서대로 스택에 push할 수 있고 또 pop하면서 결과적으로 pop하여 만들어진 수열이 입력된 수열..
![](http://i1.daumcdn.net/thumb/C148x148/?fname=https://blog.kakaocdn.net/dn/sY5Mu/btqGkutp345/xzPhvkx1wVwaa9UOrWIbKk/img.png)
https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 문제 세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다. 정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단 www.acmicpc.net 스택 C++ (2011 ICPC japan) 괄호가 섞인 문자열이 주어지고 괄호가 균형이 맞는지 조사하는 문제 (, [ 가 입력되면 stack에 push하고 ), ]가 입력되면 stack에서 pop한 값이 짝이 맞는지 검사한다. 이때 짝이 맞지 않으면 균형잡힌 문자열이 아닌걸로 판단하고 결과를 출력하고 또 마지막에 stack이 비어있지 않으면 균형잡힌 문자열이 아닌걸로 판단하고 출력한다. 소스코드..
- Total
- Today
- Yesterday
- 이분탐색
- BFS
- 최대힙
- 게임이론
- c++
- 투포인터
- 우선순위큐
- 브루트포스
- 문자열
- 웹크롤링
- 알고리즘
- 정렬
- 스택
- 수학
- 최소힙
- 백준
- 트리
- 백트래킹
- Swift
- 그리디알고리즘
- 토마토
- dp
- Stack
- 최단경로
- 프로그래머스
- 파이썬
- 다이나믹프로그래밍
- 동적계획법
- 자바
- dfs
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |