오랜만에 블로그 들어왔는데 스킨이 초기화 되어있어서 깜짝놀랐,,, 카카오 오류 때문에 아직 스킨은 복구중이라는데 어후 내거만 이상해진줄 알고 놀랐네 휴 티스토리 일ㅇ하자... https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 ..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net '쉬운' 계단 수 라길래 호기롭게 도전했다가 실패.. DP를 공부하게 만들어준 문제 다른 블로그들의 설명을 봐도 이해가 안되길래 몇시간을 끙끙댔는데, 경우의 수들을 직접 표로 정리하고나서야 이해가 됐다.ㅠ 문제 45656이란 수를 보자. 이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다. 입력 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다...

https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net DP 알고리즘을 사용해서 푸는 문제라는 것은 알고있었지만, 문제를 봐도 어디서 DP를 사용해야하는지 모르겠었다. 그래서 내가 찾았던 나름대로의 규칙(조합을 이용하여 풀었다. dp[i] = (i/2+i%2)C(i/2) + ... + i-1C1 + iC0) 을 통해 값을 구하려했지만, 정수범위 내에서 계산하기에는 범위가 너무 커져서 결국 런타임에러로 문제를 풀지 못했다. 휴 DP어렵다..ㅠ 2XN 타일을 채울 때, N이 ..

https://www.acmicpc.net/problem/1463 DP를 이해한 뒤에 처음 풀어보는 DP문제였다. 혼자 이해하는데도 시간이 오래걸렸던 문제라서 최대한 이해하기 쉽게 정리해두려고한다! 문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. 1. X가 3으로 나누어 떨어지면, 3으로 나눈다. 2. X가 2로 나누어 떨어지면, 2로 나눈다. 3. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 10^6보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 예제 2 입력 >> 1 출력 10 입력 >> 3 출력 예..

1. DP(다이나믹 프로그래밍)의 목적 DP는 완전탐색, DFS(깊이우선탐색), BFS(너비우선탐색)와 같이 수많은 경우의 수를 전부 따져봐야 할 때, 그 경우의 수가 너무 많아 속도가 느려져 수행 시간이 길어지는 문제를 개선하고자 만들어진 알고리즘이다. DP 알고리즘이 존재하기 전에는 최단 경로를 찾거나 최고 점수를 찾는 등의 '경우의 수'를 따져봐야하는 경우, 결국 모든 조합을 다 만들어보는 수 밖에 없었다. 하지만 DP 알고리즘이 만들어진 이후에는 모든 경우의 수를 비교해봐야하는 경우 수행시간이 현저하게 줄어들도록 문제를 해결할 수 있었다. 2. 예제를 통한 설명 - 프로그래머스 정수 삼각형 문제 프로그래머스의 정수삼각형 문제는 대표적인 dp문제로, 그림과 같이 삼각형의 숫자들이 주어지고 왼쪽이나 ..

EOF? EOF는 end of fie의 줄임말로, 파일의 끝을 표현하기 위해 정의해 놓은 상수이다.(-1 값을 가지고 있다.) 함수 호출의 실패나, 윈도우에서는 ctrl+z, 리눅스에서는 ctrl+d를 입력했을 경우 EOF를 반환한다. 백준 문제를 풀 때 최대 몇개의 입력이 들어오는지 모르는 문제에서 사용된다. C, C++에서 eof를 처리하는 여러 방법에 대해 정리해보았다. 첫 번째 방법 #include int main() { int x, y; while(scanf("%d %d", &x, &y) != EOF) { --- } return 0; } scanf 와 while을 같이 사용하여, x와 y의 값이 존재할 때 까지 반복해서 값을 받는 코드이다. 두 번째 방법 #include int main() { ..