본문 바로가기

분류 전체보기590

따블당의 돈봉투 선택하기 - 문제편 따블당의 대표가 자신의 체포동의안 부결된 것을 치하하기 위해서, 돈봉투를 나누어 주기로 했다. 그런데 십여명의 이탈표가 있음이 괘씸해서, 의원들을 골려줄 작전을 했다. 대표 이야기) 여기 의원들에게 돈봉투를 나누어주는데, 그냥 주면 심심하니까, 재미삼아서 이렇게 할꺼야. 돈봉투 두개가 있는데, 두 돈봉투 중 적은 금액의 돈봉투의 금액보다 다른 봉투의 금액은 "따블" 금액이 들어있거든. 그러니 잘 선택을 해봐. 그래놓고, 돈봉투에 대표만 알 수 있는 표식을 해놓았기 때문에 의원이 큰 금액이 있는 돈봉투를 고르면, 잘 생각해봐. 적은 금액, 큰 금액 고를 확률은 똑같이 50%지? 그러니 내가 선택을 바꿀 기회를 줄테니까, 기대값을 계산해봐. 방금전 선택한 돈봉투에 100만원밖에 없네. 그러면 다른 봉투에는 .. 2023. 5. 7.
우리믹스 코인 최고점에 팔기 - 문제편 주식이면 주식, 코인이면 코인. 최고점에 잘 팔기로 유명한 남쪽 나라 사람이 있다. 이 사람은 호주(Austria)에 사는 이모 교수(an aunt professor)가 알려준 방법을 이용해서 효율적으로 최고점을 판별한다. 호주 이모 교수가 알려준 방법은 보유기간 중 최고점을 찾기 위해서는 일정기간동안 가장 높은 가격을 기억하고 있다가 그 후에 그 가격보다 높은 것을 선택하라는 것이었다. 이번에 우리믹스 코인을 산 남쪽 나라 사람이 최고점에 코인을 팔기 위해서 고민해야 한다. 석달내에 우리믹스 코인을 팔아야 해서, 84 영업일동안 최대 보유하고 있어야 한다. 자존심때문에 최고점에 못 팔면, 헐값에 처분해도 상관이 없다. 우리믹스 코인은 영업일에만 거래되며, 워낙 투기성이 강해서 그날 그날 가격은 무작위에.. 2023. 5. 7.
따블당의 돈봉투 분배 - 문제편 따블당은 일을 마치면 "자 다음은 따블, 따따블로"를 외쳐서 "따블당"이라고 한다. 이 당에서는 업자로부터 돈을 받으면, 정해진 규칙에 의해서 돈봉투를 나누어 주는 그룹이 존재한다. 이 그룹의 서열 1위자가 당대표를 맡게 된다. 그만큼 힘이 있는 그룹이다. 일단 돈봉투에는 무조건 300만원씩(받는 사람들의 1회분 식사비)을 정확하게 넣는다. 남는돈은 서열 1위자인 대표가 챙긴다. 또한 1위 서열자는 자신의 이득을 최대화할 수 있게 분배 의견을 낸다. 그래서 서열이 오르는 것이 매우 중요하다. 그룹내 모든 의원들은 서열이 있으며, 동순위 서열은 존재하지 않는다. 돈봉투에는 반드시 300만원만 들어가 있다. 1. 대표(1위 서열자)가 분배 의견을 낸다. 2. 분배 의견을 낸 것에 대해 따블당의 그룹내 모든 .. 2023. 5. 7.
[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++] 백준 #2448 별 찍기 - 11(재귀 함수) #2447 문제와 같이 이번 문제도 재귀 함수를 이용한 별찍기입니다. 문제는 프랙탈에서 자주 나오는 사이펀스키 삼각형(Sierpiński triangle)을 찍는 것입니다. https://www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net #2447 문제와 마찬가지로 캔버스를 만들고 재귀 함수를 이용하여 풀었습니다. //------------------------------------------------ // baekjoon #2448 - Printing Stars - 11 // - by Aubrey Choi /.. 2023. 5. 6.
[C/C++] 백준 #2447 별 찍기 - 10(재귀 함수) 별찍기 프로그램을 작성하는 프로그래밍 언어를 배울 때, 초기에 자주 나오는 문제입니다. 일반적으로 직각삼각형, 이등변삼각형을 많이 찍습니다. 이 문제들은 피라미드 찍기라는 이름으로도 많이 나옵니다. 조금 더 가면 다이아몬드 형태도 찍을 수 있게 됩니다. 일반적인 별 찍기 문제는 난이도면에서 상당히 낮습니다. 이번 문제는 난이도가 높은 별 찍기에 속합니다. 단순한 반복문 중복으로는 해결하기 어렵습니다. https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별.. 2023. 5. 6.
728x90