컴퓨터공학 💻 도서관📚

[ 이 문제를 보고 느낀점 :  알고리즘은 지저분해 보이지만 자세히 보면 예쁜 학문이다. ]        와..... 이걸 점화식으로 한 코드로 끝냈다고... 미친.. 슈퍼 플레이   자바 최댓값 알려주는 함수 :  Math.max()

다이나믹 프로그래밍이란 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 해 수행 시간 효율성을 비약적으로 향상시키는 알고리즘이다. 다이나믹 프로그래밍은 동적 계획법이라고도 부른다자료구조에서 동적 할당의 '동적' 은 '프로그램이 실행되는 도중에' 라는 뜻을 담고 있지만알고리즘에서 다이나믹 프로그래밍의 '다이나믹' 은 별다른 의미 없이 사용된 단어이다.   1. 문제를 작은 문제로 쪼갤 수 있고,  2. 중복되는 문제들이 있다면  DP 를 활용할 수 있다.     피보나치 수열은 다아나믹 프로그래밍을 활용해서 풀 수 있는 대표적인 문제이다  1) 재귀함수를 이용한 피보나치 수열 피보나치 수열 점화식 :  An = An-1 + An-2재귀적으로 호출되는 부분 :  An-1 + An-2 ..

1. 이진탐색을 직접 구현해서 풀 수 도 있고 (이건 교재에 있다고 함) 2. 표준 라이브러리를 이용해서 구현할 수 도 있다. (강의에선 이걸로 소개) 1번째 방법은 처음 전체 탐색 범위에서 이진 탐색을 2번 수행하여 하나의 이진 탐색은 첫 위치를 찾게 하고 다른 하나의 이진 탐색은 마지막 위치를 찾게 만들면 된다    countByRange() 함수는 실제로 다양한 코딩테스트에서 효과적으로 사용될 수 있어서 잘 숙지하기파이썬에서 bisect_left() 와 bisect_right() 은  C++ 의 upper_bound() ,  lower_bound() 와 사실상 같다 (이 코드 뒤에 꺼는 강의, 깃허브에 다 없다 ㅠㅠ)

절단기 높이를 높이면 잘린 떡의 길이는 점점 줄어들고 절단기 높이를 낮추면 잘린 떡의 길이가 점점 증가한다 이러한 특징 때문에 우리는 이진탐색을 수행할 수 있는 것이다 또한 이렇게 큰 탐색 범위를 보면 이진탐색을 떠올려야 한다 왜냐하면 단순히 선형 탐색을 수행하면 시간 초과 판정을 받을 확률이 높기 때문이다   탐색범위를 0부터 19로 설정했다.

이진 탐색은 정렬되어 있는 리스트에서 특정한 데이터를 빠르게 탐색할 수 있도록 해주는 탐색 알고리즘이다   [ 이진 탐색 예시 ]  중간점을 구할 때 소수점 이하는 제거한다.   끝점이 중간점 왼쪽으로 움직여 새로운 끝점이 된다    시작점이 중간점 오른쪽으로 움직여서 새로운 시작점이 된다.      이진탐색 파이썬 예시 1 :  재귀함수 버전   이진탐색 파이썬 예시 2 :  반복문 버전    C++에서는 하나의 배열 정보를 받을 때 1. 포인터를 사용하거나 2. vector 라이브러리를 사용하되  별도로 변수를 카피하지 않고 이미 존재하는 vector 변수의 래퍼런스를 전달해야 한다 만약 &(앰퍼샌드)를 빼주게 되면 이 함수를 호출할 때 기존 vector에 담겨 있던 값을 카피하기 때문에 시간복잡도가..

병합정렬은 데이터를 가장 작은 단위까지 분할한 다음 정렬하면서 다시 병합하는 알고리즘이다. 병합정렬의 시간복잡도는  O(N*logN) 이다.  (약 2천만)  [병합정렬 예시 1]  [병합정렬 예시 2] :  데이터의 총 개수가 홀수인 경우 데이터의 총 개수가 홀수일 경우에는 분할 과정이 남았지만 더 이상 분할할 수 없는 그룹이 존재하게 된다. 이 때는 모든 분할 과정이 끝날 때까지 계속 1개의 원소를 유지합니다.     분할정복 알고리즘 :  하나의 문제를 동일한 유형의 작은 문제들로 분할한 다음에 작은 문제에 대한 결과를 조합해서 큰 문제를 해결하는 방식의 알고리즘분할 정복 알고리즘은 보통 재귀 함수로 구현된다는 특징이 있다.

파이썬에서 제공하는 기본 정렬 라이브러리는  ( sort() )병합 정렬을 기본으로 한 하이브리드 형식의 정렬 알고리즘을 제공하고 있다.        자바에서 내림차순 정렬을 할 때는 Collections 라이브러리의 reverseOrder() 메서드를 사용하기

계수 정렬은 가장 작은 데이터부터 가장 큰 데이터까지의 모든 범위를 포함할 수 있는 크기의 배열을 만들어야 하기 때문에 상대적으로 공간 복잡도가 높지만, 조건만 맞다면 다른 방법보다 더 효율적인 알고리즘이다 계수 정렬은 데이터를 정수 형태로 표현할 수 있을 때 사용 가능하다. 계수 정렬은 가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담길 수 있는 크기의 리스트를 선언해야 한다       계수 정렬 코드에서 중첩 for문을 보면 바깥쪽 for문이 K 번 돌아가고 안쪽 for문은 수행 횟수가 N 번이므로  시간복잡도는 O(K + N) 이다  계수정렬은 동일한 값을 가지는 데이터가 여러 개 나올 때 효과적이다.