혜지와 콩나무

이번 주차부터 자료구조, 알고리즘 코스를 따라가보려고 한다.제일 먼저 시간복잡도 계산에 쓰이는 점근 표기법에 대해서 배웠다. O는 가장 높은 차수 보다 같거나 높은 식을 뜻합니다.  Ω는 가장 높은 차수 보다 같거나 낮은 식을 뜻합니다. Θ는 최고차항(가장 높은 차수)을 뜻합니다. 위 개념을 바탕으로 시간 복잡도를 판단해보았다.팁은,  시간복잡도는 일반적으로 최악을 기준으로 계산한다는 점이다. 관련해서 풀이한 문제 중 아래 문제가 어렵게 느껴졌다.  난 위 선지들 중에서 1번 선지와 4번 선지를 잘못 판단했다. 1번 선지의 경우 올바른 풀이는 다음과 같다.N*N 크기의 배열의 모든 값을 한 번씩 순회하는 것은 N*N = N^2 개의 모든 인덱스를 참조하는 것이므로, 시간 복잡도는 O(N^2) 이 되어..

코드트리 조별과제에 참여하게 되었다.지난주부터 시작했는데, 신청해두고 까먹고 있다가 오늘 떠올랐다.작년 겨울방학 때 풀던 지점부터 이어서 문제를 풀었다. 기억에 남는 문제 포인트는 다음과 같다.a부터 b 사이에 있는 모든 수들이 짝수인지 아닌지 판별하려면 어떻게 해야하는가? 충분한 시간만 주어진다면 일일히 비교하며 푸는게 정석일 것이다.그러나 우리는 반복문과 조건문을 배웠기 때문에 더 간단한 방식으로 접근할 수 있다. #include using namespace std;int main() { int a, b; cin >> a >> b; bool satisfied = true; for (int i = a; i  이렇게 말이다. 이 개념을 적용하여 다음 문제를 풀었다.   #include using name..