C언어

문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. #include // int DP(int n) // { // if(n==1) return 1; // if(n==2) return 2; // return (DP(n-1) + DP(n-2))%10007; // } int main(void) { int n = 0 ; scanf("%d",&n); int DP[1010] = {0,}; DP[0] = 1; DP[1] = 1; for(int..

문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. #include int min(int x,int y) { return x > y ? y : x; } int output(int data) { if(data == 1) return 0; if(data % 3 == 0) return(min(1+output(data/3),2+o..

그래프(Graph)란? 연결되어 있는 객체 간의 관계를 표현하는 자료구조이다. 그래프 G는 (V, E)로 표시되며 V는 정점 또는 노드라고 불리며, 여러 가지 특성을 가질 수 있는 객체를 의미하고 E는 간선 또는 링크로 정점들 간의 관계를 의미한다. 그래프의 종류 무방향 그래프(undirected graph) 간선을 통해서 양방향으로 갈 수 있다. 방향 그래프(directed graph) 간선을 통해서 한쪽 방향으로만 갈 수 있다. 가중치 그래프(weighted graph) 간선에 비용이나 가중치가 할당된 그래프 그래프(graph)의 용어 인접 정점(adjacent vertex) :하나의 정점에서 간선에 의해 직접 연결된 정점 차수(degree) : 하나의 정점에 연결된 간선의 수 경로(path) : 간..

우선순위 큐(Priority Queue)란? 모든 데이터가 우선순위를 가지고 있고, 들어온 순서와 상관없이 우선순위가 높은 데이터가 먼저 출력된다. 스택이나 큐를 우선순위 큐로 구현할 수 있으며, 응용분야로는 네트워크 트래픽 제어, os의 작업 스케쥴링 등이 있다. 우선순위 큐 구현 방법 힙(heap)이란? 완전 이진트리(complete binary tree)로 구성되며 최대 힙, 최소 힙의 두 가지 표현법이 있다. 우선순위 큐를 위해 만들어진 자료구조로 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도의 느슨한 정렬 상태를 유지한다. 힙의 목적이 삭제 연산에서 가장 큰 값을 효율적으로 찾아내기만 하면 되는 것이므로 전체를 정렬할 필요는 없다.(최대 힙을 가정할 때) 최대 힙(max heap..

기본적인 트리의 구조를 알았으면 이제 트리에서 제일 중요한 순회를 배워보았습니다. 이진트리의 기본 순회 전위 순회(preorder traversal) 그림 예시 && c언어 코드 1. 루트 노드를 방문한다 2. 왼쪽 서브 트리를 방문한다 3. 오른쪽 서브 트리를 방문한다 처음 printf로 루트 노드의 값(value)을 처리하고 왼쪽 서브 트리와 오른쪽 서브 트리를 순서대로 순환 호출하여 전위 순회 문제를 해결합니다. 중위 순회(inorder traversal) 그림 예시 && c언어 코드 1. 왼쪽 서브 트리를 방문한다 2. 루트 노드를 방문한다 3. 오른쪽 서브 트리를 방문한다 왼쪽 서브트리를 먼저 순환 재귀 호출로 방문하고 printf로 루트 노드의 값(value)을 처리합니다. 마지막으로 오른쪽 ..