Patrick's Devlog

1. 개요 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 1-1. 설명 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성한다. 방문할 수 있는 정점이 여러개 일 시, 정점 번호가 작은것을 먼저 방문하고 더이상 방문할 수 없는 경우 종료한다. 1-2. 제한 사항 - 첫 줄에 정점의 개수 N, 간선의 개수 M, 탐색을 시작할 정점 번호 V가 주어짐 - N은 1 이상 1,000 이..

1. 개요 https://www.acmicpc.net/problem/11656 11656번: 접미사 배열 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000보다 작거나 같다. www.acmicpc.net 1-1. 설명 접미사 배열은 문자열 S의 모든 접미사를 사전순으로 정렬해놓은 배열이다. 문자열 S가 주어졌을 때, 모든 접미사를 사전순으로 정렬한 후 출력하는 프로그램을 작성한다. 1-2. 제한 사항 - 첫 줄에 문자열 S가 주어지며, S는 소문자로 이루어져 있고 길이는 1,000 이하 2. 구현 2-1. 풀이 S를 받아 반복문을 통해 substr을 거쳐 접미사 배열을 생성해주었다. 후에 sort 함수를 통해 정렬 후 출력해주었다. 2-2. 코드 #include #..

1. 개요 https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 1-1. 설명 오르막 수는 수의 자리가 오름차순으로 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성한다. 수는 0으로 시작할 수 있다. 1-2. 제한 사항 - 첫 줄에 N이 주어지며, N은 1 이상 1,000 이하 2. 구현 2-1. 풀이 DP의 Bottom-..

1. 개요 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 1-1. 설명 방향 그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성한다. 단, 모든 간선의 가중치는 10 이하의 자연수이다. 1-2. 제한 사항 - 첫 줄에 정점 개수 V, 간선 개수 E가 주어지며, V는 1 이상 20,000이하이고 E는 1 이상 300,000 이하 - 모든 정점은 1부터 V까지 번호가 ..

1. 개요 https://www.acmicpc.net/problem/2635 2635번: 수 이어가기 첫 번째 수가 주어진다. 이 수는 30,000 보다 같거나 작은 양의 정수이다. www.acmicpc.net 1-1. 설명 다음과 같은 규칙에 따라 수를 만든다 - 첫 번째 수로 양의 정수가 주어짐 - 두번째 수는 임의로 양의 정수중 하나 선택 - 세번째 수부터는 앞의 앞의 수에서 앞의 수를 빼서 생성 - 음의 정수가 만들어지면, 이 음의 정수는 버리고 더 이상 수를 만들지 않음 입력으로 첫번째 수가 주어질 때, 이 수에서 시작하여 위의 규칙으로 만들어지는 최대 개수의 수들을 구하는 프로그램을 작성한다. 1-2. 제한 사항 - 첫 줄에 첫 번째 수가 주어지며 이 수는 30,000 이하 양의 정수 2. 구..

1. 개요 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 1-1. 설명 2xn 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수를 구하는 프로그램을 작성한다. 1-2. 제한 사항 - 첫 줄에 n이 주어지며, n은 1 이상 1,000 이하 2. 구현 2-1. 풀이 2xn 타일링 2와 마찬가지로 Dynamic Programming을 진행하였다. 동일하게 1부터 5까지 차근차근 타일을 그려보았으며, 점화식을 찾아 코드로 구현하였다. 2-2. 코드 #includ..

1. 개요 https://www.acmicpc.net/problem/1543 1543번: 문서 검색 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한 www.acmicpc.net 1-1. 설명 영어로만 이루어진 어떤 문서를 검색하는 함수를 만드려고 한다. 이 함수는 어떤 단어다 총 몇번 등장하는지 세려고 한다. 그러나, 함수는 중복되어 세는것은 배고 세야 한다. 문서와 검색하려는 단어가 주어졌을 때, 그 단어가 최대 몇번 중복되지 않게 등장하는지 구하는 프로그램을 작성한다. 1-2. 제한 사항 - 첫 줄에 문서가 주어지며, 문서의 최대 길이는 2500 - 둘째줄에는 ..

1. 개요 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 1-1. 설명 2xn 직사각형을 1x2, 2x1과 2x2 타일로 채우는 방법의 수를 구하는 프로그램을 작성한다. 1-2. 제한 사항 - 첫 줄에 n이 주어지며, n은 1 이상 1,000 이하 2. 구현 2-1. 풀이 Dynamic Programing을 이용하여 풀면 된다. 점화식은 n이 1일때부터 타일을 배치하여 점화식을 찾았다. 점화식은 DP[n] = DP[n-1] + DP[n-2] * 2 임을 알 수 있다. n에..