목록[c언어&c++] 알고리즘 공부/개념 (18)
아무거나 내꺼 공부할래
[개념] 네트워크 선 자르기(Top-Down, 재귀, 메모이제이션) / c++ & c / 제한시간 없음
▣ 문제 현수는 네트워크 선을 1m, 2m의 길이를 갖는 선으로 자르려고 합니다. 예를 들어 4m의 네트워크 선이 주어진다면 의 5가지 방법을 생각할 수 있습니다. (2)와 (3)과 (4)의 경우 왼쪽을 기준으로 자르는 위치가 다르면 다른 경우로 생각한다. 그렇다면 네트워크 선의 길이가 Nm라면 몇 가지의 자르는 방법을 생각할 수 있나요? ▣ 입력설명 - 첫째 줄은 네트워크 선의 총 길이인 자연수 N(3≤N≤45)이 주어집니다. ▣ 출력설명 - 첫 번째 줄에 부분증가수열의 최대 길이를 출력한다. ▣ 입력 예시 7 ▣ 출력 예시 21 #pragma warning(disable:4996) #include using namespace std; int dy[101]; int dfs(int n) { if (dy[..
[개념] 네트워크 선 자르기(Bottom-Up, DP) / c++ & c / 제한시간 없음
▣ 문제 현수는 네트워크 선을 1m, 2m의 길이를 갖는 선으로 자르려고 합니다. 예를 들어 4m의 네트워크 선이 주어진다면 의 5가지 방법을 생각할 수 있습니다. (2)와 (3)과 (4)의 경우 왼쪽을 기준으로 자르는 위치가 다르면 다른 경우로 생각한다. 그렇다면 네트워크 선의 길이가 Nm라면 몇 가지의 자르는 방법을 생각할 수 있나요? ▣ 입력설명 - 첫째 줄은 네트워크 선의 총 길이인 자연수 N(3≤N≤45)이 주어집니다. ▣ 출력설명 - 첫 번째 줄에 부분증가수열의 최대 길이를 출력한다. ▣ 입력 예시 7 ▣ 출력 예시 21 #pragma warning(disable:4996) #include using namespace std; int dy[50]; int main() { int n; scanf..
#pragma warning(disable:4996) #include #include #include using namespace std; int n, r; int ch[20]; void dfs(int s, int L) { if (L == r) { for (int j = 0; j < L; j++) { printf("%d ", ch[j]); } puts(""); } else { for (int i = s; i < n; i++) { ch[L] = i; dfs(i + 1, L + 1); } } } int main() { scanf("%d %d", &n, &r); dfs(0, 0); return 0; } 위 코드는 정말 간단한 nCr를 코드로 작성한 것이다. 여러 문제에서 조합(Combination)을 사용하는..
[개념] 친구찾기(Union&Find 자료구조) / c & c++ / 제한시간 없음
▣ 문제 오늘은 새 학기 새로운 반에서 처음 시작하는 날이다. 현수네 반 학생은 N명이다. 현수는 각 학생들의 친구관계를 알고 싶다. 모든 학생은 1부터 N까지 번호가 부여되어 있고, 현수에게는 각각 두 명의 학생은 친구 관계 가 번호로 표현된 숫자쌍이 주어진다. 만약 (1, 2), (2, 3), (3, 4)의 숫자쌍이 주어지면 1번 학 생과 2번 학생이 친구이고, 2번 학생과 3번 학생이 친구, 3번 학생과 4번 학생이 친구이다. 그리고 1번 학생과 4번 학생은 2번과 3번을 통해서 친구관계가 된다. 학생의 친구관계를 나타내는 숫자쌍이 주어지면 특정 두 명이 친구인지를 판별하는 프로그램 을 작성하세요. 두 학생이 친구이면 “YES"이고, 아니면 ”NO"를 출력한다. ▣ 입력설명 - 첫 번째 줄에 반 학..
▣ 문제 이항계수는 N개의 원소를 가지는 집합에서 R개의 원소를 뽑아 부분집합을 만드는 경우의 수 를 의미한다. 공식은 nCr 로 표현된다. N과 R이 주어지면 이항계수를 구하는 프로그램을 작성하세요. ▣ 입력설명 - 첫 번째 줄에 자연수 N(1
[개념] 최대힙(priority_queue, 우선순위큐) / c++ / 제한시간 없음
▣ 문제 최대힙은 완전이진트리로 구현된 자료구조입니다. 그 구성은 부모 노드값이 왼쪽자식과 오른 쪽 자식노드의 값보다 크게 트리를 구성하는 것입니다. 그렇게 하면 트리의 루트(root)노드는 입력된 값들 중 가장 큰 값이 저장되어 있습니다. 예를 들어 5 3 2 1 4 6 7순으로 입력되면 최대힙 트리는 아래와 같이 구성됩니다. 최대힙 자료를 이용하여 다음과 같은 연산을 하는 프로그램을 작성하세요. 1) 자연수가 입력되면 최대힙에 입력한다. 2) 숫자 0 이 입력되면 최대힙에서 최댓값을 꺼내어 출력한다. (출력할 자료가 없으면 -1를 출력한다.) 3) -1이 입력되면 프로그램 종료한다. ▣ 입력설명 - 첫 번째 줄부터 숫자가 입력된다. 입력되는 숫자는 100,000개 이하이며 각 숫자의 크기는 정 수형 ..
보호되어 있는 글입니다.
[개념]이진트리 넓이우선탐색(BFS) / c & c++ / 제한시간 없음
아래 그림과 같은 이진트리를 넓이우선탐색해 보세요. 간선 정보 6개를 입력받아 처리해보세 요 넓이 우선 탐색 : 1 2 3 4 5 6 7 ▣ 입력 예시 1 2 1 3 2 4 2 5 3 6 3 7 ▣ 입력 예시 1 2 3 4 5 6 7 - c++ #pragma warning(disable:4996) #include #include #include using namespace std; int queue[100], front = -1, rear = -1, visit[10]; vector map[10]; int main() { int i, a, b, x; for (i = 1; i