trudy

1260번: DFS와 BFS (acmicpc.net) 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net dfs, 깊이 우선 탐색 재귀 또는 스택을 이용해서 구현 루트 노드에서부터 더 이상 내려갈 수 없을 때까지 내려가고, 다음 분기로 넘어가는 탐색 방법 bfs, 너비 우선 탐색 큐를 이용해서 구현 루트 노드에서부터 최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동 [알고리즘] 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS) (tistory.com) [알고..

2225번: 합분해 (acmicpc.net) 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오. 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다. [이해하기] N / K 1 2 3 4 1 1 2 3 4 2 1 3 6 3 1 4 4 1 K=1인 경우: 1가지씩 N=1, K=2인 경우: 0, 1 => 2가지 N=1, K=3인 경우: 0, 0, 1 => 3가지 N=1, K=4인 경우: 0, 0, 0, 4 => 4가지 N=2, K=2인 경우: 0, 2 / 1, 1 => 3가..

11058번: 크리보드 (acmicpc.net) 11058번: 크리보드 N = 3인 경우에 A, A, A를 눌러 A 3개를 출력할 수 있다. N = 7인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V를 눌러 9개를 출력할 수 있다. N = 11인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V, Ctrl-A, Ctrl-C, Ctrl www.acmicpc.net [이해하기] N=3일 때: i) 1번 버튼 3번: AAA N=4일 때 ( N=5일 때도 동일) i) 1번 버튼 4번 : AAAA ii) 1번, 2번, 3번, 4번 : AA N=6일 때: i) 1번 버튼 6번 : AAAAAA ii) 1번, 2번, 3번, 2번, 3번, 4번: A 백준 ..

2156번: 포도주 시식 (acmicpc.net) 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net [문제] 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를..

1932번: 정수 삼각형 (acmicpc.net) 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 위 예시의 삼각형을 아래처럼 입력을 받는다 [풀이] 가장 아랫줄부터 시작해서 올라가는 방식인 데, 가장 아랫줄에 인접한 두 원소 중 큰 원소를 대각선 위의 원소와 합하는 것을 반복한다 ex) 4번째 줄의 2는 2+ max(4, 5) = 7로 바뀐다 4번째 줄의 7은 7+ max(5, 2) = 12로 바뀐다 4번째 줄의 4는 4+ max(2, 6) = 10으로 바뀐다 4번째 줄의 4는 4+ max(6, 5) = 10 으로 바뀐다 그럼 삼각형은 이렇게 바뀜. 그 아랫줄은 이제 신경 쓰지 ..

2579번: 계단 오르기 (acmicpc.net) 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을..

11057번: 오르막 수 (acmicpc.net) 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 2차원 배열에 i길이의 j로 끝나는 오르막 수의 개수를 구해보자 0 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 1 2 1 2 3 4 5 6 7 8 9 10 3 1 3 6 10 - 0으로 끝나는 수는 길이가 몇이든 1이다 (0, 00, 000 ...) - 길이가 1인 수는 모두 1개, 길이가 2인 수는 1개씩 증가 1로 끝나는 수는 길이가 1이면 1개 (1..

010844번: 쉬운 계단 수 (acmicpc.net) 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net [문제 이해하기] T(1) = 9 1 2 3 4 5 6 7 8 9 T(2) = 17 1-> 12, 2-> 23, 21, 3-> 34, 32 12 23 34 45 56 67 78 89 90 21 32 43 54 65 76 87 98 T(3) = 2*T(2) 12-> 123 121, 23->232 234, 34->345 343, 90->901 909 21 -> 212 210 [백준 10844번 쉬운 계단 수/ C++](DP) (tistory.com) [백준 10844번 쉬운 계단 수/ C++](DP) www.acmicpc.ne..

1912번: 연속합 (acmicpc.net) 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net [백준/BOJ] 1912번 연속합 (C/C++) (tistory.com) [백준/BOJ] 1912번 연속합 (C/C++) 백준 온라인 저지(BOJ) 1912번 연속합 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 rightbellboy.tistory.com..

2193번: 이친수 (acmicpc.net) 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 규칙을 알아봅시당 1로 시작하고 11이 나오면 안되므로 아이디어 1) n>1 일 때는 10_ 으로 시작해야한다 아이디어 2) 조합을 생각했을 때, 10 다음부터는 0,1로 채워지되 1만 연속하게 안나오게 만들면 됨 ex) T(5) = 2^4 - 6 = 10 T(6) = 2^5 - 10 = 22 n=1일 때, 1가지 (1) n=2일 때, 1가지 (10) n=3일 때, 2가지 (10_: 100, 101) n=4..