(이게 왜 레벨 2가 아닌 레벨 1일까요?..)

문제

문제링크

두 숫자 X, Y가 주어질 때 X와 Y에 공통으로 있는 숫자를 모두 찾아서 그 숫자들을 조합하여 만들수 있는 최댓값을 리턴하는 함수를 작성한다.

같은 숫자가 중복되어 있을 경우 중복된 개수만큼 붙인다.

해결과정

처음엔 문제를 잘못 이해하고 중복을 없애려고 Set을 사용했다가 문제를 잘못 이해한 것을 인지하고 List로 바꿔서 구현했었습니다. ㅎ

그러나 List를 사용 시 몇 가지 테스트에서 통과를 하지 못하여 갈아엎고 ㅎ 배열로 풀었습니다. 😂

입력받은 String을 각각 char형 배열로 변환한 후 오름차순으로 정렬을 했습니다.

오름차순으로 각각 정렬한 이유는 0번 인덱스부터 배열의 끝까지 비교하면서 공통으로 있는 수를 찾으려 했기 때문입니다.

우선은 두 개의 배열을 반복문에서 동시에 순회하면서 비교할 것이기 때문에 index를 담을 변수를 선언 후 0으로 초기화해줍니다.

저는 반복문으로 for문이 아닌 while문을 사용하였는데 따로 x, y 인덱스 변수가 있기 때문에 인덱스를 증가시켜줄 필요가 없어 조건만 넣은 while 문을 사용하였습니다.

while 문의 조건은 'x인덱스가 x배열의 길이 보다 작고 y인덱스가 y배열의 길이보다 작다'로 설정하였습니다.

이미 x배열과 y배열은 정렬이 되어 있기 때문에 앞에서부터 비교하면서 값이 더 작은 배열의 인덱스의 값을 올려주었습니다.

그리고 값이 같을 경우 해당 값을 StringBuffer에 붙여주고 두 배열의 index를 동시에 증가시켜주었습니다.

(StringBuffer를 사용한 이유는 오름차순을 내림차순으로 바꿔주기 위해 reverse()를 사용할 것이기 때문입니다!)

이렇게해서 하나의 배열이라도 맨 끝에 다다르면 반복을 중지합니다.

이렇게 되면 모든 공통값이 오름차순으로 들어가게 되서 reverse()를 해줍니다.

여기까지만 작성하고 리턴하게 되면 몇가지를 통과하지 못하게 되는데..

0만 있을 경우엔 (예를 들어 "000" 같은 경우) "0"으로 변환해주어야 합니다.

만약에 결과 문자열에 0만 있다면 내림차순이기 때문에 맨 앞에 0이 올 것입니다.

따라서 맨 앞의 문자가 0인지 조건문으로 확인하여 0이라면 "0"만 리턴하면 됩니다.

이렇게 배열로 하면 시간복잡도가 O(n)으로 나쁘진 않은 편? 입니다. (이보다 좋은 방법이 있겠지만 떠오르지 않았습니다.)

코드

import java.util.Arrays;
import java.lang.StringBuffer;

class Solution {
    public String solution(String x, String y) {
        StringBuffer answer = new StringBuffer("");
        char[] xArr = x.toCharArray();
        char[] yArr = y.toCharArray();
        Arrays.sort(xArr);
        Arrays.sort(yArr);
        int xIdx = 0;
        int yIdx = 0;
        while (xIdx < xArr.length && yIdx < yArr.length) {
            if (xArr[xIdx] == yArr[yIdx]) {
                answer.append(String.valueOf(xArr[xIdx]));
                xIdx++;
                yIdx++;
            } else if (xArr[xIdx] < yArr[yIdx]) {
                xIdx++;
            } else if (xArr[xIdx] > yArr[yIdx]) {
                yIdx++;
            }
        }
        if (answer.length() < 1)    return "-1";
        answer.reverse();
        String result = answer.toString();
        if (result.charAt(0) == '0') return "0";
        return result;
    }
}

실행 결과

깃허브 코드 보러가기

읽어주셔서 감사합니다. 🤗 좋은하루 되세요~

문제

Merge Sort를 이용하여 int 형 배열을 정렬하시오.

조건

• Arrays.sort 사용 금지
• 병합 정렬을 이용하여 정렬

병합 정렬이란??

우선 입력받은 배열을 길이가 1인 배열이 될 때까지 계속 반으로 나눈다.

나눈 배열을 2개씩 병합하여 정렬한다.

길이가 2인 배열 병합 -> 길이가 4인 배열 병합 -> 길이가 8인 배열 병합 ...

병합할 때마다 요소들을 정렬한다.

해결 방법

'반으로 나눈다 -> 병합한다' 라는 반복과정이 있기 때문에 반복, 재귀 중에 한가지로 해결할 수 있습니다.

저는 재귀를 활용하여 풀었습니다.

배열을 중간을 기준으로 나눠야 하기 때문에 length / 2 를 기준으로 배열을 left, right 두부분으로 분리하였습니다.

배열의 길이가 1이 될 때까지 이과정을 반복해야 하기 때문에 left, right 배열을 초기화하는 과정에서 바로 재귀를 호출하였습니다.

브레이크 포인트로 길이가 1이하가 될 경우 멈추도록 했습니다.

이제 쪼개진 배열을 오름차순으로 병합하면 됩니다.

이때 left 배열과 right 배열은 각각 이미 정렬이 된 상태이기 때문에 두 배열을 앞에서부터 비교하면서 더 작은 쪽의 요소를 넣어주고 인덱스 카운트를 올려줍니다.

그럼 각각의 인덱스를 기억해야하기 때문에 각각 인덱스를 담을 leftIdx, rightIdx를 선언합니다.

그리고 반복문으로 정렬할 배열의 길이만큼 반복해주면서 두 배열 중 작은 요소를 결과 배열에 넣고 해당 배열의 인덱스를 +1 시켜줍니다.

여기서 배열의 길이를 넘어버리면 안되기 때문에 배열의 길이를 넘을 경우 반대쪽 배열의 남은 요소를 모두 붙여넣고 반복을 종료시키도록 합니다.

코드

import java.util.Arrays;

public class MergeSort {
    public int[] mergeSort(int[] arr) {
        if (arr.length < 2) {
            return arr;
        }
        int middle = arr.length / 2;
        int[] left = mergeSort(Arrays.copyOfRange(arr, 0, middle));
        int[] right = mergeSort(Arrays.copyOfRange(arr, middle, arr.length));

        arr = new int[left.length + right.length];
        int leftIdx = 0;
        int rightIdx = 0;
        for (int i = 0; i < arr.length; i++) {
            if (leftIdx >= left.length) {
                System.arraycopy(right, rightIdx, arr, i, right.length - rightIdx);
                break;
            } else if (rightIdx >= right.length) {
                System.arraycopy(left, leftIdx, arr, i, left.length - leftIdx);
                break;
            } else if(left[leftIdx] > right[rightIdx]) {
                arr[i] = right[rightIdx];
                rightIdx++;
            } else {
                arr[i] = left[leftIdx];
                leftIdx++;
            }
        }
        return arr;
    }
}

깃허브 코드 보러가기

감사합니다. 좋은 하루 되세요. 🤗

문제

문제 링크

카카오 성격 유형 검사지를 만들려고 합니다.

성격 유형은 아래와 같습니다.

각각의 지표에 대해서 점수가 높은 알파벳을 조합하여 성격 유형 결과가 나옵니다. -> mbti를 생각하면 됨

ex) RCMA

검사지에는 총 n개의 질문이 있고 선택지 총 7개 입니다.

• 매우 비동의
• 비동의
• 약간 비동의
• 모르겠음
• 약간 동의
• 동의
• 매우 동의

검사자의 선택에 따라(동의/비동의) 한가지 지표의 한 개의 성격 유형에 대한 점수를 얻습니다. (1번 지표일 경우 비동의가 R, 동의가 T일 수도 있고, 동의가 R, 비동의가 T일 수 있음)

R(라이언형)이 비동의, T(튜브형)이 동의일 경우 점수는 아래와 같습니다.

점수가 높은 지표를 조합하여 성격유형 검사 결과를 출력합니다.

입력

• survey : survey[i] 번째 문자열은 i+1 번째 문제의 성격유형을 의미 (2글자로 1번째 문자는 비동의, 2번째 문자는 동의에 해당하는 성격유형)
  • ex) "RT", "MJ"
• choices : choices[i]는 검사자가 선택한 i+1번째 질문의 선택지

해결 과정

처음에는 Map을 이용하여 풀려고 했으나 Map으로 푸는 건 너무 흔할 것 같아 새로운 시도를 해보고 싶어 배열로 풀었습니다.

코드

public String solution(String[] survey, int[] choices) {
    String answer = "";
    // 설문자의 점수를 담을 정수형 배열 선언, 차례대로 R, C, J, A 형의 점수, 반대 점수는 음수로 더한다.
    int[] scores = new int[4];

    // 설문지 점수표를 담을 정수형 배열 선언, i번째 인덱스의 숫자가 i점의 점수
    int[] scoreTable = {0, 3, 2, 1, 0, 1, 2, 3};

    // 계산할 점수 지표를 담을 캐릭터형 선언
    char indicator;

    // 질문지의 길이만큼 순회하여 choices의 i번째 요소를 꺼낸다.
    for(int i = 0; i < choices.length; i++) {
        int choice = choices[i];
        // 꺼낸 점수가 4일 경우 continue
        if (choice == 4) continue;
        // 꺼낸 점수가 1~3일 경우
        if (choice < 4) {
            // survey[i]의 0번째 캐릭터형이 점수 지표
            indicator = survey[i].charAt(0);
        } else {  // 꺼낸 점수가 5~7일 경우
            // survey[i]의 1번째 캐릭터형이 점수 지표
            indicator = survey[i].charAt(1);
        }
        // indicator 에 따라 점수를 계산
        switch(indicator) {
            case 'R':
                scores[0] += scoreTable[choice];
                break;
            case 'T':
                scores[0] -= scoreTable[choice];
                break;
            case 'C':
                scores[1] += scoreTable[choice];
                break;
            case 'F':
                scores[1] -= scoreTable[choice];
                break;
            case 'J':
                scores[2] += scoreTable[choice];
                break;
            case 'M':
                scores[2] -= scoreTable[choice];
                break;
            case 'A':
                scores[3] += scoreTable[choice];
                break;
            case 'N':
                scores[3] -= scoreTable[choice];
                break;
            default: break;
        }
    }
    // 점수 배열의 0번째 인덱스가 0이상인 경우 결과 문자열에 R, 음수일경우 T를 붙인다.
    if (scores[0] >= 0) {
        answer += "R";
    } else answer += "T";
    // 점수 배열의 1번째 인덱스가 0이상인 경우 결과 문자열에 C, 음수일경우 F를 붙인다.
    if (scores[1] >= 0) {
        answer += "C";
    } else answer += "F";
    // 점수 배열의 2번째 인덱스가 0이상인 경우 결과 문자열에 J, 음수일 경우 M을 붙인다.
    if (scores[2] >= 0) {
        answer += "J";
    } else answer += "M";
    // 점수 배열의 3번째 인덱스가 0이상인 경우 결과 문자열에 A, 음수일 경우 N을 붙인다.
    if (scores[3] >= 0) {
        answer += "A";
    } else answer += "N";
    return answer;
}

깃허브 코드 보러가기

문제

정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴합니다.

조건

• sort 메서드 사용 금지
• 퀵 정렬을 구현
• 오름차순으로 정렬

해결과정

퀵 정렬을 정확하게 모르기 때문에 구현할 수가 없어 퀵 정렬 방법만 검색하여 참고한 후 코드는 직접 구현하였습니다.

퀵 정렬은 pivot을 기준으로 작은 수들, 큰 수들을 각각 새로운 배열에 넣는 과정을 반복하여 정렬하는 방식입니다.

시간복잡도는 O(nlog n) 에서 최악의 경우 O(n^2) 입니다.

검색한 퀵 정렬의 개념을 토대로 재귀를 이용하여 간단하게 로직을 구현했습니다.

pivot은 주로 맨 끝 요소를 기준으로 하는 것으로 보여서 입력받은 맨끝요소를 pivot으로 하고

배열의 나머지 요소를 순회하면서 작은 수와 큰 수를 각각 나눠 리스트에 집어넣습니다.

(배열이 아닌 리스트를 사용한 이유는?

배열은 사이즈를 알고 있어야 생성할 수 있는데 pivot을 기준으로 큰 수가 몇 개이고 작은 수가 몇 개인지 순회하기 전까진 알 수 없어

번거롭더라도 사이즈가 가변하는 리스트에 넣은 후 순회를 마치면 toArray로 배열로 변환해주었습니다.)

그 후에 작은 수 배열을 재귀로 집어넣고 큰 수 배열도 마찬가지로 재귀에 집어넣습니다.

재귀 브레이크 포인트로 입력받은 배열의 길이가 1이하일 경우는 그대로 리턴하고 2일 경우는 정렬 후 리턴하도록 했습니다.

마지막으로 배열을 작은 수 배열 + pivot + 큰 수 배열 순으로 붙여서 결과 배열을 만든 후 리턴하였습니다.

코드

public int[] quickSort(int[] arr) {
    if (arr.length <= 1) {
        return arr;
    }
    if (arr.length == 2) {
        if (arr[0] > arr[1]) {
            int a = arr[0];
            arr[0] = arr[1];
            arr[1] = a;
        }
        return arr;
    }

    int[] answer = new int[arr.length];
    List<Integer> smallNums = new ArrayList<>();
    List<Integer> bigNums = new ArrayList<>();

    int pivot = arr[arr.length - 1];
    for (int i = 0; i < arr.length - 1; i++) {
        if (arr[i] < pivot) {
            smallNums.add(arr[i]);
        } else bigNums.add(arr[i]);
    }
    int[] smallArr = quickSort(smallNums.stream().mapToInt(Integer::intValue).toArray());
    int[] bigArr = quickSort(bigNums.stream().mapToInt(Integer::intValue).toArray());
    System.arraycopy(smallArr, 0, answer, 0, smallArr.length);
    answer[smallArr.length] = pivot;
    System.arraycopy(bigArr, 0, answer, smallArr.length + 1, bigArr.length);
    return answer;
}

깃허브 코드 보러가기

감사합니다. 좋은하루 되세요. 😄

자연수에서 소수(prime number)는 1보다 큰 수 중에 1과 자기자신만을 약수로 가지는 수이다.

따라서 자신보다 작은 수(1 제외)로 나눴을 때 항상 나누어 떨어지지 않아서 나머지가 존재한다는 의미다.

소수를 구하는 함수를 자바 언어를 사용하여 구현해보았다.

복잡하지 않게 작성하면 이렇게 구현할 수 있다.

public boolean prime (int num) {
	if(num == 0 || num == 1) return false;
	if(num == 2) return true;
    for(int i = 2; i < num; i++){
       if(num % i == 0) return false;
    }
    return true;
}

함수의 형식은 매개변수로 소수인지 구할 숫자를 입력받고 소수인지 여부를 true/false로 반환하는 모양으로 만들었다.

소수인지 구하기 전에 0과 1은 일단 소수가 아니므로 false를 리턴하고 2는 소수이므로 true를 리턴한다.

그리고 1보다 큰 수인 2부터 num보다 작은 num - 1까지 나누어떨어지는지 확인한다.

중간에 한번이라도 나누어떨어지면 소수가 아니므로 false를 리턴하고

num - 1 까지 확인을 마치면 true를 리턴한다.

여기서 더 효율적으로 코드를 짤 수는 없을까?

약수를 확인할 때 항상 2개씩 짝이 지어진다.

예를 들어 40의 약수를 구해보면

1, 2, 4, 5, 8, 10, 20, 40 이다.

이때 1과 40, 2와 20, 4와 10, 5와 8 이렇게 2개씩 짝이 지어진다.

그렇다면 맨 끝까지 일일이 나눠서 확인할 필요없이 중간 수 까지만 확인하면 끝까지(num - 1) 확인한 것과 같은 결과 일 것이다.

그 중간 수는 어떻게 구하는가?

2 x 20, 4 x 10, 5 x 8 = 40

중간 수는 자기자신을 곱했을 때 40이 나오는 수이다!

다시 말해 40의 제곱근이다.

자바에서 제곱근을 구하려면 Math.sqrt() 를 사용하면 된다.

다음은 제곱근까지만 확인하도록 구현해보았다.

    public boolean prime (int num) {
        if(num == 0 || num == 1) return false;
        if(num == 2) return true;
        if(num % 2 == 0) return false;
        for(int i = 3; i <= Math.sqrt(num); i++)
            if(num % i == 0) return false;
        return true;
    }

이 함수가 맨 처음에 만든 함수보다 반복문에서 num의 제곱근 까지만 반복하므로 더 효율적이다.

+ 

여기서 추가로 이웃이신 닉님의 도움으로 더 간단하게 작성했습니다!

짝수는 2로 나눠서 확인했기 때문에 3부터 +2하면서 확인하면 됩니다.

    public boolean prime (int num) {
        if(num == 0 || num == 1) return false;
        if(num == 2) return true;
        if(num % 2 == 0) return false;
        for(int i = 3; i <= Math.sqrt(num); i += 2)
            if(num % i == 0) return false;
        return true;
    }

읽어주셔서 감사합니다.

좋은 하루 되세요 ^^

+닉님 감사합니다😃

문제

동전 종류를 담은 int형 배열과 목표 액수를 매개변수로 전달받았을 때

가지고 있는 동전 종류로 목표 액수를 만들 수 있는 모든 가짓수를 구하시오.

(배열로 받은 동전 종류는 각각 개수에 제한이 없다고 가정)

해결

코드보기

public class Dp {
    public long ocean(int target, int[] type) {
        // 가짓수를 담을(반환할) 결과값 0으로 초기화
        long result = 0;
        long[][] arr = new long[type.length][target + 1];
        for(int i = 0; i < type.length; i++) {
            arr[i][0] = 1;
        }
        // type(동전)의 최소 단위로 나누어 떨어지면 교환 가능하기 때문에 방법수 1 저장
        for (int i = type[0]; i <= target; i++) {
            if (i % type[0] == 0) arr[0][i] = 1;
        }

        for (int i = 1; i < type.length; i++) {
            for (int j = 0; j <= target; j++) {
                if(type[i] > j) {
                    arr[i][j] = arr[i-1][j];
                }
                else {
                    arr[i][j] = arr[i][j-type[i]] + arr[i-1][j];
                }
            }
        }
        result = arr[type.length - 1][target];
        return result;
    }
}

코드스테이츠 학습목표

• 알고리즘이 무엇인지 설명할 수 있다.
• 알고리즘 문제를 이해하고 전략을 세울 수 있다.
• 알고리즘 풀이에 필요한 의사 코드를 작성할 수 있다.
• 의사 코드에서 세운 전략을 코드로 구현할 수 있다.
• 내가 구현한 알고리즘을 자바 언어로 설명할 수 있다.

❑ Algorithm

➤ 알고리즘이 무엇인가?

알고리즘은 어떠한 문제를 해결하기 위해 정해진 일련의 절차이다. - 위키백과 -

알고리즘은 문제를 해결하기 위한 최선의 선택이다.

➤ 코딩테스트 푸는 전략

시작하기

• 대부분의 코딩테스트는 문제의 설명, 입출력 예시, 제한사항, 주의사항 등으로 문제 상황을 제시
• 조건을 토대로 문제를 이해하는 것부터 시작

문제 해결 전략 세우기

• 수도 코드를 작성하기 전 전체적인 그림을 종이에 그려가는 작업이 필요함
• 누군가와 같이 해결해야 한다면 그림을 그려가면서 설명하고 논의해서 해결해야 함
• 코드 작성전에 수도 코드 먼저 작성하기! 수도 코드만 잘 짜도 코딩이 쉽다!

❑ 의사코드(pseudoicode)

➤ 의사코드(pseudocode) 란?

프로그래밍 언어로 코드를 작성하기 전에 우리가 쓰는 일상 언어로 프로그램이 작동하는 논리를 먼저 작성하는 것

➤ 의사코드의 장점

1. 시간이 단축된다

코드가 간단하면 수도코드를 작성하는게 더 시간이 걸린다.

하지만 길고 복잡한 코드를 작성할 때는 세세한 부분까지 작성하면서 로직이 기억나지 않을 수 있고 결국 시간이 더 걸리게 된다. 그래서 수도 코드를 먼저 작성하면 수도 코드가 지표가 되어 헤매는 시간이 줄어든다!

2. 디버깅이 용이하다

프로그래밍 언어로만 된 코드를 디버깅 할 때 오류가 난 부분이 어느 부분인지 알아보기 힘들다. 하지만 모국어로 된 수도 코드를 보면 해당 부분이 논리적으로 어느 절차인지 쉽게 이해할 수 있다.

3. 프로그래밍 언어를 모르는 사람과 소통할 수 있다

수도 코드는 우리의 일상 언어로 쓰여졌기 때문에 프로그래밍 언어를 모르는 사람도 프로그램의 수도코드를 보면 어떤 로직으로 동작하는지 이해할 수 있다.

➤ 왜 구체적으로 써야 할까?

컴퓨터는 사람과 달리 알려주지(배우지) 않은 부분은 스스로 할 수가 없기 때문에 세세한 절차까지 코드로 알려주어야 한다.

그래서 의사 코드를 빈틈없이 작성하면 실제 코드에서 빠트리는 부분이 없게 되어 코드가 문제없이 작동할 수 있다.

➤ 의사코드 작성법? 올바른 작성?

의사코드는 자연어(영어나 한국어처럼 일상에서 쓰는 언어)만 사용해도 되고 프로그램 언어와 섞어서 써도 된다.

협업을 하는 실제 업무에서는 의사코드는 매우 중요하다.

따라서 의사 코드에 대한 내용은 클린코드 ‘4장 주석’ 을 읽으면서 더 깊게 알아갈 필요가 있다.

❑ 시간 복잡도(Time Complexity)

알고리즘에서 시간 복잡도는 Big-O 표기법을 사용해서 비교한다.

알고리즘 문제를 풀다보면 해결하는 것 만큼 얼마나 효율적으로 풀었는지도 중요하다.

어떤 알고리즘 문제들은 프로그램 연산에 제한 시간이 있는 경우도 있다.

효율적인 방법을 고민한다

= 시간 복잡도를 고민한다

➤ 시간 복잡도?

입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?

알고리즘은 연산이 많아질수록 시간이 오래걸린다.

시간 복잡도는 연산 횟수와 관계있다.

➤ Big-O

• Big-O(빅-오) : 최악의 경우
• Big-Ω(빅-오메가) : 최선의 경우
• Big-θ(빅-세타) : 중간(평균)의 경우

주로 빅오(최악의 경우)를 가장 많이 사용한다.

프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있기 때문이다.

“최소한 이 정도 걸린다” 보다는 “이 정도 시간까지 걸릴 수 있다” 를 고려해야 모든 상황에 대응이 가능하기 때문이다.

➤ Big-O의 수학적 정의와 계산법

어떤 함수 f(n)의 Big-O notatino이 O(g(n))이라는 것은

n의 값이 일정 수준을 넘어가면 그 이상의 어떤 n을 대입하여도 c*g(n)보다 결과값이 작은 상수 c가 존재한다는 뜻이다.

시간 복잡도는 단위연산(정의, 단순계산, 비교, 출력 등)의 횟수를 기준 함수로 둔다.

int result = 0;
for(int i = 1; i <= n; i++) {
	for(int j = 1; j <= i; j++) {
    	result++;
    }
}

위 알고리즘의 연산횟수는 1+2+ ... + n 이므로 n(n+1)/2 이다.

단위연산의 수를 T(n)이라 할 때, T(n) = n(n+1)/2 + 2 이다.

빅오 표현법으로 나타내기 위해 적절한 g(n)과 c, n0를 선택한다.

g(n) = n^2, c = 1, n0 = 3 이라고 하면

c * g(n) = n^2 >= T(n)

n*n >= n(n+1)/2 + 2

양 변에 *2 ➡️ 2n*n >= n(n+1) + 2*2

n*n + n*n >= n^2 + n + 4

n^2 >= n + 4

➡️ n0인 3 이상의 모든 수 n에 대하여 T(n)보다 c*g(n)의 값이 크다

따라서 이 알고리즘의 시간복잡도는 O(n^2)이라고 표기한다.

※ Big-O의 표기법

가능한 가장 작은 표기법을 사용한다.

O(n^2)도 되고 O(n)도 된다면 더 작은 O(n)을 사용한다.

가능한 가장 간단하게 표기한다.

O(3n+4)과 같이 쓰지 않고 O(n)으로 쓴다.

➤ 많이 쓰는 Big-O

O(1) : constant complexity

입력값이 증가해도 시간(연산)이 늘어나지 않는다.

O(n) : linear complexity

입력값이 증가하면 시간도 같은 비율로 증가

O(log n) : logarithmic complexity

O(1) 다음으로 빠른 시간 복잡도를 가짐

BST(이진 탐색 트리)가 O(log n)의 시간복잡도를 가짐

연산을 할 수록 전체 해야할 연산 수가 줄어들 때이다

for(int i = 0; i < n; i++) {
	i *= k;
}

예를 들어 i는 연산할 수록 k가 곱해지고 n과 비교한다. 따라서 k*k*k*...(t번 실행 -> k^t) >= n 가 될 때까지 t번 실행하게 된다.

(여기서 증감문의 i++는 신경쓰지 않아도 된다. n이 무수히 커질 수록 +1이나 상수를 곱하는건 근소한 차이이기 때문에 무시해도 되기 때문이다.)

여기서 k^t = n 를 만족하는 t만큼 실행하게 되는 것이다.

t = logk n인 것이다.

따라서 시간 복잡도는 O(logk n) ➡️ O(log n) 이다.

(O(log2 n)이나 O(log3 n)등도 모두 O(log n)으로 표기한다.)

O(n^2) : quadratic complexity

O(n^2)이나 O(n^5) 등도 모두 O(n^2)으로 표기한다.

시간 복잡도가 O(n^2)이 되는 순간 부터 입력값이 커질수록 컴퓨터에 가는 부담이 어마어마 해진다...

여러번 중첩된 for문은(실행수가 입력값에 영향을 받을 때) 가능하다면 피하는 것이 좋다..

O(2^n) : exponential complexity

가장 느린 시간 복잡도를 가짐

재귀를 이용한 알고리즘이 보통 O(2^n)의 시간복잡도를 갖는다.

그래서 재귀를 이용하면 코드는 직관적이고 짧아지지만 입력값이 커질수록 실행시간이 엄청 늘어난다.

재귀로 작성한 피보나치 수열을 떠올려보자.

100번 실행하려면....2의 100승을 계산해야 한다...

피보나치는 입력값이 커질 것을 대비하고 싶다면 재귀보다는 배열을 사용해서 이전인덱스와 전전인덱스를 불러오는 것이 효율적이다..

➤ Big-O는 어떻게 활용할까?

대부분 코딩테스트에서 실행 타임에 제한 시간이 걸려있다.

최대 입력값을 확인하고 시간복잡도를 고려해서 알고리즘을 설계할 수 있는지 확인하는 것이다.

입력값이 최대일 때를 항상 고려해서 알고리즘을 설계하면 안정적인 프로그램을 만들 수 있다.

입력값의 최댓값이 많이 크다면 시간 복잡도가 작은 알고리즘으로 작성하는 것이 좋다.

그런데 입력값이 작다면 굳이 시간을 들이고 머리를 굴려가면서 시간 복잡도가 작은 알고리즘을 찾을 필요는 없다.

보통 데이터 크기에 따른 시간복잡도 설계는 이 정도만 해도 된다.

n <= 1,000,000 ➡️ O(n) or O(log n)

n <= 10,000 ➡️ O(n^2)

n <= 500 ➡️ O(n^3)

❑ 탐욕 알고리즘(Greedy)

말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황을 쫓아 최종적인 해답에 도달하는 방법

매 순간 최적이라 생각되는 해답(locally optimal solution)을 찾고 최종 문제의 해답(globally optimal solution)에 도달하는 문제 해결 방식

항상 최적의 결과를 도출하는 것은 아니지만 어느 정도 최적의 근사한 값을 빠르게 도출할 수 있다는 장점이 있음

➤ 탐욕 알고리즘  해결 방법

1. 선택 절차(Selection Procedure)

현재 상태에서의 최적의 해답을 선택

2. 적절성 검사(Feasibility Check)

선택된 해가 문제의 조건을 만족하는지 검사

3. 해답 검사(Solution Check)

원래의 문제가 해결되었는지 검사하고 해결되지 않았다면 선택 절차로 돌아가 위 과정 반복

➤ 탐욕 알고리즘은 은탄?

현재의 최적의 선택이 언제나 최적의 결과를 보장하진 않는다.

탐욕 알고리즘을 사용한 것이 꼭 최적의 결과는 아닌 경우도 있다.

ex) 마시멜로 실험 결과

마시멜로를 지금 받으면 1개 1분을 기다렸다가 받으면 2개를 받을 수 있다.

greedy는 현재의 최적의 선택인 지금 1개를 받는 것을 선택하지만

최종적으로는 1분을 기다리고 2개를 받는 것이 최적의 결과이다.

➤ 탐욕 알고리즘을 적용하기 위한 조건

1. 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다

2. 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다

읽어주셔서 감사합니다. 좋은 하루 되시고 도움이 되셨길 바랍니다.

오개념에 대한 지적은 언제나 환영입니다~😍