요약하자면 내가 제품 매니저고 새로운 제품 개발을 이끌고 있는데, 최신 버전이 제품 품질 검사에 실패 했다고 한다. 각 버전들이 그 전의 버전을 기반으로 개발되기 때문에 어떤 버전의 품질이 안좋으면 당연히 그 다음 버전의 품질은 당연히 안좋다. 그래서 주어진 bool isBadVersion API을 통해 n개의 버전중에 나쁜 버전중 제일 첫번째 버전을 찾는것이다. (안좋은 버전이면 true를 리턴함) 즉, 품질 검사 실패의 원인이 되는 버전을 찾으라는 얘기다. // The API isBadVersion is defined for you. // bool isBadVersion(int version); int firstBadVersion(int n) { long first = 1,last = n,half; ..

셸 정렬(Shell Sort)은? 단순 삽입 정렬의 장점은 살리고 단점은 보완한 정렬 알고리즘 도널드 셀(D.L.Shell)이 고안했다. 먼저 정렬할 배열의 요소를 그룹으로 나눠 각 그룹별로 단순 삽입정렬을 수행하고, 그 그룹을 합치면서 정렬을 반복하여 요소의 이동횟수를 줄이는 방법이다. 퀵정렬이 나오기 전까지는 가장 많이 쓰였다고 한다. 여기서 말하는 단순 삽입정렬의 장점과 단점은 장점 - 정렬을 마쳤거나 정렬을 마친 상태에 가까우면 정렬 속도가 매우 빨라진다. 단점 - 삽입할 위치가 멀리 떨어져 있으면 이동(대입)해야 하는 횟수가 많아진다. 셸정렬은 이 단점을 해결하고 장점을 이용하기 위해 만들어졌다. 코드로 만들어보기 //배열 a와 요소의 수 n void shell(int a[], int n) { ..

단순 선택 정렬(Straight Selection Sort) 가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘 배열의 첫번째부터 검색하면서 더 작은수(큰 수를 찾는다면 큰 수)가 있다면 , 스왑을 해주어 정렬을 한다. 바로 코드로 보자. void Selection(int a[], int element) { int i, j; for (i = 0; i < element - 1; i++) { int min = i; for (j = i + 1; j < element; j++) { if (a[j] < a[min]){ min = j; } } int temp = a[i]; a[i] = a[min]; a[min] = temp; } 1. 첫번째 for문은 총 요소의 -1만큼 돌려준다. 버블정렬때..

버블 정렬 알고리즘 버블 정렬은 이웃한 두 요소의 대소 관계를 비교하여 교환을 반복하는 정렬 알고리즘이다. 자료들이 정렬되는 모습이 마치 보글보글 거품처럼 올라오는 모습이라 버블 정렬이라고 한다는데 잘 모르겠다.. 이런식으로 붙어있는 요소들간의 비교를 해서 변경을 해야한다면 스왑을하고 그게 아니라면 비교만 하고 넘어간다. 코드로 한번 구현을 해보았다. void bubble(int a[], int element) { for (int i = 0; i a[j + 1]) { int temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; } } 1. 매개변..

각각의 정수로 정렬된 배열과 타겟 값이 주어지고, 배열안에 타겟 값이 있다면 그 인덱스를 리턴, 없다면 타겟값이 이 정렬된 배열에서 어디인덱스에 들어가야하는지 리턴해주면 된다. 이것도 O(log n) 시간복잡도를 가진 알고리즘을 사용해야 한다. 배열의 길이와 값의 제한이 있으며 nums배열은 오름차순, 별개의 값을 가진다. class Solution { public: int searchInsert(vector& nums, int target) { int MinIndex = 0; int MaxIndex = nums.size()-1; int half = 0; while(MinIndex

학원 강사님의 강력 추천으로 리트코드에서 코딩테스트 문제를 풀어보기로 했다. 대기업은 영어로 내는곳도 있고 한국 사이트들과 다르게 문제도 새로운것이 지속적으로 올라온다고 하셔서.. 대기업을 당장 노려볼수는 없겠지만 그냥 혹해서 풀어봤다. LeetCode - The World's Leading Online Programming Learning Platform LeetCode - The World's Leading Online Programming Learning Platform Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your nex..