on my way

05. 배열 05-1. 배열 개념 배열은 인덱스와 값을 일대일 대응해 관리하는 자료구조입니다. 데이터를 저장할 수 있는 모든 공간은 인덱스와 일대일 대응하므로 어떤 위치에 있는 데이터든 한 번에 접근할 수 있습니다. 배열 선언 # 일반적인 방법 arr = [0, 0, 0, 0, 0, 0] arr = [0] * 6 # 리스트 생성자 사용 arr = list(range(6)) # [0, 1, 2, 3, 4, 5] # 리스트 comprehension 사용 arr = [0 for _ in range(6)] # [0, 0, 0, 0, 0, 0] 선언한 배열은 위 사진처럼 저장된다. 파이썬의 리스트는 동적으로 크기를 조절할 수 있도록 구현되어 있습니다. 파 이썬의 리스트는 다른 언어의 배열 기능을 그대로 사용할 수..

03. 알고리즘의 효율 분석 시간복잡도 시간 복잡도(time complexity)란, 알고리즘의 성능을 나타내는 지표로 입력 크기에 대한 연산 횟수의 상한을 의미한다. "내가 구현한 알고리즘 성능이 제한 시간내 결과값을 낼수 있는지"를 위해 필요하다. 알고리즘 수행 시간을 측정하는 방법 시간 복잡도를 측정하는 법 입력 크기에 따른 연산 횟수의 추이를 활용해서 성능을 가늠하게끔 시간 복잡도를 표현하는 방법을 점근적 표기법이라고 합니다 가장 많이 사용하는 점근적 표기법은 상한선을 활용하는 방법입니다. 그리고 이 표기법을 빅오 표기법(big-O notation)이라고 합니다. 빅오 표기법은 어렵지 않습니다. 어떤 프로그램의 연산 횟수가 f(x)라고 할 때 함수의 최고차항을 남기고 차수를 지워 O(...)와 같..

* 생각한 아이디어 및 문제 풀이 * 코드 #include using namespace std; int getMax(int n1, int n2, int n3){ int max = 0; if (max > N >> M; int dp[1001][1001]; for(int i=1; i val; max = getMax(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]); dp[i][j] = ..

* 생각한 아이디어 및 문제 풀이 dp[n] = dp[n-1] + dp[n-2]; dp[1], d[2]는 초기에 선언해준다. * 코드 #include using namespace std; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int N; cin >> N; int dp[1001]; dp[1] = 1; dp[2] = 2; if(N > 2){ for(int i=3; i

* 생각한 아이디어 및 문제 풀이 다이나믹 프로그래밍을 통해 문제를 푸는 방법은 1, 2, 3의 합을 미리 수동으로 구해놓아야 한다는 것이 시간을 아낀다는 점의 핵심이다. 1을 1, 2, 3의 합으로 만드는 방법 : 1가지(1)로 dp[1] = 1 2를 1, 2, 3의 합으로 만드는 방법 : 2가지(1+1, 2)로 dp[2] = 2 3을 1, 2, 3의 합으로 만드는 방법 : 4가지(1+2, 2+1, 1+1+1, 3) 그리고 +1된 다음수부터는 이렇게 1, 2, 3을 합한 방법에서 값을 +1씩 더하면 되는 것이므로 dp[i] = dp[i-1] + dp[i-2] + dp[i-3]의 공식으로 만들어지는 것을 알 수 있다. * 코드 #include using namespace std; int main(){ i..

I. 다이나믹 프로그래밍 다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다. 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다는 것이 핵심이다. 즉, 하나의 문제는 단 한 번만 풀도록 하는 알고리즘이다. (우리가 평소에 문제를 풀이할 때 효율적인 방법으로 고안할 필요가 있다.) 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑다운-하향식, 바텀업-상향식)으로 구성된다. 매우 비효율적인 문제더라도 다이나믹으로 획기적으로 시간을 줄일 수 있다. 다이나믹 프로그래밍은 동적 계획법이라고도 부른다. 일반적인 프로그래밍 분야에서는 동적이란 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법을 의미하지만, 다이나..