IT세상

https://www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=3 #include using namespace std; int n, m; int graph[1001][1001]; bool dfs(int x, int y){ // 주어진 범위를 벗어나는 경우 즉시 종료 if(x=n || y=m){ return false; } // 현재 노드를 아직 방문하지 않았다면 if(graph[x][y] == 0){ // 해당 노드 방문 처리 graph[x][y] = 1; // 상하좌우 위치들도 모두 재귀적으로 호출 dfs(x-1, y); dfs(x, y-1); dfs(x+1, y); dfs(x, y+1); return t..

https://www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=3 스택 자료구조 설명(선입후출) 스택 동작 예시 스택 구현 예제 stack s; // 선언 s.push(x); s.pop(); 큐 자료구조(선입선출) 큐 구현 예제 queue q; //큐 선언 q.push(x); q.pop(); 재귀함수 설명 재귀 함수의 종료 조건 DFS(Depth-First Search) 깊이 우선 탐색 - 그래프에서 깊은 부분을 우선적으로 탐색 - 스택 자료구조 혹은 재귀 함수 사용 #include using namespace std; bool visited[9]; vector graph[9]; void dfs(int x)..

https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net dp[n]은 n개를 구입 할 때 최대 금액으로 정하고 n=1 은 p[1]로 초기화한다 그리고 n=2부터 dp[n] = dp[n-i] + dp[i] 의 점화식을 이용해 풀면 된다 #include using namespace std; int n; int p[1001], dp[1001]; int main(void) { cin >> n ; for(int i=1; i> p[i]; } dp[1] = p[1]; fo..

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 전에 풀어봤던 문제라서 쉽게 해결됐다 배열 a에 수열을 넣고 dp배열에는 i번째 값을 포함하는 가장 긴 수열의 수를 넣는다 dp배열은 1로 초기화하고 a값을 차례대로 비교하면서 자신의 값보다 작은 값의 dp값에 1을 더해준다 #include using namespace std; int n; int dp[1001] = {..

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 스티커 점수를 담는 배열 arr[i][j] 와 (i. j)를 포함하는 스티커 점수의 최대값 dp[i][j] 배열을 선언해준다 j열의 점수를 계산하면 j-1 대각선에 있는 점수랑 j-2 대각선에 있는 점수 중 큰 값을 비교해 자신의 값과 더해주면 된다 #include using namespace std; int t, n; int dp[2][100001], arr[2][100001]; vo..

https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 처음에는 숫자 배열만 보고 p[n] = p[n-2] + p[n-3] 라고 생각했는데 직접 그림을 그려보니 p[n] = p[n-1] + p[n-5] 였다 그리고 어느순간 int의 범위를 벗어나서 배열은 long long 형으로 선언했다 #include using namespace std; int tc; long long a[101] ={0,1,1,1,2,2}; int main(void) { cin >> ..

https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 두가지 방법으로 풀 수 있는 것 같다 다른 블로그들을 찾아보니 피보나치 수열로 많이 푼 것 같다 나는 다른 규칙을 찾아서 dp[n][s] : s로 끝나는 n자리 이친수 개수라고 정하고 dp[n][0] = dp[n-1][0] + dp[n-1][1] dp[n][1] = dp[n-1][0] 라는 점화식을 가지고 코드를 짰다 #include using namespace std; int n; l..

https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 원래는 dp[n]으로만 식을 세웠었는데 예시를 적다보니 일의자리 수가 중요하다고 생각되어 일의자리 s를 추가했다 길이가 n이고 일의자리 수가 s인 오르막수의 개수는 길이가 n-1이고 일의자리수가 0부터 s까지인 오르막수의 개수를 모두 더하면 된다 저 sum함수를 너무오랜만에 써봐서 맞게 썼는지 모르겠지만 아무튼 점화식은 맨 아래처럼 만들 수 있다 #include..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net #include using namespace std; int n; int dp[101][10]={}; #define mod 1000000000; int main(void) { cin >> n; dp[1][0] = 0; for(int i=1; i

https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 2 x n 크기의 타일을 채우는 문제이고 DP를 이용한다. 그래서 점화식은 dp(n) = dp(n-1) + dp(n-2) #include using namespace std; int n; int arr[1000]; int main(void) { cin >> n; arr[0] = 1; arr[1] =2; for(int i=2; i