알고리즘 day4

오늘은 힙에 대해 공부했다

이진 트리와 완전 이진 트리에 대한 개념을 먼저 공부하고 문제를 풀었는데

오늘은 특히 큰 어려움이 없었다.

 

다만 코치님이 추가로 생각해보란게 몇개 있었는데 그것에 대해 설명과 링크를 추가한다.

 

Redis : I/O를 줄이기 위해, 즉 디스크 부하를 줄이기 위해 많이 사용한다. 

 https://seokhyun2.tistory.com/63

[Redis] Redis란? & Redis 사용방법

 

Query DSL: Elasticsearch와 같은 검색 엔진에서 쿼리를 작성하기 위한 도메인 특화 언어(DSL)다. 이는 JSON 형식의 쿼리를 작성하는 것보다 프로그래밍 언어의 문법과 유사한 문법을 사용하여 쿼리를 작성할 수 있도록 해준다.

Query DSL은 Elasticsearch의 검색, 필터링, 집계 등 다양한 기능을 사용하여 데이터를 검색하고 분석하는 데 사용된다. 이를 통해 데이터베이스에 저장된 대량의 데이터를 빠르게 검색하고 유연하게 분석할 수 있다.

 

Query DSL의 장점

1. 프로그래밍 언어와 유사한 문법을 사용하기 때문에 개발자들이 빠르게 익히고 쿼리를 작성할 수 있다.
2. 쿼리를 작성하는 과정에서 문법 오류를 줄일 수 있으며, 디버깅이 쉽다.
3. 다양한 검색 및 집계 기능을 활용하여 복잡한 데이터 분석을 수행할 수 있다.
4. Elasticsearch와 같은 검색 엔진의 기능을 최대한 활용하여 성능을 향상시킬 수 있다.

JPA보다 jOOQ를 쓰는 이유

1. 질의 제어:
   • JPA는 객체-관계 매핑(Object-Relational Mapping)을 사용하여 객체 모델과 데이터베이스 스키마 간의 매핑을 제공합니다. 이는 객체를 데이터베이스에 저장하고 조회할 때 편리하지만, 쿼리의 세부적인 제어가 필요한 경우에는 한계가 있다.
   • jOOQ는 SQL을 자바 코드로 표현하는 방식을 사용하여 쿼리를 작성합니다. 이는 개발자가 쿼리의 세부적인 부분을 완전히 제어할 수 있게 해주므로, 복잡한 쿼리를 작성하거나 최적화할 때 유용하다.
2. 유형 안정성:
   • JPA는 쿼리를 문자열로 작성하기 때문에 컴파일 시에 쿼리의 유효성을 확인할 수 없습니다. 이는 잘못된 쿼리를 작성할 경우 런타임 오류가 발생할 수 있다는 의미다.
   • jOOQ는 자바 코드로 쿼리를 작성하기 때문에 컴파일 시에 쿼리의 유효성을 확인할 수 있습니다. 이는 잘못된 쿼리를 미리 잡아낼 수 있고, 유형 안정성(Type Safety)을 제공하여 런타임 오류를 방지할 수 있다.
3. 성능:
   • JPA는 객체 그래프를 조회할 때 지연로딩(Lazy Loading)과 같은 성능 이슈가 발생할 수 있다.
   • jOOQ는 필요한 필드만을 선택하여 쿼리를 작성할 수 있으므로, 불필요한 데이터를 조회하지 않고 성능을 최적화할 수 있다.
4. SQL에 대한 이해도:
   • jOOQ는 SQL을 자바 코드로 작성하기 때문에 데이터베이스와 관련된 세부적인 지식이 필요합니다. 이는 개발자가 SQL을 직접 작성하는 것과 유사한 방식으로 쿼리를 작성할 수 있다.
   • JPA는 객체-관계 매핑을 사용하기 때문에 SQL을 작성할 필요가 없으며, 개발자가 데이터베이스와 관련된 세부 사항을 몰라도 된다.

 

 

※ 오늘의 문제는 따로 어려웠던 점이 없어 주석으로 설명을 대체한다.

1번 문제 1464. Maximum Product of Two Elements in an Array

LeetCode - The World's Leading Online Programming Learning Platform

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        result = heapq.nlargest(2, nums)
        #result에 가장 큰 숫자 2개를 넣어줍니다.

        return (result[0]-1)*(result[1]-1)
        #해당 숫자들에서 1을 뺀 값을 곱해서 return합니다.

 

2번 문제 1337. The K Weakest Rows in a Matrix

LeetCode - The World's Leading Online Programming Learning Platform

class Solution:
    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
        heap = []
        result = []
        for i, row in enumerate(mat):
            count = sum(row)
            # 각 행의 병사 수를 더해줍니다.
            heap.append((count, i))
            # heap에 count를 첫번째 요소로 해서 나중에 count를 기준으로 정렬하게끔 해줍니다.

        for count, index in heapq.nsmallest(k, heap):
            result.append(index)
            # nsmallest를 이용해서 k만큼의 작은 count의 index를 result에 넣어줍니다.
        return result

 

3번 문제 - 215. Kth Largest Element in an Array

from typing import List
import heapq

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        return heapq.nlargest(k, nums)[-1]
        #nlargest를 이용해 가장 큰 숫자 k개를 뽑아서 그중 가장 마지막 숫자를 return합니다.

 

4번 문제 최소 힙

1927번: 최소 힙

import heapq
from typing import List
class Solution:
    def minpip(self, inputs: List[int], k: int) -> int:
        min_heap = []

        for x in inputs:
            if x == 0:
            #x가 0인지 확인하고 0일 경우 min_heap가 비어있지 않으면 heappop으로 가장 작은 숫자를 빼내서 출력합니다.
                if min_heap:
                    print(heapq.heappop(min_heap))
                else:
                    print(0)
                    #비어 있는 경우 0을 출력합니다.
            else:
                heapq.heappush(min_heap, x)
                #x가 0이 아닐경우 heappush로 min_heap에 x를 넣어줍니다.


k = int(input())
inputs = [int(input()) for _ in range(k)]
#k개 만큼의 입력값을 받아와서 inputs 배열에 넣어줍니다.
solution = Solution()
solution.minpip(inputs,k)

 

5번 문제 최대 힙

11279번: 최대 힙

import heapq
from typing import List
class Solution:
    def maxpip(self, inputs: List[int], n: int) -> int:
        max_heap = []

        for x in inputs:
            if x == 0:
                if max_heap:
                    print(-heapq.heappop(max_heap))
                    #최소힙과 다른점은 -를 해서 밑에 0이 아닐경우 추가한 x값을 다시 양수로 바꿔 출력합니다.
                else:
                    print(0)

            else:
                heapq.heappush(max_heap,-x)
                # 음수로 바꾼 이유는 기본적으로 최소힙으로 정렬되기 때문에 -를 붙여 큰 수대로 정렬하기 위함입니다.

n = int(input())
inputs = [int(input()) for _ in range(n)]
#n개 만큼의 입력값을 받아와서 inputs 배열에 넣어줍니다.

solution = Solution()
solution.maxpip(inputs, n)

*이렇게 한 이유가 문제를 거꾸로 풀어 nlargest와 nsmallest를 몰랐었어서 이런 방식으로 풀었습니다.