[TIL] 어려운 알고리즘...

*20221111의 회고

 

   오늘의 스케줄도 하루종일 알고리즘 강의를 듣는 것이였다. 근데 강의는 파이썬 강의라 자바를 하는 나에게는 알고리즘 개념과 풀이방식만 이해하는 방식으로 수업을 듣고, 코드는 자바코드로 스스로 짜보면서 공부를 진행하였다. 그런데 확실히 파이썬 너무 편해 보인다. 자바는 배열을 반으로 자를 때, 반쪽짜리 배열을 생성해줘서 각각 for문을 돌면서 배열안에 원소를 하나씩 넣어주거나, Arrays.copyOfRange()를 사용해야되는데, 파이썬은 그냥 배열이름 옆에 대괄호 열고 범위만 지정해주면 알아서 잘라준다. 그 외에도 정말 편한 내장함수들이 많아보였다... 그래서 세상이 나를 파이썬으로 코테 준비하라고 유혹하는 느낌...ㅠ 그래서 너무 고민이 되어서 튜터님을 찾아뵙고 상담을 요청하였다. 결과는 자바 압승. 그래 난 스프링 할꺼니까 자바 기릿!!!!!!!!!!!! (김승민 튜터님 너무나도 감사드립니다ㅠㅠ)

 

   오늘 배운 내용을 회고해 보자면, 오늘은 이진탐색의 시간복잡도가 O(logN)인지 이유를 알게 되었고, 재귀함수와 정렬(버블정렬, 선택정렬, 삽입정렬)에 대해 배웠다.

 

- 이진탐색의 시간복잡도 O(logN)

: 탐색해야 하는 총 숫자가 1~N 까지라고 한다면,

1번 탐색하면 반절이 줄어드니 N/2개가 남는다.

2번 탐색하면 반절이 줄어드니 N/2^2개가 남는다.

3번 탐색하면 반절이 줄어드니 N/2^3개가 남는다.

...

k번 탐색하면 반절이 줄어드니 N/2^k개가 남는다.

이 때, 이분탐색 결과가 하나가 남았다고 가정해보자. 그러면 N/2^k = 1 -> k = logN 따라서 시간복잡도가 O(logN)이 된다. 

(

- 재귀 함수(recursive method)

    - 재귀(recursive)는 어떠한 것을 정의할 때 자기 자신을 참조하는 것을 뜻한다.

    - 재귀함수 : 자기 사진을 호출하는 함수. 재귀 함수를 이용하여 간결하고 효율성 있는 코드를 작성할 수 있다.

    - 재귀함수를 사용할 때는 반드시 탈출 조건 고려하기!

    - 스택이라고 생각할 수 있는데, 처음 불려진 함수에서(스택 맨 밑에 있는 메소드) return되는 값이 최종 return 값이 된다.

 

- 정렬 : 데이터를 순서대로 나열하는 방법

    - 버블 정렬(bubble sort) : 첫번째 자료와 두번째 자료, 두번째 자료와 세번째 자료, .... , n-1번째 자료와 n번째 자료를 두개씩 서로 비교하며 교환하면서 자료를 정렬하는 방식. 이웃한 두개의 수를 비교하여 swap 해줌 / 시간복잡도 : O(N^2)

    - 선택 정렬(select sort) : 선택해서 정렬한다. 데이터의 값을 선택하여 앞으로 보냄  / 시간복잡도 : O(N^2)

    - 삽입 정렬(insertion sort) : 두번째 자료부터 시작하여 그 앞의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고, 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘. 삽입정렬은 필요할 때만 위치를 변경하므로 좀 더 효율적인 방법이다.  / 시간복잡도 : O(N^2)

    - 병합 정렬(merge sort) : 배열의 앞부분과 뒷부분의  두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복하는 알고리즘. 두 개의 정렬된 배열을 각자의 원소를 바교하면서 더 작은 수를 다른 배열에 추가시키며 두 배열을 병합. / 시간복잡도 : O(logN)  

 

   여기까지는 어느정도 이해가 되었는데... 지금 병합 정렬 알고리즘을 구현하다가 막혀버렸다 ㅎㅎ 자바로 재귀함수는 처음 구현해봐서 아직 감이 완전 잡히지 않았는데, 재귀함수를 이용하는 정렬 알고리즘이라 아주아주 헷갈리고 모르겠다! ㅋㅋ 근데 버블, 선택, 삽입도 처음엔 되게 어렵다고 생각했는데, 예전에 한번 공부하고 다시 보니까 이해가 잘 되어버렸다(?) 그러니 병합정렬로 내일 다시 보면 이해가 잘 될거라고 생각한다. 오늘 하루도 수고했고 주말에도 틈틈히 공부해놓자 ~!~!~!~! (+pseudo-code 알아보기) 뽜이링 ~!~!