Algorithm 썸네일형 리스트형 [C] 삼분 탐색(Ternary Search)과 이진 탐색(Binary Search) 이진 탐색(binary search)은 정렬된 데이터 집합을 이분화하면서 탐색하는 방법이다 다음과 같은 코드를 사용한다 int biSearch(int l, int r, int target) { // list에서 target 찾기 int mid; while (l < r) { mid = (l + r) / 2; if (list[mid] < target) l = mid + 1; else r = mid; } //return idx값 return r; //or l } 다음은 이진 탐색을 이용한 알고리즘이다 - snupi.tistory.com/71 [백준 12015번][C] 이진 탐색(Binary Search)을 이용한 LIS(최장 증가 수열) 최장 증가 부분 수열, LIS(Longest Increasing Subs.. 더보기 [C] 소수 판별하기 / 에라토스테네스의 체 / 소인수 분해 1. 소수 판별하기 소수는 양의 약수가 1과 자기 자신 두 개 뿐인 자연수를 의미한다 정수를 입력하였을 때 이를 판별할 수 있는 가장 단순한 알고리즘을 알아보도록 하자 1, 2 예외 처리 후, 3 ~ n-1의 모든 수를 순회하며 n의 약수가 있는지 확인하는 방법이 있다 최적화 1) √n * √n = n 이므로, n-1까지 순회하는 대신, √n까지만 순회한다 최적화 2) 2를 예외 처리한다면 그 외 모든 짝수는 합성수이므로 배제한다 두 가지의 최적화를 거친 후, 코드는 다음과 같다 #include #include #include //bool, true, false #include //sqrt() _Bool isPrime(int n) { if (n 더보기 알고리즘의 정당성 증명들 (귀납법, 귀류법, 비둘기집의 원리, 순환소수 찾기, 구성적 증명) 귀납법 귀납(歸納, induction)은 개별적인 특수한 사실이나 현상에서 그러한 사례들이 포함되는 일반적인 결론을 이끌어내는 추리의 방법이다 귀납법을 이용해 우리는 다음과 같이 반복문의 정당성을 증명할 수 있다 1. 초기 조건 : 반복문 진입시에 불변식이 성립함을 보인다 2. 유지 조건 : 반복문 내용이 불변식을 깨뜨리지 않음을 보인다 3. 반복문 종료시에 불변식이 성립하면 반복문이 항상 정답을 구함을 보인다 예시로 이진 탐색으로 반복문 불변식을 살펴보자 snupi.tistory.com/62 [Java code] 이진 탐색(binary search) - 선형 이하 시간(sublinear time) 알고리즘 100,000개의 순차적인 사진들 중에서 한 장의 사진을 찾고싶다면, 몇 장의 사진을 확인해야 할.. 더보기 [Java code] 이진 탐색(Binary Search) - 선형 이하 시간(Sublinear Time) 알고리즘 100,000개의 순차적인 사진들 중에서 한 장의 사진을 찾고싶다면, 몇 장의 사진을 확인해야 할까? 50,000번 째의 사진을 확인하고 내가 찾는 사진이 그 이전인지 이후인지 알 수 있다면 계속 절반으로 나누니 밑이 2인 log를 사용하면 된다 (25,000 -> 12,500 -> ...) 따라서 확인해야 하는 사진의 장수는 대략 밑이 2인 logN이라고 할 수 있다 위의 알고리즘을 이진 탐색(binary search)라고 부르고 다음과 같이 정의할 수 있다 biSearch(A[], x) = 오름차순으로 정렬된 배열 A[]와 찾고 싶은 값 x가 주어질 때 A[i-1] 더보기 스캐폴딩 코드(Scaffolding Code) 란 무엇인가 ? 스캐폴딩(Scaffolding)이라 함은 "무대의 높은 곳에서 일할 수 있도록 설치하는 임시 가설물. 재료 운반이나 작업원의 통로 및 작업을 위한 발판이 된다." 이라고 사전에 나와있다 이는 간단히 비계로, 건축 공사장의 임시 지지 구조물이다 이를 프로그래밍 언어로 재정의해보자 "데이터베이스의 각 테이블에 대한 웹 페이지를 자동으로 생성하는 Dynamic Data 요소를 말한다. 자동 생성된 웹 페이지를 통해 각 테이블에 대해 만들기, 읽기, 업데이트 및 삭제(CRUD) 작업을 수행 할 수 있습니다. 스캐폴딩은 페이지 템플릿, 엔터티 페이지 템플릿, 필드 페이지 템플릿 및 필터 템플릿으로 구성된다." 찾아본 바 위와 같이 설명되어있었으며, 이는 "웹상에서 간단한 조작으로 DB의 데이터를 다룰 수 있게 해.. 더보기 이전 1 2 3 4 5 6 7 다음
