방구석 컴퓨터/방구석 자료구조&알고리즘

하노이 탑

아래의 그림에서 A 타워에 놓인 N개의 원반을 규칙을 만족하며 모두 C로 이동시켜야 한다. 규칙 1. 최소한의 횟수만 움직여야 한다. 규칙 2. 더 큰 원반이 자신보다 작은 원반위로 올 수 없다. 규칙 3. 동시에 하나의 원반만 다른 기둥으로 옮길 수 있다. 위의 하노이 탑 문제는 보통 재귀로 풀게된다. 재귀로 풀기위해서는 보통 몇 번의 경우를 생각해보고 일정한 규칙을 반복하면 그것을 통해서 재귀적으로 함수를 호출하면 된다. 사실 나도 이 문제가 처음에 잘 이해가 되지않았지만 손으로 해보니깐 알게되었다. 헷갈린다면 원판이 3개가 있다고 가정하고 그림을 그려가면서 생각해보면 도움이 될 것이다. 정답 소스는 아래와 같다. #include void hanoi(int n, char start, char work..

2021. 1. 14. 13:57

방구석 컴퓨터/C,C++

포인터의 위험성💀

더보기 C 프로그래밍을 할 때 포인터가 실제로 어떤 대상을 가리키고 있지 않을 때는 값을 전부 NULL로 설정하는 것이 바람직 하다. 위와 같이 설정함으로써 프로그램 밖이나 합당하지 않은 메모리 영역을 참조할 가능성이 적어진다. 덧붙여서 또 다른 유용한 프로그래밍 기법은 포인터 타입 간의 변환을 할 때 명시적인 타입 변환(type cast)을 하는 것이다. 예를 들면 아래와 같다. pi = malloc(sizeof(int)); //pi에 정수에 대한 포인터를 저장 pf = (float*)pi; //정수에 대한 포인터를 부동소수에 대한 포인터로 변환 많은 시스템에서 포인터의 크기는 int 타입의 크기와 같다. 또 int는 디폴트 타입 명세자이므로, 어떤 프로그래머들은 함수를 정의할 때 반환 값의 타입을 생..

2021. 1. 14. 12:38

방구석 컴퓨터/C,C++

동적 메모리 할당[C]

프로그램에서 새로운 정보를 저장할 공간을 확보하기를 원할 때가 있다. 프로그램을 작성할 당시에는 얼마나 많은 공간이 필요한지 알 수도 없고 그렇다고 사용되지 않을지도 모르는 아주 큰 공간을 미리 할당해놓기는 부담스럽기 때문이다. 이러한 문제를 해결하기 위해 C 에서는 실행 중에 메모리 할당을 할 수 있도록 히프(heap)라는 기법을 제공한다. 위에서 말한 메모리 할당을 위해서는 malloc 이라는 함수를 호출하여 필요한 양의 공간을 요구할 수 있다. malloc에 대한 MSDN 설명 : https://msdn.microsoft.com/ko-kr/library/6ewkz86d.aspx malloc 함수를 사용했을 때, 요구한 공간의 크기를 사용할 수 있으면 메모리 영역에 있는 그 공간의 시작 주소에 대한 ..

2021. 1. 13. 22:54

방구석 컴퓨터/C,C++

포인터[C]

포인터(pointers)는 C 언어에 기본적이기 때문에 C는 이들에 대해 많은 지원을 제공하고 있다. 실제로 C 언어에서는 어떤 타입 T에 대해서 T의 포인터 타입이 존재한다. 그리고 포인터 타입의 실제 값은 메모리의 주소가 된다. 포인터 타입에서 사용되는 두 가지 중요한 연사자는 2개가 있다 - & : 주소 연산자 - * : 역참조(간접 지시) 연산자 사용되는 예를 살펴보면 int i, *pi; // i는 정수 변수이고, pi는 정수에 대한 포인터 pi = &i; // &i는 i의 주소를 돌려주어 그 값을 pi의 값으로 지정 i = 10; // i에 값을 저장하는 방법 *pi = 10; // i에 값을 저장하는 또 다른 방법 위에 있는 예시중 마지막 2줄의 경우 모두 변수 i의 값으로 10 이 저장된다..

2021. 1. 13. 18:03