231223 동계 모각코 1차

방학동안 모각코 계획은 이렇다. 우선 code tree 의 자료구조와 알고리즘 문제집을 풀어 볼것이다. 

이미 2학년 1학기, 2학기 때 자료구조와 알고리즘 과목을 수강했지만, 복습하는 차원에서 빠르게 한 번 돌려볼 생각이다. 더하여 이렇다 하게 익숙하게 느껴지는 프로그래밍 언어가 없는데 , 이 문제집을 c언어로 수강하여 공부할것이다. 

 

 

오늘 배워볼 것은 수도코드 이다 . 첫번째 문제에서는 이중 for 문을 수도 코드로 작성했는데 i = 0일때부터 5일때까지 총 6번 각각의 경우에 5번의 반복이 된다. 따라서 x는 총 30번 더해져 30 이 출력된다.  간단한 for문이 세 문제정도 나오고, 어렵지 않게 풀어볼 수 있다.

 

다음은 빅-오, 빅-오메가, 빅-세타 표기법을 묻는 문제이다. 

보통 우리가 사용하는 점근적 표기법은 빅-오 표기법이다. O는 가장 높은 차수보다 같거나 높은 식을 뜻한다. 시간 복잡도 식에서, 가장 차수가 높은 upper bound 로서 나타낼 수 있다. 

만약 f(n)=n3+n2+n−1,g(n)=n5 이었다면, f(n)=O(g(n)) 으로도 나타내 볼 수 있겠다. f의 차수가 g의 차수보다 같거나 작기 때문이다. 

 

오메가는 가장 높은 차수보다 같거나 낮은 식을 뜻한다. 따라서 n3+n2+n−1에서 가장 높은 차수는 n3 이므로 Ω(n3), Ω(n), Ω(logn) 모두 맞는 말이 된다.  f(n) = Ω(g(n)) : f가 g의 증가율보다 크거나 같다. 

 

세타는 최고차항을 뜻한다. 점근적 표기법에서 상수는 무시된다. n이 무한이 커질 때를 가정하기 때문이다. 

 

마찬가지로 비슷하게 각 표기법을 계산하는 방법이 나온다. 

다시 정리하자면, 빅 오 표기법은 f = O(g) 일때 f의 차수는 g보다 작거나 같고, 오메가는 그 반대이다. f의 차수가 g보다 무조건 크거나 같다. 세타 표기법은 최고차항을 나타낸다. 1학기 자료구조 맨 처음에 배웠던 기억이 나는데, 다시 해보려니까 생각보다 꽤 헷갈렸던 주제였다. 

 

 

마지막 펜트하우스 문제이다. 빅 세타로 계산하여 성립하면 -> 즉 최고차항의 계수가 같으면 두 코드는 같은 층에 배정된다고 하다. 

또한 만약  f(n)=O(g(n))이지만 g(n)!=O(f(n))이라면, f(n)은 g(n)보다 낮은 층에 배정된다고 했는데 , 이 얘기는 f의 차수가 g보다 작을 때 아래층에 배정되는 간단한 알고리즘이다. 쉽게 말해 차수가 높은 식 부터 위층에 배정된다는 소리이다. 

2^n 2^n+2021

1/2n^5

n^3 10n^3

n^2logn

nlogn

logn

이렇게 총 6개의 층이 만들어지고, 정답은 3이다. 

 

 

어느 함수의 어퍼 바운드가 N이라는 말은, 이 함수의 증가율이 최대 N 이란 소리이다. 오메가는 로어 바운드가 N 이라는 얘기인데 조금의 예시만 생각해봐도 이게 동일하지 않다는 것을 알 수 있다. 

자료구조 수업시간에 봤던 유명한 시간 복잡도 그림이다. 

사실 최근 2-2 알고리즘 수업시간에도 시간 복잡도에 대한 설명을 알고리즘마다 듣는다. 하지만 이해보다는 암기의 영역으로 받아들여 공부를 했다. 코드에 대한 이해를 차치하더라도 시간 복잡도 개념 자체에 대한 공부가 안되었다는 반증이다. 

 

어느 유튜브 영상에서 봤던 내용. N의 범위와 제한시간을 보고 우리는 시간 복잡도를 유추해내어 알고리즘을 떠올릴 수 있다.

 

반복문이나 알고리즘에서의 시간 복잡도는 어느정도 익숙해져서 뒤의 문제들은 어렵지 않게 풀어갈 수 있었다. 

선택 정렬 코드이다. selection sort 의 시간 복잡도는 n^2인데, 선택 정렬이란, 맨 앞의 값과 그 뒤의 값들을 비교해가며 스왑하는 방식이다.최악의 경우 n개의 수마다 n-1번 비교 하므로 시간 복잡도는 n^2 라는 것을 알 수 있다.  

 

조금 어려운 for 

function solution1(n)
  for i = 0 ... i < n * n
    for k = 0 ... k <= i
      print("Hi")
    for j = n ... j >= 0
      print("Bye")

 

: 제일 바깥쪽 for문에서 n^2, 안쪽 첫번째 for문에서 i번 즉 n^2 번 -> n^4

  그 밑 for문에서 j번, 즉 n번 돈다 n^3 . 

 두 사건은 동시에 일어나는 사건임으로 더하기 연산 하여 최종 시간복잡도는 O(n^4)

 

function solution2(n)
  for i = 0 ... i < n
    set j = 1
    while j < i
      j *= 2

: 제일 바깥쪽 for문에서 n번. 이때 유의해야 할 것은 while문 안의 변수 j는 *2가 누적 연산되어 1 2 4 8 16 ... 와 같이 지수 연산식으로 늘어난다. 따라서 n/2 라고 생각하는게 아니라 로그 연산으로 생각하여아 한다. 

컴퓨터 공학에서의 기본 상용로그는 밑이 2다. 따라서 nlogn

 

처음 문제가 풀리지 않아 해설과 설명을 보았다. 하지만 뒤의 문제들은 감을 잡고 그렇게 어렵지 않게 풀어나갈 수 있었다.