문제1 3n+1문제출처 : http://www.programming-challenges.com/ Consider the following algorithm to generate a sequence of numbers. Start with an integer n. If n is even, divide by 2. If n is odd, multiply by 3 and add 1. Repeat this process with the new value of n, terminating when n = 1. For example, the following sequence of numbers will be generated for n = 22:22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 ..
간단한 큐(Queue)의 구현 순환 큐가 가장 좋은 것으로 알고 있지만 빠른 알고리즘의 구현을 할 경우에는 전체 큐의 범위를 넉넉하게 잡고 아래와 같은 방식으로 구현하였다.큐는 BFS 알고리즘을 쓸때 주로 이용된다. 여기서 사용된 Front 와 Rear 의 용도는 다음과 같다. 값의 존재 기준으로 보면Front 는 값이 존재하는 제일 앞에서 index 값이 -1 만큼인 값Rear 는 값이 존재하는 제일 마지막에서 index 값이 +1 만큼인 값 값을 넣어야 하는 기준으로 보면값을 꺼낼 때 Front 의 현재 index 에서 +1의 위치 값을 꺼내온다.값을 넣을 때 Rear 의 index 위치에 값을 넣는다. Queue에 Push 할때는 Rear 가 가리키는 Index 에 넣고 Rear 의 값을 +1 한다..
[BackTracking] 체스 여왕말 놓기 (N-Queen Problem) 되추적(Backtracking) 방법을 얘기 할 때 가장 많이 거론 되는 듯한 N-여왕말(N-Queen) 문제이다. 어떤 문제인가하면 서양 장기(Chess:이후 체스)의 여왕말(Queen:이후 퀸)을 서로가 서로의 이동경로가 아닌 위치에 있도록 최대한 많은 퀸을 체스판 위에 놓는 문제이다. 원래 체스판은 8ⅹ8이지만 간단히 4ⅹ4일 경우에 좌측의 결과와 같이 되는 경우를 찾는 것이 바로 N-Queen 문제 이다. 4ⅹ4일 경우에는 좌측과 같은 2가지의 경우만 나오지만 체스판이 커지면 커질수록 다양한 경우의 수가 나온다. 우선 정해진 것은 NⅹN의 체스판에 올라갈 수 있는 퀸의 최대 갯수는 언제나 N이 된다는 점이다. 그렇다면 어..
Quick Sort(퀵정렬) 알고리즘 연속적인 분할에 의한 정렬. 처음 하나의 축을 정해서 이 축의 값보다 작은 값은 왼쪽에큰 값은 오른쪽으로 위치시킨다. 왼쪽과 오른쪽의 수 들은 다시 각각의 축으로 나누어져축값이 1이 될 때까지 정렬한다 특징 안정성 없음 O(NlogN) : 최선의 경우 log2N (축값이 정확히 가운데를 가질 경우)O(N^2) : 최악의 경우 가장 많이 사용되는 정렬법으로 1960년 C.A.R. Hoare에 의해 고안되었다. Code(코드) 재귀함수를 사용한다. #include #include #include #define SIZE 20 #define SWAP(x,y,t) ( (t)=(x), (x)=(y), (y)=(t) ) void QuickSort(int left, int righ..