우노

문제 링크 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,..

들어가기 앞서, 배낭 문제(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)-..

문제 링크 https://www.acmicpc.net/problem/2011 풀이 마지막 숫자까지 해석할 수 있는 경우의 수는 아래 두 가지 경우의 수의 합과 같습니다. 마지막 1개 숫자 이전의 숫자들로 가능했던 경우의 수 마지막 2개 숫자 이전의 숫자들로 가능했던 경우의 수 따라서, “251”을 해석할 수 있는 경우의 수는 아래 두가지 경우의 수의 합과 같습니다. “마지막 1개 숫자 이전의 숫자들로 가능했던 조합” + “1” 즉, “25”의 경우의 수와 동일합니다. 마지막 1개의 숫자가 0 이상이기 때문에 가능합니다. “마지막 2개 숫자 이전의 숫자들로 가능했던 조합” + “51” 즉, “2”의 경우의 수와 동일합니다. 해당 경우엔 마지막 2개의 숫자가 10 이상 26 이하가 아니기 때문에 불가능합니다..

문제 링크 https://www.acmicpc.net/problem/2293 풀이 우선, 동전 1원으로 10을 만들 수 있는 경우의 수와 동전 1, 2원으로 10을 만들 수 있는 경우의 수를 구함으로써 규칙을 찾을 수 있습니다. 즉, 새로 갱신되는 dp[n]의 값은 이전의 dp[n]의 값에 dp[n - 현재 사용한 동전의 종류 크기] 가 됩니다. 해당 규칙을 통해 1, 2, 5원으로 10을 만들 수 있는 경우의 수를 계산할 수 있습니다. 추가적으로, dp[0]은 주어진 동전을 통해 0원을 만들 수 있는 경우의 수인데, 아무 동전을 사용하지 않았을 때 0을 만들 수 있으므로, 경우의 수는 1입니다. 코드 import sys n, k = map(int, sys.stdin.readline().split()) ..

문제 링크 https://www.acmicpc.net/problem/17609 풀이 왼쪽 포인터 값과 오른쪽 포인터 값이 동일할 경우, 양쪽 포인터를 그 다음 포인터로 이동 왼쪽 포인터 값과 오른쪽 포인터 값이 동일하지 않을 경우 왼쪽 포인터를 오른쪽으로 이동했을 때, 양쪽 포인터 내부 문자열이 회문이 되는지 확인 오른쪽 포인터를 왼쪽으로 이동했을 때, 양쪽 포인터 내부 문자열이 회문이 되는지 확인 나머지 경우(회문이나 유사회문도 아닌 일반 문자열인 경우) 코드 import sys t = int(sys.stdin.readline()) for i in range(t): result = 0 str = list(sys.stdin.readline().rstrip()) left_idx = 0 right_idx =..

문제 링크 https://www.acmicpc.net/problem/2812 풀이 큰 수가 되려면 높은 자리수의 숫자가 커야합니다. 그래서 스택을 이용합니다. 예를 들어, 4177252841 이고 k = 4이면 775841이 최대값이겠죠? 먼저 4를 stack에 집어넣습니다. stack = [4] 다음 1을 stack에 넣어야 하는데, stack의 최근 값인 4보다 1이 작거나 같죠? 그래서 그냥 stack에 1을 넣습니다. stack = [4, 1] 다음 7을 stack에 넣어야 하는데, stack의 최근 값인 1보다 7이 크죠? 그래서 1을 pop 합니다. stack = [4], k = 3 아직 stack의 최근 값인 4보다 7이 크죠? 그래서 4를 pop 합니다. stack = [], k = 2 이..

문제 링크 https://www.acmicpc.net/problem/3078 풀이 문제에 대한 설명이 길지만, 결국 등수의 차이가 K보다 작거나 같으면서 이름의 길이가 같은 친구 쌍이 얼마나 있는지를 찾는 문제입니다. 해당 문제는 슬라이딩 윈도우 알고리즘을 사용해 해결할 수 있습니다. 딕셔너리를 사용해, k 크기를 가지는 윈도우 내에 존재하는 학생들을 {이름 길이 : 인원} 형식으로 저장합니다. 윈도우를 오른쪽으로 한 칸씩 이동하며, 윈도우에서 빠지는 학생은 딕셔너리에서 제거하고, 윈도우에 추가되는 학생은 딕셔너리에 추가합니다. 이때, 추가되는 학생의 이름 길이와 동일한 길이가 딕셔너리에 존재한다면, 친구 쌍의 개수를 +1 해줍니다. 코드 import sys from collections import d..

문제 링크 https://www.acmicpc.net/problem/2230 풀이 투 포인터 알고리즘을 사용해 해결할 수 있습니다. 우선, 투 포인터 알고리즘을 사용하기 위해 입력 수열을 오름차순으로 정렬해야합니다. 이후, 두 포인터에 위치한 수의 차이에 따라 왼쪽 또는 오른쪽 포인터를 오른쪽으로 한 칸씩 이동하면 됩니다. 참고 m의 최대값은 2,000,000,000이기 때문에 result의 초기값은 int(2e9) 또는 sys.maxsize로 설정해야합니다. 코드 import sys n, m = map(int, sys.stdin.readline().split()) # 수열 저장 arr = [] for _ in range(n): arr.append(int(sys.stdin.readline())) # 수열..