자 이쯤에서 슬슬 앞의 정렬을 까먹은분을 위해 짧막 상식 우리가 배웠던 정렬의 방식을 짧게 설명하고자 한다 1. Counting Sort (계수 정렬) - O(n) = 배열을 생성해서 그 안에 숫자를 받는다 그리고 같은 숫자가 있다면 카운트하여 인덱스로 저장해두었다가 정렬할때 한개씩 나열하며 정렬한다. 2. Selection Sort (선택 정렬) - O(n2) = 무작위로 받은 숫자를 쭈욱 나열하고 인덱스에 위치해야하는 수를 직접 찾아 해당 인덱스로 보내고 거기있던 수와 바꿔치기 한다. 3. Insertion Sort (삽입 정렬) - O(n2) = 무작위로 받은 숫자를 나열하고 첫번째 인덱스와 두번째 인덱스를 비교한다. 그리고 이 정렬은 인덱스가 커지더라도 계속해서 앞의 숫자와 비교하며 수를 정렬한다..
자 제목 부터 삽입 정렬이 나온다. 그럼 기본적으로 삽입 정렬에 대한 지식이 필요하지 않을까? 한번 보고 왔으면 좋겠당 삽입정렬 삽입 정렬(Insertion Sort) 이번에는 삽입 정렬을 배워보겠다. 간단히 정의하자면 현재 비교하고자 하는 target과 그 이전의 원소들과 비교하며 자리를 교환하는 정렬이다. 삽입정렬 역시 "안정 정렬"이다. 삽입 정렬의 과정 latewalk.tistory.com 앞서 봤던 삽입정렬은 선형탐색을 통한 원소가 들어갈 위치를 잡았다. 하지만 이진 삽입 정렬은 다르다. 이진 탐색(Binary Search)을 이용해 보자 천천히 생각해보자 저 위에 삽입 정렬은 target으로 숫자를 설정하고 그 숫자를 맞는 위치를 찾기위해 반복을 계속했다 이게 무슨 문제인가? 당연한거 아닌가?..
어쩌면 이글을 정렬을 공부하다 들어왔을것이다. 그러길 바라며 글을 작성한다..물론 내 공부가 크지만... 이진 탐색은 데이터가 이미 정렬된 상태에서 특정한 값을 찾고자 할때 사용한다. 원하는 값을 찾는 과정에서 앞에서 구하지 않고 배열의 중간값과 비교해 배열을 반으로 자르고 비교값이 가까운 배열에서 또 반으로 자르고 거기서 또 원하는값과 가까운 배열을 찾고 이것을 반복한다. 말이 어렵다면 바로 보여주겠다. 10 20 30 40 50 60 70 80 90 100 이런식의 배열이 있다. 우린 여기서 90을 찾아 보도록 하겠다. 배열을 중간으로 나누고 90에 가까운 배열을 찾는다 = 60 70 80 90 100 그럼 거기서 한번 더 나누고 90에 가까운 배열 = 80 90 100 또 반으로 나눴더니 90이 나..
이번에는 삽입 정렬을 배워보겠다. 간단히 정의하자면 현재 비교하고자 하는 target과 그 이전의 원소들과 비교하며 자리를 교환하는 정렬이다. 삽입정렬 역시 "안정 정렬"이다. 삽입 정렬의 과정 현재 타깃이 되는 숫자와 이전 위치에 있는 원소들을 비교한다. (첫 번째 원소는 두 번째부터 비교한다.) 타깃이 되는 숫자가 이전 위치에 있던 원소보다 작다면 위치를 서로 교환한다. 그다음 타깃을 찾아 위와 같은 방법으로 반복한다. 짧게 얘기하면 배열을 쭈욱 나열하고 앞뒤로 서로 비교하며 오름차순으로 정렬하는 것이다. 첫번째 원소는 타겟이 되어도 비교할 전 원소가 없어서 2번째 원소부터 타겟으로 잡고 시작한다. 구현은 나의 깃허브에 해놓았다 시간이 된다면 보는것을 적극 추천한다 https://github.com/..
다이내믹 프로그래밍을 풀면서 많이 만날 수 있는 소스 코드들이 있다. 바로 Top-Down이나 Bottom-Up이다. 우선 어려운말은 내가 잘못하니 쉽게 말해보겠다. Top-Down = 큰 값이 들어오고 그 값을 구하기 위해 그것보다 작은 값을 가져와 조합하여 정답을 도출해 낸다. Bottom-Up = 정답을 구하기 위해 가장 작은 값부터 차근차근 구하여 문제의 정답을 도출해 낸다. 사실 위에 글만 봐서는 잘 모른다. 왜냐하면 굉장히 비슷한 말이기 때문이다. 결과적으로 작은 값을 통해 정답을 구하는 건 공통적인 주제인 것이다. 그럼 저것의 차이가 무엇인지 알아보자. ◐ Top-Down 재귀함수를 이용한 방식(하향식) 재귀함수의 대표적인 예로는 피보나치의 수열이 있다. 그리고 함수호출을 줄이기 위해 메모이..
우리가 코드를 짤 때 (자료구조 + 알고리즘)을 이용하여 만들 것이다. 그 코드는 다양한 크기로 입력될 것이고 그 코드를 누군가와 공유를 하는 상황이 올 수 있다. 여기서부터 문제가 시작된다. 내가 가지고 있는 컴퓨터와 상대방이 가지고 있는 컴퓨터가 사양이 다른 것이다. 그러면 각자 다른 사양으로 인해 작업속도의 차이가 나기 시작하면서 불편함이 시작된다. 그래서 우리는 시간의 개념을 다르게 잡기로 했다.. 빠르다 느리다를 시간으로 즉, 초로 표현하지 않는 것이다. 간단히 말하자면 "완료까지 걸리는 절차의 수"라고 할 수 있다. 실행시간( Running Time = 함수/ 알고리즘 수행에 필요한 스텝의 수 그럼 바로 문제로 들어가보자, 이 함수의 실행시간이 얼마나 될 것인가? int[] multiply(i..
