Programming456 [C/C++] 정올 1141. 불쾌한 날 문제는 다음과 같습니다. http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=421&sca=3020 이 문제를 풀기 위해서는 모든 입력을 배열에 넣고 할 수도 있지만, 사실 큰 소가 들어오면, 그 사이에 있는 작은 소들은 더 이상 앞의 소들을 볼 수 없기 때문에 계속 입력을 유지할 필요가 없습니다. 예를 들면, 현재 소들의 키가 다음과 같이 되어 있다면, 13 10 9 6 4 여기에 8 의 소가 오면, 6과 4의 키를 가지는 소들은 더 이상 유지할 필요가 없습니다. 그래서 그 소들을 없애면서 볼 수 있는 소들의 숫자 합을 늘린 후 다음과 같이 배열을 유지하면 됩니다. 13 10 9 8 이렇게 하면 소들의 배열을 최소화할 수 있습니다. 제가 작성한 소스입니다... 2015. 3. 4. [C/C++] 프로젝트 오일러 #28 : 회전하는 숫자들의 대각선 합 이 프로그램은 사실 원하는 배열을 잡고, 숫자를 배열한 후에 대각선의 합을 구해도 됩니다.그렇게 한다고 해서 시간이 엄청 걸리는 것도 아니니 말이죠. 그러나 처음 제가 이 프로젝트 오일러 글들을 쓰면서, 어떻게 하면 보다 빠르게 계산할 것인가를 고민했기 때문에, 이 문제 역시 복잡도를 낮추어 계산하도록 하였습니다. 1부터 N까지의 합, 제곱 합 등의 공식을 도출할 줄 안다면, 이 문제 역시 간단하게 하나의 식으로 만들 수 있습니다. 여기서는 다음과 같은 식이 나오게 됩니다. \[ \text{result} = 1 + \frac{8n(n+1)(2n+1)}{3} + 2n(n+1) + 4n \] 이 수식에 따라서 구한 프로그램은 다음과 같습니다.역시 이 프로그램은 참고용으로만 해주세요.//-----------.. 2015. 3. 4. [C/C++] 프로젝트 오일러 #27 : 2차식 소수 생성 Project Euler #27 “Quadratic Primes” 문제는 다음을 요구합니다:주어진 이차식 \(n^2 + an + b\) 에서 n 은 0부터 시작하는 정수이고, a 와 b 는 정수 범위 |a| 요약:1. \(n^2 + an + b\) 가 연속된 n 에 대해 최대한 많은 소수를 생성하도록 하는 a 와 b 를 찾는다.2. 그런 a 와 b 의 곱을 구한다. \( n^2 + n + 41 \) 식은 너무나도 유명한 2차식 소수 생성 공식입니다. n의 값이 0부터 39까지 총 40개의 연속된 소수를 생성합니다.더 많은 소수를 내기 위해서는 더 큰 숫자가 필요하겠죠. 일단 문제에 있는 것을 조금 더 보자면,\[ n^2 + an + b \quad \text{where} \quad .. 2015. 2. 28. [C/C++] 프로젝트 오일러 #26 : 순환고리 이번 문제는 가장 긴 순환고리를 찾는 문제입니다. 사실 순환고리는 오일러의 수 문제로 귀결됩니다. 오일러수는 다음과 같은 형태로 정의해서 낼 수 있습니다.\[ n = \prod_{p_k \mid n} p_k^{a_k} \]라고 한다면, 오일러의 수는\[ \phi(n) = \prod_{p_k \mid n} (p - 1)p^{a_k - 1} \]이라고 할 수 있습니다.즉, n이 합성수라고 한다면, 오일러의 수는 엄청나게 줄어들게 됩니다. n이 소수라면 n-1 이 오일러의 수가 됩니다.가장 긴 순환고리를 찾기 위해서는 사실 오일러의 수만 가지고 판단할 수는 없습니다. 10이란 숫자를 가지고 10이 n의 원시근이면 오일러의 수와 동일한 순환고리를 가지겠지만, 원시근이 아니라면, 오일러의 수의 약수 중 .. 2015. 2. 27. [C/C++] 슬라이딩 퍼즐 - A* 알고리즘으로 풀기 이제, 최종적으로 구현을 한 프로그램입니다. A* 알고리즘을 적용하기 위해서 A* 용 자료구조를 설계했습니다. A* 알고리즘에서는 기본적으로 힙 구조를 사용하며, 검색을 빨리 하기 위해서 해시테이블을 이용합니다. 그래서 두 가지 모두를 결합한 형태의 자료구조를 만들었습니다. [PuzzleNode 자료구조]class PuzzleNode : public PQueue::Node{public: PuzzleNode(char *csquares, int cEmptySquare, int cvalue) : value(cvalue), visited(false) { squares = csquares; emptySquare = cEmptySquare; est = 0; .. 2015. 2. 18. [C/C++] 슬라이딩 퍼즐 - 움직임 슬라이딩 퍼즐의 자료구조를 잡는 것이 필요한데요. 제 경우에는 단순 배열로 작성을 했습니다. char *squares; int emptySquare; squares 변수는 1차원 배열로, 2차원 배열을 따로 복잡하게 구성하지 않았습니다. 사실 C/C++ 언어에서 단순 배열은 모두 1차원 배열로 인식을 합니다. 형식만 2차원, 3차원이 되는 것 뿐이죠. emptySquare는 어떤 칸이 비어있는지를 나타냅니다. 해당 칸은 0이란 값을 적게 됩니다. 이 자료구조를 토대로 움직임 함수를 구현한 것입니다. bool Move(PuzzleParams *param, eMove move){ int newEmptySquare = Move(param->squares, param->rows, param->c.. 2015. 2. 18. 이전 1 ··· 61 62 63 64 65 66 67 ··· 76 다음 728x90
