본문 바로가기

분류 전체보기252

[LeetCode] 300. Longest Increasing Subsequence 접근 다이나믹 프로그래밍을 활용하여 문제를 풀어야 함 subsequence의 특징 중 앞의 원소에서 가능했던 갯수를 포함할 수 있다는 점을 캐치해야 함 문제 링크 https://leetcode.com/problems/longest-increasing-subsequence/description/ 솔루션 class Solution: def lengthOfLIS(self, nums: List[int]) -> int: nums_length = len(nums) dp = [1 for _ in range(nums_length)] for i in range(nums_length): for j in range(i): if nums[i] > nums[j]: dp[i] = max(dp[i], dp[j]+1) return .. 2023. 4. 6.
[Python3] input 입력 받기 백준, 알고스팟 같은 알고리즘 사이트 솔루션을 작성할 때 테스트 케이스에 대한 입력을 감안하여 솔루션을 작성해야 합니다. 이 글에선 솔루션 작성 때 자주 사용하는 input 3가지 경우를 소개합니다. 1개의 값 입력받기 input 함수를 사용하여 1개의 값을 입력받을 수 있습니다. 입력 받은 값의 자료형은 문자열입니다. a = input() N개의 값 입력받기 input 함수 뒤에 split 함수를 작성하여 구현할 수 있습니다. b,c = input().split() d = input().split() 리스트로 입력받기 반복문을 활용하여 입력받는 값을 원하는 자료형으로 만들 수 있습니다. 아래 코드는 리스트로 값는 예제입니다. team = [] for i in range(3): b,c = input()... 2023. 4. 4.
[LeetCode] 11. Container With Most Water 접근 O(n) 시간복잡도 탐색을 통해 문제에서 요구하는 성능을 만족하는 것이 핵심 two pointers 기법을 사용해야 한다. 문제 링크 https://leetcode.com/problems/container-with-most-water/description/ O(n^2) 시도 TLE: 해당 솔루션은 오답입니다. class Solution: def maxArea(self, height: List[int]) -> int: answer = 0 left = 0 height_length = len(height) while left < height_length-1: for i in range(left+1, height_length): WIDTH, HEIGHT = i-left, min(height[left], h.. 2023. 4. 4.
[알고리즘] 백트래킹(backtracking) 문제 정복 커리큘럼 서론 백트래킹(Backtracking)은 주로 BFS 및 DFS와 같은 모든 경우의 수를 탐색하는 완전 탐색 대신 중간에 더 이상 조건을 충족하지 못하는 경우 이하 탐색을 종료하고 조건을 충족하는 다른 경우를 탐색하는 기법입니다. 완전 탐색에 비해 성능이 좋은 장점이 있습니다. 솔루션 예 백트래킹 문제는 다음과 같은 형식으로 솔루션을 작성하면 쉽게 풀 수 있습니다. 조건을 만족하지 않는 경우를 모두 체크하는 것이 아닌 조건을 모두 만족하는 경우만 체크 조건을 만족하는 경우들을 이하 반복문을 통해 재귀 탐색 def backtracking(tmp_answer): # 조건을 모두 만족하는 경우를 조건문으로 처리합니다. if answer == tmp_answer: return True for i in (추가 탐.. 2023. 4. 3.
[LeetCode] 1306. Jump Game III 접근 기존 점프 게임처럼 그리디를 쓰는 방법도 있겠지만, DFS 와 백트래킹을 통해 문제를 풀 수도 있음. DFS를 활용할 때에는 Runtime error를 조심하도록 합시다. visited 리스트를 활용해 불필요한 재귀를 줄여야 함 문제 링크 https://leetcode.com/problems/jump-game-iii/description/ 솔루션 class Solution: def canReach(self, arr: List[int], start: int) -> bool: arr_length = len(arr) visited = [False for _ in range(arr_length)] def dfs(index): # if out of bound or already visited if index.. 2023. 4. 3.
[LeetCode] 45. Jump Game II 접근 그리디로 풀면 되는 문제 기술적인 스킬이 부족해서 안될 코드를 계속 붙잡고 있었다. 머리를 써야 한다. 왜 상황 이해를 제대로 하지 않는 듯 문제 링크 https://leetcode.com/problems/jump-game-ii/description/ 솔루션 class Solution: def jump(self, nums: List[int]) -> int: nums_length = len(nums) left = right = 0 answer = 0 while right < nums_length-1: max_index = 0 # get max index of available range for i in range(left, right+1): max_index = max(max_index, i+nums.. 2023. 4. 3.

티스토리툴바