코딩 끝에 낙이 온다 코딩 끝에 낙이 온다

정렬된 수열에서 특정 수를 찾고자 할 때 사용되는 탐색 알고리즘. 학부 시간에 가장 첫번째로 배우는 탐색 알고리즘이 아닌가 한다. 수행원리상 이 알고리즘을 사용하기 위해선 오름차순으로 배열이 정렬되어 있어야 한다. 일반적으로 배열을 전부 순차적으로 탐색하는 방식보다 훨씬 효율적인 방식이다. 이진 탐색이라는 이름과 같이 배열을 반으로 쪼개어 수행한다. 간결한 코드이지만, 꽤나 훌륭한 성능을 보여준다. 수행 방식은 다음과 같다. 1.배열의 시작을 left, 배열의 마지막을 right으로 정한다. 2.left와 right의 중간 점을 mid로 정한다. 3.mid로 정한 값이 찾으려는 수보다 크다면 right을 mid-1로 정하고, mid로 정한 값이 찾으려는 수보다 작으면 left를 mid+1로 정한다. 4...

계수 정렬. 이름처럼 숫자를 세어 진행하는 정렬이다. 시간 복잡도는 O(n)으로 퀵 정렬 O(n log n), 합병 정렬(O(n log n)) 보다도 빠르다(!) 어떻게 이렇게 빠른 것일까?? 계수 정렬이 이루어지는 방식은 다음과 같다. 1.정렬하는 배열의 최대 값을 크기로 가지는 배열을 하나 생성. 2.정렬하는 배열을 순회하면서 각 수들이 등장하는 빈도를 각 배열의 인덱스에 저장. 3.각 빈도를 누적한 합을 저장한 배열을 새로 생성한다. 4.다시 정렬해야 하는 배열을 역순으로 순회하면서 어떤 수가 나오면 누적합 배열의 해당 인덱스로 간다. 5.누적합 배열에 저장된 값을 인덱스로 하여 정렬된 값이 들어간 배열에 값을 저장한다. 6.누적합 배열에 저장된 값을 1씩 빼준다. 7.럼 숫자를 세어 진행하는 정렬..

수열을 입력받고, 찾아야 하는 수들이 포함된 배열을 추가로 입력받아 수열 내에 수들이 포함되어 있는 지에 대한 여부를 1 또는 0으로 출력해야 하는 문제이다. n = int(input()) entries = input().split() m = int(input()) tofind = input().split() result =[0]*m for i in entries: for b in range(0,m): if int(i) == int(tofind[b]): result[b] = 1 for u in result: print(u) 우선 입력받은 수열을 반복문으로 전체 순회하고, 하나의 요소를 찾아야할 수열 중에 하나와 일치하는 지를 반복문으로 순회하여 판별하는 방식으로 진행. 결과는 당연히 시간 초과! impo..