허브포트의 티스토리

하노이의 탑 점화식은 다음과 같다. f(n) = 1 ( n = 1) f(n) = f(n-1) + f(n-1) + 1 (n>=2) 하노이의 탑은 이렇게 표현 가능하다. 그러면 왜 이렇게 되는 걸까? 일단 1개일 때는 그냥 3번째로 바로 옴기면 된다. 3개를 옮기는 경우를 생각해보자. 두개를 2번째 칸으로 옮긴다 +f(2) 마지막 1개를3번째 칸으로 옮긴다. +1 2개를 3번째 칸으로 옮긴다. +f(2) 즉, f(3) = f(2) + 1 + f(2) 이러한 것은 n=>2일때 모두 적용되는 것이다. 따라서 이것을 일반화 해보자면. f(n) = f(n-1) + f(n-1) +1 =2f(n-1) + 1 이 된다. 또 재귀적인 방법 말고도 다른 방식으로 하노이의 탑을 표현 할 수 있다. f(n) = 2^n - 1 ..

알고리즘 2019. 12. 29. 14:03

링크드 리스트(Linked List)는 리스트를 구현하는 방법 중에서도 간단한 자료구조이다. 리스트 내의 각 요소는 노드(Node)라고 부른다. 링크드 리스트는 이다. 링크드 리스트의 노드는 데이터를 보관하는 필드와, 다음 노드와의 연결을 하는 포인터로 이루어 진다. 이런 노드들을 연결하면 링크드 리스트가 된다. 링크드 리스트에는 헤드와 테일이라는 요소를 가지고 있다. (head, tail) 이러한 링크드 리스트는 다뤄야 하는 데이터 집합의 크기를 알지 못한다고 해도 걱정할 필요가 없다. 새로운 데이터가 생기면 노드를 만들어 테일에 붙이면 되기 때문이다. 그리고, 리스트 사이에 노드를 끼워 넣거나 제거하는 것도 아주 쉽다. 해당 노드를 가르키는 포인터만 교환해주면 된다. https://domaindeve..

알고리즘 2019. 12. 28. 12:01

//잘못된 예제 int a = 10; int b = 20; a = b; b = a; //a = 20 //b = 20위의 방식대로 하면 두 변수의 값이 전혀 바뀌지 않습니다 그렇다면 어떤 방식(알고리즘)을 사용해야 할까요? 1. 바꿀 두 변수 a, b 준비2. 임시로 값을 저장할 변수, temp 준비3. temp에 a값 대입4. a에 b대입5. b에 temp 대입 이것이 두 변수의 값을 바꾸는 알고리즘입니다. 그럴싸한 예제 int a = 10; int b = 20; int temp = a; a = b; b = temp; //a는 20 //b는 10

알고리즘 2019. 12. 25. 23:46

- c++ 데이터 형식 범위(자료형 크기) 형식이름 바이트 기타 이름 값의 범위 int 4 signed –2,147,483,648 ~ 2,147,483,647 unsigned int 4 unsigned 0 ~ 4,294,967,295 __int8 1 char -128 ~ 127 unsigned __int8 1 unsigned char 0 ~ 255 __int16 2 short, short int 및 signed short int –32,768 ~ 32,767 unsigned __int16 2 unsigned short, unsigned short int 0 ~ 65,535 __int32 4 signed, signed int 및 int –2,147,483,648 ~ 2,147,483,647 unsigned..

알고리즘 2019. 12. 21. 12:42

팩토리얼은 느낌표로 자연수 뒤에 느낌표를 붙이는 것으로써 표현합니다. n! 은 1부터 n까지의 자연수를 모두 곱한 것입니다. 예를 들어 5! = 1 x 2 x 3 x 4 x 5 = 120이고 3! = 1 x 2 x 3 = 6입니다 factorial(int n)이라는 함수를 만들고 싶습니다. 그렇다면 이 함수를 어떻게 작성해야 할까요? 알고리즘을 생각해봅시다. 일단 반복문을 사용해서 시작해볼까나~~ 1에서부터 숫자를 n까지 증가시켜서 하나의 변수에 모두 곱합니다. int factorial(int n) { int temp = 1; for(int i = 2; i 결괏값이 int형의 범위를 넘어가는지 체크하고 만약 int형의 범위를 넘어간다면 int형의 범위를 넘어간다는 메시지를 띄워 주면 됩니다. int fa..

알고리즘 2019. 12. 21. 12:32