본문 바로가기

Programming456

[C/C++] 백준 #2491 수열(구현) #2491 문제는 간단하게 구현만 하면 되는 문제입니다. https://www.acmicpc.net/problem/2491 2491번: 수열 0에서부터 9까지의 숫자로 이루어진 N개의 숫자가 나열된 수열이 있다. 그 수열 안에서 연속해서 커지거나(같은 것 포함), 혹은 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾 www.acmicpc.net 문제를 해결하는 방법은 간단합니다. 이전수와 비교해서 감소하지 않는 값이면, inc값을 1 증가하고 그렇지 않으면 1로 설정을 합니다. 마찬가지로 증가하지 않는 값이면, dec값을 1 증가하고, 그렇지 안으면 1로 설정을 합니다. 이렇게 얻어진 값 중, 최대값을 기록한 후에 그 값을 출력하면 됩니다. 동적 계획법이 알고리즘에 적혀있기는 하지만,.. 2023. 5. 23.
[C/C++] 백준 #2482 색상환(동적 계획법) 색상환 문제는 중복조합 문제입니다. 중복조합 문제는 식만 잘 세우면, 조합으로 문제를 해결할 수 있습니다. https://www.acmicpc.net/problem/2482 2482번: 색상환 첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다. www.acmicpc.net 색상환이 있습니다. 이 색상환은 비슷한 색들이 순차적으로 바뀌면서 쭉 이어지게 환(ring)을 이루게 됩니다. 색상환에 있는 모든 색은 이웃한 색과 비슷합니다. 그래서 이 색상환에서 몇개의 색을 고를때 이웃한 색을 고르지 않으려고 합니다. 고르는 경우의 수가 얼마가 되는지가 문제입니다. 환을 이루지 않는 경우에는 .. 2023. 5. 22.
[C/C++] 프로젝트 오일러 #84 모노폴리 확률(몬테카를로) 이 문제를 2015년 10월에 풀었네요. 지금 소스를 보니까, 몬테카를로(Monte Carlo) 기법을 이용해서 풀었네요. 문제가 요구하는대로 구현하고, 결과는 굉장히 많은 수로 무작위 연산을 한 것이죠. 그래도 여전히 결과가 잘 나오는 것으로 보아서는 몬테카를로 기법이 그렇게 나쁘지는 않은 기법이라고 봅니다. https://projecteuler.net/problem=84 모노폴리는 널리 알려진 게임입니다. 우리나라에서는 블루마블이라는 게임으로 소개되었습니다. 문제를 번역해보았습니다. (chatGPT로 번역) 더보기 게임 "모노폴리"에서 표준 보드는 다음과 같은 방식으로 구성됩니다: 플레이어는 GO 스퀘어에서 시작하며, 6면 주사위의 두 번의 결과를 합산하여 시계 방향으로 진행하는 스퀘어 수를 결정합니.. 2023. 5. 20.
[C/C++] 백준 #2468 안전 영역(탐욕 알고리즘) #2468 문제는 그래프 이론, 부르트포스 방법 등으로 풀 수 있겠지만, 전 정렬을 이용한 탐욕 알고리즘을 이용해서 풀었습니다. 어쩌다 보니, 푼 사람 내에서 상위권에 있다보니 제 소스 참조횟수가 많은 문제가 되었네요. https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 제가 생각한 것은 단순합니다. 일단 지대가 높은 것부터 낮은 순으로 정렬을 합니다. 지대가 가장 높은 곳은 비가 가장 많이 왔을 때에도 안전지대가 되겠죠. 그리고 그 영역의 개수는 상호 .. 2023. 5. 16.
[C/C++] 백준 #2458 키 순서(플로이드 워샬) #2458은 n명의 사람들중에 일부 사람들끼리 키를 비교해서 그 결과를 아는 경우에, 정확하게 자신이 몇번째 키 순서를 가졌는지 알 수 있는 사람들의 숫자를 구하라는 문제입니다. https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 처음에 접근한 방법은 위상정렬이었습니다. 하지만 위상정렬로 처리하기에는 한계가 있어서 플로이드 워샬 알고리즘을 변형해서 사용하기로 했습니다. 플로이드 워샬은 그래프에서 모든 노드간의 최소 비용 경로값을 계산해주는 알고리즘으.. 2023. 5. 11.
[Python] 백준 #2457 공주님의 정원(탐욕 알고리즘) #2457 문제는 탐욕 알고리즘을 이용해서 풀 수 있습니다. 탐욕 알고리즘은 정렬을 하고, 조건에 맞는 경우에는 우선 선택 과정을 하게 됩니다. https://www.acmicpc.net/problem/2457 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, www.acmicpc.net 문제는 공주님의 정원에 늘 꽃이 한종류 이상 피어있게 하면서, 최소의 꽃을 정원에 두는 것입니다. 최소의 꽃의 개수를 구하는 것이 목표입니다. 이 문제를 풀기 위해서는 (꽃 피는 날짜, 꽃이 지는 날짜) 쌍을 적절하게 유지해야 합니다... 2023. 5. 8.

티스토리툴바