💟 문자 char 0~9 는 int 48~57 이다.

💟 문자 char A~Z는 int 65~90 이다.

💟 문자 char a~z는 int 97~122 이다.

💟 그러므로 String.charAt(0) >= 48 && String.charAt(0) <= 57 이면 문자열의 첫 글자는 숫자이다.

String str = "mOoN";

🌟 전체 소문자화 ⬇️

str.toLowerCase();

🌟 전체 대문자화 ⬇️

str.toUpperCase();

🌟 첫 글자만 대문자화 ⬇️

str.substring(0,1).toUpperCase() + str.substring(1);

🟪 객체지향 프로그래밍 I

🟪 객체지향 프로그래밍 II

🟪 예외처리

🟪 java.lang패키지와 유용한 클래스

🟪 컬렉션 프레임웍

🟪 지네릭스, 열거형, 애너테이션

🟪 쓰레드

🟪 람다와 스트림

🟪 입출력

🟪 네트워킹

가을의 맑은 하늘처럼 내 마음도 맑아졌으면 좋겠다. 이 파우치가 완성 된 것 처럼 나의 우테코 준비도 잘 완성되었으면 좋겠다. 내년에는 우테코에 참여할 수 있었으면 좋겠다.

이 파우치에 행운이 가득 담겨서 내 바람이 이루어졌으면 좋겠다. (앗, 구멍 송송 네트 무늬인데... 행운이 다 빠져나가는 건...ㅎ)

💓 코바늘 파우치 완성 과정 ⬇️ 💓

처음 만들어본 거라서 그런지 여기저기 엉성한 부분이 많다 헤헤 😉

🟪 Cache Hit

메모리가 캐시에 존재하고 있을 경우 Cache Hit라고 한다.

🟪 Cache Miss

메모리가 캐시에 존재하지 않을 때 Cache Miss라고 한다.

🟪 Least Recently Used

가장 오랫동안 "참조"되지 않은 페이지를 교체하는 방식이다. 캐시가 가득 찼을때, 가장 오랫동안 참조되지 않은 페이지를 찾아서 없애는 과정이 필요하다. 사용된지 가장 오래된 페이지는 앞으로도 사용될 확률이 낮다는 가설에 의해 만들어진 알고리즘이다.

💟 원리

가장 오랫동안 참조되지 않은 페이지를 찾아서 없애는 과정

• 페이지를 새로 참조할 때마다 연결리스트의 맨 앞에 페이지번호를 추가한다.
  그러면 맨 뒤에 있는 페이지번호가 가장 오랫동안 참조되지 않은 페이지번호가 된다.

• Doubly Linked List 를 사용하고 head 에 가까운 node 일수록 가장 최근에 참조된 페이지, tail 에 가까운 node 일수록 가장 오랫동안 참조되지 않는 페이지이다.

  • hit 일 때 : 기존 페이지 삭제 후 맨 앞에 다시 추가
  • miss 일 때 : 맨 앞에 추가
  • cache size 를 넘어서게 될 때 : tail 에 가장 가까운 페이지 삭제 후 맨 앞에 다시 추가

캐시의 크기는 3이다. 새로운 참조값은 맨 앞에 추가한다. 이미 3개의 참조값이 캐시에 들어있다면 맨 뒤에 있는 참조값을 제거하고 새로운 참조값을 맨 앞에 추가한다. 새로운 참조값이 이미 캐시에 들어있는 값이라면 기존 위치에서 제거하고 다시 맨 앞에 추가한다.

• 캐시 리스트의 크기는 3 이다.
  
• 참조값 1 이 캐시 리스트의 맨 앞에 추가된다. ↳ miss , 참조값 1은 캐시리스트에 없는 값이므로.
  
• 참조값 2 가 캐시 리스트의 맨 앞에 추가된다. ↳ miss , 참조값 2는 캐시리스트에 없는 값이므로.
  
• 참조값 1 이 캐시 리스트의 맨 앞에 추가된다. ↳ hit , 참조값 1은 캐시리스트에 있던 값이므로 기존 위치에서 지워지고 다시 맨 앞에 추가 된다.`
  
• 참조값 3 이 캐시 리스트의 맨 앞에 추가된다. ↳ miss , 참조값 3는 캐시리스트에 없는 값이므로.
  
• 참조값 4 가 캐시 리스트의 맨 앞에 추가된다. ↳ miss , 참조값 4는 캐시리스트에 없는 값이므로. : 캐시리스트가 가득 찼으므로 리스트의 맨 뒤에 있는 = 가장 오랫동안 참조되지 않은 참조값 2가 삭제되고, 참조값 4가 캐시리스트의 맨 앞에 추가된다.
  
• 참조값 1 이 캐시 리스트의 맨 앞에 추가된다. ↳ hit , 참조값 1은 캐시리스트에 있던 값이므로 기존 위치에서 지워지고 다시 맨 앞에 추가 된다.
  
• 참조값 5 가 캐시 리스트의 맨 앞에 추가된다. ↳ miss , 참조값 5는 캐시리스트에 없는 값이므로. : 캐시리스트가 가득 찼으므로 리스트의 맨 뒤에 있는 = 가장 오랫동안 참조되지 않은 참조값 3이 삭제되고, 참조값 5가 캐시리스트의 맨 앞에 추가된다.
  
• 참조값 4 가 캐시 리스트의 맨 앞에 추가된다. ↳ hit , 참조값 4는 캐시리스트에 있던 값이므로 기존 위치에서 지워지고 다시 맨 앞에 추가 된다.

🦄 출처 : 이 글의 모든 내용과 사진들은 사과개발자의 일상 블로그의 LRU 알고리즘 (Least Recentely Used) 개념 및 구현방법 게시물에서 가져온 것입니다.

: 티스토리 사이트의 daily_D님의 사과개발자의 일상 블로그의 LRU 알고리즘 (Least Recentely Used) 개념 및 구현방법 게시물

🟪 문제 바로가기

이 글은 문제를 정리하고 저의 풀이를 보여드리는 거예요. 실제로 문제를 보고 풀어보세요. 클릭! 클릭! 해보세요! 🖱️

🟪 문제 설명

지도에서 도시 이름을 검색하면 해당 도시와 관련된 맛집 게시물들을 데이터베이스에서 읽어 보여주는 서비스를 개발하고 있다.

이 프로그램의 테스팅 업무를 담당하고 있는 어피치는 서비스를 오픈하기 전 각 로직에 대한 성능 측정을 수행하였는데 데이터베이스에서 게시물을 가져오는 부분의 실행시간이 너무 오래 걸린다는 것을 알게 되었다.

DB 캐시를 적용하여 성능 개선을 시도하고 있지만 캐시 크기를 얼마로 해야 효율적인지 몰라 난감한 상황이다.

DB 캐시를 적용할 때 캐시 크기에 따른 실행시간 측정 프로그램을 작성하시오.

💟 입력 형식

• 캐시 크기(cacheSize)와 도시이름 배열(cities)을 입력받는다.
• cacheSize는 정수이며, 범위는 0 ≦ cacheSize ≦ 30 이다.
• cities는 도시 이름으로 이뤄진 문자열 배열로, 최대 도시 수는 100,000개이다.
• 각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다. 도시 이름은 최대 20자로 이루어져 있다.

💟 출력 형식

입력된 도시이름 배열을 순서대로 처리할 때, "총 실행시간"을 출력한다.

💟 조건

• 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.
• cache hit일 경우 실행시간은 1이다.
• cache miss일 경우 실행시간은 5이다.

💟 입출력 예제

💟 추가 해설

LRU 캐시 교체 알고리즘을 구현하는 문제이고, 검색해봤다면 잘 구현된 LRU 알고리즘 코드는 많이 찾을 수 있습니다.

단, 이 문제에는 입출력 예제에 캐시 사이즈 0이 포함되어 있습니다. 공개된 대부분의 LRU 구현 코드는 0일 때의 비정상적인 상황은 가정하지 않고 있기 때문에 생각 없이 그냥 가져와 붙인다면 에러가 나서 많이 고생했을 거 같네요.

사이즈 0을 처리하는 예외 처리 자체는 어렵지 않게 구현할 수 있으므로 입출력 예제가 왜 자꾸 틀리는지를 유심히 살펴봤다면 쉽게 풀 수 있는 문제입니다.

🟪 나의 로직

💟 LRU 캐시 교체 알고리즘

💟 LinkedList 자료구조

• 주어진 도시이름 배열 cities 을 읽을 때마다 캐시 교체시간이 생기고 그 교체시간들을 전부 더 하면 총 실행시간이 나온다.
• LinkedList.contains() : cache hit 과 cache miss 을 구별
• cache hit : 기존 데이터 지우고 맨 앞에 새로 추가한다. LinkedList.remove() ➡️ LinkedList.addFirst()
• cache miss : 맨 앞에 새로 추가한다. LinkedList.addFirst()
• cache miss && 캐시가 가득 찼을 때 : 맨 뒤의 데이터를 지우고 맨 앞에 새로 추가한다. LinkedList.removeLast() ➡️ LinkedList.addFirst()

❗ 도시이름 대소문자 구분하지 않는 처리하기

" 각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다. "고 문제에는 되어있다.

그러므로 만약 도시 이름 문자열 배열 - cities 가 [Daegu, daegu] 이렇다면 첫 번째 Deagu 는 cache miss 이고 두 번째 daegu 는 이미 앞에 Daegu 와 같은 페이지이므로 cache hit 이 되는 것이다.

이렇게 되기 위해서는 cache hit 또는 cache miss 하기 전에 미리 도시 이름을 *toUpperCase() / toLowerCase() *처리하면 된다.

❗cacheSize가 0일때 예외 처리하기

cacheSize 가 0일때는 캐시에 도시이름을 담아둘 수가 없으므로 cash hit 경우는 아예 없게 되고, 모든 경우가 cash miss 가 된다.

도시 이름 페이지가 추가될 때마다, 같은 도시 이름이 연속 2번 추가 되더라도, 늘 cash miss 다.

모든 경우가 cache miss 이므로 도시이름 갯수 * cache miss 실행시간 을 하면 총 실행시간을 구할 수 있다.

💟 구현

• 총 실행시간 : int runtime

• 캐시 : LinkedList<String> cache

• cacheSize 가 0일 때 : 모든 경우가 cache miss 이므로 도시이름 갯수 * cache miss 실행시간을 하면 총 실행시간을 구할 수 있다. if (cacheSize == 0) runtime = cities.length * cacheMiss

• for문 : 캐시 LRU 교체 알고리즘으로 총 실행시간 runtime 을 계산한다. for (int idx = 0; idx < cities.length; idx++)

  • 시티이름을 미리 대문자화 시켜 대소문자가 다른 시티이름이 같은 문자열로 취급될 수 있게 한다. String city = cities[idx].toUpperCase()

  • if(cache.contains(city)) : cache hit

    • runtime++ : cache hit 일 경우 실행시간은 1이다.
    • cache.remove(city) : 기존 위치 지우고
    • cache.addFirst(city) : 맨 앞에 다시 추가한다.

  • else : cache miss

    • runtime += 5 : cache miss일 경우 실행시간은 5이다.
    • if(cache.size() == cacheSize) : 캐시가 꽉 찼을 때 cache.removeLast() : 맨 뒤를 지우고 cache.addFirst(city) : 맨 앞에 추가한다.
    • else : 캐시에 자리가 있을 때 cache.addFirst(city) : 맨 앞에 추가한다.

  • for문이 끝나면 총 실행시간 runtime이 계산되어 졌다. 이것을 return runtime 함으로써 끝낸다.

🟪 나의 코드

public static int solution(int cacheSize, String[] cities) {
    int runtime = 0;
    int cacheHit = 1;
    int cacheMiss = 5;
    LinkedList<String> cache = new LinkedList<>();

    if (cacheSize == 0) {
        runtime = cities.length * cacheMiss;
        return runtime;
    }

    for (int idx = 0; idx < cities.length; idx++) {
        String city = cities[idx].toUpperCase();
        if (cache.contains(city)) {
            runtime += cacheHit;
            cache.remove(city);
            cache.addFirst(city);
        } else {
            runtime += cacheMiss;
            if (cache.size() >= cacheSize) {
                cache.removeLast();
                cache.addFirst(city);
            } else
                cache.addFirst(city);
        }
    }
    return runtime;
}

🟪 결과 : 성공 💞

🥶❓만약 런타임 에러가 난다면❗

필요한 패키지는 꼭 임포트 해야한다.

🟪 문제 바로 가기

이 글은 문제를 정리하고 저의 풀이를 보여드리는 거예요. 실제로 문제를 보고 풀어보세요. 클릭! 클릭! 해보세요! 🖱️

🟪 문제 설명

• 문자열 s에는 공백으로 구분된 숫자들이 저장되어 있습니다.

• 문자열 s에 나타나는 숫자 중 최소값과 최대값을 찾아
• 이를 "(최소값) (최대값)"형태의 문자열을 반환하는 함수, solution을 완성하세요.
• 문자열 s에는 둘 이상의 정수가 공백으로 구분되어 있습니다.

💟 입출력 예시

🟪 나의 로직

💟 선택 정렬

• 선택 정렬로 주어진 문자열s을 문자열 배열에 대입한다.
• 문자열 배열을 정수 리스트에 대입한다.
• 정수 리스트를 선택정렬 알고리즘을 이용하여 정렬시킨다.
• 정렬된 리스트의 첫 인덱스의 값과 마지막 인덱스의 값을 String.format("%d %d")를 이용해서 "(최소값) (최대값)"형태의 문자열을 반환할 것이다.

💟 구현

• 주어진 문자열 s를 배열String[] array로 대입
  • String[] array = s.split(" ")
• String[] array를 ArrayList<Integer> orderedArrList로 대입
  • for(String num : array) orderedArrList.add(Integer.parseInt(num))
• for문 2개로 선택정렬 구현
  • 첫번째 for 문 == 패스스루
    • 범위 : 인덱스0에서 마지막인덱스 바로 전까지 orderedArrList.size()-2 (선택정렬은 배열의 마지막인덱스 바로 전의 인덱스가 되면 마지막 패스스루가 되기 때문이다.)
    • for(int startIdxOfPassThrogh=0; startIdxOfPassThrogh<orderedArrList.size()-1; startIdxOfPassThrogh++)
    • 최솟값의 인덱스-minmumValueIdx 를 패스스루의 시작인덱스-startIdxOfPassThrogh 로 초기화 시킨다. (패스스루가 처음 시작될 때는 시작인덱스의 값이 곧 최솟값이므로)
    • minmumValueIdx = startIdxOfPassThrogh
  • 두번째 for 문 == 현재 최솟값과 각각의 값들을 비교하여 최종 최솟값을 정한다
    • 범위 : 패스스루의 시작인덱스-startIdxOfPassThrogh의 바로 다음 인덱스부터 마지막 인덱스까지
    • for(nowIdx=startIdxOfPassThrogh+1; nowIdx<orderedArrList.size(); nowIdx++)
    • 최솟값과 다음값을 비교한다.
    • 최솟값보다 더 작은 값이 나오면 최솟값을 바꾼다.
    • if(orderedArrList[nowIdx]<orderedArrList[minmumValueIdx]) minmumValueIdx = nowIdx
  • 두번째 for 문이 끝나면
    • 패스스루의 시작인덱스-startIdxOfPassThrogh와 패스스루에서 최종적으로 결정된 최솟값의 인덱스-minmumValueIdx를 교환한다.
    • if(startIdxOfPassThrogh != minmumValueIdx) int temp = orderedArrList[minmumValueIdx] orderedArrList[minmumValueIdx] = orderedArrList[startIdxOfPassThrogh] orderedArrList[startIdxOfPassThrogh] = temp
  • for문이 끝나면 최소값과 최대값을 "(최소값) (최대값)"형태의 문자열로 반환한다.
    • return String.format("%d %d", orderedArrList.get(0), orderedArrList.get(orderedArrList.size()-1))

🟪 나의 코드

public static String solution(String s) {
    String[] array = s.split(" ");
    ArrayList<Integer> orderedArrList = new ArrayList<>();

    for (String num : array)
        orderedArrList.add(Integer.parseInt(num));

    for (int startIdxOfPassThrogh = 0; startIdxOfPassThrogh < orderedArrList.size()-1; startIdxOfPassThrogh++) {
        int minmumValueIdx = startIdxOfPassThrogh;

        for (int nowIdx = startIdxOfPassThrogh + 1; nowIdx < orderedArrList.size(); nowIdx++) {
            if (orderedArrList.get(nowIdx) < orderedArrList.get(minmumValueIdx))
                minmumValueIdx = nowIdx;
        }

        if (startIdxOfPassThrogh != minmumValueIdx) {
            int temp = orderedArrList.get(minmumValueIdx);
            orderedArrList.set(minmumValueIdx, orderedArrList.get(startIdxOfPassThrogh));
            orderedArrList.set(startIdxOfPassThrogh, temp);
        }
    }

    return String.format("%d %d", orderedArrList.get(0), orderedArrList.get(orderedArrList.size()-1));
}

🟪 결과 : 성공💕

🥶❓만약 런타임 에러가 난다면❗

필요한 패키지 임포트를 하지 않았기 때문입니다!

그러니까 지금 주니어 개발자도 아닌 그저 취준생인 나인데 어떤 언어든지 배워서 이것 저것 배워보는 게 좋지 않을까? 어플도 만들어 보고, 서버도 만들어 보고, css도 써보고, shell도 써보고 이런식으로 말이야

모든 시간을 이렇게 탐험하겠다는 것은 아니고

탐험 하는 시간이 이때까지는 전혀 없었으니까 가끔씩 조금씩 이렇게 탐험해보자는 거얌 왜냐면 나는 산만하고 새로운 것을 좋아하니까! 이러한 탐험 시간이 생기면 활기와 재미가 더해져서 개발직을 더욱 사랑하고 몰두할 수 있을 것 같아!

사진 출처

티스토리사이트의 525님의 525의 일상블로그의 상어와 함께 자란 소년은 수영을 배울 필요가 없다게시물을 보러가 보아요!

• 선택 정렬 = selection sort

🔶 방법

• 인덱스0까지에서 정해진 최솟값 = 2 (유일한 값이므로)

• ↳ 인덱스0까지에서 정해진 최솟값 2는 인덱스1의 값 6보다 작으므로 최솟값이 2로 결정됐다.

• 인덱스1까지에서 정해진 최솟값 = 2

• ↳ 인덱스2의 값 1이 인덱스1까지에서 정해진 최솟값 2보다 작으므로 최솟값이 1로 결정됐다.

• 인덱스2까지에서 정해진 최솟값 = 1

• ↳ 인덱스2까지에서 정해진 최솟값 1이 인덱스3의 값 3보다 작으므로 최솟값이 1로 결정됐다.

• ↳ 이번 패스스루에서 정해진 최솟값 1의 인덱스인 인덱스2와 이번 패스스루의 시작 인덱스인 인덱스0을 교환한다.
• ( 마지막 인덱스까지에서 정해진 최솟값은 1이고 비교할 오른쪽 셀이 없으므로 이 최솟값이 이번 패스스루의 최솟값이 된다. )*

1단계 : 현재 최솟값과 오른쪽 셀의 값을 비교하여 최솟값을 정한다.

현재 최솟값 : 지금 가리키고 있는 인덱스 까지 에서 정해진 최솟값

첫번째 패스스루의 첫 단계에서는 인덱스0과 인덱스1을 비교하여 최솟값을 정한다.

정해진 최솟값의 인덱스를 변수에 저장한다.

변수에 들어 있는 값보다 작은 값이 들어 있는 셀을 만나면 변수가 새 인덱스를 가리키도록 값을 대체한다.

2단계 : ** 배열의 끝에 도달하면 최솟값의 인덱스와 패스스루의 시작인덱스를 교환한다. **최솟값의 인덱스와 시작인덱스가 같은 위치면 교환이 일어나지 않으므로 이 단계 또한 일어나지 않는다.

패스스루를 시작했을 때 인덱스는 첫 패스스루에서는 인덱스 0이고, 두 번째 패스스루에서는 인덱스 1이다.

3단계 : 매 패스스루는 1, 2 단계로 이뤄진다. 패스스루의 시작인덱스가 배열의 마지막인덱스가 되기 전 까지 패스스루(1~2단계)를 반복한다. 즉 패스스루의 시작인덱스가 배열의 마지막인덱스 바로 전의 인덱스가 되면 마지막 패스스루가 된다는 뜻이다. *왜냐하면 패스스루가 끝나면 패스스루의 시작인덱스까지 올바르게 정렬된다. 그러므로 마지막 패스스루에서는 마지막 셀을 제외한 모든 셀이 올바르게 정렬이 되므로 이는 곧 전체 배열이 올바르게 정렬되는 것이기 때문이다. *

🔶 {4, 2, 7, 1, 3} 정렬 해보기

🔵 첫 번째 패스스루

1단계 : 인덱스0에 들어 있는 값 4가 현재 최솟값이므로 이 인덱스를 변수에 저장한다. 그리고 현재 최솟값과 오른쪽 값 2를 비교하여 최솟값을 정한다. 오른쪽 값이 더 작으므로 결정된 최솟값은 2가 된다.

2단계 : 여기까지 정해진 현재 최솟값은 2이다. 다음 값인 7이 더 크므로 2가 최솟값으로 유지된다.

3단계 : 현재 최솟값 2와 다음 값 1을 비교한다. 오른쪽 값이 더 크므로 최솟값은 1로 새롭게 결정된다.

4단계 : 인덱스 3을 가리키고 있을 때 현재 최솟값은 1이다. 다음 값 3과 비교했을 때 여전히 최솟값이다. 배열의 끝 값과 비교했을 때 제일 작은 수를 알아냈으므로 전체 배열의 최솟값은 1로 결정됐다.

5단계 : 이번 패스스루에서 결정된 최솟값 1의 안덱스3과 이번 패스스루의 시작 인덱스인 인덱스0을 교환한다.

🔵 두 번째 패스스루

6단계 : 인덱스0은 첫 번째 패스스루에서 이미 정렬된 값이므로 두 번째 패스스루는 다음 인덱스인 인덱스1부터 시작한다. 인덱스1의 값 2가 현재 최소값이므로 이 인덱스를 변수에 저장한다. 현재 최솟값과 오른쪽 값 7을 비교하여 결정된 최솟값은 2이므로 변수는 그대로 유지된다.

7단계 : 현재 최솟값 2와 오른쪽 값 4를 비교하여 결정된 최솟값은 2이므로 변수는 그대로 유지된다.

8단계 : 현재 최솟값 2와 오른쪽 값 3을 비교하여 결정된 최솟값은 2이므로 변수는 그대로 유지된다. 마지막 인덱스까지 비교가 끝났으므로 이제 교환을 할 차례이다. 이번 패스스루의 최솟값 2의 인덱스인 인덱스1과 이번 패스스루의 시작인덱스인 인덱스1이 같은 위치이므로 교환은 일어나지 않고 두 번째 패스스루가 끝난다.

🔵 세 번째 패스스루

9단계 : 인덱스0과 인덱스1은 이때까지의 패스스루에서 이미 정렬된 값이므로 세 번째 패스스루는 인덱스2가 시작인덱스가 된다. 인덱스2의 값7이 현재 최솟값이므로 이 인덱스를 변수에 저장한다. 현재 최솟값과 오른쪽 값4를 비교하여 결정된 최솟값은 4이므로 변수에 저장되는 값도 7에서 4로 바뀐다.

10단계 : 마지막 인덱스와 비교를 하므로 이 단계에서 정해지는 최솟값이 이번 패스스루의 최솟값이 된다. 현재 최솟값 4와 오른쪽 값 3을 비교한다. 이 때 오른쪽 값이 더 작으므로 결정되는 최솟값은 3이 된다. 변수에 저장되는 값도 4에서 3으로 바뀐다.

11단계 : 마지막 인덱스를 가리키게 되었으니 이번 패스스루의 최솟값과 시작인덱스를 교환하면 패스스루가 종료된다. 이번 패스스루의 최솟값 3의 인덱스인 인덱스4와 이번 패스스루의 시작인덱스인 인덱스2를 교환하고 패스스루는 종료된다. 이번 패스스루로 인하여 이번 패스스루의 시작인덱스까지, 인덱스0부터 인덱스2까지 정렬이 되었다.

🔵 네 번째 패스스루

12단계 : 이때까지의 패스스루에서 인덱스0 ~ 인덱스2까지는 이미 정렬됐으므로 인덱스3이 이번 네 번째 패스스루의 시작인덱스가 된다. 마지막 인덱스와 비교를 하므로 이 단계에서 정해지는 최솟값이 이번 패스스루의 최솟값이 된다. 시작인덱스의 값 4가 현재 최솟값이 된다. 현재 최솟값 4와 다음 인덱스의 값 7을 비교하여 결정된 최솟값은 4가 된다. 이번 패스스루의 최솟값의 인덱스인 인덱스3과 이번 패스스루의 시작인덱스인 인덱스3은 같은 위치이므로 교환이 일어나지 않는다. 그러므로 다음 단계 없이 여기서 패스스루가 끝난다. 이번 패스스루의 시작인덱스(인덱스3)가 배열의 마지막인덱스(인덱스4)의 바로 전 인덱스이므로 이번 패스스루가 마지막 패스스루가 되며 선택정렬이 완전히 종료된다.

❕코드 구현 ❗

• 각 패스스루를 나타내는 for루프를 시작한다. 루프는 변수startIndexOfPassThrough를 통해 배열의 각 인덱스를 가리키며 배열의 마지막인덱스 바로 전까지 살펴본다.

• 변수lowestNumberIndex에 현재 최솟값의 인덱스를 저장한다.

• 각 패스스루에서는 for루프를 이용해 현재 최솟값과 다음 인덱스를 마지막인덱스까지 비교한다. (중첩 for루프가 된다)

• 각 패스스루에서는 현재최솟값과 다음인덱스의 값을 비교하여 현재 최솟값보다 더 작은 값인지 확인한다. 더 작은 값이라면 변수lowestNumberIndex를 다음인덱스로 다시 저장한다.

• 패스스루의 최솟값과 패스스루의 시작인덱스를 비교했을 때 같지 않다면 교환한다.

• 끝으로 정렬된 배열을 반환한다.

public static int[] selectionSort(int[] array) {
    for (int startIndexOfPassThrough = 0; startIndexOfPassThrough < array.length - 1; startIndexOfPassThrough++) {
        int lowestNumberIndex  = startIndexOfPassThrough;

        for (int nextIndex = startIndexOfPassThrough+1; nextIndex < array.length; nextIndex++) {
            if (array[nextIndex] < array[lowestNumberIndex])
                lowestNumberIndex = nextIndex;
        }

        if (lowestNumberIndex != startIndexOfPassThrough) {
            int temp = array[startIndexOfPassThrough];
            array[startIndexOfPassThrough] = array[lowestNumberIndex];
            array[lowestNumberIndex] = temp;
        }
    }

    return array;
}

** main 출력 테스트 통과 **

🔶 효율성 : O(N²)

선택 정렬은 비교와 교환, 두 종류의 단계를 포함한다.

• 비교 : 각 패스스루 내에서 각 값을 현재까지 찾은 최솟값과 비교한다.
• 교환 : 그렇게 결정된 최종 최솟값을 패스스루의 시작 인덱스와 교환한다.

🔵 {4, 2, 7, 1, 3} 정렬 예제를 보면은

{4, 2, 7, 1, 3} 정렬 예제를 보면은 총 4번의 패스스루에 총 10번의 비교를 교환은 두 번 일어났다.

배열의 크기가 5인데 교환은 총 (5 - 1) + (5 - 2) + (5 - 3) + 1 = 10번이 일어났다.

🔵 모든 크기의 배열에 적용되도록 생각해보면은

배열에 원소 N개가 있을 때

• 비교 : (N - 1) + (N - 2) + (N - 3) … + 1
• 교환 : 한 패스스루당 최대 한 번 (배열이 역순으로 정렬된 최악의 시나리오에서는 각 패스스루마다 빠짐없이 교환을 한 번씩 해야한다.)

🔵 버블정렬과 선택정렬의 단계수를 비교하면은

선택정렬은 버블 정렬보다 단계 수가 반 정도(÷2) 적다. 즉, 선택 정렬이 두 배 더 빠르다.

하지만 선택정렬의 효율성은 버블정렬과 똑같이 O(N²)으로 나타낸다. 왜일까? 그 이유는 빅 오의 상수 무시하기 법칙 때문이다.

🟪 빅 오의 <상수 무시하기> 법칙

왜 선택정렬이 버블정렬보다 2배 더 빠름에도 불구하고 빅 오는 똑같이 O(N²)으로 효율성이 표기 되는 걸까? ➡️ 빅오의 상수 무시하기 법칙 때문이다.

빅 오 표기법은 데이터 원소가 N개일 때 얼마나 많은 단계 수가 필요한가라는 질문에 답하는 것이다.

선택 정렬에서는 데이터 원소가 N개일 때 N²/2단계가 걸린다. 선택 정렬은 대략 N²의 반 단계 정도가 걸리므로 O(N²/2)로 효율성을 표기하는 것이 맞는 것 같다. 하지만 선택 정렬의 효율성은 O(N²)이다. 이유는 다음의 빅 오 규칙 때문이다.

❗빅 오 표기법은 상수를 무시한다❗

상수 : 수식에서 변하지 않는 값

↳ N + 2 에서 N은 변하는 값이지만 2는 절대 변하지 않으므로 상수이다.

↳ N/3 + 6에서 N은 그 때 그 때 계속 변하는 값이지만 3과 6은 어떤 상황에서도 절대 변하지 않으므로 상수이다.

❓ 지수가 아닌 수

이해하지 못한 문장들 ↓

빅 오 표기법은 지수가 아닌 수는 포함하지 않는다는 것을 단순히 수학적으로 표현한 문장이다. 표현식에서 이러한 수는 그냥 버린다.

• 지수 : 제곱되는 수를 "밑", 제곱하는 횟수가 "지수"이다.
• 지수가 아닌 수가 상수라는 말인가.....?

  오키에 질문해봤다. 답글을 보고 의미를 유추해보면

이러한 빅 오의 상수무시하기 법칙 때문에

• N/2 단계가 필요한 알고리즘은 O(N)으로 표현한다.
• N²+10 단계가 필요한 알고리즘은 지수가 없는 10을 버리고 O(N²)으로 표현한다.
• 2N 단계가 필요한 알고리즘은 상수 2를 버리고 O(N)으로 표현한다.
• O(N)보다 100배나 느린 O(100N)이라 해도 결국 O(N)으 알고리즘 효율성이 표기된다.

빅 오의 상수무시하기 법칙에 의해서 빅 오로는 정확히 똑같이 표현하는 두 알고리즘이지만 실제로는 한쪽이 다른 한쪽보다 100배나 빠를 수도 있다.

이것의 완벽한 예시가 선택 정렬과 버블 정렬이다. 선택 정렬과 버블 정렬이 빅 오로는 O(N²)이지만 실제로는 선택 정렬이 N²/2단계의 알고리즘이고 버블 정렬이 N²단계의 알고리즘이므로 선택정렬이 버블정렬보다 2배 더 빠르다.

여기까지 왜 선택 정렬이 버블 정렬보다 2배 더 빠름에도 불구하고 둘 다 똑같은 빅 오로 표기되는지 알아보았다. → 빅 오의 상수 무시하기 법칙 때문에.

상수무시하기가 무엇인지 이제는 알겠다. 이것때문에 N²/2이나 N²이나 같은 알고리즘 단계수로 표현 되는 것도 이제는 알겠다.

그런데

왜 빅 오는 상수를 무시할까? ➡️ 일반적인 카테고리로만 분류해도 현저한 차이를 나타내기 충분하기 때문이다. 빅 오는 일반적인 카테고리만 나타내기 위한 표기법이기 때문이다.

🟪 빅 오 카테고리 - 상수 무시하기 법칙의 이유

🔶 루프의 실행 횟수에 더 초점을 맞추게 된다.

아래는 주어진 숫자까지의 양의 정수에서 짝수만 찾아내 프린트 하는 함수이다.

public void printEvenNumbers (int upperLimit) {
    int number = 2;

    while (number <= upperLimit) {
        if (number % 2)
            System.out.prinln(number);        
        number++;
    }
}

upperLimit이 N일 때 루프가 N번 실행되고, 출력은 N과 상관없이 1번 되는 알고리즘이다. 따라서 알고리즘은 O(N+1)이라고 할 수 있고, 이는 상수 무시하기 법칙에 따라 결국엔 O(N)으로 표시된다.

이렇게 상수를 제거함으로써 루프 안에서 정확히 무슨 일이 일어나는지 보다는 실질적으로 루프가 실행되는 횟수에 더 초점을 맞추게 된다.

🔶 건물을 분류하는데 층수까지 표시할 필요는 없다

건물에 비유해서 「빅 오 카테고리」를 설명해보면, 건물의 종류는 매우 다양하다. 고층건물, 상가건물, 아파트, 공장 등등이 있다.

하나는 단독 주택이고 하나는 고층건물인 두 건물을 비교할 때 굳이 각각이 몇 층인지 언급할 이유가 없다.

두 건물의 크기와 기능이 현저히 달라서 "이 건물은 2층짜리 단독주택이고, 저 건물은 100층짜리 고층 건물이다."라고 말 할 필요가 없는 것이다. 그냥 하나는 집이고 하나는 고층 건물이라고 부르면 된다.

🔶 일반적인 카테고리로만 분류해도 현저한 차이를 나타내기 충분하다.

이러한 맥락으로 알고리즘의 효율성 역시 일반적인 카테고리의 알고리즘 속도만 고려하는 것이다.

O(N) 알고리즘과 O(N²) 알고리즘을 비교할 때 두 효율성 간 차이가 너무 커서 O(N)이 실제로 O(2N) 이든 O(N/2) 이든 O(100N) 이든 별로 중요하지가 않는 것이다.

빅 오 표기법은 단지 알고리즘에 필요한 단계 수만 의미하지 않는다. 데이터가 늘어날 때 알고리즘 단계 수가 장기적으로 어떤 궤적을 그리는지가 중요하다.

O(N)은 직선 성장straight growth을 보여준다. 즉 단계 수가 데이터에 일정 비율로 비례해 직선을 그리며 증가한다.

O(N²)은 지수 성장exponential growth의 하나다.

지수 성장은 어떤 형태의 O(N)-직선성장과도 비교되지 않는 완전히 다른 카테고리다. O(N)에 어떤 수를 곱하든 데이터가 커지다 보면 언젠가 결국 O(N²)이 더 느려지기 때문이다.

O(2N)과 O(N²/50)을 비교하는 것은 2층 주택과 50층 고층건물을 비교하는 것과 다를 바 없다. 간단명료하게 O(N)과 O(N²)으로 비교하면 된다. 단독주택과 고층건물로 두 건물을 비교하면 되는 것과 마찬가지로.

주택끼리, 고층건물끼리 비교하는 것도 아니고 주택과 고층건물 이 두 가지 다른 카테고리를 비교할 때는 주택이 몇 층이고 고층건물이 몇 층인지까지 언급할 필요가 없는 것 처럼 빅 오 또한 서로 다른 카테고리 일 때는 실제 어떤 상수가 곱해져 있고 더해져 있는지 상관없이 카테고리 자체로만 나타내고 비교하면 되는 것이다. O(139N+11) -> O(N) 그래서 빅 오는 카테고리로만 표기하기 위해서 상수무시하기 법칙이 있는 것이다.

🔶 정리

** O(1), O(logN), O(N), O(2N), O(2ⁿ), O(N²) 등과 같은 빅 오 유형은 서로 차이가 큰 일반적인 빅 오 카테고리다.**

지수가 아닌 수로 단계 수를 곱하거나 나누거나 더한다고 카테고리가 바뀌지 않는다. 각각의 카테고리 간의 차이가 너무 커서 특정 카테고리에 속하는 어떤 알고리즘이 실제로는 O(N²/2) 이든 O(logN+9) 이든 별로 중요하지가 않아진다. 그래서 O(N/2) 이든 O(100N) 이든 같은 O(N) 카테고리로 분류하고, O(4)이든 O(1000)이든 같은 O(1)카테고리로 분류하는 것이다.

그렇기 때문에

빅 오에서 서로 다른 카테고리에 속하는 두 효율성을 비교할 때 일반적인 카테고리로 분류하는 것으로 충분하다.

빅 오 표기법은 일반적인 카테고리의 알고리즘 속도만 고려할 뿐만 아니라. 일반적인 카테고리로만 분류해도 현저한 차이를 나타내기 충분하기 때문이다.

그렇기 때문에 빅오의 상수무시하기 법칙이 있는 것이다.

🔶 두 알고리즘이 같은 카테고리에 속할 때는

하지만 두 알고리즘이 같은 카테고리에 속하더라도 서로 처리 속도가 다를 수 있다.

앞에서 계속 예시로 들었듯이 버블 정렬과 선택 정렬은 둘 다 같은 O(N²) 카테고리에 속하지만 실제로 더욱 깊게 비교해보면 버블 정렬은 선택 정렬보다 두 배 느리다.

따라서 빅오에서 서로 다른 카테고리에 속하는 알고리즘을 대조할 때는 빅 오가 완벽한 도구지만 같은 카테고리에 속하는 두 알고리즘이라면 어떤 알고리즘이 더 빠를지 알기 위해 더 분석 해야 한다.

🟪 함수의 효율성 맞춰보기

🔵 1.

주어진 배열의 모든 수를 두 배로 만든 후 그 합을 반환하는 함수

public int doubleThenSum (int[] array) {
    int[] doubledArray = new int[array.length];
    int sum = 0;

    for (int idx = 0; idx < array.length; idx++) {
        doubledArray[idx] = array[idx] * 2;
    }

    for (int num : doubledArray)
        sum += num;

    return sum;
}

: array의 원소 갯수가 N일 때 2개의 for루프가 모두 각각 N번씩 수행되므로 O(2N) ➡️ O(N)이다.

🔵 2.

문자열 배열을 받아 각 문자열을 다양한 형태로 출력하는 함수

public void multipleCases (String[] array) {
    for (String str : array) {
        System.out.println(str.toLowerCase());
        System.out.println(str.toUpperCase());
        System.out.println(str.substring(0,1).toUpperCase() + str.substring(1));
    }
}

: array의 원소 갯수가 N일 때 출력이 3번씩 N번(for루프) 수행되므로 O(3N) ➡️ O(N)이다.

🔵 3.

주어진 배열의 인덱스가 짝수이면 배열 내 모든 수에 대해 그 인덱스의 수를 더해 출력하는 함수

public void everyOther(int[] array) {
    for (int idx = 0; idx < array.length; idx++) {
        if (idx % 2 == 0) {
            for (int num : array)
                System.out.println(num + idx);
        }
    }
}

: array의 원소 갯수가 N일 때 출력이 N번씩 N/2번(중첩 for루프) 수행되므로 O(N²/2) ➡️ O(N²)이다.

🟦 출처

🔷 그림1

123RF사이트에서 marcopolo님의 에스프레소에서 현대적인 고층 건물에 이르기까지 다양한 종류의 건물게시물을 확인해보세요

🔷 글의 내용

이 글 내용은 '제인 웬그로우'의 '누구나 자료구조와 알고리즘 개정 2판' 책을 100% 참고하여 작성하였습니다. 설명에 전문적인 용어보다는 일상적인 용어를 사용하고 그림으로 원리를 설명해주어 왕초보인 저가 이해하기에 아주 좋았습니다. 가격이 많이 나가는 편이지만 꼭 배워야 하는 내용이 모두 들어있고 그것을 제가 이해할 수 있는 수준으로 쓰여있어 전혀 아깝지 않은 소비였습니다.

🖱 클릭! | '제인 웬그로우'의 '누구나 자료구조와 알고리즘' 책 구경하러 가보기

정렬되지 않은 배열이 주어졌을 때, 어떻게 오름차순/내림차순으로 정렬할 수 있을까?

정렬 알고리즘은 컴퓨터 과학 분야에서 폭넓게 연구된 주제이며, 지난 수년간 수십 개의 정렬 알고리즘이 개발돼 왔다. 이러한 알고리즘 모두 "정렬되지 않은 배열이 주어졌을 때, 어떻게 오름차순/내림차순으로 정렬할 수 있을까?"라는 문제를 해결한다.

버블 정렬, 힙 정렬, 퀵 정렬, 트리 정렬 등 모두 정렬 알고리즘 중 하나이다.

🟪 🌟버블 정렬🌟

1단계 : 배열 내 연속된 두 항목을 비교한다. 처음에는 배열의 첫 번째 원소부터 시작하므로 첫 번째 항목과 두 번째 항목을 비교한다.

2단계 : 왼쪽 값이 오른쪽 값보다 크면 두 항목을 교환swap한다. 만약 순서가 올바르다면 아무것도 하지 않고 그 다음 항목으로 넘어간다.

3단계 : "포인터"를 오른쪽으로 한 셀씩 옮긴다.

4단계 : 배열의 끝까지 또는 이미 정렬된 값까지 1단계부터 3단계를 반복한다.** ➡️ 이미 정렬된 값 : 각 패스스루마다 정렬되지 않은 값 중 가장 큰 값 "버블"이 올바른 위치로 가게 된다.**

이것이 배열의 첫 패스스루pass-through가 끝난 것이다. 즉 배열 끝까지(정렬된 값까지) 값을 하나하나 가리키며 배열을 "통과"한 것이다.

5단계 : 이제 두 포인터를 다시 배열의 처음 두 값으로 옮겨서 1단계부터 4단계를 다시 실행함으로써 새로운 패스스루를 실행한다. 교환이 일어나지 않는 패스스루가 생길 때까지 반복한다. ** ➡️ 패스스루에서 교환이 한 번이라도 수행되었다면 다음 패스스루도 수행해야 한다.** 교환할 항목이 없다는 것은 배열이 완전히 정렬됐다는 뜻이다.

🔵 {4, 2, 7, 1, 3} 정렬 해보기

• 첫 번째 패스스루

  • 1단계 : 먼저 4와 2를 비교한다.

  • 2단계 : 왼쪽값 > 오른쪽값 이므로 둘을 교환한다.

  • 3단계 : 다음으로 4와 7를 비교한다. 순서가 올바르므로 교환하지 않고 다음 포인터로 넘어간다.

  • 4단계 : 다음으로 7와 1를 비교한다.

  • 5단계 : 왼쪽값 > 오른쪽값 이므로 둘을 교환한다.

  • 6단계 : 다음으로 7와 3를 비교한다.

  • 7단계 : 왼쪽값 > 오른쪽값 이므로 둘을 교환한다.

첫 번째 패스스루가 끝났으므로 정렬되지 않은 값 중 가장 큰 값 "버블7"이 확실히 올바른 위치에 있게 되었다.

이번 패스스루에서 교환을 한 번 이상 하였으므로 다음 패스스루도 수행해야 한다.

• 두 번째 패스스루

  • 8단계 : 먼저 2와 4를 비교한다. 순서가 올바르므로 교환하지 않고 다음 포인터로 넘어간다.

  • 9단계 : 다음으로 4와 1를 비교한다.

  • 10단계 : 왼쪽값 > 오른쪽값 이므로 둘을 교환한다.

  • 11단계 : 다음으로 4와 3를 비교한다.

  • 12단계 : 왼쪽값 > 오른쪽값 이므로 둘을 교환한다.

첫 번째 패스스루로 인해 7이 올바른 위치에 있으므로 4와 7은 비교할 필요가 없다.

두 번째 패스스루가 끝났으므로 정렬되지 않은 값 중 가장 큰 값 "버블4"가 확실히 올바른 위치에 있게 되었다.

이번 패스스루에서 교환을 한 번 이상 하였으므로 다음 패스스루도 수행해야 한다.

• 세 번째 패스스루

  • 13단계 : 먼저 2와 1를 비교한다.

  • 14단계 : 왼쪽값 > 오른쪽값 이므로 둘을 교환한다.

  • 15단계 : 다음으로 2와 3를 비교한다. 순서가 올바르므로 교환하지 않는다.

이때까지의 패스스루로 인해 4와 7이 올바른 위치에 있으므로 3과 4는 비교할 필요가 없다.

세 번째 패스스루가 끝났으므로 정렬되지 않은 값 중 가장 큰 값 "버블3"이 확실히 올바른 위치에 있게 되었다.

이번 패스스루에서 교환을 한 번 이상 하였으므로 다음 패스스루도 수행해야 한다.

• 네 번째 패스스루

  • 16단계 : 먼저 1와 2를 비교한다. 순서가 올바르므로 교환하지 않는다.

이때까지의 패스스루로 인해 3과 4와 7이 올바른 위치에 있으므로 2와 3은 비교할 필요가 없다.

네 번째 패스스루가 끝났으므로 정렬되지 않은 값 중 가장 큰 값 "버블2"가 확실히 올바른 위치에 있게 되었다.

이번 패스스루에서는 어떤 교환도 하지 않았으므로 패스스루를 더 이상 수행하지 않고 종료한다. 이제 이 배열은 완전히 정렬되었다.

🔵 {9, 1, 5, 2, 1, 6} 정렬 해보기

• 첫 번째 패스스루

  • 1단계 : 먼저 9와 1을 비교한다.

  • 2단계 : 왼쪽값 > 오른쪽값 이므로 둘을 교환한다.

  • 3단계 : 다음으로 9와 5를 비교한다.

  • 4단계 : 왼쪽값 > 오른쪽값 이므로 둘을 교환한다.

  • 5단계 : 다음으로 9와 2를 비교한다.

  • 6단계 : 왼쪽값 > 오른쪽값 이므로 둘을 교환한다.

  • 7단계 : 다음으로 9와 1를 비교한다.

  • 8단계 : 왼쪽값 > 오른쪽값 이므로 둘을 교환한다.

  • 9단계 : 다음으로 9와 6를 비교한다.

  • 10단계 : 왼쪽값 > 오른쪽값 이므로 둘을 교환한다.

첫 번째 패스스루가 끝났으므로 정렬되지 않은 값 중 가장 큰 값 "버블9"가 확실히 올바른 위치에 있게 되었다.

이번 패스스루에서 교환을 한 번 이상 하였으므로 다음 패스스루도 수행해야 한다.

• 두 번째 패스스루

  • 11단계 : 먼저 1과 5를 비교한다. 순서가 올바르므로 교환하지 않고 다음 포인터로 넘어간다.

  • 12단계 : 다음으로 5와 2를 비교한다.

  • 13단계 : 왼쪽값 > 오른쪽값 이므로 둘을 교환한다.

  • 14단계 : 다음으로 5와 1을 비교한다.

  • 15단계 : 왼쪽값 > 오른쪽값 이므로 둘을 교환한다.

  • 16단계 : 다음으로 5와 6을 비교한다. 순서가 올바르므로 교환하지 않는다.

첫 번째 패스스루로 인해 9가 올바른 위치에 있으므로 6과 9는 비교할 필요가 없다.

두 번째 패스스루가 끝났으므로 정렬되지 않은 값 중 가장 큰 값 "버블6"이 확실히 올바른 위치에 있게 되었다.

이번 패스스루에서 교환을 한 번 이상 하였으므로 다음 패스스루도 수행해야 한다.

• 세 번째 패스스루

  • 17단계 : 먼저 1과 2를 비교한다. 순서가 올바르므로 교환하지 않고 다음 포인터로 넘어간다.

  • 18단계 : 다음으로 2와 1을 비교한다.

  • 19단계 : 왼쪽값 > 오른쪽값 이므로 둘을 교환한다.

  • 20단계 : 다음으로 2와 5를 비교한다. 순서가 올바르므로 교환하지 않는다.

이때까지의 패스스루로 인해 6과 9가 올바른 위치에 있으므로 5와 6은 비교할 필요가 없다.

세 번째 패스스루가 끝났으므로 정렬되지 않은 값 중 가장 큰 값 "버블5"가 확실히 올바른 위치에 있게 되었다.

이번 패스스루에서 교환을 한 번 이상 하였으므로 다음 패스스루도 수행해야 한다.

• 네 번째 패스스루

  • 21단계 : 먼저 1과 1을 비교한다. 순서가 올바르므로 교환하지 않는다.

  • 22단계 : 다음으로 1과 2를 비교한다. 순서가 올바르므로 교환하지 않는다.

이때까지의 패스스루로 인해 5와 6과 9가 올바른 위치에 있으므로 2와 5는 비교할 필요가 없다.

네 번째 패스스루가 끝났으므로 정렬되지 않은 값 중 가장 큰 값 "버블2"가 확실히 올바른 위치에 있게 되었다.

이번 패스스루에서는 어떤 교환도 하지 않았으므로 패스스루를 더 이상 수행하지 않고 종료한다. 이제 이 배열은 완전히 정렬되었다.

❕코드 구현 ❗

• 함수는 정렬되지 않은 배열을 전달하여 사용한다.

• 그러면 함수는 정렬된 배열을 반환한다.

• unsortedUntilIndex 변수 : 아직 정렬되지 않은 배열의 가장 오른쪽 인덱스를 기록한다. ( 알고리즘이 처음 시작할 때는 전체 배열의 마지막 인덱스로 변수를 초기화한다. )

• sorted 변수 : 배열의 정렬 여부를 기록한다. (알고리즘이 처음 시작할 때는 정렬되지 않았으므로 false로 초기화한다.)

• while루프
  • 배열이 정렬될 때까지 실행한다. ↳ while (!sorted) {}
  • 루프 한 번 실행이 배열의 한 패스스루에 해당한다.
    ⬇️ 루프안에서

• 각 패스스루 안에서는 교환이 일어나기 전까지 배열이 정렬되어 있다고 가정하고 교환이 일어났을 때 다시 false로 바꾸는 방식을 취한다. ↳ sorted = true;

• for루프 : 배열 내 모든 값 쌍을 가리킨다. i를 첫 포인터로 사용해 배열의 첫 인덱스부터 아직 정렬되지 않은 인덱스까지 수행한다. ↳ for(int pointer = 0; pointer < unsortedUntilIndex; pointer++) {}
  • for루프 내에서는 모든 인접 값 쌍을 비교하고 왼쪽값 > 오른쪽값이면 교환한다. ➡️ 교환이 일어났으므로 sorted = false

• 각 패스스루가 끝나면 버블이 이제 올바른 위치에 있게 된다. 즉 unsortedUntilIndex변수가 기존에 가리키고 있던 인덱스가 정렬된 상태이니 unsortedUntilIndex변수의 값을 1 감소 시킨다.

• sorted변수가 true인 채로 패스스루가 끝나면 while루프가 종료된다. 이 때 정렬된 배열을 반환한다.

public static ArrayList<Integer> bubbleSort(ArrayList<Integer> list) {
    int unsortedUntilIndex = list.size() - 1;
    boolean sorted = false;

    while (!sorted) {
        sorted = true;

        for (int pointer = 0; pointer < unsortedUntilIndex; pointer++) {
            int thisValue = list.get(pointer);
            int nextValue = list.get(pointer+1);
            if (thisValue > nextValue) {
                list.set(pointer, nextValue);
                list.set(pointer+1, thisValue);
                sorted = false;
            }
        }

        unsortedUntilIndex--;
    }

    return list;
}

• main 출력 테스트 통과!

public static void main(String[] args) {
    ArrayList<Integer> list1 = new ArrayList<>(Arrays.asList(4, 2, 7, 1, 3));
    ArrayList<Integer> list2 = new ArrayList<>(Arrays.asList(9, 1, 5, 2, 1, 6));

    bubbleSort(list1);
    for (int i : list1)
        System.out.print(i +" ");

    System.out.println("\n --------");

    bubbleSort(list2);
    for (int i : list2)
        System.out.print(i +" ");
}

🔶 효율성 : O(N²)

버블 정렬 알고리즘은 비교comparison과 교환swap의 두 가지 단계를 포함한다.

원소가 5개인 정렬되지 않은 배열을 생각해보자.

• 비교 comparison

  • 첫 번째 패스스루에서는 비교를 4번 일어난다.

  • 두 번째 패스스루에서는 비교를 3번 일어난다.

  • 세 번째 패스스루에서는 비교를 2번 일어난다.

  • 네 번째 패스스루에서는 비교를 1번 일어난다.

  • 총 10번의 비교다.

  ➡️ 배열의 원소가 N개일 때, (N-1) + (N-2) + (N-3) + … + 1 번의 "비교"를 수행한다.

• 교환 swap

  • 배열이 역순으로 정렬된 최악의 시나리오라면 비교할 때마다 교환을 해야한다.

  • 첫 번째 패스스루에서는 비교를 4번 했으니 교환도 4번 일어난다.

  • 두 번째 패스스루에서는 비교를 3번 했으니 교환도 3번 일어난다.

  • 세 번째 패스스루에서는 비교를 2번 했으니 교환도 2번 일어난다.

  • 네 번째 패스스루에서는 비교를 1번 했으니 교환도 1번 일어난다.

  • 총 10번의 교환이다.

  ➡️ 배열의 원소가 N개일 때, (N-1) + (N-2) + (N-3) + … + 1 번의 "교환"을 수행한다.

원소 5개가 역순으로 된 배열에서는 4+3+2+1 = 10번의 비교와 4+3+2+1 = 10번의 교환이 일어나므로 총 20단계다.

원소 10개가 역순으로 된 배열에서는 9+8+7+6+5+4+3+2+1 = 45번의 비교와 45번의 교환이 일어나므로 총 90단계다.

원소 20개가 역순으로 된 배열에서는 19 + 18 + 17 + 16 + 15 + 14 + 13 + 12 + 11 + 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 190번의 비교와 교환이 일어나므로 총 380단계다.

원소 수가 증가할수록 단계 수가 기하급수적으로 늘어난다.

N이 증가할 때마다 단계 수가 대략 N²만큼 늘어남을 알 수 있다.

배열의 원소가 N개일 때 버블 정렬에는 N²단계가 필요하다. ➡️ O(N²)

🟪 O(N²)

🔶 버블정렬과 중첩루프

버블정렬과 중첩루프가 대표적인 O(N²)알고리즘의 예시이다.

버블정렬을 살펴보았고 중첩루프의 예시를 들겠다.

🔵 중첩루프 예시

주어진 배열의 모든 숫자 쌍의 최대곱the greatest product을 찾는다.

public static int greatestProduct(int[] array) {
    int greatestProduct = array[0] * array[1];

    for (int i = 0; i < array.length; i++) {
        for (int j = 0; j < array.length; j++) {
            int nowProduct = array[i] * array [j];
            if (i != j && ( nowProduct > greatestProduct))
                greatestProduct = nowProduct;
        }
    }

    return greatestProduct;
}

🔶 이차시간

O(N²)을 이차시간quadratic time 이라고도 부른다.

🔶 O(N²) vs O(N) 그래프

단순한 대각선을 그리는 O(N)과 대비되게 데이터가 늘어날수록 O(N²)의 단계 수가 매우 급격히 증가하고 있다. 그래서 O(N²)은 비효율적인 알고리즘으로 분류된다.

🔶 이차 문제

느린 O(N²) 알고리즘을 빠른 O(N) 알고리즘으로 대체하고자 하는 것을 이차문제라고 한다.

🔵 중첩루프 문제와 선형 해결법

루프 내에 다른 루프를 중첩하는 알고리즘은 O(N²)이다. (항상은 아니다.)

O(N²)은 상대적으로 느린 알고리즘이다.

느린 알고리즘을 마주할 때는 시간을 들여 더 빠른 속도의 알고리즘 대안은 없을 지 고민해 보는 것이 좋다.

대안 중 하나로 선형 해결법을 고려해볼 수 있다.

선형 해결법은 중첩 루프를 쓰지 않는 것을 의미한다.

🟪 이차문제 연습

🔶 중복 값 확인하는 함수

( 사용자가 제품에 대해 1부터 10사이로 매긴 평점을 분석하는 애플리케이션에서 평점 ) 배열에 중복 숫자가 들어 있는지 확인하는 함수

예를 들어 배열 { 1, 5, 3, 9, 1, 4 } 에는 숫자 1이 중복되므로 true를 반환한다.

🔵 중첩루프로 구현한다. ➡️ O(N²)

: 함수는 반복해서 i와 j를 비교한다. 최악의 시나리오는 배열에 중복 값이 없는 경우다. 배열에 N개가 있을 때 함수는 N²번의 비교를 수행한다. ➡️ O(N²)

public static boolean hasDuplicateValue(int[] array) {
    for (int i = 0; i < array.length; i++) {
        for (int j = 0; j <array.length; j++) {
            if (i != j && array[i] == array[j])
                return true;
        }
    }
    return false;
}

🔵 선형해결법으로 구현한다. ➡️ O(N)

: 단 하나의 루프에서 단지 배열에 있는 원소 수만큼 순회하기 때문에 배열에 N개의 원소가 있을 때 N단계가 걸린다. ➡️ O(N)

• JS 코드
  • existingNumbers라는 빈 배열을 생성한다.
  • for루프를 사용해 array의 각 숫자를 확인한다.
  • 숫자가 나올 때마다 existingNumbers배열에 그 숫자 해당하는 인덱스에 임의의 값 1을 넣는다.
    • 예시) {3, 5, 8}배열에서 3이 나오면 existingNumbers배열의 인덱스3에 1을 대입한다.
    • 그러면 existingNumbers배열은 이렇게 된다. : { null , null , null , 1 }
  • 본질적으로 existingNumbers의 인덱스를 사용해 지금까지 array에서 어떤 숫자들이 나왔는지 알 수 있다.
  • 해당 인덱스에 1을 저장하기 전에 이 인덱스의 값이 이미 1인지 확인한다.
  • 해당 인덱스의 값이 1이면, 중복값이라는 뜻이므로 true를 반환한다.
  • 루프 끝까지 갔다면 중복 값이 없다는 뜻이므로 false를 반환한다.

function hasDuplicateValue(array) {
  let existingNumbers = [];

  for(let i = 0; i < array.length; i++) {
    if(existingNumbers[array[i]] === 1)
      return true;
    else
      existingNumbers[array[i]] = 1;
  }

  return false;
}

• Java 코드
  • existingNumbers라는 ArrayList을 생성한다.
  • ❗ArrayList는 리스트의 끝으로만 추가할 수 있기 때문에, array의 값을 인덱스로 하여 임의의 값 1을 추가 할 수 없다.
    • {3,5,8}에서 ArrayList.add(3, 1)이렇게 하면 (인덱스는 {3,5,8}의 3, 값은 임의의 값 1) ** IndexOutOfBoundsException: Index: 3, Size: 0라는 에러가 뜬다.**
    • 그래서 그냥 array의 값을 넣는 식으로 해야한다.
    • {3,5,8}에서 ArrayList.add(3)이런 식으로.
  • for루프를 사용해 array의 각 숫자를 확인한다.
  • 숫자가 나올 때마다 existingNumbers배열에 그 숫자를 추가add()한다.
    • 예시) {3, 5, 8}배열에서 3이 나오면 existingNumbers배열에 3을 대입한다. : existingNumbers.add(3)
    • 그러면 existingNumbers배열은 이렇게 된다. : { 3 }
  • 해당 값을 ArrayList에 저장하기 전에 이미 있는 값인지 확인한다. 있으면 true를 반환한다. : existingNumbers.contains(3)
  • 루프 끝까지 갔다면 중복 값이 없다는 뜻이므로 false를 반환한다.

public static boolean hasDuplicateValue2(int[] array) {
    ArrayList<Integer> existingNumbers = new ArrayList<>();

    for (int value : array) {
        if (existingNumbers.contains(value))
            return true;
        else
            existingNumbers.add(value);
    }

    return false;
}

🔶 최댓값 찾는 함수

배열에서 가장 큰 수를 찾는 함수이다.

🔵 중첩루프로 구현한다. ➡️ O(N²)

• 우선 첫번째 for루프로 나오는 숫자가 제일 크다고 가정한다 : isNumber1GreatestNumber = true
• 첫번째 for루프로 나오는 숫자가 두번째 for루프로 나오는 숫자보다 작으면 제일 큰 값이 아니게 된다. : isNumber1GreatestNumber = false
• 첫번째 for루프로 나오는 숫자가 두번째 for루프로 나오는 숫자들 모두 확인했는데도 제일 크면, 전체 배열에서 가장 큰 수 이므로 return한다.
• java에서는 if문에서 return하면 else문 또는 메소드 자체에서 return값이 있어야 하므로 int failResult = 0;을 선언하여 마지막에 return failResult;한다.

public static int greatestNumber(int[] array) {
    int failResult = 0;
    for (int number1 : array) {
        boolean isNumber1GreatestNumber = true;
        for (int number2 : array) {
            if (number1 < number2)
                isNumber1GreatestNumber = false;
        }
        if (isNumber1GreatestNumber)
            return number1;
    }
    return failResult;
}

🔵 선형해결법으로 구현한다. ➡️ O(N)

• greatestNumber을 임의로 정해서 for루프로 나오는 숫자들과 비교하여 결과에 맞춰 greatestNumber값을 계속 바꾸다가 마지막에 return한다.

public static int greatestNumber2(int[] array) {
    int greatestNumber = array[0];

    for (int number : array) {
        if (number > greatestNumber)
            greatestNumber = number;
    }

    return greatestNumber;
}

🟦 출처

🔷 그림 1

티스토리 사이트의 베카의에러뿌시기 블로그의 '빅오표기법(Big O notation)' 게시글 보러가기

🔷 글의 내용

이 글 내용은 '제인 웬그로우'의 '누구나 자료구조와 알고리즘 개정 2판' 책을 100% 참고하여 작성하였습니다. 설명에 전문적인 용어보다는 일상적인 용어를 사용하고 그림으로 원리를 설명해주어 왕초보인 저가 이해하기에 아주 좋았습니다. 가격이 많이 나가는 편이지만 꼭 배워야 하는 내용이 모두 들어있고 그것을 제가 이해할 수 있는 수준으로 쓰여있어 전혀 아깝지 않은 소비였습니다.

🖱 클릭! | '제인 웬그로우'의 '누구나 자료구조와 알고리즘' 책 구경하러 가보기

'알고리즘 수행에 필요한 단계 수'가 알고리즘의 효율성을 결정하는 주된 요인이다.

그러나 단순히 알고리즘을 "22단계의 알고리즘", "400단계의 알고리즘" 이라고 표시할 수는 없다. 이 단계 수라는 것을 하나의 수로 확정지을 수 없기 때문이다.

예를 들어 선형 검색에는 배열의 원소 개수 만큼 단계 수가 필요하다. 그래서 원소가 4개일 땐 4단계가, 100개일 땐 100단계가 필요하므로 그때 그때 마다 달라지는 것이다.

이러한 *선형 검색의 효율성을 '배열에 N개의 원소가 있을 때 N단계가 필요하다'라고 표현하는 것이 몇 단계로 정량화 하는 것보다 훨씬 효과적이다. *

컴퓨터 과학자는 시간 복잡도를 쉽게 소통할 목적으로 자료 구조와 알고리즘의 효율성을 간결하고 일관된 언어로 설명하기 위해 수학적 개념을 차용했다.

이러한 개념을 형식화한 표현을 빅 오 표기법이라고 부른다.

빅 오 표기법을 사용해 주어진 알고리즘의 효율성을 쉽게 분류할 수 있다.

빅 오 표기법을 알면 일관되고 간결한 방법으로 어떤 알고리즘이든 분석할 수 있는 도구가 생긴 것이다.

🟪 🌟빅 오의 본질🌟

🔶 데이터 원소 N개에 대한 알고리즘의 단계 수를 의미한다.

빅 오 : 데이터 원소가 N개일 때 알고리즘에 몇 단계가 필요할까? *↳ 빅 오 표기법의 핵심질문이자 정의이다 ! *

핵심 질문에 대한 답은 빅 오 표현의 괄호 안에 들어있다.O(N)은 알고리즘에 N 단계가 필요하다는 핵심 질문에 대한 답을 나타낸다.

❗빅 오는 데이터 원소가 N개일 대 알고리즘에 몇 단계가 필요한가에 대한 답이다. 데이터 원소 N개에 대한 알고리즘의 단계 수를 나타낸다.

🔶 데이터가 늘어날 때 단계 수가 어떻게 증가하는가를 의미한다.

🔵 O(3) == O(100) == O(1)

데이터가 몇 개든 항상 3단계가 걸리는 알고리즘을 가정하자. 즉 원소가 N개일 때 알고리즘에 항상 3단계가 필요하다. 이를 빅 오로 어떻게 표현할까?

O(3)일까? 아니다. O(1)이다.

이유는 빅오가 알고리즘에 필요한 단계 수를 알려주는 것 말고도 한 가지 더 역할을 한다는 것에 있다.

빅 오는 단순히 알고리즘에 필요한 단계 수 뿐만 아니라, ❗데이터가 늘어날 때 알고리즘의 단계 수가 어떻게 증가하는지, 성능이 어떻게 바뀌는지도 설명한다.

이러한 관점에서 보면 알고리즘이 O(1)이든 O(3)이든 별로 중요하지 않다.

O(1)과 O(3) 두 알고리즘 모두 데이터 증가에 영향을 받지 않는, 즉 단계 수가 변하지 않는 유형이므로 본질적으로 같은 알고리즘 유형이다. N이 얼마든 항상 상수 단계만 필요하다. 그래서 O(1) 알고리즘을 상수시간constant time을 갖는 알고리즘이라고도 표현한다.

둘 다 데이터에 관계없이 단계 수가 일정한 알고리즘이므로 둘을 구분할 필요가 없다.

🔵 O(1)과 O(N)에서 데이터 변화가 미치는 영향

O(1)이 데이터 증가 또는 감소에 영향을 받지 않는 반면 O(N) 알고리즘은 데이터 증가가 성능에 영향을 미친다. 데이터가 늘어날 때 정확히 그 데이터에 비례해 단계 수가 증가하는 알고리즘 유형이다. 알고리즘의 효율성과 데이터가 비례 관계이다. 데이터가 증가할 때 단계 수가 정확히 어떻게 증가하는지 설명한다.

🔵 O(1) & O(N) 그래프

O(N)은 완벽한 대각선을 그린다. 데이터가 하나씩 추가될 때마다 알고리즘이 한 단계씩 더 걸리기 때문이다. 따라서 데이터가 많아질수록 알고리즘에 필요한 단계 수도 늘어난다.

O(1)은 완벽한 수평선을 그린다. 데이터의 증가나 감소에 영향 받지 않고 단계 수가 일정하다.

🔵 O(1)알고리즘이 항상 O(N)보다 빠를까 ?

데이터 크기에 상관없이 항상 100단계가 걸리는 상수 시간 알고리즘이 있다면? 이 알고리즘이 O(N) 알고리즘보다 성능이 우수한가?

원소가 100개 이하인 데이터 세트에서는 100단계가 걸리는 O(1) 알고리즘보다 O(N) 알고리즘이 단계 수가 더 적다.

두 선이 교차하는 원소가 정확히 100개인 지점에서는 두 알고리즘의 단계 수가 동일하게 100단계이다.

100보다 큰 모든 배열에서는 O(N) 알고리즘이 100단계 O(1) 알고리즘보다 항상 더 많은 단계가 걸린다. 이것이 핵심이다.

변화가 생기는 일정량의 데이터가 있을 것이고 O(N)은 그 순간부터 무한대까지 더 많은 단계가 걸리므로 O(1) 알고리즘에 실제로 몇 단계가 걸리든 O(N)이 전반적으로 O(1)보다 덜 효율적이라 볼 수 있다.

🔶 최악의 시나리오를 의미한다.

선형 검색이 항상 O(N)은 아니다. 검색값이 배열의 맨 처음에 있는 최선의 시나리오에서는 O(1)이고 검색값이 배열의 맨 끝에 있는 최악의 시나리오에서는 O(N)이다.

빅 오 표기법은 일반적으로 최악의 시나리오를 의미한다.

"비관적인" 접근이 유용한 도구일 수 있기 때문이다.

최악의 시나리오에서 알고리즘이 얼마나 비효율적인지 정확히 알면 최악을 대비함과 동시에 알고리즘의 선택에 중요한 영향을 미칠 수 있기 때문이다.

🟪 O(N)

데이터 원소가 N개일 때 N단계가 걸리는 알고리즘이다. 데이터가 늘어날 때 정확히 그 데이터에 비례해 단계 수가 증가하는 알고리즘이다.

선형검색 알고리즘을 빅 오로 표현해보자.

< 빅 오 표기법으로 시간 복잡도를 표현하는 사고 과정 >

• 핵심 질문 : 배열에 원소가 N개일 때 선형 검색에 몇 단계가 필요할까?

• 정답 : 배열에 N개의 원소가 있을 때 선형 검색에 N단계가 필요하다.

• 표현 : O(N) - "빅 오 N", "차수 N", "오 N"이라고 부른다.

🟪 O(1) : 상수시간

데이터 원소가 N개와 상관없이 항상 일정한 상수 갯수의 단계 수만 걸리는 알고리즘이다. 데이터 증가에 영향을 받지 않는 알고리즘이다.

배열에서 읽기의 효율성을 빅 오로 표현해보자.

< 빅 오 표기법으로 시간 복잡도를 표현하는 사고 과정 >

• 핵심 질문 : 데이터 원소가 N개일 때 배열에서 읽기에 몇 단계가 필요할까?

• 정답 : 배열 읽기에 필요한 단계 수는 배열의 크기와 상관없이 딱 하나다.

• 표현 : O(1) - "오 1"

데이터 원소가 "N"개 일때 알고리즘에 필요한 단계 수를 질문했다. 이 질문은 N에 대한 물음이었으나 답은 N과 무관하다. 배열에 원소가 몇 개든 배열에서 읽기는 항상 한 단계면 된다.

N에 구애받지 않고 항상 1단계만 걸리므로 O(1)을 가장 빠른 알고리즘 유형으로 분류한다. 데이터가 늘어나도 알고리즘의 단계 수는 증가하지 않는다.

N이 얼마든 항상 상수 단계만 필요하다. 그래서 O(1) 알고리즘을 상수시간constant time을 갖는 알고리즘이라고도 표현한다.

🟪 로그 log 뜻

로그는 로가리즘logarithm의 줄임말이다.

❗로그log

• 지수exponent와 역inverse의 관계다.
• 2를 몇 번 곱해야 N이 나올까? = log₂N
• 1이 될 때까지 N을 2로 몇 번 곱해야 할까? = log₂N

🔵 지수exponent와 역inverse의 관계다.

log₂8은 2³의 역converse 관계다.

log₂64은 2⁶의 역이다.

🔵 2를 몇 번 곱해야 N이 나올까?

2를 세 번 곱해야 8이 나오므로 log₂8 = 3이다.

2를 여섯 번 곱해야 8이 나오므로 log₂64 = 6이다.

🔵 1이 될 때까지 N을 2로 몇 번 곱해야 할까?

8 / 2 / 2 / 2 = 1 8이 1이 될 때까지 2를 세 번 나눠야 하므로 log₂8 = 3이다.

64 / 2 / 2 / 2 / 2 / 2 / 2 = 1 64가 1이 될 때까지 2를 여섯 번 나눠야 하므로 log₂64 = 6이다.

🟪 O(logN) : 로그시간

🔶 O(logN) == O(log₂N)

컴퓨터 과학에서 O(logN)은 O(log₂N)을 줄여 부르는 말이다.

• 핵심 질문 : 데이터 원소가 N개 일 때 알고리즘에 몇 단계가 필요할까?
• 정답 : O(logN)은 데이터 원소가 N개 있을 때 알고리즘에 log₂단계가 걸린다.

원소가 8개면 log₂8 = 3이므로 이 알고리즘은 3단계가 걸린다.

이진 검색이 정확히 O(logN) 알고리즘 방식으로 동작한다.

이진 검색을 빅 오 표기법의 관점에서 어떻게 설명할까?

• 배열의 크기가 3일 때 이진 검색은 2단계
• 배열의 크기가 7일 때 이진 검색은 3단계
• 배열의 크기가 15일 때 이진 검색은 4단계
• 배열의 크기가 100일때 이진 검색은 7단계
• 배열의 크기가 10,000일때 이진 검색은 13단계
• 배열의 크기가 1,000,000일때 이진 검색은 20단계

데이터가 커질수록 단계 수가 늘어나므로 이진 검색은 O(1)이라 표현할 수 없다. 검색하고 있는 배열의 원소 수보다 단계 수가 훨씬 적으므로 O(N)이라 표현할 수도 없다.

이진 검색은 O(1)과 O(N)사이 어디쯤엔가 있다. 이것을 빅 오로 O(logN)으로 나타낸다. 그리고 오 로그 엔 이라고 부른다.

🔶 데이터가 두 배로 증가할 때마다 한 단계씩 늘어나는 알고리즘

❗O(logN) : 오 로그 N

• 로그시간log time의 시간 복잡도
• 데이터 원소가 N개 있을 때 알고리즘에 log₂단계가 걸린다.
• 데이터가 두 배로 증가할 때마다 한 단계씩 늘어나는 알고리즘

이러한 유형의 알고리즘을 로그시간log time의 시간 복잡도라고 말한다. 이 말의 뜻은 빅오의 방법으로 O(logN)을 데이터가 두 배로 증가할 때마다 한 단계씩 늘어나는 알고리즘이라고 설명하는 것이다.

🟪 O(1) & O(N) & O(logN) 그래프

O(1) > O(logN) > O(N) 순으로 가장 효율적이다.

O(logN)은 아주 조금씩 증가하는 곡선을 그리고 있는데 O(1)보다는 덜 효율적이지만 O(N)보다는 훨씬 효율적이다.

🟪 연습문제

다음 알고리즘의 효율성을 빅 오 표기법으로 나타내라.

🔶 리스트 내 모든 항목을 출력함

public static void printThings() {
    String[] things = {"apples", "chairs", "files", "notes"};

    for (String thing : things)
        System.out.printf("Here's a thing : %s \n", thing);
}

이 알고리즘의 for루프에서 배열의 원소가 4개이기 때문에 4단계가 걸린다. 만약 배열의 원소가 10개이면 10단계가 걸릴 것이다.

for루프에 대입되는 배열의 원소 갯수만큼 단계가 걸리므로 이 알고리즘의 효율성은 O(N)이다.

🔶 주어진 수가 소수인지 알아봄

소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수다.

public static boolean isPrime(int number) {
    if (number == 1) return false;
    for (int i = 2; i < number; i++) {
        if (number % i == 0)
            return false;
    }
    return true;
}

이 코드는 number를 인수로 받아 2부터 number-1까지의 모든 수로 number를 나눠서 나머지가 있는지 확인한다.

나머지가 없으면 이 수는 소수가 아니므로 바로 false를 반환한다.

모든 수로 나눴는데도 항상 나머지가 있으면 이 수는 소수이므로 true를 반환한다.

number가 1이면 당연히 소수가 아니므로 false를 반환한다.

핵심 질문 : number에 N을 전달할 때 알고리즘에 몇 단계가 필요한가? ↳ ( number가 함수 루프 실행 횟수를 좌우하기 때문에 N은 number이다. )

7을 number에 전달하면 for루프는 일곱단계를 실행한다. (실제로는 2~6까지므로 다섯단계이다.)

101이면 루프는 101단계를 실행한다. (실제로는 2~100까지므로 99단계이다.)

함수로 전달된 수에 비례해 단계 수가 증가하므로 O(N)알고리즘이다.

🔶 주어진 해가 윤년인지 알아봄

public static boolean isLeapYear(int year) {
    return (year % 100 == 0) ? (year % 400 == 0) : (year % 4 == 0);
}

N은 number이다. 함수로 전달된 수에 상관없이 단계 수가 일정하므로 O(1)알고리즘이다.

🔶 주어진 배열의 모든 수를 합함

public static int arraySum(int[] array) {
    int sum = 0;

    for (int num : array)
        sum += num;

    return sum;
}

N은 배열의 원소 갯수다. 배열의 원소 갯수만큼 for루프가 실행되므로 O(N)알고리즘이다.

🔶 몇 번째 칸에 쌀을 놓아야 하는지 계산해줌

체스판 한 칸에 쌀 한톨을 놓는다. 두 번째 칸에는 이전 칸에 놓았던 쌀 양보다 두 배 더 많은 쌀 두 톨을 놓는다. 세 번째 칸에는 쌀 네 톨을 놓는다. (두 번째 칸 * 2) 네 번째 칸에 쌀 여덟 톨을 놓는다. (세 번째 칸 * 2) 다섯 번째 칸에 쌀 열여섯 톨을 놓는다. (네 번째 칸 * 2)

16을 함수에 전달하면 5를 반환한다.

public static int getChessboardSpace(int grains) {
    int chessboardSpace = 1;
    int placedGrains = 1;

    while (placedGrains < grains) {
        chessboardSpace++;
        placedGrains *= 2;
    }

    return chessboardSpace;
}

N은 함수에 전달된 grains이다.

grains = 256 이면 for루프는 9번 실행된다. grains = 512 이면 for루프는 10번 실행된다. grains = 1024 이면 for루프는 11번 실행된다.

grains가 두배로 늘어날 때 루프는 한 단계만 더 늘어나므로 O(logN)알고리즘이다.

🔶 문자열 배열을 받아 "a"로 시작하는 문자열만 포함시킨 새 배열을 반환함

public static String[] getAStringsArr(String[] array) {
    ArrayList<String> aStringsArr = new ArrayList<String>();

    for (int i = 0; i <array.length; i++) {
        String firstChar = array[i].split("")[0];
        if ("a".equals(firstChar))
            aStringsArr.add(array[i]);
    }

    return aStringsArr.toArray(new String[aStringsArr.size()]);
}

N은 함수에 전달된 배열의 원소 갯수이다. 전달된 배열의 원소 갯수만큼 for루프가 실행되므로 O(N)알고리즘이다.

🔶 정렬된 배열의 중앙값을 계산함.

public static int median(int[] array) {
    int middle = array.length / 2;

    if (array.length % 2 == 0)
        return (array[middle-1] + array[middle]) / 2;
    else
        return array[middle];
}

N은 함수에 전달된 배열의 길이이다. 전달된 배열의 길이가 얼마든 상관없이 한 단계면 중앙값이 계산되어 반환된다. N이 얼마든 상관없이 정해진 단계수만 걸리므로 O(1)알고리즘이다.

🟦 출처

🔷 그림 1

벨로그 사이트의 welloff_jj님의 hyeojung.log블로그의 '복잡도(Complexity): 시간 복잡도와 공간 복잡도, 그리고 빅오(Big-O) 표기법' 게시물 보러가기

🔷 그림 2

Towards Data Science사이트의 Semi Koen의 The Big O Notation 게시물 보러가기

🔷 글의 내용

이 글 내용은 '제인 웬그로우'의 '누구나 자료구조와 알고리즘 개정 2판' 책을 100% 참고하여 작성하였습니다. 설명에 전문적인 용어보다는 일상적인 용어를 사용하고 그림으로 원리를 설명해주어 왕초보인 저가 이해하기에 아주 좋았습니다. 가격이 많이 나가는 편이지만 꼭 배워야 하는 내용이 모두 들어있고 그것을 제가 이해할 수 있는 수준으로 쓰여있어 전혀 아깝지 않은 소비였습니다.

🖱 클릭! | '제인 웬그로우'의 '누구나 자료구조와 알고리즘' 책 구경하러 가보기

ordered array

정렬된 배열과 일반 배열의 차이점은 "값이 항상 순서대로 있어야 한다" 는 점이다. ❗값을 추가할 때마다 적절한 위치에 삽입하여 값을 정렬된 상태로 유지한다.

🔶 삽입 : [ ⓝ+②단계 ]

아래의 정렬된 배열에 75를 삽입해보자.

일반 배열이라면 배열의 맨 끝에 75를 삽입하여 한 단계만 삽입이 처리 된다.

하지만 정렬된 배열에서는 값을 오름차순으로 유지해야 하기 때문에 적절한 위치를 찾고 다른 값들을 옮겨 그 위치를 빈 공간으로 만드는 과정이 추가로 필요하다. 그 다음에 삽입을 처리할 수 있는 것이다.

• 1단계 : [ 비교 ] 인덱스0의 값을 확인하여 삽입값 75와 비교한다. 75는 3보다 크므로 오른쪽에 들어가야 한다. 하지만 정확한 삽입 위치를 알 수 없으므로 다음 셀을 확인해야 한다.

• 2단계 : 인덱스1의 값을 확인한다. 75가 더 크므로 다음 셀을 확인한다.

• 3단계 : 인덱스2의 값을 확인한다. 75보다 더 큰 값이 나왔다! 앞 셀은 75보다 작고 지금 셀은 75보다 큰 첫 값이다. 그러므로 여기 인덱스2에 75를 삽입하면 정렬된 배열을 유지할 수 있다 는 것을 알 수 있다.

• 4단계 : [ 옮기기 ] 인덱스2를 빈 공간으로 만들기 위해 마지막 값인 인덱스3의 값을 *오른쪽으로 옮긴다. *

• 5단계 : 인덱스3을 오른쪽으로 옮긴다.

• 6단계 : [ 삽입 ] 인덱스2가 적절한 위치이고 빈공간이 되었다. 여기에 75를 삽입한다.

여기서 원소가 4개 였고 비교에 3단계 옮기기에 2단계 삽입에 1단계, 총 6단계가 걸렸다.

그래서 ❗N개의 원소를 가진 정렬된 배열에서 삽입의 연산은 N+2단계가 걸린다고 볼 수 있다.

삽입의 위치가 어디든 단계 수는 비슷하다. 배열 앞 부분일수록 비교가 줄어들지만 이동이 늘어나고, 뒷 부분일수록 비교가 늘어나도 이동이 줄어들기 때문이다.

배열의 맨 끝에 놓이면 이동이 필요없으므로 제일 빠른 경우이다. 이 때는 비교에 N단계와 삽입에 1단계, 총 N+1단계가 걸린다.

가장 느릴 때 N+2단계, 가장 빠를 때 1단계가 걸리는 일반 배열의 삽입에 비해 정렬된 배열의 삽입이 느림을 알 수 있다.

🔶 검색_선형검색 : [ ⓝ단계 ]

"선형검색"으로 정렬된 배열을 검색연산 해보자. 아래의 정렬된 배열에서 존재하지 않는 값 22를 검색해본다면?

정렬된 배열에서는 22*보다 큰 값이 나오면 바로 검색을 중단하고 해당 값이 없다고 판단할 수 있다. *

선형검색은 정렬된 배열에서 보통은 일반 배열보다 단계 수가 더 적게 걸린다. 하지만 만약 찾으려는 값이 배열에서 제일 큰 값이라면 정렬된 배열과 일반 배열 모두 모든 셀을 검색해야 한다.

그러므로 선형검색으로 정렬된 배열을 검색 연산 한다면 일반배열과 똑같이 ❗N단계가 걸린다.

❕코드 구현 ❗

• 메서드는 두 인수를 받는다.

• orderedArray : 검색할 정렬된 배열
• searchValue : 찾으려는 값

  • 배열의 모든 원소를 순회한다.

  • 원하는 값을 찾으면 그 인덱스를 반환한다.

  • 찾고 있던 값보다 큰 원소에 도달하면 루프를 종료한다.

  • 배열에서 값을 찾지 못하면 null을 반환한다.

public static Integer linearSearch(int[] orderedArray, int searchValue) {
    for (int index = 0; index < orderedArray.length; index++) {
        if (orderedArray[index] == searchValue)
            return index;

        else if (orderedArray[index] > searchValue)
            break;
    }

    return null;
}

• JUNIT TEST 통과!

import org.junit.Test;
import static org.junit.Assert.*;

@Test
public void linearSearchTest() {
    int[] array1 = {1, 3, 9, 10};

    Integer expectedNull = null;
    Integer expected0 = 0;
    Integer expected1 = 1;
    Integer expected2 = 2;
    Integer expected3 = 3;

    // 예상값 , 실제값
    assertEquals(expectedNull,linearSearch(array1,11));
    assertEquals(expectedNull,linearSearch(array1,2));
    assertEquals(expectedNull,linearSearch(array1,8));

    assertEquals(expected0,linearSearch(array1,1));
    assertEquals(expected1,linearSearch(array1,3));
    assertEquals(expected2,linearSearch(array1,9));
    assertEquals(expected3,linearSearch(array1,10));
}

🔶 검색_🌟이진검색🌟 : [ ⓛⓞⓖⓃ단계 ]

원소가 9개인 정렬된 배열이 있다. 이 배열에 어떤 값들이 있는지 전혀 모르는 상태에서 값 7을 찾아보자.

• 1단계 : 가운데 셀부터 검색을 시작한다. 배열의 길이를 2로 나누어 가운데 셀의 인덱스를 계산한다.

가운데 셀의 값은 9이므로 7은 왼쪽 어딘가에 있다. 9와 9보다 오른쪽의 있는 셀 모두가 제거 되었으므로 이로써 배열의 절반이 제거됐다.

• 2단계 : 9의 왼쪽 셀들 중 가운데 값을 확인한다. 가운데 값이 두 개이므로 임의로 왼쪽 값을 선택한다. 셀의 값이 4이므로 7은 오른쪽 어딘가에 있다. 4와 4의 왼쪽 셀 모두가 제거 되었다.

• 3단계 : 7일 수 있는 두 개의 셀 중 임의로 왼쪽 셀을 선택한다. 값이 6이므로 7은 바로 오른쪽에 있다. 만약 거기도 없다면 이 배열에는 7은 없는 것이다.

• 4단계 : 4단계만에 검색이 완료됐다.

이진 검색은 정렬된 배열에만 쓸 수 있다. 이진 검색을 쓸 수 있다는 것이 정렬된 배열의 장점 중 하나이다.

검색 값이 배열의 원소 중 가장 큰 값이면 이진 검색에 최대 단계수가 걸린다. 배열의 크기가 3일 때 이진 검색에 필요한 최대 단계 수는 2다. 배열의 크기를 두 배로 늘리면 크기가 7이 되고, 이진 검색에 필요한 최대 단계 수는 3이 된다. 배열의 크기를 두 배로 늘리면 크기가 15가 되고 이진 검색에 필요한 최대 단계 수는 4가 된다.

❗이진 검색을 쓰면 추측할 때마다 검색해야 할 셀 중 절반을 제거할 수 있다. 그러므로 데이터를 두 배로 늘릴 때마다 이진 검색 알고리즘에서는 최대 한 단계만 더 추가된다. 이것을 logN단계가 걸린다고 한다.

❕코드 구현 ❗

• 먼저 찾으려는 값이 있을 수 있는 상한선과 하한선을 정한다.

• 최초의 상한선은 배열의 첫 번째 값, 하한선은 마지막 값이다.

• 상한선과 하한선 사이의 가운데 값을 계속해서 확인하는 루프를 시작한다.

  • *루프를 상한선과 하한선이 같아질 때까지만 실행한다. *

  • 상한선과 하한선이 같아지면 검색값이 이 배열에 없다는 뜻이므로,
    ⬇️ 루프안에서

    • 상한선과 하한선 사이에 중간 지점을 찾는다.

  • 결괏값이 정수가 아닐 때는 올림한다. ↳ java의 ceil함수

• 중간 지점의 값을 확인한다.

• 중간 지점의 값이 찾고 있던 값이면 검색을 끝낸다.

• 아니라면 검색값이 중간지점값보다 작은지, 큰지 확인하여 상한선이나 하한선을 바꾼다.

• 루프를 빠져나오면 배열에 값이 없다는 뜻이므로 null을 반환한다.

public static Integer binarySearch(int[] orderedArray, int searchValue) {
    int lowerBound = 0;
    int upperBound = orderedArray.length - 1;

    while (lowerBound <= upperBound) {
        int midpoint = (int) Math.ceil( ((double) upperBound + lowerBound) / 2 );

        if (searchValue == orderedArray[midpoint])
            return midpoint;
        else if (searchValue < orderedArray[midpoint])
            upperBound = midpoint - 1;
        else if (searchValue > orderedArray[midpoint])
            lowerBound = midpoint + 1;
    }

    return null;
}

• JUNIT TEST 통과!

import org.junit.Test;
import static org.junit.Assert.*;

@Test
public void binarySearchTest() {
    int[] array = {3, 10, 37, 39, 44, 81, 659};

    Integer expectedNull = null;
    Integer expected0 = 0;
    Integer expected1 = 1;
    Integer expected2 = 2;
    Integer expected3 = 3;
    Integer expected4 = 4;
    Integer expected5 = 5;
    Integer expected6 = 6;

    //예상값, 실제값
    assertEquals(expectedNull, binarySearch(array, 788));
    assertEquals(expectedNull, binarySearch(array, 45));
    assertEquals(expectedNull, binarySearch(array, 2));
    assertEquals(expected0, binarySearch(array, 3));
    assertEquals(expected1, binarySearch(array, 10));
    assertEquals(expected2, binarySearch(array, 37));
    assertEquals(expected3, binarySearch(array, 39));
    assertEquals(expected4, binarySearch(array, 44));
    assertEquals(expected5, binarySearch(array, 81));
    assertEquals(expected6, binarySearch(array, 659));
}

🟪 선형검색 vs 이진검색

작은 크기의 배열이라면 이진 검색 알고리즘이 선형 검색 알고리즘보다 크게 나은 점은 없다. 하지만 배열이 더 커질 수록 이진 검색이 훨씬 선형 검색보다 빨라진다.

100개의 원소를 가진 배열에서 검색 연산에 필요한 최대 단계수 :

• 선형 검색 : 100단계
• 이진 검색 : 7단계

원소가 10,000개일 때 :

• 선형 검색 : 10,000단계
• 이진 검색 : 13단계

원소가 1,000,000개 일 때 :

• 선형 검색 : 1,000,000단계
• 이진 검색 : 20단계

선형 검색에서는 원소 수만큼의 단계가 필요하다. 배열의 원소 수를 두 배로 늘릴 때마다 단계 수도 두 배로 늘어난다. 반면 이진 검색에서는 한 단계만 늘어난다.

⬇️ 선형 검색과 이진 검색의 이러한 성능 차이를 그래프로 표현하면

선형 검색에 해당하는 선을 보면 배열에 원소가 많아질수록 그에 비례해 검색에 걸리는 단계 수도 늘어난다. 기본적으로 배열에 원소 하나가 늘어날 때마다 선형 검색에는 4단계가 더 걸린다. 그래서 대각선 형태의 직선이 만들어진다.

이진 검색에 해당하는 선을 보면 데이터가 많아질수록 알고리즘의 단계 수는 아주 조금만 늘어난다. 이진 검색이 한 단계 늘어나려면 데이터 크기를 두 배로 늘려야 한다는 사실에 완벽히 부합한다.

🟪 알고리즘이란

알고리즘은 특정 과제를 달성하기 위해 컴퓨터에 제공되는 명령어 집합이다. 어떤 코드를 작성하든 컴퓨터가 따르고 실행할 알고리즘을 만드는 것이다.

• 예시

public static void printThings() {
    String[] things = {"apples", "chairs", "files", "notes"};

    for (String thing : things)
        System.out.printf("Here's a thing : %s \n", thing);
}

복잡하지 않을지라도 뭔가를 하는 코드는 모두 엄밀히 알고리즘, 즉 문제를 풀어나가는 절차다. 이 코드는 리스트의 모든 항목을 출력하고 싶다는 문제를 해결한다. 이 문제를 푸는 데 사용한 알고리즘은 print문이 포함된 for 루프다.

🟪 알고리즘이 중요한 이유

선형 검색과 이진 검색의 성능 차이처럼, 같은 자료구조와 같은 연산을 하더라도 선택한 알고리즘에 의해서 속도 차이가 확연하게 날 수 있기 때문이다.

🟦 출처

🔷 그림1

🖱 클릭! | '더 북'사이트의 '컴퓨터 사이언스 부트캠프 with 파이썬' 게시글의 '그림 15-4 선형 탐색 알고리즘 vs. 이진 탐색 알고리즘'표 보러가기

🔷 글의 내용

이 글 내용은 '제인 웬그로우'의 '누구나 자료구조와 알고리즘 개정 2판' 책을 100% 참고하여 작성하였습니다. 설명에 전문적인 용어보다는 일상적인 용어를 사용하고 그림으로 원리를 설명해주어 왕초보인 저가 이해하기에 아주 좋았습니다. 가격이 많이 나가는 편이지만 꼭 배워야 하는 내용이 모두 들어있고 그것을 제가 이해할 수 있는 수준으로 쓰여있어 전혀 아깝지 않은 소비였습니다.

🖱 클릭! | '제인 웬그로우'의 '누구나 자료구조와 알고리즘' 책 구경하러 가보기

rust document, rust의 간단한 예제와 토이프로젝트 예제와 심화 프로젝트 예제들, 그리고 니콜라스의 rust 설명 영상을 보게 되었어요.

이 글은 니콜라스의 rust언어 영상을 보고 간략하게 적어본 것입니다.

❗이 글은 엉성하고 짧은 지식 글입니다. 부디 출처를 꼭 방문해주세요 😉

🟪 C와 C++의 대체 언어로 각광 받고 있다.

( ⬆️출처 : 영상의 0:28 스크린샷 )

다른 언어와 비교하여 최고 수준으로 편리한 컴파일러와 소유권 개념 도입으로 보장되는 강력한 안전성과 빠른 속도 덕분에 C와 C++을 대체하는 언어로 각광 받고 있다.

예시로 아마존, 클라우드플레어, 마이크로소프트 같은 회사들이 C와 C++로 된 코드들을 Rust로 대체하고 있다.

🟪 low level language , System programming

( ⬆️출처 : 영상의 2:43 스크린샷 )

RUST는 low level language로서 system programming에 가깝다. assembly language 바로 그 다음의 단계에 있는 저수준 언어이다. java 그리고 특히 js와 python와 비교하면 아주 저수준 언어인 것이다.

rust의 강점은 fast와 safe이다.

🟪 fast

( ⬆️출처 : 영상의 5:53 스크린샷 )

한 사례로 DISCORD회사는 빠른 속도로 인한 서비스 질 향상을 꾀하며 GO에서 RUST로 바꾸었다.

🔶 중간단계가 없다

( ⬆️출처 : 영상의 3:51 스크린샷 )

java는 class파일로 변환 후 컴퓨터가 기계어로 읽을 수 있게 된다. (더 많은 단계가 있겠지만 아주 간단하게 설명하자면 말이다.) python언어는 C언어로 이해된 후에 컴퓨터가 기계어로 읽을 수 있게 되는 것이다.

Rust는 java, python, js와 같이 컴퓨터가 기계어로 읽기 전에 거치게 되는 중간 단계가 없기 때문에 속도가 빠른 것이다.

🔶 garbage collector가 없다

( ⬆️출처 : 영상의 5:13 스크린샷 )        ( ⬆️출처 : 영상의 5:18 스크린샷 )

그리고 또한 garbage collector가 없기 때문에 빠르다.

c언어와 같은 저수준 언어는 변수를 만들 때 메모리 할당을 요청하고 더이상 쓰이지 않을 때는 메모리 공간 해제를 해야한다.

그러나 java, js, python같은 고수준 언어에서는 이렇게 할 필요가 없는 데 이는 garbage collector가 있기 때문이다. garbage collector는 쓰이지 않는 데이터가 메모리 공간에 있는지 늘 탐색하고 있다. 그리고 해당 공간을 발견하면 삭제한다. garbage collector가 이러한 일을 하기 때문에 개발자에게는 편리함을 주는 반면 프로그램의 성능은 느려지게 만드는 것이다.

그래서 garbage collector가 없는 언어들이 있는 언어들보다 빠른 것이다.

🟪 safe

❗Ownership 개념 덕분에 Memory Access Bug로부터 안전하다!

( ⬆️출처 : 영상의 6:22 스크린샷 )

보안 문제의 70%가 메모리 엑세스와 관련이 있다. ➡️ 그렇게 때문에 Rust가 안전하다는 것이다.

Memory Access Bug는 할당되지 않은 메모리 장소에 접근하거나, 이미 해제된 메모리 부분에 접근하려고 하거나, 또는 할당된 변수를 두 번 해제할려고 할 때 발생한다. 이는 곧 Runtime Error로 이어질 수 있다.

이 문제 때문에 Rust가 인기가 많은 것이다. Rust는 C와 C++보다 느리더라도 거의 비슷한 퍼포먼스를 제공할 뿐만 아니라 더욱 안전하다.

그 이유는 Rust는 프로그램의 데이타에 대한 관념이 다르기 때문이다. 그것이 바로 소유권 Ownership이라는 개념이다.

** 소유권 [ Ownership ] 이라는 개념에서는 프로그램의 데이터는 변수에 의해 소유된다. 그리고 데이터는 한번에 한 owner에게만 소유된다. Owner가 더이상 사용되지 않는다면, 데이터는 메모리에서 제거된다. **

Ownership

** Owner = 변수 하나의 Owner( 변수 )에게 한번만 사용된다. 그리고 바로 메모리에서 제거된다. **

with the concept of ownership , the data of your program is owned by variables. the data can only be owned by one owner at a time. if the owner is not is scope or used anymore the data in dropped from memory.

🌟 예시 코드 🌟

( ⬆️출처 : 영상의 8:06 스크린샷 )

main함수는 my_name 이라는 변수를 갖고 있다. 그리고 main함수는 say_hi라는 함수를 부르는데 my_name 변수를 인수로 보낸다.

그리고 say_hi함수에서 인수로 받은 my_name 변수를 프린트한다.

모든 걸 완료한 후 main함수로 돌아와서 my_name변수를 한번더 프린트 한다.

❓❔ 결과는 어떻게 될까

( ⬆️출처 : 영상의 8:37 스크린샷 )

java, python 같은 언어를 하는 사람들은 🧔🏻‍♀️ : "만약 my_name변수에 니꼬라는 문자열 값이 할당되어 있다면 『hi 니꼬! a is equals to 니꼬』 이렇게 출력이 되는 결과가 나타나겠지!!"

Rust에선 어림도 없다구❗❕

➡️ 실제 결과로는 이렇게 나온다 ❗

🙀 : 앵?? 왜 두번째 print함수는 출력되지 않은거야??!!!

my_name에 니꼬가 할당되었고, data 니꼬가 my_name 변수에서 say_hi함수로 이동함으로서 say_hi함수는 data 니꼬의 owner가 된다. 이 순간 부터 main함수의 my_name변수는 사용할 수 없게 된다.

🟪 어디에 쓰일 수 있을까?

( ⬆️출처 : 영상의 10:28 스크린샷 )

• 블록체인 프로젝트의 스마트 컨트랙 구축
• 커맨드라인 인터페이스
• 백엔드
• 임베디드 소프트웨어
• 비디오 게임 엔진
• 웹 애플리케이션 등등등

✍🏻 이 글의 모든 내용과 사진들의 출처

📻 노마드코더의 <C가 주옥같은 개발자들 보세요. Rust 10분 정리!> 영상 보러가기

이 글은 문제를 정리하고 저의 풀이를 보여드리는 거예요. 실제로 문제를 보고 풀어보세요. 클릭! 클릭! 해보세요! 🖱️

🔷 문제

1937년 Collatz란 사람에 의해 제기된 이 추측은, 주어진 수가 1이 될때까지 다음 작업을 반복하면, 모든 수를 1로 만들 수 있다는 추측입니다. 작업은 다음과 같습니다.

1-1. 입력된 수가 짝수라면 2로 나눕니다. 1-2. 입력된 수가 홀수라면 3을 곱하고 1을 더합니다. 2. 결과로 나온 수에 같은 작업을 1이 될 때까지 반복합니다.

위 작업을 몇 번이나 반복해야하는지 반환하는 함수, solution을 완성해 주세요. ❗단, 주어진 수가 1인 경우에는 0을, 작업을 500번 반복할 때까지 1이 되지 않는다면 –1을 반환해 주세요. ❗입력된 수, num은 1 이상 8,000,000 미만인 정수입니다.

✅ 입출력 예시

• 입력된 수가 6이라면 6 ➡️ 3 ➡️ 10 ➡️ 5 ➡️ 16 ➡️ 8 ➡️ 4 ➡️ 2 ➡️ 1 이 되어 총 8번 만에 1이 됩니다.
• 16 ➡️ 8 ➡️ 4 ➡️ 2 ➡️ 1 이되어 총 4번만에 1이 됩니다.
• 626331은 500번을 시도해도 1이 되지 못하므로 -1을 리턴해야합니다.

🔷 내가 만든 로직

✅ 실패한 로직

• while문으로 구현할 때
  • 1이 될 때 까지
  • 짝수일 때는 num /= 2 한 후, answer++
  • 홀수일 때는 num *= 3 + 1 한 후, answer++
  • 위의 연산을 끝낸 후, if num == 1이면 return answer
    
• for문으로 구현할 때
  • 500번 반복
  • 짝수일 때는 num /= 2 한 후, answer++
  • 홀수일 때는 num *= 3 + 1 한 후, answer++
  • 위의 연산을 끝낸 후, if num == 1이면 return answer

✅ 성공한 로직

• ❗num의 자료형은 long으로! int는 ❌
  • 모든 코드가 똑같은데도 불구하고 num의 자료형이 int이냐, long이냐에 따라 결과가 달라진다.
  • 그리고 num의 자료형이 long일 때의 결과만 통과한다. ➡️ 이유가 뭘까... 더 알아봐야겠다.
    
• while문으로 구현
  • 조건 : num이 1이 아닐 때
  • while(num != 1)
• while문 시작하자 마자 바로 루프 카운팅 시작
  • collatzCount++
• while루프가 500번 반복되면 바로 -1 반환
  • if문으로 구현
  • -1은 itsNotCollazNum변수명으로 의미부여
  • if(collazCount == 500) return itsNotCollazNum
• 짝수일 때는 num /= 2 , 홀수일 때는 num *= 3 + 1 한 후, num에 대입
  • 삼항연산자 이용
  • num = (num%2==0) ? (num/2) : (num*3+1)

🔷 실패한 나의 코드 1

public class CollatzConjecture {
    public static int solution(int num) {
        int answer = 0;

        while (num <= 1000) {
            if(num % 2 == 0) {
                num /= 2;
                answer++;
            }

            if (num == 1)
                return answer;

            if(num % 2 == 1) {
                num = (num * 3) + 1;
                answer++;
            }
        }

        answer = -1;
        return answer;
    }
}

⬇️ 결과는..🥲

🔷 실패한 이유

✅ 이상한 while문 조건

✅ if(num == 1)문 위치

🥲 바꿔서 다시 해봤지만 다시 실패함. 결국 예상한 실패 이유가 틀렸다는 뜻!

🔷 실패한 나의 코드 2

public class CollatzConjecture {
    public static int solution(int num) {
        int collatzCount = 0;
        int itsNotCollatzNum = -1;

        while (collatzCount <= 500) {
            if (num % 2 == 0) {
                num /= 2;
            } else  {
                num = (num * 3) + 1;
            }
            collatzCount++;

             if (num == 1) return collatzCount;
        }

        return itsNotCollatzNum;
    }
}

⬇️ 바꾼 점

✅ while()문 조건

while(num <= 1000) ➡️ while(collatzCount <= 500)

✅ if()문 * 3

if() if() if() ➡️ if() else if()

✅ if(num==1)문 위치

짝수연산과 홀수 연산 사이 ➡️ 짝수 연산과 홀수 연산 뒤에

✅ answer++문 위치

짝수 연산과 홀수 연산 각각에 ➡️ 짝수 연산과 홀수 연산에 모두 지우고, 짝수 연산과 홀수 연산이 끝나고 한번만 answer++할 수 있도록 했다.

⬇️ 결과는..🥲

아까보다 틀린 횟수는 확연하게 줄긴 했다..🥲

🔷 엄청나게 어이없는 실패한 이유2

✅ 새로 추가된 규칙

내가 처음 문제를 풀었을 때는 6월 3일! 그러나 6월 10일에 주어진 수가 1인 경우에는 0을 반환해 주세요.라는 제한 규칙이 추가되었다. 최근에 추가된 이 제한 규칙을 충족시키지 못했기 때문에 아무리 코드를 고쳐도 계속 똑같이 테스트5랑 테스트13번만 계속 틀리는 것이었다!

✅ num의 자료형

num의 자료형이 int일 때와 long일 때 return값이 달라진다.

num의 자료형이 int면 불합격, long면 통과된다.

🔷 드디어 성공한 나의 코드

class Solution {
    public int solution(long num) {
        int collatzCount = 0;
        int itsNotCollatzNum = -1;

        while (num != 1) {
            collatzCount++;

            if (collatzCount == 500)
                return itsNotCollatzNum;

            num = (num % 2 == 0) ? num / 2 : (num * 3) + 1;
        }

        return collatzCount;
    }
}

⬇️ 바뀐점

✅ 결국은 다른 사람의 풀이를 참고하여 통과했다..

public static int sol(long num) {
    int answer = 0;

    while(num != 1){
        answer++;
        if(answer==500)
            return -1;
        if(num%2==0){
            num/=2;
        }else{
            num=num*3+1;
        }
    }
    return answer;
}

✅❗ int num ➡️ long num

↳ 이유 : INT 오버플로우

num의 자료형이 int일 때와 long일 때 return값이 달라진다.

• public int solution(long num) ➡️ num=626331 일때 return -1 ➡️ 통과

• public int solution(int num) ➡️ num=626331 일때 return 488 ➡️ 불합격

✅ while문 조건

↳ while(collazCount <= 500) ➡️ while(num != 1)

문제의 조건은 num이 1일 떄는 0을 반환하고, num이 1이 될 때까지 콜라츠연산을 반복하는 것이므로 num이 1일 때는 루프를 타지 않아야 한다. 그러므로 while문의 조건이 collazCount <= 500이어야 하는 것이 아니라 num != 1인 것이 맞다.

✅ while문 안의 collatzCount++ 맨 위로 위치 변경

while문이 시작하자마자 카운팅을 시작해야지 collazCount가 500일 때 바로 -1을 반환시킬 수 있기 때문이다.

✅ while문 안의 if문 조건

↳ if(num ==1) return collazCount ➡️ if (collazCount == 500) return itsNotCollazNum

while문의 조건과 if문의 조건을 반대로 해놔서 이때까지 틀린 것이었다. num이 1이면 while문이 돌아가면 안되고 collazCount가 500이 되면 while문이 멈춰야 되는 것이었는데 이것을 정반대로 해서 collazCount가 500이 될 때까지 num이 1이어도 while문이 돌아가게 했고 그래서 num이 1일 때 0을 반환해야 하는데, 콜라츠 연산 횟수인 collazCount를 반환되어 버렸다.

✅ return 값

↳ return itsNotCollazNum ➡️ return collazCount

이 문제는 콜라츠 연산의 횟수를 요구한 것이었는데 나는 -1을 반환했으니 당연히 틀리는 것이었다.

⬇️ 결과는..😄

🔷 solution함수의 매개변수num의 타입이 int면 불합격, long이면 합격인 이유

⬆️ 클릭하면 그 이유에 대한 설명으로 이동됨

🔷 그림출처

구글플레이사이트의 김시현님의 콜라츠 추측 계산기어플 보러가기 클릭! 🖱️

이 글은 문제를 정리하고 저의 풀이를 보여드리는 거예요. 실제로 문제를 보고 풀어보세요. 클릭! 클릭! 해보세요! 🖱️

🔷 문제

정수를 담고 있는 배열 arr의 평균값을 return하는 함수, solution을 완성해보세요. arr은 길이 1 이상, 100 이하인 배열입니다. arr의 원소는 -10,000 이상 10,000 이하인 정수입니다.

✅ 입출력 예시

🔷 내가 만든 로직

✅ solution()

• ❗결과는 double형이므로 합계 또한 자료형을 double로 해야 합계/갯수 했을 때 결과가 double로 나온다.
• for문을 이용하여 double형 변수 sum에 인수 int[] 배열의 각각의 값들을 더한다.
• sum에 배열의 길이가 곧 갯수이므로 나눈다.

🔷 내가 만든 코드

class Solution {
    public double solution(int[] arr) {
        double sum = 0;
        for (int value : arr)
            sum += value;

        double answer = sum/arr.length;
        return answer;
    }
}

🔷 나의 코드 결과

🔷 그림출처

123RF사이트의 jameschipper작가님의 신용 점수 측정기일러스트(콘텐츠 ID: 76165125) 보러가기 클릭! 🖱️

이 글은 문제를 정리하고 저의 풀이를 보여드리는 거예요. 실제로 문제를 보고 풀어보세요. 클릭! 클릭! 해보세요! 🖱️

🔷 문제

양의 정수 x가 하샤드 수이려면 x의 자릿수의 합으로 x가 나누어져야 합니다. 예를 들어 18의 자릿수 합은 1+8=9이고, 18은 9로 나누어 떨어지므로 18은 하샤드 수입니다. 자연수 x를 입력받아 x가 하샤드 수인지 아닌지 검사하는 함수, solution을 완성해주세요. x는 1 이상, 10000 이하인 정수입니다.

✅ 입출력 예시

🔷 내가 만든 로직

✅ solution()

• 숫자를 자릿수별로 분리한다.
  • 숫자를 String으로 바꾼 다음 .split("")을 이용하여 각각 자릿수 별로 분리하여 <문자열 배열>에 넣는다.
• for문을 이용하여 각 자릿수를 더한다.
• 숫자 / 더한 각 자릿수 의 결과가 나누어 떨어지면 true를 반환, 아니면 false 를 반환한다.
  • if문과 % == 0을 이용하여 나누어 떨어지는 지 판단한다.

🔷 내가 만든 코드

class Solution {
    public boolean solution(int x) {
        boolean answer = false;

        String[] splittedNumbersArr = Integer.toString(x).split("");
        int sumSplittedNumbers = 0;
        for (String number : splittedNumbersArr)
            sumSplittedNumbers += Integer.parseInt(number);

        if (x%sumSplittedNumbers == 0)
            answer = true;

        return answer;
    }
}

🔷 나의 코드 결과

🔷 그림출처

희망누리님의 근로복지공단 대표 공식블로그 희망누리블로그의 [신기한 인도 수학] 인도수학, 인도 수학공식, 수학의 나라 인도게시글 보러가기 클릭! 🖱️

이 글은 문제를 정리하고 저의 풀이를 보여드리는 거예요. 실제로 문제를 보고 풀어보세요. 클릭! 클릭! 해보세요! 🖱️

🔷 문제

프로그래머스 모바일은 개인정보 보호를 위해 고지서를 보낼 때 고객들의 전화번호의 일부를 가립니다. 전화번호가 문자열 phone_number로 주어졌을 때, 전화번호의 뒷 4자리를 제외한 나머지 숫자를 전부 *으로 가린 문자열을 리턴하는 함수, solution을 완성해주세요. phone_number는 길이 4 이상, 20이하인 문자열입니다.

✅ 입출력 예시

🔷 내가 만든 로직

✅ solution()

• 보여지는 마지막 4자리를 새로운 String 변수에 담는다.
  • substring() 메소드의 index : phone_number_length - 4
• 가려지는 번호들의 숫자들을 *로 바꾼다
  • StringBuilder의 append()메소드를 이용하여 가려지는 번호의 갯수만큼 *을 for문으로 반복한다.
• 가려진 번호와 보여지는 번호 두 개를 합친다.

🔷 내가 만든 코드

public static String solution(String phone_number) {
        int phone_number_length = phone_number.length();
        int numbers_shown_length = 4;
        int numbers_hidden_length = phone_number_length - numbers_shown_length;
        String numbers_shown = phone_number.substring(numbers_hidden_length);

        StringBuilder numbers_hidden = new StringBuilder();
        for (int i =0; i < numbers_hidden_length; i++)
            numbers_hidden.append("*");

        String answer = numbers_hidden + numbers_shown;
        return answer;
    }

🔷 나의 코드 결과

🔷 그림출처

텐바이텐사이트의 라이언과 춘식이는 통화중 주차번호판상품 사진 보러 가기 클릭! 🖱️

이 글은 문제를 정리하고 저의 풀이를 보여드리는 거예요. 실제로 문제를 보고 풀어보세요. 클릭! 클릭! 해보세요! 🖱️

🔷 문제

** 행렬의 덧셈은 행과 열의 크기가 같은 두 행렬의 같은 행, 같은 열의 값을 서로 더한 결과가 됩니다. 2개의 행렬 arr1과 arr2를 입력받아, 행렬 덧셈의 결과를 반환하는 함수, solution을 완성해주세요. 행렬 arr1, arr2의 행과 열의 길이는 500을 넘지 않습니다.**

✅ 입출력 예시

🔷 2차원배열

✅ *2차원 배열은 2중 for문과 구조가 같다. *

✅ 2차원 배열 생성 방법

** int[][] array4 = new int[5][7];**

✅ 2차원 배열에 값을 저장하는 방법

array4[3][6] = 10;

❗ array4[1] = 10 ; ➡️ 🚫이렇게 사용하면 오류!!🚫 ❗array4[1] 은 또 다른 1차원 배열을 가리킬 수 있는 참조형 변수이기 때문에 값을 담을수는 없다.

✅ 선언과 동시에 초기화하는 방법

int[][] array6 = {{1}, {2,3}, {4,5,6}};

✅ ❗🌟가변크기의 2차원 배열을 생성하는 방법

int[][] array5 = new int[3][]; ➡️ array5는 3개짜리 배열을 참조한다. ➡️ 3개짜리 배열은 아직 참조하는 배열이 없다 ** array5[0] = new int[1]; ➡️ 정수를 하나 담을 수 있는 배열을 생성 ➡️ array5 의 0 번째 인덱스가 참조 array5[1] = new int[2]; ➡️ 정수를 두 개 담을 수 있는 배열을 생성 ➡️ array5 의 1 번째 인덱스가 참조 array5[2] = new int[3];** ➡️ 정수를 세 개 담을 수 있는 배열을 생성 ➡️ array5 의 2 번째 인덱스가 참조

🔷 내가 만든 로직

✅ solution()

• 가변크기의 2차원 배열을 생성한다.
• arr1과 arr2는 solution 메소드의 인자이고, answer은 solution 메소드의 return값이다.
• arr1과 arr2와 answer, 이 세개의 이차원 배열은 같은 행열의 크기를 가졌으므로
• answer의 행의 크기와 열의 크기를 정할 때 arr1을 이용한다.
• answer의 행의 크기는 arr1의 열의 크기와 같고, answer의 각각의 행의 크기는 arr1의 각각의 행의 크기와 같은 점을 이용하여
• 처음에는 answer을 가변크기의 2차원 배열로 선언하고 ( new int[arr1.length][] )
• for문을 이용하여 각 행의 크기를 정한다. ( new int[arr1.length][arr1[0~n].length] )

🔷 내가 만든 코드

public class Solution {
    public static int[][] solution(int[][] arr1, int[][] arr2) {
        int columnLength = arr1.length;
        int[][] answer = new int[columnLength][];

        for (int column = 0; column < columnLength; column++) {
            int rowLength = arr1[column].length;
            answer[column] = new int[rowLength];

            for(int row = 0; row < rowLength; row++) {
                answer[column][row] = arr1[column][row] + arr2[column][row];
            }
        }

        return answer;
    }
}

✅ 🚫주의

• 두번째 for문 안에 answer[column] = new int[rowLength];을 선언하면 row가 바뀔 때 마다 행이 초기화 되기 때문에 꼭! 첫번째 for문 안에서 미리 선언하고 난 후에 두번째 for문에서 각 row에 값을 넣어줘야 한다.

🔷 나의 코드 결과

🔷 2차원 배열 내용 출처

프로그래머스사이트의 자바입문-2차원배열글 보러가기 클릭! 🖱️

🔷 그림출처

인사이트사이트의 애니팡사진 보러가기 클릭! 🖱️

이 글은 문제를 정리하고 저의 풀이를 보여드리는 거예요. 실제로 문제를 보고 풀어보세요. 클릭! 클릭! 해보세요! 🖱️

🔷 문제

** 함수 solution은 정수 x와 자연수 n을 입력 받아, x부터 시작해 x씩 증가하는 숫자를 n개 지니는 리스트를 리턴해야 합니다. x는 -10000000 이상, 10000000 이하인 정수입니다. n은 1000 이하인 자연수입니다.**

✅ 입출력 예시

🔷 내가 만든 로직

✅ solution()

🔷 내가 만든 코드

class Solution {
    public long[] solution(int x, int n) {
        long[] answer = new long[n];

        for(int answerIndex = 0; answerIndex < n; answerIndex++) {
            int multiplyNumber = answerIndex + 1;
            answer[answerIndex] = x * multiplyNumber;
        }

        return answer;
    }
}

🔷 나의 코드 결과

🔷 틀린이유

** ❗자료형 때문!! **

return될 answer[]은 long자료형만 들어갈 수 있다. 인수 x를 int로 한다면 제한되는 범위 끝에 다다를 때 answer[]에 들어가야 하는 수를 int자료형은 담을 수 없게 될 것이다. 그래서 long자료형으로 처음부터 x를 받아야한다.

🔷 다시 도전하는 코드

class Solution {
    public long[] solution(long x, int n) {  ⬅️⬅️❗❗❗
        long[] answer = new long[n];

        for(int answerIndex = 0; answerIndex < n; answerIndex++) {
            int multiplyNumber = answerIndex + 1;
            answer[answerIndex] = x * multiplyNumber;
        }

        return answer;
    }
}

🔷 다시 도전한 결과

이 글은 문제를 정리하고 저의 풀이를 보여드리는 거예요. 실제로 문제를 보고 풀어보세요. 클릭! 클릭! 해보세요! 🖱️

🔷 문제

** 이 문제에는 표준 입력으로 두 개의 정수 n과 m이 주어집니다. 별( * ) 문자를 이용해 가로의 길이가 n, 세로의 길이가 m인 직사각형 형태를 출력해보세요. n과 m은 각각 1000 이하인 자연수입니다.**

숫자 두 개가 입력되면, 첫 번째 숫자는 가로의 길이이고, 두 번재 숫자는 세로의 길이가 됩니다. 여기에 맞게 별*을 출력하면 됩니다.

✅ 입력되는 데이터의 제한 조건

각각 1000 이하인 자연수 2개만 입력됩니다.

✅ 입출력예시

🔷 내가 만든 로직

✅ printResult()

• 인수로 정수 2개를 받는다.
• for문을 2번 돌린다.
• 첫번째 for문은 열column,세로을 표현하므로 두번째 인수만큼 반복하여 < * >을 출력한다.
• 두번째 for문은 행row,가로을 표현하므로 첫번째 인수만큼 반복하여 System.out.println()을 출력하여 다음 행으로 넘긴다. 이때 System.print.out("\n" )을 출력하면 다음 행으로 넘어간다음 또 다음 행으로 넘어가므로 이건 안된다.

🔷 내가 만든 코드

import java.util.Scanner;

class Solution {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int first_number = scanner.nextInt();
        int second_number = scanner.nextInt();

        printResult(first_number, second_number);
    }

    public static void printResult(int first_number, int second_number) {
        for (int column = 0; column < second_number; column++) {
            for (int row = 0; row < first_number; row++) {
                System.out.print('*');
            }
            System.out.println();
        }
    }    

}

🔷 나의 코드 결과

🔷 그림 출처

🖱️ 'icons.kr'사이트의 무료일러스트, < 'Bonbon'작가의 별 일러스트 > 다운 받기 클릭