New Gate New Gate

느낀점Python은 백트랙킹 부분을 주의해서 구현해야 한다. 문제https://leetcode.com/problems/path-sum-ii/description/ Node 끝에 도달한 시점에 해당 Path 내 모든 노드의 값을 더했을 때 타겟값과 동일하면 리스트에 추가하여 반환하기풀이# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution: def pathSum(self, root: Optional[T..

느낀점약간의 수학적 트릭이 있는 경우 잘 감안해서 로직을 작성해야 한다.문제https://leetcode.com/problems/integer-replacement/description/ 주어진 양의 정수 n에 대해 다음 연산 중 하나를 적용한다.n이 짝수면, n을 n / 2로 바꾼다.n이 홀수면, n을 n + 1 또는 n - 1로 바꿉니다.목표는 n을 1로 만드는 데 필요한 최소 연산 횟수를 반환하는 것풀이문제를 보면 구현하는 것은 어렵지 않은데, 홀수일 때 언제 n+1, n-1을 해야하는지 고려해야 한다. 이 부분은 n = 3일 때, 그리고 n이 4의 배수보다 하나 더 클 때, n에서 1을 빼야 하고 나머지 홀수는 그냥 하나를 추가하는 것으로 구현했다. 중요한 것은 왜 3일 때, 그리고 4의 배수보다..

느낀점슬라이딩 윈도우에서는 왼쪽, 오른쪽 인덱스를 잘 구분한 후 오른쪽 인덱스는 선행이니 왼쪽 부분만 조율하면 된다.문제https://leetcode.com/problems/minimum-size-subarray-sum/description/?source=submission-noac 리스트에서 타겟을 넘는 서브배열들을 확인하고, 그 중 가장 짧은 길이를 반환하는 문제이다.풀이두 개의 포인터를 기준으로 오른쪽은 그대로 가고, 타겟을 넘어갔는지 안 넘어갔는지만 판단하여 왼쪽 인덱스를 조율한다. 전형적인 슬라이딩 윈도우 문제.class Solution: def minSubArrayLen(self, target: int, nums: List[int]) -> int: min_len = float..

느낀점시간 복잡도에서 O(log N)이면 이진 탐색부터 생각하자. 문제https://leetcode.com/problems/find-peak-element/ 1차원 배열에서 피크 지점을 찾는 문제이며 시간 제약이 있다.풀이이진탐색을 약간 변형한다. 선택한 배열에서 양쪽의 높이를 확인하며 탐색 범위를 변경해 나아간다.class Solution: def findPeakElement(self, nums: List[int]) -> int: l, r = 0, len(nums)-1 while l nums[mid+1]: r = mid else: l = mid + 1 return l 결과공간복잡도: $..

느낀점오래전 프로그래머스에서 풀었던 "에라토스테네스의 체"를 다시 한번 보게 되었다. 문제https://leetcode.com/problems/count-primes/ 특정 숫자 직전까지의 소수 갯수 찾기풀이갯수 만큼 배열을 생성한 이후, 소수를 발견할 때마다 그의 배수들에 접근하지 못하도록 막는다. 또한, 바깥쪽 루프에서 i가 소수일 때만 안쪽 루프가 실행되기 때문에 단순 소수 판별 알고리즘 보다는 빠르다.class Solution: def countPrimes(self, n: int) -> int: if n 결과공간복잡도: $$ O(NLogLogN) $$시간복잡도: $$ O(N) $$

느낀점여러 문제를 풀다보면 그래도 어떠한 문제도 익숙하게 접근하게 되는 것 같다. 너무나 편안하게 DP가 생각이 들었고 바로 구현했다.문제https://leetcode.com/problems/triangle/ 삼각형 모양으로 숫자들이 배열된 리스트가 주어졌을 때, 꼭대기에서 시작해서 맨 아래 바닥까지 이동하면서 거쳐간 숫자들의 합이 최소가 되는 경로를 찾는 문제입니다.이동 규칙:현재 행의 인덱스 i에 있다면, 다음 행에서는 동일한 인덱스 i 또는 바로 오른쪽 인덱스 i + 1로만 이동할 수 있습니다.목표:꼭대기에서 바닥까지 이동하는 모든 가능한 경로 중에서 숫자들의 합이 가장 작은 경로의 합을 반환해야 합니다.풀이트라이앵글 문제라고해서 배열이 아닌 것은 아니고, 보통 이런 건 첫번째부터 반복을 돌 필요가..

느낀점IP 주소의 구성과 백트랙킹을 구현하는 문제로 그리 어렵지 않게 구현할 수 있다. 주요 포인트는 불필요한 순회를 줄이기 위한 가지치기와 IP주소의 구성을 검증하는 부분일 것 같다. 문제https://leetcode.com/problems/restore-ip-addresses/description/ - 주어진 숫자 문자열 s에 점(.)을 세 번 찍어서 만들 수 있는 모든 유효한 IP 주소를 찾는 문제입니다.- 유효한 IP 주소는 정확히 네 개의 숫자로 이루어져 있으며, 각 숫자는 0부터 255 사이의 값이어야 하고, 0으로 시작하는 숫자는 허용되지 않습니다 (단, 숫자 자체가 '0'인 경우는 제외).- 문자열 s의 숫자 순서를 바꾸거나 삭제할 수는 없습니다.풀이from typing import Lis..

"Haruhi Problem"은 애니메이션 "스즈미야 하루히의 우울"의 방영 순서와 관련된 문제입니다. 이 애니메이션은 2006년에 처음 방영되었는데, 특이하게도 시간 순서대로 방영되지 않고 뒤섞인 순서로 방영되었습니다.제작진의 의도적인 방영 순서 변경: 제작진은 시청자들에게 혼란과 궁금증을 유발하기 위해 의도적으로 에피소드 순서를 뒤섞었습니다.시간 순서와 뒤섞인 순서의 차이: 예를 들어, 이야기의 시작 부분에 해당하는 에피소드가 나중에 방영되거나, 중요한 사건이 발생하는 에피소드가 중간에 끼어들어 이해하기 어려웠습니다.시청자들의 혼란과 논쟁: 이 때문에 당시 많은 시청자들이 어떤 순서로 봐야 하는지 혼란스러워했고, 온라인 커뮤니티 등에서 방영 순서와 시간 순서에 대한 활발한 논쟁이 벌어졌습니다.이러한 ..