https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 💡IDEA 동적 계획법을 사용하는 문제이다. 0번째 값은 이전 행의 0번째, 1번째 값 중 최대(최소)값 + 현재 행 0 번째 값 1번째 값은 이전 행의 0번째, 1번째, 2번째 값 중 최대(최소)값 + 현재 행 1 번째 값 2번째 값은 이전 행의 1번째, 2번째 값 중 최대(최소)값 + 현재 행 2 번째 값 2차원 배열로 최대값 dp와 최소값 dp를 만들어버리면 메모리 초과가 발생한다. 메모리를 적게 사용하기..
https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 💡IDEA 재귀와 DFS를 사용하는 문제이다. 조건을 만족하는 수열을 출력하기 위해서 요소의 방문을 확인할 배열 하나, 중복된 수열을 출력하는 것을 방지할 상수 하나가 필요하다. 중복 수열 제거용 상수는 깊이가 다를 때마다 초기화 해주어야 한다. 방문 확인 및 이전에 쓰인 요소 값과 같은지 확인해주며 DFS를 수행한다. 📌CODE import sys input = sys.stdin.readlin..
https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 💡IDEA 스택을 사용하는 문제이다. 중위 표기식을 후위 표기식으로 변환하기 위해서 변환식 스택 하나, 연산자 스택 하나가 필요하다. 입력받은 문자 중 알파벳인 경우와, 연산자인 경우로 나눈다. 알파벳인 경우 변환식 스택에 추가한다. 연산자인 경우 여는 괄호( '(' )인 경우, 연산자 스택에 추가한다. 닫는 괄호( ')' )인 경우, 여는 괄호가 나올 때 까지 연산자 스택에서 pop 하여 변..
https://www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net 💡IDEA 재귀를 사용하는 문제이다. 입력이 3×2k 인 것으로 유추해보면, N에서 2씩 나누어 가다가 마지막 3이 남을 때 반환하지 않을까 추측한다. 기본 삼각형은 5×3 배열로 이루어져있다. N = 6인 경우를 생각해보면, 0 ≤ i ≤ 2 번째 행은 공백 3칸 + 기본 삼각형의 i 행 + 공백 3칸, 3 ≤ i ≤ 5 번째 행은 기본 삼각형의 i 행 + 공백 1칸 + 기본 삼각형의 i 행 처럼 규칙을 가지고 있다. 📌CODE N = int(in..
