문제 출처 : https://www.acmicpc.net/problem/1406 풀이과정 스택을 사용하는 문제이지만 문제를 보고나서 스택을 사용하지 않고도 해결할 수 있을 것 같다는 생각이 들었다.그래서 스택을 사용하지 않고 string만을 이용해서 해결해봤다.입력은 문자열로 받았으며 N번만큼 명령어를 입력받았다.계속해서 스택을 이용해서도 문제를 풀어봐야겠다.처음 소스코드 이후로 커서 기준 왼쪽, 오른쪽 스택을 이용해서 풀이를 해봤다.그리고 스택으로 풀고나니 문자열도 왼쪽 오른쪽으로 나누어서 풀어보면 어떨까 싶어서 이 문제는 총 3가지의 방법으로 풀이를 해봤다스택을 사용한 방법이 가장 속도가 빨랐다. 소스코드 12345678910111213141516171819202122232425262728293031..
문제 출처 : https://www.acmicpc.net/problem/10799 풀이과정스택을 사용하는 대표적인 문제 중 하나이다.입력은 문자열을 이용하여 받았고, 문자열의 길이만큼 반복문을 통해서 괄호를 체크하였다.문제의 핵심은 '()'가 나올 때 '('의 개수를 체크하는 부분인 것 같다. (레이저로 떨어지는 쇠막대기의 개수를 파악할 수 있다.)'('를 만나면 스택에 push 해주고 ')'를 만날 경우에는 두 가지 경우로 나누어서 처리했다.1. ')' 만날 경우 바로 이전의 index의 문자가 '('인 경우에는 레이저이기 때문에 '('를 pop 시켜주고 '('의 개수를 파악해준다.2. ')' 만났지만 바로 이전의 index의 문자가 '('가 아닌 경우에는 쇠막대기의 끝이기 때문에 1만 더해준다. 소스..
문제 출처 : https://www.acmicpc.net/problem/1152 풀이과정어제 새벽에 잠들어서 낮잠을 오래오래 자느라 늦게 풀었다.단어의 개수라고 해서 띄어쓰기로 구분해서 단어를 세려고 했다.하지만 맨 앞이 공백이거나 마지막이 공백인 경우의 예외처리를 하지않아 좀 오래 걸렸다. 소스코드12345678910111213141516171819202122232425262728293031#include #include using namespace std;#define SIZE 1000000 int main(){ char std[SIZE]; int cnt = 0; cin.getline(std,SIZE); for (int i = 0; i
문제 출처 : https://www.acmicpc.net/problem/10808 풀이과정조별과제 때문에 바빠서 쉬운문제를 풀었다.문자열을 입력받고 문자열의 길이만큼 문자의 아스키코드를 확인하여 카운트 하는 방법으로 해결했다. 소스코드123456789101112131415161718192021222324252627#include #include int alpha[26];int main(){ std::string S; std::cin >> S; for (int i = 0; i
문제 출처 : https://www.acmicpc.net/problem/2631 풀이과정어제 푼 문제와 똑같이 LIS(최장 부분 증가 수열)에 관한 문제이다. 아직 LIS 개념을 정확히 모르겠다. 더 찾아봐야겠다.DP[i] 를 i번째 원소를 끝으로 가지는 배열이 가질 수 있는 최장 부분 증가 수열의 길이라고 할 때, 정답을 출력하려면 입력 배열의 총 길이에서 최장 부분 증가 수열의 길이를 빼면 된다. 소스코드12345678910111213141516171819202122232425262728293031#include #pragma warning(disable:4996) int children[201], DP[201]; int main(){ int N,max=0; scanf("%d", &N); for (i..
문제 출처 : https://www.acmicpc.net/problem/2579 풀이과정 DP[i] 를 i번째 계단을 밟을 경우 최대로 얻을 수 있는 점수라고 한다.3번째 계단일 경우에는 2, 3번째 계단을 밟을 경우와 1, 3번째 계단을 밟을 경우를 비교하여 큰 값을 저장한다.4번째 이후로는 현재 계단만 밟을 경우와 현재, 이전 계단을 밟을 경우를 비교하여 큰 값을 저장한다. 소스코드 123456789101112131415161718192021222324252627282930313233#include #include using namespace std;int DP[301], stair[301]; int main(){ int n; cin >> n; for (int i = 1; i > stair[i]; }..
문제 출처 : https://www.acmicpc.net/problem/2156 풀이과정 DP[i] 를 i번째 포도주 잔까지 최대로 마실 수 있는 양이라 한다.이 문제는 3가지의 경우로 나누어서 생각한다.1. 현재 포도주를 마시지 않는 경우 2. 현재 포도주를 마시고 이전 포도주를 마시지 않는 경우 ( o x o )3. 현재 포도주와 이전 포도주를 마시는 경우 ( x o o )3가지의 경우 중 가장 큰 값을 찾는다. 소스코드 12345678910111213141516171819202122232425262728293031#include #include using namespace std;int DP[10001], wine[10001]; int main(){ int n; cin >> n; for (int i..
문제 출처 : https://www.acmicpc.net/problem/9095 풀이과정 DP[i] 는 i를 1, 2, 3 의 합으로 나타내는 방법의 수라고 생각한다.수작업으로 DP[1], DP[2], DP[3] 을 구해보니 DP[4]는 DP[1], DP[2], DP[3]의 합으로 나타낼 수 있다는 생각이 들었다.소스코드 123456789101112131415161718192021222324252627#include using namespace std; int DP[11]; int main(){ int T,n; cin >> T; DP[1] = 1; DP[2] = 2; DP[3] = 4; for (int i = 4; i > n; cout
문제 출처 : https://www.acmicpc.net/problem/10164 풀이과정 DP[n][m] : (n,m) 까지 올 수 있는 경로의 수를 저장하는 배열DP[n][m] = DP[n-1][m] + DP[]n][m-1] 라는 점화식 이용0,0 부터 K값을 가진 x,y 까지의 경로의 수와 x,y 부터 n,m 까지의 경로의 수를 곱하면 답이 된다는 접근까지 했다. 소스코드 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#include #include using namespace std; int DP[16][16]; // 해당 위치까지 올 수 있는 경로의 개수int N,M,K..