11 to 9, Day 16, 17

Today, ToDoList

• 프로그래머스 레벨 1 도전
• 인프런 강의 수강

---

레벨 1

class Solution {
    public int solution(int[] nums) {
                int answer = 0;
        for ( int i=0; i < nums.length; i++ ) {
            for ( int j=i+1; j < nums.length; j++ ) {
                for ( int k=j+1; k < nums.length; k++) {
                    int sum = nums[i]+nums[j]+nums[k];
                    for ( int n=2; n <= sum; n++ ) {
                        if ( n == sum ) {
                            answer++;
                        } else if ( sum%n == 0 ) {
                            break;
                        }
                    }
                }
            }
        }
        return answer;
    }
}

class Solution {
    public long solution(long n) {
        long x=0;
        for (x = 1; x*x < 50000000000000l; x++) {
            if ( n == x*x ) {
                return (x+1)*(x+1);
            } 
        }
        return -1;
    }
}

---

알고리즘 복잡도

빅 오 노테이션: O(n), O(logN), O(1), O(n^2)

• 주어진 함수에서 엄밀한 점근적 상한을 나타내는 점근적 표기법
• 숫자는 다 빼기
• 가장 증가율이 높은 수식만 남기기

함수의 복잡도

• f(n) = 4 => O(1)
• f(n) = 2n+3 => O(n)
• f(n) = 3n^2+2n+1 => O(n^2)
• f(n) = 4n+log(n)+3 => O(n)

코드에서의 시간과 공간 복잡도

boolean isFirstTwoMatch(int[] nums) {
    return nums[0] == nums[1];
}

시간 복잡도 : 입력값에 따라 시간이 변하지 않는다. O(1)

공간 복잡도 : 입력값에 따라 사용되는 메모리가 증가하지 않는다. O(1)

int sum(int[] elements) {
    int sum = 0;
    for(int number : elements) {
        sum += number;
    }
    return sum;
}

시간 복잡도 : 입력값에 따라 시간이 비례하여 증가한다. O(n)

공간 복잡도 : 입력값에 따라 사용되는 메모리가 증가하지 않는다. O(1)

## 재귀
int factorial(int number) {
    if(number <= 2) {
        return number;
    }
    return number*factorial(number-1);
}

시간 복잡도 : 입력값에 따라 시간이 비례하여 증가한다. O(n)

공간 복잡도 : 입력값에 따라 사용되는 메모리가 비례하여 증가한다. O(n)

int findNumber(int numberToFind, int[] sortedNumbers) {
    int low = 0;
    int high = sortedNumbers.length - 1;
    int index = 0;

    while(low <= high) {
        int mid = (low+high)/2;
        int midNumber = sortedNumbers[mid];
        if (midNumber < numberToFind) {
            low = mid + 1;
        } else if (midNumber > numberToFind) {
            high = mid - 1;
        } else if (midNumber == numberToFind) {
            index = mid;
            break;
        } 
    }
    return sortedNumbers[index];
}

시간 복잡도 : 전체를 순회하지 않고 절반씩 제외됨. O(log(n))

공간 복잡도 : 입력값에 따라 사용되는 메모리가 증가하지 않는다. O(1)