개발하는 사막여우

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문이..

https://www.acmicpc.net/problem/27497 27497번: 알파벳 블록 첫째 줄에 버튼을 누른 횟수 $N$이 주어진다. $(1 \leq N \leq 1\,000\,000)$ 둘째 줄부터 $N$개의 줄에는 버튼을 누른 순서대로 누른 버튼에 대한 정보를 주며 아래와 같은 형식으로 주어진다. 1 c : 문자열 www.acmicpc.net 소스코드 풀이 ★ 누르는 버튼에 따라 순서대로 들어오는 알파벳을 기록할 stack과 문자를 만드는 큐를 따로 만들어 풀이를 진행했습니다. 버튼 2의 경우에는 문자열의 앞에 알파벳을 추가해야 하고, 버튼 3을 눌렀을 경우 문자열의 앞에서 알파벳을 제거해야 하기 때문에 양방향 push, pop이 가능한 큐를 사용하였습니다. ★ 문자열에 추가될 때 해당 알파..