개발하는 사막여우

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씩 감소시키는 코드를 짜야합니다 !

https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 소스코드 풀이 ★ 원리를 이해하는 데에는 시간이 오래 걸리지 않았지만 점화식을 세우는 게 조금 난해했던 문제였습니다. ★ DP문제 특성 상 카드를 1개 구매할 때의 최대값부터 n개 구매할 때의 최대값까지를 구해다보면 패턴을 알 수 있습니다. ex) arr = [5, 2, 8, 10] - 카드를 1개 구매할 때 최댓값 => 5 - 카드를 2개 구매할 때 최댓값 => 2 or 10 - 카드를 3개 구매할 때..

https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 소스코드 풀이 ★ 전형적인 DP문제였습니다 ! 풀이부터 말하자면 n이 가질 수 있는 이친수의 개수는 n-1의 이친수 개수 + n-2의 이친수 개수입니다. ex) ★ n이 6일 경우 이친수의 수는 8입니다. n으로 만들 수 있는 이친수의 개수를 dp에 저장한 뒤 이를 가지고 점화식을 세워보면, dp[n] = dp[n-1] + dp[n-2]로 세울 수 있고 이는 다음과 같이 적용됩니다 ! ..

https://www.acmicpc.net/problem/25556 25556번: 포스택 포닉스가 순열을 청소할 수 있으면 YES, 불가능하다면 NO를 출력한다. www.acmicpc.net 소스코드 풀이 ★ 핵심은 각각의 스택의 최상단 값보다 스택에 넣으려고 하는 값이 커야한다는 것입니다 ! ex) 예제와 같이 5,4,3,2,1이 주어졌을 때 스택 4개에 5,4,3,2가 각각 들어가고 1이 아무 스택에나 들어간다고 하더라도 그 스택들을 하나씩 뽑아서 오름차순을 만들 수 없습니다 ! [5],[4],[3],[2,1]처럼 수가 들어간 경우 4번째 스택에서는 1이 먼저 나오고 2가 나오기 때문에 이미 내림차순 형태가 되어버립니다. ★ 구현하는 과정에서 for ~ else 구문을 사용하였습니다. 만약 for문이..