공부 기록

[알고리즘] 카데인 알고리즘 (Kadane's Algorithm)

카데인 알고리즘 (Kadane's Algorithm) ?배열 내의 연속된 부분 배열의 합 중에서 합이 최대인 부분 배열을 찾는 알고리즘이다.배열을 한 번 순회하면서 현재 위치에서 끝나는 가장 큰 부분 배열의 합을 계산하고 이를 통해 전체 배열에서의 최대 부분 배열 합을 구하는 방식이다. 이 알고리즘은 시간 복잡도가 O(n), 공간 복잡도가 O(1)로 매우 효율적이다. 또한 1차원 배열뿐만 아니라 2차원 배열에서도 적용할 수 있다. 2차원 배열에서 최대 합을 갖는 부분 행렬을 찾는 문제는 복잡하지만 알고리즘을 행별로 적용하여 문제를 1차원 문제로 축소함으로써 해결할 수 있다. 핵심 아이디어카데인 알고리즘은 다음과 같은 두 가지 값을 사용한다.현재까지의 최대 부분 배열 합 (current_max) : 특정 ..

[Python] 1912번 연속합

✏️ 문제 문제 파악처음에 이중 반복문 써서 풀고 있다가.. 시간 초과나서 찾아보니 최대 부분합을 푸는 방법 중 카데인 알고리즘을 써야 풀리는 문제였다.간단하게 설명하자면 시작 원소를 기준으로 부분 배열을 구하는 게 아니라 끝 원소를 기준으로 모든 부분 배열을 구하는 알고리즘이다.   알고리즘다이나믹 프로그래밍   코드시간 초과 코드import sysinput = sys.stdin.readlinen = int(input())ary = list(map(int, input().split())) value = -1000for i in range(n): temp = ary[i] for j in range(i+1, n): value = max(value, temp) temp += ary[j]pri..

[Python] 1932번 정수 삼각형

✏️ 문제 문제 파악입력으로 주는 배열을 기준으로 합을 담은 dp 배열의 값을 구하면 다음과 같이 나온다.중요한 것은 그림의 빨간 부분과 같이 중간에 겹치는 부분이 생기는데 이때문에 경우를 나눠서 구해야 한다.dp[n][0]dp[n][1] ~ dp[n][n-1] : 어짜피 최대값을 구하므로 max 값만 두면 된다.dp[n][n]  알고리즘다이나믹 프로그래밍   코드n = int(input())ary = [list(map(int, input().split())) for _ in range(n)] dp = [[0] * (n+1) for _ in range(n)]dp[0][0] = ary[0][0]for i in range(1, n): for j in range(i + 1): if j == 0: ..

[Python] 9461번 파도반 수열, 그림 설명

✏️ 문제 문제 파악첨에 반복되는 게 있는 지 찾는데 안보였다..고민하다가 문제에서 P(1)부터 P(10)까지 주는 이유가 있을 것 같아서 찾아보니 다음과 같은 반복이 보였다!이를 토대로 점화식은 P(n) = P(n-1) + P(n-5) 이 나왔다.  알고리즘다이나믹 프로그래밍   코드for _ in range(int(input())): p = [0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9] n = int(input()) for i in range(len(p), n+1): p.append(p[i-1] + p[i-5]) print(p[n])

[React] 라이프사이클(Lifecycle)에 대해서

React Component의 라이프사이클(Lifecycle)이란?컴포넌트가 생성 - 업데이트 - 제거되는 과정을 의미한다. React에서는 컴포넌트가 이 과정을 통해 초기화되고 데이터가 변경될 때 다시 렌더링되며 필요할 때 제거된다. 라이프사이클은 각각의 단계에서 특정 메서드를 호출하여 필요한 작업을 수행할 수 있게 한다.주로 클래스형 컴포넌트에서 사용했으나 React 16.8 이후로 함수형 컴포넌트에서 Hooks를 통해 라이프사이클을 처리할 수 있게 되었다.React 라이프사이클은 컴포넌트가 언제 생성되고 업데이트되고 제거되는 지를 이해하는 데 매우 중요하다. React Lifecycle 단계React 컴포넌트의 라이프사이클은 크게 세 가지로 나눌 수 있다.마운트 (Mount) : 컴포넌트가 처음 D..

[Python] 11727번 2xn 타일링 2

✏️ 문제 문제 파악11726번 2xn 타일 의 업그레이드(?)된 문제이다. 11726번 문제와 같이 점화식을 찾는 것이 중요한데 시간 좀 걸렸다... 그래도 풀었으니..!직접 n이 1, 2, 3, 4 일 때 dp(n)의 값을 찾았을 때 1, 3, 5, 11이 나왔다.n = 3일 때 dp(n) = 5인데 이는 dp(n-1) + dp(n-2) + dp(n-2) 의 값과 같은 것을 알 수 있다. 이를 토대로 점화식은 dp(n) = dp(n-1) + (dp(n-2) * 2) 이다.  알고리즘다이나믹 프로그래밍   코드n = int(input())dp = [0, 1, 3, 5, 11]for i in range(len(dp), n+1): dp.append(dp[i-1] + dp[i-2]*2)print(dp[n]..

[Python] 2579번 계단 오르기

✏️ 문제 문제 파악이 문제는 출발점을 기준으로 다음을 계산하는 거 보다 도착점을 기준으로 계산하는 게 더 편하게 풀 수 있다.도착점을 기준으로 계산하기 위해 도착점으로 오는 경우는 생각하면 다음과 같다.직전 칸에서 온 경우 (직전 칸을 밟은 경우 필히 3칸 전 칸을 꼭 밟음)stair[n] + stair[n-1] + dp[n-3]전전 칸에서 온 경우stair[n] + dp[n-2]이 두 경우 중 최대가 되는 값을 선택하면 된다.이때 0 도 생각해야 한다. 아니면 IndexError가 발생한다. (내 얘기) 알고리즘다이나믹 프로그래밍   코드n = int(input())stair = [0]for _ in range(1, n+1): stair.append(int(input()))if n == 1: pr..

[Python] 11726번 2xn 타일링

✏️ 문제 문제 파악n이 1일 때부터 4일 때까지 직접 해보면 다음과 같이 나온다.여기서 점화식을 찾을 수 있는데 피보나치 수열과 같다는 것을 알 수 있다.점화식을 기준으로 코드를 짜면 쉽게 풀 수 있다! 알고리즘다이나믹 프로그래밍   코드n = int(input())ary = [0, 1, 2, 3]for i in range(4, n+1): ary.append(ary[i-1] + ary[i-2])print(ary[n] % 10007)

[React] 함수형 컴포넌트와 클래스형 컴포넌트

React에서 컴포넌트는 사용자 인터페이스를 구축하는 기본 블록을 말한다.컴포넌트는 크게 함수형 컴포넌트와 클래스형 컴포넌트로 나눌 수 있다. 1. 함수형 컴포넌트 (Functional Component)자바스크립트 함수로 정의된 컴포넌트를 말한다.특징상태(state)와 생명주기 메서드가 없었으나 React 16.8에서 도입된 Hooks를 사용하여 함수형 컴포넌트에서도 상태 관리와 생명주기 관련 기능을 사용할 수 있다.코드가 더 간결하고 이해하기 쉽다.사이드 이펙트 없이 순수 함수처럼 사용될 수 있다.this 키워드를 사용하지 않는다.컴포넌트 로직을 분리하기 쉽고 테스트가 용이하다.메모리 사용이 더 효율적이다.예시import React from 'react';const MyComponent = (prop..

[Python] 1463번 1로 만들기, 그림 설명, 자세한 설명

✏️ 문제 문제 파악문제에서 나온 연산은 3가지이다.3으로 나누어 떨어지면 3 배수로 가는 방법2로 나누어 떨어지면 2 배수로 가는 방법1 차이로 가는 방법연산하는 횟수의 최솟값을 구하므로 해당 값으로 가는 3가지 방법 중 연산이 최소로 되는 값을 출력해야 한다.위의 그림을 기준으로 코드를 짜면 된다.  알고리즘다이나믹 프로그래밍   코드n = int(input())d = [0] * (n + 1) for i in range(2, n + 1): d[i] = d[i - 1] + 1 # 1 차이로 가는 방법, 3번 방법 if i % 3 == 0: d[i] = min(d[i], d[i // 3] + 1) # 3번 방법으로 나온 값과 1번 방법으로 나온 값 중 최솟값을 대입 if i % 2 == 0:..