목록전체 글 (760)
우노
문제 링크 https://leetcode.com/problems/maximum-subarray/description/ 풀이 해당 문제는 그리디 알고리즘(Greedy Algorithm)의 한 종류인 카데인 알고리즘(Kadane’s Algorithm)을 사용해서 해결할 수 있습니다. 카데인 알고리즘(Kadane's Algorithm)은 배열에서 연속된 부분 배열의 최대 합을 구하는 효율적인 알고리즘입니다. 이 알고리즘은 O(N)의 시간 복잡도를 가지며, 다음과 같은 단계로 진행됩니다. "현재 합"과 "최대 합"을 -inf(음의 무한대)로 초기화합니다. 배열을 순회하며 다음 두 가지 경우 중 큰 값을 “현재 합”으로 갱신합니다. 이전 인덱스까지의 “현재 합” + 현재 인덱스의 값 현재 인덱스의 값 “현..
문제 링크 https://www.acmicpc.net/problem/11722 코드 import sys n = int(sys.stdin.readline()) item = list(map(int, sys.stdin.readline().split())) # 아이템 역순 정렬 item_reversed = item[::-1] # DP 테이블 생성 dp = [1] * n for i in range(n): for j in range(i+1,n): # 현재 위치의 값(item_reversed[i])보다 비교 대상(item_reversed[j])보다 크면, # 증가하는 순서가 성립하므로 DP 테이블 업데이트 if (item_reversed[i] < item_reversed[j]): dp[j] = max(dp[i]+1,..
들어가기 앞서, 해당 포스팅에선 Google Cloud의 BigQuery Python 클라이언트 라이브러리를 사용하여 BigQuery에 파티션된 테이블을 생성하는 코드에 대해서 다뤄보겠습니다. 예제 코드 # Google Cloud의 BigQuery 클라이언트 라이브러리를 가져옵니다. from google.cloud import bigquery # 사용할 BigQuery 프로젝트의 ID를 설정합니다. project_id = "your_project_id" # BigQuery 클라이언트 객체를 생성합니다. bigquery_client = bigquery.Client(project=project_id) # 생성할 BigQuery 테이블의 스키마를 정의합니다. schema = [ bigquery.SchemaFi..
들어가기 앞서, 해당 포스팅에선 Google Cloud Storage(GCS)에서 CSV 파일을 읽어서 Google BigQuery에 데이터를 저장하는 코드에 대해서 다뤄보겠습니다. 예제 코드 # 필요한 라이브러리를 불러옵니다. from google.cloud import storage, bigquery import pandas as pd from io import StringIO # Google Cloud Storage(GCS) 설정 bucket_name = 'your_bucket_name' # GCS 버킷 이름 prefix = 'your_file_prefix' # 파일 경로 및 이름의 공통된 시작 부분 gcs_client = storage.Client() # GCS 클라이..
들어가기 앞서, DB 데이터를 수정할 때, 여러 트랜잭션이 동시에 동일한 데이터에 접근하여 충돌이 발생할 수 있습니다. 이러한 상황에서 데이터 무결성을 유지하기 위해서는 적절한 잠금(Locking) 기법을 사용해야 합니다. 해당 포스팅에서는 Optimistic Lock(낙관적 락), Pessimistic Lock(비관적 락), Distributed Lock(분산 락)에 대해서 살펴보겠습니다. Optimistic Lock(낙관적 락)이란? 설명 데이터 수정 시, 다른 트랜잭션에 의해 데이터가 변경되지 않았는지 확인하는 방식입니다. 특징 동시성이 높고 충돌 가능성이 낮은 경우 효율적입니다. 충돌 시, 작업을 재시작해야 하므로 낭비가 발생할 수 있습니다. 개발자가 수동으로 롤백처리를 한땀한땀 해줘야합니다. 데..
들어가기 앞서, 배낭 문제(Knapsack Problem)는 제한된 공간에 가치가 높은 물건들을 최대한 많이 넣는 문제입니다. 이 문제는 물건을 나눌 수 있냐 없냐에 따라 두 가지 유형으로 나뉩니다. 분할 가능한 배낭 문제(Fractional Knapsack Problem) 물건을 일부분으로 나눌 수 있는 경우 (예: 설탕 500g 중 300g만 넣기) 그리디 알고리즘으로 해결 가능 0-1 배낭 문제(0-1 Knapsack Problem) 물건을 나눌 수 없고, 전부 넣거나 전혀 넣지 않아야 하는 경우 동적 프로그래밍(Dynamic Programming)으로 해결 가능 해당 문제는 0-1 배낭 문제(0-1 Knapsack Problem)에 해당됩니다. 설명 문제 설정 물건 개수: N = 4 배낭 용량: ..
B 트리란? B트리는 데이터베이스와 파일 시스템에서 널리 사용되는 자가 균형 이진 검색 트리의 일종입니다. B트리의 설계는 디스크 I/O 작업의 최소화를 목표로 하며, 이를 위해 트리의 높이를 가능한 낮게 유지합니다. 해당 포스팅에선 B트리의 규칙과 조회, 삽입, 삭제 방법에 대해서 다뤄보겠습니다. 규칙 노드 노드 차수(M): 각 노드가 가질 수 있는 자식 노드의 최대 개수 각 노드는 최소 M/2개에서 최대 M개의 자식 노드를 가질 수 있습니다. 루트 노드: 최소 2개의 자식 노드 (트리 생성/삭제 시 예외 가능) 내부 노드: 최소 ⌈M/2⌉개의 자식 노드 리프 노드: 모든 리프 노드는 동일한 레벨에 있어야 함 (데이터 접근 시간 균일화) 키 각 노드에 저장된 값입니다. 키 개수 범위: 최소 (M/2)-..
리스트(List) 가변(Mutable) : 요소의 추가, 삭제, 변경이 가능합니다. 대괄호 []를 사용하여 생성합니다. 중복된 요소를 가질 수 있습니다. 순서가 있어 인덱스를 통해 요소에 접근 가능합니다. 주로 동적인 데이터 관리에 사용됩니다. my_list = [1, 2, 3] my_list.append(4) # 추가 my_list[1] = 5 # 변경 del my_list[0] # 삭제 튜플(Tuple) 불변(Immutable) : 한 번 생성된 후에는 요소의 추가, 삭제, 변경이 불가능합니다. 소괄호 ()를 사용하여 생성합니다. 중복된 요소를 가질 수 있습니다. 순서가 있어 인덱스를 통해 요소에 접근 가능합니다. 주로 데이터의 불변성이 필요한 경우에 사용됩니다. my_tuple = (1, 2, 3)..
선요약 Sync / Async 는 호출된 함수의 종료를 호출한 함수가 처리하느냐, 호출된 함수가 처리하느냐의 차이입니다. Sync A 함수가 B 함수를 호출 할 때, B 함수의 결과를 A 함수가 처리하는 것입니다. Sync 작업들이 연속적으로 실행될 땐, 작업의 순서가 유지됩니다. Async A 함수가 B 함수를 호출 할 때, B 함수의 결과를 B 함수가 처리하는 것입니다. Async 작업들이 연속적으로 실행될 땐, 작업의 순서가 유지되지 않을 수 있습니다. Blocking / Non-blocking 은 호출된 함수가 호출한 함수에게 제어권을 바로 주느냐 안주느냐의 차이입니다. Blocking A 함수가 B 함수를 호출 할 때, B 함수가 자신의 작업이 종료되기 전까지 A 함수에게 제어권을 돌려주지 않는..
Xcoms란? XComs(Cross-Communications)는 Apache Airflow에서 태스크 간에 메시지나 데이터를 교환하기 위한 메커니즘입니다. Xcoms를 통해 한 태스크가 생성한 데이터를 다른 태스크가 사용할 수 있으며, 이는 태스크 간의 의존성 관리와 데이터 공유에 매우 유용합니다. XComs는 Key-Value 쌍으로 데이터를 저장하며, Airflow의 메타데이터 데이터베이스에 저장됩니다. 예제 코드 태스크에서 데이터를 XCom에 push하는 가장 간단한 방법은 태스크의 실행 함수에서 값을 반환하는 것입니다. Airflow는 반환된 값을 자동으로 XCom에 push합니다. @task def push_task(): # XCom으로 메시지를 push return 'Hello fro..