반응형 분류 전체보기586 우리믹스 코인 경품타기 - 문제편 남쪽나라 사람은 돈이 많다. 하지만 다른 사람들은 그것을 잘 모른다. 이 남쪽나라 사람은 특이하게도 확실한 것을 좋아한다. 무작위로 무언가 뽑더라도 반드시 당첨이 되어야 한다. 그래서 이 남쪽나라 사람은 로또를 절대 안 한다. 왜냐하면 무작위로 814만장을 로또를 사더라도 확실하게 1등 담첨될 것을 보장받지 못하니 말이다. 어느날 우리믹스 코인 경품을 1등 상품으로 주는 이벤트를 보았다. 우리믹스 코인은 이미 상폐되어서 구하고 싶어도 구하지 못 하는 코인으로 경품은 무려 80만 우리믹스 코인이었다. 돈 가치는 없지만, 본인의 전자지갑에 기념품으로 박제하고 싶었다. 한때 200억이 넘었던 코인이었으니말이다. 문제는 이것이 무작위로 할 때 반드시 당첨될 수 있는가였다. 1부터 31까지 써져있는 카드들이 어떤.. 2023. 5. 9. [Python] 백준 #2457 공주님의 정원(탐욕 알고리즘) #2457 문제는 탐욕 알고리즘을 이용해서 풀 수 있습니다. 탐욕 알고리즘은 정렬을 하고, 조건에 맞는 경우에는 우선 선택 과정을 하게 됩니다. https://www.acmicpc.net/problem/2457 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, www.acmicpc.net 문제는 공주님의 정원에 늘 꽃이 한종류 이상 피어있게 하면서, 최소의 꽃을 정원에 두는 것입니다. 최소의 꽃의 개수를 구하는 것이 목표입니다. 이 문제를 풀기 위해서는 (꽃 피는 날짜, 꽃이 지는 날짜) 쌍을 적절하게 유지해야 합니다... 2023. 5. 8. 따블당의 돈봉투 선택하기 - 문제편 따블당의 대표가 자신의 체포동의안 부결된 것을 치하하기 위해서, 돈봉투를 나누어 주기로 했다. 그런데 십여명의 이탈표가 있음이 괘씸해서, 의원들을 골려줄 작전을 했다. 대표 이야기) 여기 의원들에게 돈봉투를 나누어주는데, 그냥 주면 심심하니까, 재미삼아서 이렇게 할꺼야. 돈봉투 두개가 있는데, 두 돈봉투 중 적은 금액의 돈봉투의 금액보다 다른 봉투의 금액은 "따블" 금액이 들어있거든. 그러니 잘 선택을 해봐. 그래놓고, 돈봉투에 대표만 알 수 있는 표식을 해놓았기 때문에 의원이 큰 금액이 있는 돈봉투를 고르면, 잘 생각해봐. 적은 금액, 큰 금액 고를 확률은 똑같이 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. 이전 1 ··· 16 17 18 19 20 21 22 ··· 98 다음 728x90
