복's

https://leetcode.com/problems/add-two-numbers/description/ Add Two Numbers - LeetCode Can you solve this real interview question? Add Two Numbers - You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and leetcode.com submissions 기록을 보면 올해 초 1월에 제출했다가 통과 못했던 기록..

https://leetcode.com/problems/generate-parentheses/ Generate Parentheses - LeetCode Can you solve this real interview question? Generate Parentheses - Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. Example 1: Input: n = 3 Output: ["((()))","(()())","(())()","()(())","()()()"] Exa leetcode.com 만들 수 있는 괄호의 수 n이 주어졌을 때 만들 수 있는 괄호의 형태의 가짓 수를 구..

https://leetcode.com/problems/valid-parentheses/description/ Valid Parentheses - LeetCode Can you solve this real interview question? Valid Parentheses - Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if: 1. Open brackets must be closed by the sam leetcode.com 스택하면 자주 보이는 문제인 것 같다. 스택 특성을 이용해서 괄호의 ..

https://leetcode.com/problems/expression-add-operators/description/ Expression Add Operators - LeetCode Can you solve this real interview question? Expression Add Operators - Given a string num that contains only digits and an integer target, return all possibilities to insert the binary operators '+', '-', and/or '*' between the digits of num so that the re leetcode.com 일반적인 백트래킹(Backtracking) ..

https://leetcode.com/problems/longest-common-prefix/ Longest Common Prefix - LeetCode Can you solve this real interview question? Longest Common Prefix - Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string "". Example 1: Input: strs = ["flower","flow" leetcode.com 모든 단어들이 공통으로 시작하는 단어를 찾아내는 문제로 모든 단어들이 공통으로 무..

https://www.acmicpc.net/problem/12891 12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA” www.acmicpc.net 마침 LeetCode 문제 슬라이딩 윈도우 자주 만났었는데 백준 슬라이딩 윈도우 문제도 만나게 되었다. 대신 이 문제는 문자열 안에 Sub Array가 고정 길이를 갖고 있다. [ 📌 풀이 ] [ ⚙︎ 입력 ] s, p = map(int, input().split()) dna = list(str(input()).strip()) A, C, G, T = map(int, inpu..

https://leetcode.com/problems/minimum-size-subarray-sum/ Minimum Size Subarray Sum - LeetCode Can you solve this real interview question? Minimum Size Subarray Sum - Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarr leetcode.com 슬라이딩 윈도우(Sliding Window)를 통해서 문제를 ..

https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 문제를 보고 고민하다가 결국 다 범위를 좁혀가면서 확인을 해봐야 할 것 같다는 생각이 들었다. 투 포인터 방식으로 문제를 풀어 봤는데, 계속해서 반례에 걸려서 반례들을 찾느라고 시간을 썼다. [ 📌 고려사항 ] 음수가 있을 수 있음 |A| index로 바꿔야 코드를 읽는데 더 편할 것 같은데 변수 이름을 잘못 준 것 같다. import sys input = sys.stdin.readline N = int(input()) nu..

https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 문제 그림만 봐도 위상정렬이라고 생각이 들었다. 마지막 건물을 짓기 위해서는 해당 건물이 필요로 하는 건물들이 필요한데 아마 스타크래프트 같은 게임을 생각하면 편할 것 같다. 팩토리를 짓기 위해서는 배럭이 필요한 느낌? 근데 각 건물들에는 짓는데 걸리는 시간이 있어서 A를 건설하기 위해서 B, C가 있다면 B, C가 둘 다 완성되어야 A를 지을 수 있기 때문에 최장 시간 걸리는 건물의 시간을..

https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net DP 문제로 다양한 동전 문제가 있는데 비교적 쉬웠던 동전 1문제!! 왜 쉬웠나? -> 내가 풀었으니까 (내가 DP문제를!?) [ 📌 코드 흐름 ] 1. 0원을 만들 수 있는 경우는 아무 동전도 사용하지 않은 경우다. 2. 각 동전마다 1 ~ target(k)원까지 만들 수 있는 경우의 수를 구한다. (이 때 각 동전들은 이전 결과값을 기준으로 계산하며 동전 개수에 제한이 없음을 염두한다.) 1원 ..