Jubil의 프로그래밍 블로그

9461_파도반 수열 링크 https://www.acmicpc.net/problem/9461 풀이 그림으로 설명하겠습니다. P1 = 1, P2 = 1, P3 = 1, P4 = 2, P5 = 2, P6 = 3, P7 = 4, P8 = 5, P9 = 7, P10 = 9 빨간색 3은 P6이고 구성은 P5 + P1입니다. 빨간색 4는 P7이고 구성은 P6 + P2입니다. 빨간색 12는 P10이고 구성은 P9 + P5입니다. 그렇다면 파도반 수열의 점화식을 구할 수 있습니다. Pn = Pn-1 + Pn-5 (n >= 6) DP를 이용해서 코드를 짜봅시다. n은 100까지니 숫자가 커질 수 있습니다. long long으로 P[101]를 선언해야 합니다. 코드

2294_동전 2 링크 https://www.acmicpc.net/problem/2294 풀이 위 문제의 예제로 어떻게 풀어낼 수 있을 지 생각해 봅시다. 일단 0을 제외한 모든 배열의 인덱스를 10001로 초기화 해야합니다. 왜냐하면 최솟값을 구하는 문제이기 때문이죠. 그래서 나올 수 있는 최댓값보다 더 큰 값으로 초기화 했습니다(불가능한 경우까지 고려). 이제부터 1원을 이용해서 값을 만들어 봅시다. 1원을 만들려면, DP[1]과 DP[1-1]에 1원을 더하는 경우를 비교해야 합니다. DP[1]은 초기값 10001이고, DP[1-1]에 1원을 더하는 경우는 DP[0] + 1이기 때문에 1입니다. 1이 더 작기 때문에 DP[1] = DP[0] + 1로 채택합니다. 2원을 만들겠습니다. 원래 DP[2]는..

2293_동전 1 링크 https://www.acmicpc.net/problem/2293 풀이 일단 k원을 만들 수 있는 경우의 수를 담을 배열 DP[10001]과 가치를 가진 동전을 담을 배열 coin[101]을 만들어 줍니다. 그리고 DP[0]은 동전을 가지고 0원을 만들 경우의 수이니 1로 초기화 해줍니다. 예제로 설명을 하자면, 1원, 2원, 5원짜리 동전으로 10원을 만드는 경우의 수를 구해야 합니다. DP[n] = DP[n-1] + DP[n-2] + DP[n-5] 1원을 만들려면 0원에 + 1원을 해줍니다. 1가지 2원을 만들려면 0원에 + 2원을 해주거나 1원에 + 1원을 해줍니다. 2가지 3원을 만들려면 1원에 + 2원을 해주거나 2원에 + 1원을 해줍니다. 3가지 (2가지인데 중복이 생김..

10844_쉬운 계단 수 링크 https://www.acmicpc.net/problem/10844 풀이 잠깐 생각해보면, n-1까지의 계단 수에 어떤 걸 더해서 n까지의 계단 수의 경우의 수를 구할 수 있을 것 같지만 조건이 부족합니다. 계단 수는 마지막 자리의 숫자로 그 다음 자리의 숫자가 뭐가 될지 결정됩니다. 다음 자리의 숫자가 3이 되려면 -1과 +1인 2, 4가 마지막 숫자여야 됩니다. 보통 이렇게 2가지를 갖지만 0과 9는 각각 1과 8가 마지막 자리일 때 가지게 됩니다. 이러한 특성 때문에 계단 수의 경우의 수를 구하기 위해서는 마지막 자리의 어떤 숫자가 몇 개씩 있는지 알아야만 합니다. n은 1

1932_정수 삼각형 링크 https://www.acmicpc.net/problem/1932 풀이 우선 어떤 정수로 올 수 있는 방법을 알아봅시다. 양 끝 대각선에 있는 정수로 올 수 있는 방법은 단 한 가지입니다. 이렇게 말이죠. 그럼 양 끝 대각선에 있는 정수가 아닌 경우에는 어떤 방법이 있을까요? 어떤 정수를 잡던지 방법은 왼쪽 위와 오른쪽 위 두 가지 방법이 있을 것입니다. 그렇다면 어떠한 정수로 오는 경로의 합의 최댓값을 구해줘서 저장해 놓으면 되겠네요. 그림으로 설명하겠습니다. 이렇게 두 선택지 중 더 큰 쪽에서 오는 걸로 선택해 더해주면 됩니다. 삼각형의 크기 n은 1

9095_1, 2, 3 더하기 링크 https://www.acmicpc.net/problem/9095 풀이 정수 n을 1, 2, 3의 조합으로 나타내는 방법을 찾아야 합니다. 그 방법은 n-1까지의 조합 + 1과 n-2까지의 조합 + 2와 n-3까지의 조합 + 3이 있을 것입니다. 4를 1, 2, 3의 조합으로 나타내는 방법을 위를 통해 구해보면, n-1까지의 조합 -> 3까지의 조합 1 + 1 + 1 + 1 1 + 2 + 1 2 + 1 + 1 3 + 1 n-2까지의 조합 -> 2까지의 조합 1 + 1 + 2 2 + 2 n-3까지의 조합 -> 1까지의 조합 1 + 3 이렇게 7가지가 됩니다. 점화식을 세워보면 DP[n] = DP[n-1] + DP[n-2] + DP[n-3] (n >= 4) 이 됩니다. D..

11727_2xn 타일링 2 링크 https://www.acmicpc.net/problem/11727 풀이 점화식을 세우기 위해서 그림을 그려보겠습니다. 이렇게 되어 2*n까지 타일을 채우는 방법은 f(n-1) + 2*f(n-2)라는 것을 알 수 있습니다. 점화식은 DP[n] = DP[n-1] + 2*DP[n-2]입니다. DP[1]과 DP[2]는 미리 구해 놓아야 합니다. 코드로 구현하겠습니다. 주의할 점은 n은 1000까지 -> 배열은 1001로 선언, 출력은 10,007로 나눈 나머지로 해야 합니다. 코드

11726_2xn 타일링 링크 https://www.acmicpc.net/problem/11726 풀이 점화식을 세우기 위해서 그림을 그려보겠습니다. 이렇게 되어 2*n까지 타일을 채우는 방법은 f(n-1) + f(n-2)라는 것을 알 수 있습니다. 점화식은 DP[n] = DP[n-1] + DP[n-2]입니다. DP[1]과 DP[2]는 미리 구해 놓아야 합니다. 코드로 구현하겠습니다. 주의할 점은 n은 1000까지 -> 배열은 1001로 선언, 출력은 10,007로 나눈 나머지로 해야 합니다. 코드

[pwnable.kr] Rookiss – fsb 문제는 32bit 바이너리입니다. 코드를 보면, key에 8자리 숫자를 가져옵니다. 그리고 alloca라는 함수를 사용해서 스택에 공간을 할당하고 fsb라는 함수를 호출합니다. fsb 함수는 이렇게 생겼는데요, 4번 fsb를 터트릴 수 있고, key를 입력하고 맞추면 쉘을 실행할 수 있습니다. fsb를 이용해서 key를 가져올 수 있을까요? 일단 한 번 디버깅 해보겠습니다. alloca 함수 때문에 fsb로 main 함수의 스택 공간까지 접근하기는 힘들 것 같습니다. fsb가 터지는 곳에 bp를 걸고 메모리를 보겠습니다. 스택에 보면 빨간 동그라미 값을 이용해서 화살표 메모리의 값을 변경할 수 있고, 그 변경한 값에 다시 접근해서 원하는 값으로 변경할 수 ..

장학생으로 뽑히게 되어 영광입니다..앞으로 더 열심히 하겠습니다!