Jupitor's Blog

Write a program that solves the following problem: Three missionaries and three cannibals come to a river and find a boat that holds two people. Everyone must get across the river to continue on the journey. However, if the cannibals ever outnumber the missionaries on either bank, the missionaries will be eaten. Find a series of crossings that will get everyone safely to the other side of the ri..

You have two jugs: a 4-gallon jug and a 3-gallon jug. Neither of the jugs have markings on them. There is a pump that can be used to fill the jugs with water. How can you get exactly two gallons of water in the 4-gallon jug? 당신한테 물통 2개가 있는데, 4갤런짜리랑 3갤런짜리다. 2개 다 어떤 마킹같은건 안되있다. 옆에는 물통에 물을 가득 채울 수 있는 펌프가 있다. 4갤런짜리 물통에 2리터를 담을 수 있는가? 바로 다음 문제는 Generalize the problem above so that the parameters to y..

저번 포스트에서 정확한 BFS방법은 아니지만 그와 흡사한 제가 혼자 생각한 알고리즘으로 PrimePath 문제를 풀어보았는데요. 굉장히 느렸고, Dijkstra 알고리즘이 궁금해서 이 알고리즘으로 한번 해볼까, 싶더군요. 결과를 먼저 말씀드리자면 제가 독자적으로 만들어낸 알고리즘은 Trash(...) 였습니다. 시간이 얼마나 걸렸는지를 먼저 보시죠. 위에가 Dijkstra 알고리즘, 아래가 저의 알고리즘을 이용한 결과입니다. 둘다 최단 경로를 찾아냈지만 시간 차이가 엄청납니다. Dijkstra는 139ms, 제 건 16252ms... 100배 이상이 차이납니다 =_=; Dijkstra는 유명한 알고리즘으로 알려져 있고 많은 응용이 된다고 합니다. 자세한 설명은 검색하면 정말 많이 나옵니다. (wikipe..

알고리즘 문제 중에 이런 문제가 있습니다. 특정한 4자리 숫자 2개 a, b가 있습니다. 숫자 a의 한 자리 숫자만을 변경해서 b를 만들되, 이 때 거쳐가는 숫자들은 모두 소수여야 합니다. 몇 번을 거쳐야만 숫자 b를 만들 수 있는지 구하는 문제입니다. 예를들면, 1033 에서 8179 로 바꾸는 경로를 생각해봅시다. 1033 1733 3733 3739 3779 8779 8179 이렇게 여섯 단계를 거쳐서 8179로 만들 수 있겠죠. 중간에 1733부터 8779는 모두 소수입니다. 이 문제를 처음 접하고 저는 어떻게든 해서 문제를 풀 수 있게 됬는데 다른 사람의 글을 보니 Breadth-first search 또는 Dijkstra’s algorithm algorithms 알고리즘을 사용해서 풀 수 있다고..

c언어에서 malloc, realloc 등으로 메모리를 할당하고 free로 메모리를 반환할때, 이미 해제된 메모리를 또 한번 잘못 free로 반환하게 될 경우 자칫하다간 심각한 오류를 발생시킬 수 있다. 따라서 free로 해제시킨 포인터에 NULL을 할당하여 사고를 예방할 수 있다. 그렇다면 free 함수 자체가 해당 포인터가 가르키는 메모리를 해제 한 후 포인터에 NULL을 대입하면 되지않는가?? 라고 할 수 있는데, free의 프로토 타입을 한번 보자. void free(void *ptr) 다들 알다시피 free 함수에 매개변수로는 포인터의 주소가 간접참조되므로 포인터의 주소 자체를 변경할 수는 없다. 그래서 위에서 말했다 시피 free 문을 쓰고 난 후 ptr = NULL 을 해주거나 이게 귀찮으면..

부록에 나오는 선택정렬을 c언어로 한번 구현해 봤습니다. 간단합니다. 첫번째 항부터 마지막 바로 전 항까지, 해당 항을 제외한 나머지 항들을 비교하고 해당 항이 비교항보다 클 경우 두 항의 위치를 변경합니다. 뭔가 말로 설명하면 부족한데, 코드를 보시면 이해가 가실 겁니다. 가장 시간이 오래 걸리는 경우는 오름차순으로 정렬되어있는 배열이겠으므로, (n-1) + (n-2) + ... 1 = Big-O(N^2) 이고 Big-Ω(1) 이겠네요. 실행 결과입니다.

책의 마지막 챕터의 도전 실전 예제입니다. 어렵습니다. =.=;; 정말 전 c언어에 재능이 없는듯... 실행 결과입니다. 운영체제마다 Ctrl + z을 몇번 입력하느냐에 따라 scanf 가 -1 을 반환하는 경우가 다르다고 하네요.

마찬가지로 간단한 c언어 문제입니다만 저한테는 정말 간단하지가 않군요... b.txt의 단어들 중에 a.txt에도 존재하는 단어들만 c.txt에 적어두는 프로그램입니다. a.txt, b.txt, c.txt 의 내용은 이와 같구요. 소스코드입니다. 결과 화면입니다. 정말 쉬운건데도 정말 어렵네요 ㅡ.ㅡ;; 역시 명불허전 c언어...