분류 전체보기590 [C/C++] 백준 #2468 안전 영역(탐욕 알고리즘) #2468 문제는 그래프 이론, 부르트포스 방법 등으로 풀 수 있겠지만, 전 정렬을 이용한 탐욕 알고리즘을 이용해서 풀었습니다. 어쩌다 보니, 푼 사람 내에서 상위권에 있다보니 제 소스 참조횟수가 많은 문제가 되었네요. https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 제가 생각한 것은 단순합니다. 일단 지대가 높은 것부터 낮은 순으로 정렬을 합니다. 지대가 가장 높은 곳은 비가 가장 많이 왔을 때에도 안전지대가 되겠죠. 그리고 그 영역의 개수는 상호 .. 2023. 5. 16. 짤짤이에 진심인 남쪽나라 사람의 짤짤이 - 문제편 남쪽나라 사람은 짤짤이에 정말 진심이다. 시간이 날 때마다 짤짤이를 하는데, 화장실에서도 짤짤이를 하기 때문에, 화장실에서도 쨍그랑 소리가 울려퍼진다. 짤짤이는 원래는 확률 게임이므로 수수료를 내면서 짤짤이로 돈을 번다는 것은 쉽지 않다. 남쪽 나라 사람은 짤짤이에 진심이므로 자신의 모든 것을 걸기로 유명하다. 우리믹스 코인의 정보를 알려준 사람과 배분율을 정하기 위해서 만났다. 일반적으로 정보제공자에게 더 많은 배분이 되기 때문에 잘해야 6:4, 심하면 8:2 까지 배분율이 정해진다. 그렇지만 남쪽나라 사람들은 어떤 사람인가? "형님, 이왕 하는 것 배분율도 짤짤이로 정하시죠!!" "짤짤이로? 얌마, 기본이 7:3인데, 짤짤이로 하면 내가 불리해질 수 있잖아." "아뇨아뇨, 형님, 제 말을 잘 들어보쇼.. 2023. 5. 15. 22 나누기 7 은 11 성냥개비 퍼즐 - 문제편 성냥개비 퍼즐은 정말 다양한 문제들이 가능합니다. 여기 재미있는 퍼즐이 있어서 소개합니다. 문제는 위 그림과 같은 수식이 있을때, 아래의 화살표에 보이는 여분의 성냥개비로 수식이 성립하도록 만드는 것입니다. 총 3가지의 성립하는 수식을 만들 수 있는데, 그것들은 무엇일까요? 답을 알기 위해서는 고대의 수학 지식도 참조해야 합니다. 2023. 5. 15. [C/C++] 백준 #2458 키 순서(플로이드 워샬) #2458은 n명의 사람들중에 일부 사람들끼리 키를 비교해서 그 결과를 아는 경우에, 정확하게 자신이 몇번째 키 순서를 가졌는지 알 수 있는 사람들의 숫자를 구하라는 문제입니다. https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 처음에 접근한 방법은 위상정렬이었습니다. 하지만 위상정렬로 처리하기에는 한계가 있어서 플로이드 워샬 알고리즘을 변형해서 사용하기로 했습니다. 플로이드 워샬은 그래프에서 모든 노드간의 최소 비용 경로값을 계산해주는 알고리즘으.. 2023. 5. 11. 우리믹스 코인 경품타기 - 문제편 남쪽나라 사람은 돈이 많다. 하지만 다른 사람들은 그것을 잘 모른다. 이 남쪽나라 사람은 특이하게도 확실한 것을 좋아한다. 무작위로 무언가 뽑더라도 반드시 당첨이 되어야 한다. 그래서 이 남쪽나라 사람은 로또를 절대 안 한다. 왜냐하면 무작위로 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. 이전 1 ··· 18 19 20 21 22 23 24 ··· 99 다음 728x90
