2차원 편순 문제를 활용한 레몬의 행복도 계산
레몬 나무에 n개의 레몬이 매달려 있으며, 각각은 두 가지 속성인 시각적 아름다움(a_i)과 신맛 강도(b_i)를 가진다. 특정 레몬 i를 섭취했을 때 얻는 기쁨 값 e_i는 자기 자신을 제외하고, 아름다움과 신맛 모두가 자신 이하인 다른 레몬들의 개수로 정의된다.
즉, 다음 조건을 동시에 만족하는 인덱스 j의 수이다:
j ≠ i
a_j ≤ a_i
b_j ≤ b_i
모든 레몬에 대해 ...
8월 4일 07:24에 게시됨
정수 배열에서 최대 부분 배열 합 찾기: 세 가지 접근 방식
정수 배열이 주어졌을 때, 그 안에서 연속된 부분 배열 중 합이 가장 큰 부분 배열을 찾아 그 합을 반환하는 것은 고전적인 알고리즘 문제입니다. 이 문제는 다양한 최적화 기법을 통해 해결할 수 있으며, 여기서는 세 가지 주요 접근 방식인 무차별 대입(Brute Force), 분할 정복(Divide and Conquer), 그리고 동적 계획법(Dynamic Programming)을 다룹니다. 특히, 대규모 ...
7월 13일 17:10에 게시됨
무(莫) 알고리즘: 원본 질의 처리를 위한 분할 정복
무 타오(Mo Tao)가 개발한 이 알고리즘은 일반적으로 구간 작업을 비효율적으로 처리하는 데 사용됩니다
짧은 프레임워크, 쉽게 기억할 수 있는 템플릿 표현, 그리고 우수한 복잡도로 유명합니다
하지만 무 알고리즘이 적용되는 문제의 복잡성으로 인해 많은 템플릿 문제들이 높은 난이도 등급을 가지고 있어 초보자들이 접근하기 어렵습니다
하지만 무 알고리즘의 원리를 ...
7월 12일 22:10에 게시됨
알고리즘 실습 문제 풀이 분석
1부: 재귀
문제 1: 숫자 세기
/*
n=1, 결과 1
n=2, 결과 2 (12, 2)
n=3, 결과 2 (13, 1)
n=4, 결과 4 (14, 13, 24, 124)
n=5, 결과 4 (15, 25, 125, 5)
관찰 결과:
n이 홀수이면 f[n] = f[n-1]
n이 짝수이면 f[n] = f[n-1] + f[n/2]
*/
#include <iostream>
using namespace std;
const int MAX = 10000;
int dp[MAX];
int main() {
dp[1] = 1;
int n;
...
7월 5일 00:14에 게시됨
백트래킹, 그리디, 분할정복, 동적계획법 알고리즘 비교
백트래킹 알고리즘
백트래킹은 해결 가능한 모든 경로를 탐색하는 알고리즘으로, 재귀 호출을 통해 결정 트리를 탐색하며 실패 시 이전 상태로 돌아가는 방식을 사용합니다.
def backtrack(current_path, choices):
if is_solution(current_path):
add_to_result(current_path)
return
for choice in choices:
if not is_valid(ch ...
6월 15일 16:23에 게시됨