on my way

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

* 생각한 아이디어 및 문제 풀이 체스에서 queen의 특성은 거리와 상관없이 모든 방향으로 움직일 수 있다. n*n 정사각형 안에 n개의 queen을 배치하는 문제로, queen들은 자신의 일직선상 및 대각선상에 아무 것도 놓이면 안된다. Queen함수에서는 각각 단계별로 퀸이 존재할 수 있는 여부를 확인한다. isUsed1는 같은 열에 퀸이 존재하는지, isUsed2는 우상대각선에 퀸이 존재하는지, isUsed3는 좌상대각선에 퀸이 존재하는지 확인한다. (가로의 인덱스가 i, 세로의 인덱스가 j일때 우상대각선은 i+j가 모두 일치, 좌상대각선은 i-j=0이다.) 만약 (level, i)에 퀸을 둘 수 없다면 isUsed1, isUsed2, isUsed3를 모두 true로 변경하고 Queen(level..