포스팅
-
백준 23978번 급상승알고리즘 2023.03.07 13:10
문제 설명 이번 문제는 효석이가 자신이 정한 N개의 날짜에 코인을 X원으로 급상승시키고 처음 코인 가격이 오른 날부터 한 개씩 매도할 때, K원 이상 현금화할 수 있는 가장 작은 정수 X를 구하는 문제입니다. (단, 코인이 X원으로 오른 뒤 하루에 1원씩 0원이 될 때까지 가격이 낮아진다.) 문제 풀이 아이디어 X를 알 때 최종 현금화할 수 있는 금액을 구하는 방법 정해진 N개의 날짜에 코인이 X원 상승한 뒤, 하루에 1원씩 작아집니다. 여기서, 코인이 급상승하는 날짜 사이의 일 수가 X보다 크다면 코인은 0원까지 떨어지게 될 것이고, 코인이 급상승하는 날짜 사이의 일 수가 X보다 작다면 코인은 X-{코인이 급상승하는 날짜 사이의 일수 } 까지만 떨어지게 됩니다. 이분 탐색 문제에서 주어진 N,K(1
-
백준 2357번 최솟값과 최댓값 (Python)알고리즘 2023.09.06 11:11
N개의 정수가 주어질 때, 구간 a~b 사이에 최소, 최대값을 찾는 문제입니다. 아이디어 1. 세그먼트 트리 주어진 숫자 개수 N과 구간 쌍 M개의 범위가 (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 100,000)이므로 모두 탐색하면서 찾는다면 시간 초과가 발생할 것으로 예측됐습니다. 그래서 세그먼트 트리를 활용하게 됐습니다. 세그먼트 트리는 데이터가 연속적으로 존재할 때 특정 범위의 데이터의 합을 구하는 방법입니다. 세그먼트 트리 5 3 8 11 2 9 4 14 8 6 의 연속된 데이터가 있다고 가정해보도록 하겠습니다. 이 숫자들 중 여러 개의 특정 구간의 숫자 합을 구할 때, 계속해서 반복을 통해 구하게 된다면 O(N) 시간이 걸리게 되므로, 데이터의 개수가 많아진다면 시간 초과가 발생해 불가능하..
-
21738번 얼음깨기 펭귄알고리즘 2023.01.25 10:14
문제 설명 이번 문제는 얼음깨기 게임의 업그레이드 버전을 플레이하면서 펭귄을 떨어뜨리지 않고 가장 많은 얼음을 깰 수 있는 방법을 찾는 문제입니다. 얼음깨기 게임의 업그레이드버전에 추가된 규칙은 다음과 같습니다. 얼음의 종류는 지지대의 역할을 하는 얼음과 일반 얼음 두 가지가 있다. 일반 얼음들은 지지대가 연결되어 있어야만 깨지지 않고 있는다. 펭귄이 올라가 있는 일반 얼음은 두 개의 지지대가 연결되어 있어야지만 깨지지 않는다. 연결된다는 의미는 지지대로부터 서로 다른 일반 얼음들을 통해 연결 관계가 이어져 있는 것을 이야기 한다. 서로 다른 지지대가 펭귄이 올라가 있는 얼음을 거치지 않고 연결되는 경우는 없다. 지지대도 깨지는 얼음입니다. 문제 풀이 아이디어 1. 펭귄을 거치지 않으면 1개의 지지대만 ..