반응형 Programming/Project Euler89 [C/C++] 프로젝트 오일러 #84 모노폴리 확률(몬테카를로) 이 문제를 2015년 10월에 풀었네요. 지금 소스를 보니까, 몬테카를로(Monte Carlo) 기법을 이용해서 풀었네요. 문제가 요구하는대로 구현하고, 결과는 굉장히 많은 수로 무작위 연산을 한 것이죠. 그래도 여전히 결과가 잘 나오는 것으로 보아서는 몬테카를로 기법이 그렇게 나쁘지는 않은 기법이라고 봅니다. https://projecteuler.net/problem=84 모노폴리는 널리 알려진 게임입니다. 우리나라에서는 블루마블이라는 게임으로 소개되었습니다. 문제를 번역해보았습니다. (chatGPT로 번역) 더보기 게임 "모노폴리"에서 표준 보드는 다음과 같은 방식으로 구성됩니다: 플레이어는 GO 스퀘어에서 시작하며, 6면 주사위의 두 번의 결과를 합산하여 시계 방향으로 진행하는 스퀘어 수를 결정합니.. 2023. 5. 20. [C/C++] 프로젝트 오일러 #83 Path sum: four ways(다익스트라) #83 문제는 난이도 25%로 설정되어 있습니다. 동적 계획법 등으로는 구현하기 어렵고, 다익스트라 알고리즘을 사용해야 합니다. 다익스트라 알고리즘 자체는 너비 우선 탐색, 프림 알고리즘과 비슷한 구현 방법으로 큐 자료구조와 우선순위 큐 자료구조의 이해가 필요합니다. https://projecteuler.net/problem=83 다익스트라 알고리즘 구현은 그래프에서 경로 찾기에서 자주 나옵니다. https://sdev.tistory.com/119 다익스트라 알고리즘 다익스트라 알고리즘은 시작점에서 다른 모든 경로로 가는 최단 거리에 대한 그래프(트리)를 만들어줍니다. 다익스트라 알고리즘을 사용하려면, 힙을 이용해서 최소의 엔티티를 찾는 것이 필요 sdev.tistory.com https://sdev.t.. 2023. 5. 6. [C/C++] 프로젝트 오일러 #82 path sum : three ways(다익스트라) 이번 문제는 앞에 #81 문제와 동일하게 경로의 합을 구하는데 있어서 최소의 경로값을 잦는 것입니다. 앞의 문제가 two ways였던 것에 비해서 이번 것은 three ways입니다. 프로젝트 오일러 문제들 초창기가 제가 알고리즘 문제들 풀기 시작한 초기였던 점을 생각했을 때, 지금 보면 유치하기 짝이 없네요. 일단 힙구조를 사용하지도 않고 짰고, 삽입정렬을 이용해서 짰네요. 뭐 삽입정렬을 한다고 한다면, \(O(N^2)\) 알고리즘이었다는 것이죠. 이것 작성할 때만 해도 STL 사용도 안 했을 때이니까요. 우선순위 큐를 사용하면 해결되었을텐데요. 행렬이 크기 않았기 때문에 풀 수 있던 것이죠. 동적 계획법으로 풀 수도 있습니다. 하지만 사이클이 있기때문에 반복을 많이 해야 안정된 값이 나오게 됩니다. .. 2022. 10. 10. [C/C++] 프로젝트 오일러 #81 Path sum : two ways(동적 계획법) 이 문제는 난이도 10% 문제로, 그래프 이론을 이용해서 풀어도 되겠지만, 기본 자체가 동적 계획법을 이용하는 것이 더 쉽습니다. 시작점은 왼쪽 위의 지점이고, 오른쪽과 아래로만 이동할 수 있고, 도착점은 오른쪽 아래의 지점입니다. 다양한 경로가 나올 수 있는데, 이 때, 최대의 값을 찾는 프로그램을 작성하면 됩니다. \[ \begin{pmatrix} \color{red}{131} & 673 & 234 & 103 & 18\\ \color{red}{201} & \color{red}{96} & \color{red}{342} & 965 & 150\\ 630 & 803 & \color{red}{746} & \color{red}{422} & 111\\ 537 & 699 & 497 & \color{red}{121}.. 2022. 9. 26. [Python] 프로젝트오일러 #80 제곱근 확장(수학) 이번 문제는 난이도 20%입니다. 사실 이 문제의 뜻을 정확하게 파악하는데 좀 문제가 있습니다. 영어권 사용자들에게도 헷갈리는 문제이기도 하죠. https://projecteuler.net/problem=80 일단 중요한 것은 이 문제를 풀기 위해서는 큰 정수 계산을 할 수 있거나, 높은 정밀도의 실수 연산이 필요합니다. 이미 알고있는 32비트 실수형이나 64비트 실수형은 정밀도가 그렇게 높지 않습니다. 32비트 실수형은 유효자리수가 6자리정도이고, 64비트 실수형은 유효자리수가 15자리 정도입니다. 그런데 이 프로그램은 100자리 이상의 유효자리수를 요구합니다. 일단 문제를 해석하면, \(\sqrt{2}\)와 같은 자연수의 제곱근은 무한소수로 표현됩니다. \( \sqrt{2} = 1.4142135623.. 2022. 9. 13. #79 암호 알아내기(Topology Sort) 이번문제는 난이도 5%로 아주 쉬운 문제로 분류되어 있습니다. 아마 단순무식(Brute Force) 방법으로도 풀리는 문제로 분류되어서인 듯 합니다. 숫자가 많지 않기 때문에 단순하게 조건에 맞도록 배열하는 것이 가능합니다. 예를 들어서 317 236 이 있다면, 총 숫자는 5가지 숫자가 쓰였으므로 5가지 숫자를 적절하게 배열한 다음에 조건에 맞는 수열을 고르는 것입니다. 일단 문제를 살펴본다면 다음과 같습니다. 주어진 숫자가 있습니다. 예를 들어서 531278이란 숫자가 있다면요. 이 숫자를 가지고 있음을 확인하면서, 네트웍 전송상에서 원래의 숫자를 알아내기 힘들게 하기 위해서 첫번째, 세번째, 다섯번째 숫자를 보내길 요구할 수 있습니다. 그러면 517을 전송하게 됩니다. 그런데 이러한 전송이 많아지면.. 2020. 2. 8. 이전 1 2 3 4 ··· 15 다음 728x90
