늦깍이 코린이

https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 문제 // 입력 27 // 출력 *************************** * ** ** ** ** ** ** ** ** * *************************** *** ****** ****** *** * * * ** * * ** * * * *** ****** ****** *** *************************** * ** ** ** *..

https://www.acmicpc.net/problem/10870 10870번: 피보나치 수 5 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 문제 문제 풀이 기본 재귀함수 문제다. 푼 방법 1) base case 를 생각한다. 2) 피보나치의 수는 0 과 1로 시작한다. 첫 번째, 두 번째 수가 이미 정해져있으므로, base case는 fibo(0), fibo(1)이 되겠다. 3) 피보나치는 f(n) = f(n-1) + f(n-2)를 하면 되는데, 앞서 base case가 설정되어있기 때문에, 0..

https://www.acmicpc.net/problem/10872 10872번: 팩토리얼 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net 문제 문제 풀이 기본 재귀함수 문제다. *재귀함수란? - 본인을 다시 호출하는 함수 - (주의) 본인을 다시 호출하는 함수이기 때문에 무한 루프에 빠질 가능성이 있다. - (중요) 무한 루프에 빠지지 않기 위해 base case를 만들어 놓는 것이 매우 중요 푼 방법 1) 정수 N 이 1일때, 1을 return해주는 base case 를 만들어 무한 루프에 빠지지 않도록 한다. 2) 정수 N 까지의 곱을 구하는 팩토리얼이므로, factorial 함수는 정수 N 과 factorial(N-1)이 계속해서..

https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net Remind Binary Tree Binary Tree란 무엇인가? 각 부모 노드가 최대 두 개의 자식 노드를 가지는 자료구조 각각의 자식 노드는 왼쪽, 오른쪽이라고 명시하기 때문에, 일반적인 트리 구조가 아님! 전위 순회, 후위 순회, 중위 순회 루트 노드부터 모든 노드를 어떻게 방문하는 순서 (부모(1) - 왼쪽 자식(2) - 오른쪽 자식(3)) 전위 순회 : (1) - (2) - ..

학교 수업 '자료구조' 복습입니다. Binary Search Trees(BST)란? 다음 조건을 따르는 이진 트리이다. 1) 모든 노드는 유일한 키를 갖는다. 2) K라는 키를 갖는 노드의 왼쪽 subtree에 있는 모든 노드는 K보다 작은 키를 갖는다. 3) K라는 키를 갖는 노드의 오른쪽 subtree에 있는 모든 노드는 K보다 큰 키를 갖는다. 4) 모든 subtree는 BST이다. BST as a Dictionary Implementation Search Insert/Remove Sorted list(array) O(log𝓃) O(𝓃) Unsorted list(array) O(𝓃) O(𝓃) Binary Search Tree O(𝑑) = O(log𝓃) (이상적인 경우) O(𝑑) = O(log𝓃) (..

학교 수업 '자료구조' 복습입니다. Binary Tree 구현(Link를 사용한 Implementation) 방법 1 : 리프 노드와 내부 노드를 똑같이 구현한다. interface BinNode { E getItem(); BinNode left(); BinNode right(); } 해당 방법으로 구현시, null 값의 개수가 node의 개수 + 1 개 이다. 방법 1의 space overhead *space overhead란? total space(사용 메모리의 총량) - data space(담고자하는 데이터를 위한 메모리 사용량) 위 그림) 데이터 A,B,C,D,E,F,G,H,I -- 9개의 data space total space -- 9 * data + 9 * 2 * pointer space o..

학교 수업 '자료구조' 복습입니다. Binary Trees란? 이진 트리의 정의 각 노드가 자식 노드를 최대 두 개까지만 가지는 트리. 두 자식 노드는 각 각 왼쪽 자식, 오른쪽 자식이라고 부름. *왼쪽, 오른쪽이라고 위치를 명시하기 때문에, 같은 두 개의 자식을 가지고 있는 트리라도 일반적인 트리와 이진 트리는 서로 다름. 정 이진 트리 full binary tree : 각 노드의 자식 노드 수가 2 또는 0인 트리 완전 이진 트리 complete binary tree : 가장 깊은 레벨을 제외한 모든 레벨이 가득 차 있음 마지막 레벨의 노드들은 가능한 왼쪽에 존재 포화 이진 트리 perfect binary tree : 모든 단말 노드의 레벨이 같음 모든 내부 노드의 자식의 수가 2임 Q1) 포화 이진..

Tree란? 자료의 계층적 성질의 도식화 조직도, 토너먼트, 카테고리, etc. acyclic, undirected, connected graph를 의미한다. graph : 노드와 노드들을 연결하는 edge로 구성된 자료. ayclic : 노드들 사이에서 서로 순환하는 고리가 없는 것. undirected : 간선에 방향이 없는 것. connected : 모든 노드들이 전부 연결되어 있는 것. 위 세 가지 조건을 모두 만족해야, 트리라고 할 수 있다. Rooted Tree - Tree Data Structure (자료구조에서의 Tree) 루트가 있는 트리 : 트리구조를 노드와 간선의 집합으로 표현한 것. 일반적인 트리는 루트가 없지만, 자료구조에서는 대체로 루트가 있는 트리를 말한다. Tree와 Root..

인프런의 '영리한 프로그래밍을 위한 알고리즘 강좌' 내용 정리입니다. 순환적 알고리즘의 설계 적어도 하나의 base case, 순환되지 않고 종료되는 case가 반드시 있어야한다. 모든 case는 결국 base case로 수렴해야함. 암시적 매개변수를 명시적 매개변수로 바꾸어라. 다양한 예들 순차 탐색(sequential search) - recursion이 없는 버전 // data[0]에서 data[n-1] 사이에서 target을 검색하는 것. // 검색 구간의 시작 인덱스 0은 보통 생략(암시적 매개변수) int search(int [] data, int n, int target){ for(int i = 0 ; i < n ; i++){ if (data[i] == target) return i; ret..

인프런의 '영리한 프로그래밍을 위한 알고리즘 강좌' 내용 정리입니다. Recursion이란? 자기 자신을 호출하는 함수 ( 재귀 함수 ) pubilc class Code01 { public static void main(String [] args) { func(); } public static void func() { System.out.println("Hello..."); func();// 재귀 함수 } } 무한 루프에 빠지지 않는 재귀 함수 적어도 하나의 recursion에 빠지지 않는 경우를 만들면 된다. pubilc class Code01 { public static void main(String [] args) { int n = 4; func(n); } public static void func..