본문 바로가기

분류 전체보기

알고리즘의 정당성 증명들 (귀납법, 귀류법, 비둘기집의 원리, 순환소수 찾기, 구성적 증명) 귀납법 귀납(歸納, 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의 데이터를 다룰 수 있게 해.. 더보기
[Java] 사용자 정의 객체 정렬하기 Comparable과 Comparator 인터페이스 사용자 정의 객체 배열에서 sort() 메소드를 사용하기 위해 Comparable과 Comparator 인터페이스를 이용한다 또, TreeSet의 객체와 TreeMap의 키는 저장과 동시에 자동 오름차순으로 정렬되는데 이는 정렬을 위해 Comparable 인터페이스의 compareTo() 메소드를 구현하고있다 다음 코드는 Comparable 구현 클래스이다 public class Person implents Comparable { public String name; public int age; public Person(String name, int age) { this.name = name; this.age = age; } //getter //setter @Override public int compar.. 더보기
[백준 9095번][Java] 1, 2, 3 더하기 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 풀이 n일 때의 값을 생각해보자 1, 2, 3의 수만 사용할 수 있고, 순서가 다른 방법을 독립적인 방법으로 친다는 것을 생각해야한다 무작정 하나씩 세기에는 알고리즘의 속도도, DP의 방법론도 맞지 않는 것 같다 그렇다면 이미 세어진 갯수에서 +1, +2, +3 을 뒤에다 붙이는 방법은 어떨까? dp[3] 1 1 1 2 1 1 2 3 일 때, dp[4] 1 1 1 +1 2 1 +1 1 2 +1 3 +1 임을 알.. 더보기

티스토리툴바