다락방

분할정복(Divide and Conquer) 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방식 대표적인 예 퀵정렬 합병정렬 이진탐색 선택문제 고속 푸리에 변환 분할정복의 설계 Divide - 원래 문제가 분할하여 비슷한 유형의 더 작은 하위 문제로 분할 가능할때까지 나눈다. Conquer - 각 하위 문제를 재귀적으로 해결한다. 하위 문제의 규모가 나눌 수 없는 단위가 되면 탈출 조건을 설정하고 해결한다. Combine - Conquer한 문제들을 통합하여 원래 문제의 답을 얻어 해결한다. Divide를 제대로 나누면 Conquer 과정은 자동으로 쉬워진다. 그래서 Divide를 잘 설계하는 것이 중요하다. 분할정복 알고리즘은 재귀 알고리즘이 많이 사용되는데, 이 부분에서 분할정복..

이진탐색(BinarySearch) 이진탐색(이분 탐색) 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 이진탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 변수 3개(start,end,mid)를 사용하여 탐색한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진탐색의 과정이다. def binary_search(target,start,end): if start >= end: return 0 mid = (start + end) // 2 if target == mid: return 1 elif target > mid: start = mid + 1 else: end = mid -1 retu..

완전탐색(ExhaustiveSearch) 간단히 가능한 모든 경우의 수를 다 체크해서 정답을 찾는 방법. 무식하게 한다는 의미로 ‘BruteFroce’ 라고도 부르며, 직관적이여서 이해하기 쉽고 문제의 정확한 결과값을 얻어낼 수 있는 가장 확실하며 기초적인 방법이다. 완전탐색 기법을 활용하는 방법 해결하고자 하는 문제의 가능한 경우의 수를 대략적으로 계산한다. 가능한 모든 방법을 다 고려한다. BruteForce기법 - 반복/조건문을 활용해 모두 테스트 하는 방법 순열(Permutation) - n개의 원소 중 r개의 원소를 중복 허용 없이 나열하는 방법 재귀호출 비트마스크 - 2진수 표현 기법을 활용하는 방법 BFS,DFS를 활용하는 방법 실제 값을 구할 수 있는지 적용한다.

검색(Search) 검색과 키 키(Key) - 데이터의 일부 검색의 종류 배열검색 선형검색 - 무작위로 늘어놓은 데이터 집합에서 검색수행 이진검색 - 일정한 규칙으로 늘어놓은 데이터 집합에서 아주 빠른 검색 수행 해시법 - 추가 삭제가 자주 일어나는 데이터 집합에서 아주 빠른 검색 수행 체인법 - 같은 해시값 데이터를 연결리스트로 연결 오픈 주소법 - 데이터를 위한 해시값이 충돌할 때 재해시 하는 방법 연결리스트 검색 이진 검색 트리 검색 선형 검색(LinearSearch) 직선 모양(선형)으로 늘어선 배열에서 검색하는 경우에 원하는 키값을 가진 원소를 찾을때까지 맨앞부터 스캔하여 순서대로 검색하는 알고리즘 선형 검색의 종료조건 검색할 값을 찾지 못하고 배열의 맨 끝을 지나간 경우 - 검색 실패 검색할 ..

정렬_Sorting Key를 항목값의 대소 관계에 따라 데이터 집합을 일정한 순서로 바꾸어 늘어놓는 작업 오름차순 ascend_order - 값이 작은 데이터를 앞쪽에 배치 내림차순 descend_order - 값이 큰 데이터를 앞쪽에 배치 정렬 알고리즘의 안정성 정렬 알고리즘은 안정적인(stable), 안정적이지않은(unstable) 정렬로 나뉜다. 안정적인 정렬알고리즘은 값이 같은 원소의 순서가 정렬 후에도 유지된다. 안정적이지 않은 정렬은 순서가 유지 된다는 보장을 할 수 없다. 내부정렬 외부정렬 내부정렬(internal sorting) - 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우 사용하는 알고리즘 외부정렬(external sorting) - 정렬할 데이터가 많아서 하나의 배열에 저..

정수론_NumberTheory 정수의 성질을 다루는 수학의 한 분야이다. 우리가 왜 why? 공부해야 하는가 현대 암호학은 주로 정수론에서 다루어지는 수학적인 성질을 바탕으로 하기에, 암호화 알고리즘을 이해하고 구현하기 위해서는 정수론에 대한 공부가 필요하다. 컴퓨터에서 정수는 정확한 값을 가질 수 있다. 실수형 타입의 경우 반올림 오차(round off error)가 발생하기 때문에 이로 인한 문제가 발생할 수 있다. 정수와 자연수 소수를 중심적으로 다룬다. 소수_PrimeNumber 정수론에서 가장 중심적으로 연구하는 것 1과 자기 자신만을 약수로 가지는 수 에라토스테네스의 체 소수를 찾는 방법 √n 까지의 배수를 지운다 노가다 방식이라 상당히 무식한 방식이지만 특정 범위가 주어지고 그 범위 내 모든..