https://leetcode.com/problems/palindrome-linked-list/ 문제 요약 : 연결 리스트가 패린드롬(앞뒤로 읽어도 같은 값)인지 검증해라 로직은 다음과 같다. 1. 연결 리스트를 돌면서, 현재 값을 origin에 쭉 저장하고, 순서를 반대로 해서 reverse에 저장한다. 2. 두개가 같은지 비교해서 리턴한다. # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def isPalindrome(self, head: Optional[ListNode]) -> bool:..
https://leetcode.com/problems/array-partition/ 문제 요약 : 배열에서 두 개씩 짝을 지었을 때의 최솟값으로 만들 수 있는 최대 합을 구하라 최솟값끼리 더한 것이 최대 합이 되려면 작은 것끼리 짝을 맞추면 된다. 로직은 다음과 같다. 1. 오름차순으로 정렬한다 2. 두개씩 짝지었을 때 짝수번째가 작은 값이 되기 때문에 이를 합산해 준다. class Solution: def arrayPairSum(self, nums: List[int]) -> int: sum = 0 for i, n in enumerate(sorted(nums)): if i % 2 == 0: sum += n return sum 시간복잡도는 O(n)이다
https://leetcode.com/problems/trapping-rain-water/ 요약 : 벽 사이에 고인 물의 양을 계산하기 Hard 단계의 문제, 너무 어려웠다. 기본 로직은 다음과 같다 height 리스트를 돈다 스택에 0번째 값이 현재 벽 높이 보다 크거나 같으면 물이 고인다 스택을 pop하면서 물 높이를 더해준다 스택에 벽 높이를 쌓는다 마지막까지 스택이 비어있지 않다면 뒤에서부터 벽 높이를 정해서 고인 물을 더해준다 class Solution: def trap(self, height: List[int]) -> int: result = 0 stk = [] for h in height: if stk and stk[0] = 0: water = max - stk.pop() if water >..
JavaScript 알고리즘 & 자료구조 마스터클래스 재귀 함수 : 자기 자신을 호출하는 함수 function a(){ a() } 자기 자신을 계속 호출하기 때문에 무한 루프를 돌지 않도록 종료 조건 (base case)가 있어야 한다. JS의 내장 함수 중 하나인 JSON.parse / JSON.stringify도 재귀적으로 작동한다고 한다. JS에서는 함수의 호출을 관리하는 call stack이라는 자료 구조가 있다. 함수를 호출하면 스택에 push 된다. 함수가 리턴(또는 종료)되면 pop 된다 재귀 함수는 계속해서 자기 자신을 호출하면서 콜 스택에 함수를 추가한다 → 언젠가는 멈춰야 한다 멈추기 위해 필요한 두 가지가 있다. 종료 조건 = base case 매번 다른 인풋으로 자기 자신을 호출한다..
