스터디룸

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

LeetCode #239 Sliding Window Maximum

문제 풀이

슬라이딩 윈도우를 사용하는데 이 문제는 기존 최댓값이 교체될 때 이후에 들어온 값이나 남아있는 값들 중 최댓값을 최대한 빠르게 찾아야 한다. 이 문제를 해결해야 시간 복잡도를 해결할 수 있다. 문제 해결을 위해 window를 deque로 선언하고 deque의 첫 번째 값이 최대값임을 보장하도록 해보자.

• i = 0부터 len(nums) - 1까지 (시작부터 끝까지 순회)의 좌표에 대해
• 만약 i - q[0] == k라면 이번 좌표가 입력될 시 window에 있는 가장 오래된 좌표가 k의 범위를 초과하므로 popleft한다.
• q에 원소가 남아있는 동안 탐색값 nums[i]보다 nums[q[-1]]이 작다면 최댓값 결정에 쓸모가 없는 원소이므로 pop한다. 만약 탐색값보다 큰 값이 등장하면 종료한다. 이 과정으로 q에 대해 nums[q]의 값은 단조 감소 함수가 된다.
• 이후 q에 i좌표 입력한다. 만약 위 과정으로 q에 원소가 없으면 새롭게 q[0]이 된 i좌표의 값이 최댓값이고 q에 원소가 남아있다면 q[0]가 최댓값이다.
• 만약 i < k - 1이면 아직 window size보다 덜 탐색했으므로 skip, i >= k - 1이면 결과값을 저장하는 배열에 nums[q[0]]을 저장한다.
• 이후 최대값들이 저장된 배열을 리턴

python 코드

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        q = collections.deque()
        sol = []
        for i in range(len(nums)):
            if q and i - q[0] == k:
                q.popleft()
            while q:
                if nums[q[-1]] < nums[i]:
                    q.pop()
                else:
                    break
            q.append(i)
            if i >= k - 1:
                sol.append(nums[q[0]])
        return sol

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

문제 2143. 두 배열의 합

문제 풀이

처음엔 부분합 문제로 A와 B의 모든 부분 배열의 합을 배열로 저장하고 A의 모든 원소에 대해 탐색 배열을 B의 부분배열의 합 배열로 두고 타겟 - A의 부분합 배열의 원소값을 이진 탐색으로 찾아서 해결할 수 있을 줄 알았다. 그야 메모리 제한이 64MB라서 공간복잡도가 작아보였기 때문...

그러나 이 문제는 A의 부분합을 배열로 생성하고 B의 부분합은 dictionary로 생성하여 탐색 과정을 $O(1)$로 줄여야 하는 문제였다. C계열 언어였다면 통과했을 지 몰라도 python에서는 시간 초과가 발생하기 때문이다. 그럴만도 한게 부분합 배열은 엄연히 $O(n^2)$이고 매번 B의 배열을 이진탐색으로 찾으면 탐색과정은 대충 $2log\ n$이 되는데 상당히 버거울 만도 하다. A의 부분합 배열에 대해 순차적으로 탐색하여 B 부분합 딕셔너리에 타겟 - A 부분합 배열의 원소 키를 조회하여 더하면 되겠다.

python 코드

import sys
from collections import defaultdict
input = sys.stdin.readline

T = int(input())
N = int(input())
A = list(map(int, input().split()))
M = int(input())
B = list(map(int, input().split()))
sum_A, sum_B = [], defaultdict(int)
for i in range(1, N):
    l, r = 0, i
    buf = sum(A[l:r])
    sum_a.append(buf)
    while r < N:
        buf -= A[l]
        buf += A[r]
        sum_a.append(buf)
        l += 1
        r += 1
for i in range(1, M):
    l, r = 0, i
    buf = sum(B[l:r])
    sum_b[buf] += 1
    while r < M:
        buf -= B[l]
        buf += B[r]
        sum_b[buf] += 1
        l += 1
        r += 1
sol = 0
for s_a in sum_a:
    sol += sum_b[T - s_a]
print(sol)

알고리즘 & 자료구조

- 허프만 코드

- 위상 정렬

- 비트 마스크

 - 가산기 전가산기 등등 구현 첨부

- KMP 알고리즘

- 강한 연결 요소

- 최소 공통 조상

자바

- GC Root, Java Reference와 Memory Leak(메모리 누수)

- 오토박싱과 성능저하 이슈

네트워크

- STUN

- TURN

- 홀펀칭

코틀린

- sealed class와 sealed interface

안드로이드

- 22' Google IO

  - Large Screen 관련 시리즈

  - Jetpack Compose 관련 코드랩

  - App Performance testing tool

- Large Screen 대응

- 안드로이드 컴포넌트

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

LeetCode #148 Sort List

문제 풀이

$O(nlog\ n)$에 연결리스트를 정렬해야 한다. $O(nlog\ n)$이니 최악의 경우 $O(n^2)$를 보이는 퀵 정렬이 아니라 병합 정렬을 사용해야 함은 자명한데 재귀 구조로 이루어진 연결리스트라서 뇌정지가 온다. 병합 정렬의 핵심은 더 이상 분할할 수 없을 때까지 2분할한 뒤 merge하는 과정이므로 우서 분할에 대해 고민해야 한다.

2분할은 런너 기법을 사용하면 되겠다. 하나의 런너가 2개씩 전진하고 이를 fast 런너라 하자. 1개씩 전진하는 런너를 slow라 하자. slow 런너는 fast 런너가 끝에 다다르면 입력받은 head의 절반을 지나쳐 우측 절반을 가르키게 된다. 그러나 좌측 절반은 아직 할당하지 못했다. 좌측 절반은 head와 할당이 똑같게끔 slow 노드를 따라가는 left 버퍼를 하나 생성하자. 전진이 종료되면 left의 다음 노드를 None으로 만들어 잘라낸다. 그렇다면 left는 head와 할당 주소가 같기 때문에 head는 slow의 시작지점 이전까지로 잘려서 좌측 절반이 완성된다.

merge 과정은 만약 두 ListNode가 존재하면 값이 작은 쪽이 l1으로 가게끔 치환하고 l1.next에 대해 재귀호출하여 한쪽 ListNode가 None이 될 때까지 호출한다. 이후 병합된 형태의 ListNode가 반환되면 재귀를 종료한다.

python 코드

class Solution:
    def mergeList(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 and l2:
            if l1.val > l2.val:
                l1, l2 = l2, l1
            l1.next = self.mergeList(l1.next, l2)
        return l1 or l2

    def sortList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        left, slow, fast = None, head, head
        while fast and fast.next:
            left, slow, fast = slow, slow.next, fast.next.next
            # left에 slow를 할당하여 slow 직전까지 따라감
        left.next = None
        # left 다음을 None으로 만들어 head의 좌측 절반까지 자름
        # 처음 slow에 head를 할당하여 서로 연결되어 있기 때문에 가능
        l1 = self.sortList(head) # 좌측 절반
        l2 = self.sortList(slow) # 우측 절반
        return self.mergeList(l1, l2)

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

LeetCode #147 Insertion Sort List

문제 풀이

일반적인 삽입 정렬은 탐색 시작 지점부터 다음 지점과 대소관계를 비교해서 swap하는 과정으로 이루어지지만 ListNode는 클래스 변수로 val과 next밖에 않아 왼쪽 방향으로의 swap이 불가하다. 이를 해결하기 위해 별도의 ListNode를 저장할 객체를 선언하고 주어진 head의 각 노드에 대해 커서를 새로운 객체의 처음부터 마지막까지 탐색하여 조건이 충족되면 객체에 ListNode를 삽입하고 원점으로 돌아가 head의 다음 Node의 값과 비교연산을 수행하게 해야 한다.

python 코드

class Solution:
    def insertionSortList(self, head: ListNode) -> ListNode:
        cur = node = ListNode(0)
        while head:
            while cur.next and cur.next.val < head.val:
                # cur.next의 값이 head보다 작아서 우측에 삽입할 필요가 없다면
                # cur 전진
                cur = cur.next
            # cur.next의 값이 head와 같거나 커서 우측에 삽입
            cur.next, head.next, head = head, cur.next, head.next
            if head and cur.val > head.val:
                # head가 존재하고 cur 값이 head보다 커서 좌측에 삽입해야 하면
                # cur를 원점으로 복귀
                cur = node
        return node.next