별일없는 범고래님의 이글루입니다
Posts
238 posts[c++] 11052 붕어빵판매하기
1234567891011121314151617181920212223242526272829#include using namespace std;int price[10001], memo[10001];int P(int N) { if (N == 0) return memo[N] = 0; if (N == 1) return memo[N] = price[N]; int k; for (k = 1; k < P(N - k) + price[k]) { memo[N] = P(N - k) + price[k]; } } return memo[N];} int
[c++] stack 개념과 예제
백준의 알고리즘 오프라인 강의를 들으면서 지금까지 배웠던 내용들을 간단하게 정리하려고 한다. 스택 -한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조이다. 마지막으로 넣은 것이 가장 먼저나오기 때문에 LIFO(Last In First Out)이라고 한다. 스택은 두가지 연산으로 이루어져있는데 -push함수 : 스택에 자료를 넣는 연산 -pop 함수 : 스택에서 자료를 빼는 연산 -top 함수 : 스택의 가장 위에 있는 자료를 보는 연산 (가끔 인덱스와 혼동할 수 있다.) -size 함수 : 스택에 저장되어있는 자료의 개수 이다. (size이므로 스택의 크기를 생각 할 수 있으나 개수임을 명심하자) 사실 스택 같은경우 자료구조에서 배열이나 연결리스트로 많이들 구현하고는 하는데 문제를
[c++]10799번 쇠막대기 / stack
문제는 굉장히 어려워 보이나 규칙성을 찾는다면 스택을 이용해 간단하게 해결할 수 있는 문제이다. 입력받은 string을 순차적으로 검사해괄호 ( 가 있다면 스택에 추가하고,괄호 ) 가 있다면 레이저에 의한 ')'인지 쇠막대기에 의한 ')'인지확인하여 각각의 경우를 처리해주면 된다. 레이저에의한 ) 괄호 같은 경우엔 겹쳐져있는 막대기를 한번에 자르는 것이므로 스택에 남아있는 ' ( ' 의 수를 추가하면 될 것 같다.또한 레이저가 끝났으므로 pop을 하여 앞에 남아있는 레이저의 ( 괄호 또한 삭제해준다. 쇠막대기에 의햔 ) 괄호는 쇠막대기가 끝났다는 것을 의미하므로 결과에 +1을 추가해주고, 쇠막대기의 시작을 알려주는 ( 괄호를 pop해준다. 결과값 출력을 해주면 정답을 얻어낼 수 있다. 1
[c++] 2579번 계단 오르기 / DP- topdown
이번 문제도 DP관련 문제이다. DP관련 문제가 나오는 경우엔 점화식을 세우는 것이 중요하다.이글을 쓰기 3일 전에 미리 풀어보았는데 왠지모르게 오류가나서 잠깐 미뤘다가 오늘 다시보았는데 술술 풀렸다.환기를 시키는 것이 중요하다는 것을 알았다. 사실상 점화식을 잘못세워서 시간을 낭비했는데 이런 곳에서 수학의 중요성을... 깨닫는다.흫그흑 머리가 좋아야해 ... 머리가 굳은 것 같아서 말랑말랑해질때까지 계속 봐야겠다!설명은 주석을 참고! 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859#include #include
[c/ c++]1,2,3 더하기-2가지 방법
백준 알고리즘의 1,2,3 더하기 문제이다. dynamic을 이용하여 풀었다.이 문제를 풀땐 점화식을 세우고 그 점화식을 통해 문제를 해결해야한다. N이라는 숫자를 만들려면 N = ? + ? + ? + .... + ? + 1 로 만드는 방법 1. N = N-1 + 1N = ? + ? + ? + .... + ? + 2 로 만드는 방법 2. N = N-2 + 2N = ? + ? + ? + .... + ? + 3 로 만드는 방법 3. N = N-3 + 3 3가지가 존재한다. f(N)을 N으로 만드는 개수라고 할때, f(N) = f(N-1) + f(N-2) + f(N-3)으로 나타낼 수 있다. 다음은 topdown을 이용해서 풀어본 코드. [c++] - topdown123456789101112131415
