https://www.acmicpc.net/problem/15666 15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 💡IDEA 백트래킹을 사용하는 문제이다. 백준에 N과 M 문제가 많은데, 12번 쯤 되면 순열을 조건별로 구할 수 있는 달인이 되었을 것이다. 15657. N과 M (8) 과 15663. N과 M (9) 두 문제를 적절하게 섞어서 풀 수 있는 문제다. 같은 수를 여러 번 골라도 되고, 비내림차순인 수열을 구한다. 같은 수 중복 허용이므로 반복문의 시작점은 idx 부터이고, tmp를 통해 중복되..
https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 💡IDEA 조합의 개념을 알면 풀 수 있는 문제이다. nCr = n!/(n-r)!r! 으로 나타낼 수 있는데, 팩토리얼을 재귀로 구해도 되고, DP를 사용해도 될 것 같다. 아래 코드는 그냥 반복문으로 곱하면서 답을 구하는 풀이이다. n!/(n-r)! = n(n-1)(n-2)...(n-r+1) 임을 사용해서 먼저 구한 후, r!를 나누어준다. 📌CODE n, m = map(int, input().split()) ans = 1 for i in range(n, n-m, -1): ans *= i tmp = 1 for ..
https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 💡IDEA 스택을 사용하는 문제이다. 처음에는 replace를 사용하여 풀었지만 역시나 시간 초과가 발생했다. 스택을 사용해서 입력 문자를 하나씩 넣고, 스택에 쌓인 문자열 끝에 폭발 문자열이 있으면 그만큼 pop 해준다. 조인을 잘 활용해야 하고 스택에 아무것도 남아있지 않다면 "FRULA"를 출력한다. 📌CODE import sys input = sys.stdin.readline..
https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 💡IDEA DFS를 사용하는 문제이다. 행, 열, 파이프 방향 세 변수를 사용하여 DFS를 수행한다. 파이프 방향은 0이 가로, 1이 세로, 2가 대각선이다. 다음 파이프가 가로로 갈 수 있는 경우는 현재 파이프가 가로 혹은 대각선 인 경우이다. 가로로 가기 위해서는 다음 열 값이 범위 내에 있고, 빈 칸(0)이어야 한다. 다음 파이프가 세로로 갈 수 있는 경우는 현재 파..
https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 💡IDEA BFS를 사용하는 문제이다. 현재 값의 2배, 또는 10배 후 더하기 1 한 값이 되므로, 현재 값보다 작아지는 경우가 없다. 즉, 방문을 확인할 배열이 굳이 필요 없다. BFS를 수행하며 A가 B가 될 때 수행할 동안 카운트해준 값을 반환한다. BFS를 수행했음에도 B가 되지 못했다면 -1을 반환한다. 📌CODE from collections import deque A, B = map(int, input().split()) def solve(n): q = deque() q.append((n, 1)) while..
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..
