https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 2차원 DP배열을 사용하는 문제이다. 1. house를 입력받고, house크기만큼 dp배열을 선언해준다. 2. N == 1일때는 세 집중 최솟값을 그냥 출력하면 된다. 3. N이 2이상일때 DP테이블을 갱신하는 과정은 다음과 같다. dp[i][0]: 그 이전의 i-1번째에서 house[i-1][1]이나 house[i-1][2]를 선택한 경우 중 최솟값 + 현재 i번째에서 0..
https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net # 삼성SW 역량테스트 기출문제이다. (백트래킹) 1. N과 숫자들 A를 입력받고 덧셈, 뺄셈, 곱셈, 나눗셈의 연산 갯수도 입력받는다. 2. BT(add, sub, mul, div, A[0], 1)을 실행한 뒤, max(answer)와 min(answer)를 출력한다. # BT함수: a. 종료조건: 모든 연산갯수가 0이라면 answer에 r..
https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 간단한 DP문제이다. 1. 우선 dp배열을 N만큼 선언해주고, 포도주의 양을 입력받아 grape배열에 넣는다. 2. N==1일 때는 포도주가 1개이므로 grape[0]을 출력하고, N==2일 때는 두 잔 다 마시면 되니 grape[0] + grape[1]을 출력한다. 3. N이 3개이상일 때부터 Bottom-Up방식으로 dp테이블을 갱신해주면 된다. # i번째 잔을 고를 때 최댓값은 다음 3가지 케..
https://leetcode.com/problems/decode-ways Decode Ways - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com * 문제해석: 1 -> 'A', 2 -> 'B', 3 -> 'C' ... 26 -> 'Z' 이런식으로 디코딩을 할 수 있다. Incoding된 문자열을 Decoding하려면 모든 숫자를 '그룹화'한 다음 다시 문자로 mapping 해야한다. ex) "11106"을 mapping하는 경우 "AAJF" with the g..
https://leetcode.com/problems/coin-change/ Coin Change - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com * 문제해석: 주어진 coins배열의 동전들을 가지고 amount에 해당하는 값을 만들 때, 필요한 동전의 최소 갯수를 return, 만들 수 없으면 -1 return # DP문제이다. Greedy문제인 '거스름돈 문제'와 비슷해 보이지만, 이 문제는 coins의 동전들이 다른 동전의 배수가 아닐 수 있으므로(배수인..
https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net # N과 M (1) 문제에서 중복된 수열들을 출력하지 않고, 각 수열은 오름차순이어야 하는 조건이 추가된 문제이다. # prev변수를 통해 중복된 수열을 출력하지 않는 방법은 다음과 같다. ex) 처음에 prev가 0이므로 for문에서 comb에 1을 넣고 BT(1, 1, [1])을 호출한다. BT(1, 1, [1])에서 prev가 1이므로 for문에서 i가 2부터 N-1까지 돈다. 따라서 co..
https://leetcode.com/problems/restore-ip-addresses/ Restore IP Addresses - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com # 확실히 재귀가 코드 진행상황이 직관적으로 보이거나 와닿지가 않아서 힘든 것 같다.. class Solution: def restoreIpAddresses(self, s: str) -> List[str]: if len(s) < 4: return [] answer = [] IPs = ..
https://leetcode.com/problems/combination-sum/ Combination Sum - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com # 요즘 연습하고 있는 백트래킹 문제이다. candidates의 수들 중 합이 target인 배열을 return하는 문제이다. # 6번째 줄에서 comb를 바로 append하면 안되고, comb.copy()를 append해줘야 answer에 값이 제대로 들어간다. class Solution: def c..
모르는 사이에 조금씩 조금씩..
