개발하는 사막여우

https://www.acmicpc.net/problem/19638 19638번: 센티와 마법의 뿅망치 마법의 뿅망치를 센티의 전략대로 이용하여 거인의 나라의 모든 거인이 센티보다 키가 작도록 할 수 있는 경우, 첫 번째 줄에 YES를 출력하고, 두 번째 줄에 마법의 뿅망치를 최소로 사용한 횟수 www.acmicpc.net 소스코드 풀이 ★ 가장 키가 큰 거인의 키부터 반토막을 내기 위해 최대힙을 만들어줍니다. ★ 이후 반복문을 도는데, 키가 가장 큰 거인의 키가 센티의 키보다 크거나 같을 때를 보면, 1인 경우에는 더이상 쪼갤 수 없으며 최대힙인데도 가장 큰 거인의 키가 1이라는 것은 양의 정수 중 가장 작은 경우이기 때문에 break를 통해 반복문을 바로 빠져나옵니다. 이러한 코드가 없다면 예제로 주..

https://www.acmicpc.net/problem/23757 23757번: 아이들과 선물 상자 모든 아이들이 실망하지 않고 각자 원하는 만큼 선물을 가져갈 수 있으면 $1$을, 그렇지 않으면 $0$을 출력한다. www.acmicpc.net 소스코드

https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 소스코드 풀이 ★ 문제 자체는 쉬운 거 같은데 왜 정답률이 낮을까라는 의문이 있었는데, 메모리 초과를 2번이나 확인하고서 깨달았던 문제였습니다 ! ★ 입력값이 1,000,000까지 들어오기 때문에 엄청나게 큰 메모리가 dp 배열에 들어가게 됩니다. 그렇기에 dp 배열에 값을 넣기 전에 15746으로 나눈 나머지의 값을 그때마다 저장하여 메모리의 크기를 낮춰줘야 합니다 !

https://www.acmicpc.net/problem/14235 14235번: 크리스마스 선물 크리스마스에는 산타가 착한 아이들에게 선물을 나눠준다. 올해도 산타는 선물을 나눠주기 위해 많은 노력을 하고 있는데, 전세계를 돌아댕기며 착한 아이들에게 선물을 나눠줄 것이다. 하지만 www.acmicpc.net 소스코드 풀이 ★ 우선순위 큐를 활용하여 문제를 풀었습니다. 파이썬은 heap 자료구조를 통해 우선순위 큐를 만들 수 있습니다. 최초의 힙은 최소힙의 형태를 띄지만 이 문제에서는 최대힙 구조가 필요하였습니다. ★ 최대힙 구조를 만들기 위해 힙에 원소를 삽입하는 과정에서 - 부호를 붙였습니다. 이렇게 되면 -2 보다 -3이 더 작기 때문에 [-3, -2] 형태로 힙이 만들어지고, 출력할 때는 양수로 ..

https://www.acmicpc.net/problem/1935 1935번: 후위 표기식2 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이 www.acmicpc.net 소스코드 풀이 ★ 후위 표기식을 스택을 사용하여 어떻게 계산하는지는 알고 있는데, 주어진 알파벳에 맞는 수를 대입하는 방식을 고민할 수도 있을 거 같습니다 ! 문제에서 알파벳 A부터 순서대로 n개의 문자는 n+2번째 줄부터 입력 받는 피연산자에 대응한다고 했습니다 ! 그렇기에 A는 배열 arr의 인덱스 0, B는 arr의 인덱스 1이 됩니다 ★ 대문자 A를 아스키코드로 변환하면 65입니..

https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 소스코드 풀이 ★ 2 x n 직사각형을 1 x 2, 2 x 1 타일로 채울 수 있는 방법의 수는 2 x (n-1)을 채울 수 있는 방법의 개수 + 2 x (n-2)를 채울 수 있는 방법의 개수입니다 ! ★ 점화식을 세우기 위해선 패턴을 파악해야 합니다. n이 1부터 5일때까지를 대입해보면 n = 1, 방법: 1가지 n = 2, 방법: 2가지 n = 3, 방법: 3가지 (n이 1일 때 + n이 2일 때) n = 4, 방..

https://www.acmicpc.net/problem/15815 15815번: 천재 수학자 성필 길이가 100이 넘지 않는 수식이 예제 입력과 같이 공백 없이 입력된다. 수식은 0부터 9까지의 숫자와 연산자 '+', '-', '*', '/' 로만 이루어져 있다. 또한, 수식의 계산 중간 과정의 모든 결과는 항상 2 www.acmicpc.net 소스코드

https://www.acmicpc.net/problem/2841 2841번: 외계인의 기타 연주 첫째 줄에 멜로디에 포함되어 있는 음의 수 N과 한 줄에 있는 프렛의 수 P가 주어진다. (1 ≤ N ≤ 500,000, 2 ≤ P ≤ 300,000) 다음 N개 줄에는 멜로디의 한 음을 나타내는 두 정수가 주어진다. 첫 번째 www.acmicpc.net 소스코드 풀이 ★ 문제를 이해하는 데 헷갈렸던 부분은 줄이 다른 경우에는 상호간에 아무런 영향을 끼치지 않는다는 것입니다 ! 저는 줄이 1일 때와 2일때를 동일하게 생각하여 줄이 다른 경우 무조건 손가락을 떼고 다시 줄과 프렛을 눌러야 한다고 생각했습니다. 하지만 줄이 다른 경우는 독립적인 경우라고 생각해야 합니다. ★ 줄이 총 6개이고, 1번 줄부터 인덱..

https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 소스코드 풀이 ★ n길이대로 오르막수를 나열했을 때 끝에 오는 수의 개수를 기준으로 점화식을 세울 수 있습니다. n이 3일 때 각 길이별로 가질 수 있는 오르막 수를 확인해보면 다음과 같습니다. 위의 패턴을 이중 반복문을 사용해 구현하시면 됩니다 :) ★ dp[1] 은 1로 초기화를 해주는데, 그 이유는 길이가 1인 경우엔 0부터 9까지 모든 수가 각각 오르막 ..

https://www.acmicpc.net/problem/13699 13699번: 점화식 다음의 점화식에 의해 정의된 수열 t(n)을 생각하자: t(0)=1 t(n)=t(0)*t(n-1)+t(1)*t(n-2)+...+t(n-1)*t(0) 이 정의에 따르면, t(1)=t(0)*t(0)=1 t(2)=t(0)*t(1)+t(1)*t(0)=2 t(3)=t(0)*t(2)+t(1)*t(1)+t(2)*t(0)=5 ... 주어진 입력 0 ≤ n www.acmicpc.net 소스코드 풀이 ★ 문제에서 주어진 점화식을 코드로 구현하는 문제입니다. 구현하는 과정에서 이중 반목문을 사용하여 dp[0]은 1씩 증가시켜주고 dp[n-1]은 1씩 감소시키는 코드를 짜야합니다 !