본문 바로가기

전체 글

(C언어) 백준 11726번 : 2×n 타일링 - 컴도리돌이 문제 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.. 더보기
(c언어) 백준 1463번 : 1로 만들기 - 컴도리돌이 문제 정수 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)란? - 컴도리돌이 그래프(Graph)란? 연결되어 있는 객체 간의 관계를 표현하는 자료구조이다. 그래프 G는 (V, E)로 표시되며 V는 정점 또는 노드라고 불리며, 여러 가지 특성을 가질 수 있는 객체를 의미하고 E는 간선 또는 링크로 정점들 간의 관계를 의미한다. 그래프의 종류 무방향 그래프(undirected graph) 간선을 통해서 양방향으로 갈 수 있다. 방향 그래프(directed graph) 간선을 통해서 한쪽 방향으로만 갈 수 있다. 가중치 그래프(weighted graph) 간선에 비용이나 가중치가 할당된 그래프 그래프(graph)의 용어 인접 정점(adjacent vertex) :하나의 정점에서 간선에 의해 직접 연결된 정점 차수(degree) : 하나의 정점에 연결된 간선의 수 경로(path) : 간.. 더보기
[자료구조] 우선순위 큐(Priority Queue)란? + 힙(heap)이란? - 컴도리돌이 우선순위 큐(Priority Queue)란? 모든 데이터가 우선순위를 가지고 있고, 들어온 순서와 상관없이 우선순위가 높은 데이터가 먼저 출력된다. 스택이나 큐를 우선순위 큐로 구현할 수 있으며, 응용분야로는 네트워크 트래픽 제어, os의 작업 스케쥴링 등이 있다. 우선순위 큐 구현 방법 힙(heap)이란? 완전 이진트리(complete binary tree)로 구성되며 최대 힙, 최소 힙의 두 가지 표현법이 있다. 우선순위 큐를 위해 만들어진 자료구조로 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도의 느슨한 정렬 상태를 유지한다. 힙의 목적이 삭제 연산에서 가장 큰 값을 효율적으로 찾아내기만 하면 되는 것이므로 전체를 정렬할 필요는 없다.(최대 힙을 가정할 때) 최대 힙(max heap.. 더보기
[자료구조] 이진탐색트리(Binary Search Tree)란? - 컴도리돌이 이진 탐색 트리(Binary Search Tree)란? 이진트리 기반의 탐색을 위한 자료 구조로 효율적인 탐색 작업을 할 때 사용하는 자료 구조입니다. 이진 탐색 트리(Binary Search Tree)의 정의 -모든 노드는 유일한 키를 갖는다. -왼쪽 서브 트리 키들은 루트 키보다 작다. -오른쪽 서브 트리의 키들은 루트의 키보다 크다. -왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다. -탐색작업을 효율적으로 하기 위한 자료구조 이진 탐색 트리(Binary Search Tree)의 탐색 그림 예시 && C언어 코드 -비교한 결과가 같으면 탐색이 성공적으로 끝난다. -키 값이 루트보다 작은면 왼쪽 자식을 기준으로 다시 탐색 -키 값이 루트보다 크면 오른쪽 자식을 기준으로 다시 탐색 이진 탐색 트리(Bin.. 더보기
[자료구조/트리(tree)] 중위순회,후위순회,전위순회,레벨 순회 - 컴도리돌이 기본적인 트리의 구조를 알았으면 이제 트리에서 제일 중요한 순회를 배워보았습니다. 이진트리의 기본 순회 전위 순회(preorder traversal) 그림 예시 && c언어 코드 1. 루트 노드를 방문한다 2. 왼쪽 서브 트리를 방문한다 3. 오른쪽 서브 트리를 방문한다 처음 printf로 루트 노드의 값(value)을 처리하고 왼쪽 서브 트리와 오른쪽 서브 트리를 순서대로 순환 호출하여 전위 순회 문제를 해결합니다. 중위 순회(inorder traversal) 그림 예시 && c언어 코드 1. 왼쪽 서브 트리를 방문한다 2. 루트 노드를 방문한다 3. 오른쪽 서브 트리를 방문한다 왼쪽 서브트리를 먼저 순환 재귀 호출로 방문하고 printf로 루트 노드의 값(value)을 처리합니다. 마지막으로 오른쪽 .. 더보기
[자료구조] 트리(Tree) 란? - 컴도리돌이 트리(Tree)란? 트리는 부모-자식 관계의 노드들로 이루어져있으며, 계층적인 구조를 나타내는 자료구조입니다. 응용분야로는 회사의 조직도, 컴퓨터의 폴더 구조 ,인공지능 바둑 프로그램의 거대한 결정 트리 , 등이 있습니다. 트리(Tree)의 용어 노드(node) : 트리의 구성요소 루트(root) 부모가 없는 노드(A) 서브트리(subtree) : 하나의 노드와 자손들로 이루어짐 단말노드(terminal) : 자식이 없는 노드(E,FG,H,I,J) 비단말노드 : 자식을 가지는 노드(A,B,C,D) 레벨(level) :트리의 각층의 번호 높이(height) : 트리의 최대 레벨 차수(degree) : 노드의 자식 노드수 트리(Tree)의 종류 이진트리(binary tree) 이진트리란 모든 노드가 2개의 .. 더보기
[자료구조] 단순 연결 리스트(singly linked list), 이중 연결리스트(double linked list) - 컴도리돌이 단순 연결 리스트(singly linked list) -하나의 링크 필드를 이용하여 연결 -마지막 노드의 링크 값은 NULL 연결 리스트로 구현한 리스트 (삽입, 삭제 연산 예시 && 코드) 연결 리스트 구조체는 int형 data와 포인터 링크로 구성되어 있으며 전역 변수로 포인터 head가 NULL값으로 설정해 놓습니다. 전역 변수를 포인터 head을 사용할 경우 삽입 삭제할 때 전 노드를 찾아야 할 경우가 있기 때문에 get_entry 함수로 따로 만들어놔야 합니다. 굳이 만들지 않고 삽입 삭제 안에서 설정해놓아도 되는데 코드 길이가 길어지기 때문에 함수를 임의로 만들어 놓았습니다. 삽입 연산에서는 prev와 new_node라는 두 개의 포인터 변수를 설정하여, new_node는 현재 삽입할 값을 가.. 더보기
728x90

티스토리툴바