2) 함수와 관계

함수: 한 집합의 원소를 각각 다른 집합의 단일 원소로 배정하는 규칙 f가 한 함수라 한다면 첫번째 집합을 함수 f의 정의역이라 하며, 두번째 집합을 치역이라 한다. 이러한 함수를 아래와 같이 표기한다. $$f:S_1→S_2$$ 전체 함수, 부분함수: 함수 f의 정의역이 S_1과 같은경우 f를 "전체함수"라 하고, 그렇지 않을경우 "부분함수"라한다. 순위: f(n)과 g(n)을 정의역이 양의 정수들의 부분집합인 함수라 했을때, 충분히 큰 모든 n에 대해 $$f(n)=c|g(n)|$$이 성립하는 상수 c가 존재할 시 f의 순위가 g의 순위보다 낮지 않다고 한다. 이를 아래와 같이 표기한다. $$f(n)=Ω(g(n))$$ 그리고 $$c_1|g(n)|

• format_list_bulleted 계산이론
• · 2021. 3. 19.
• textsms

1) 집합

집합이란? 집합이란 원소들의 모임이다. x가 집합 S의 원소임을 나타내면 "x∈S"로 표기한다. ex) 정수 0,1,2를 포함하는 집합 : S={0,1,2} 집합 표현시에 의미가 명확한 경우에는 생략부호를 사용 할 수 있다.집합 {a,b,c....,z}는 알파벳 소문자들의 집합이고, 집합 {2,4,6,8.....}은 정수중에 짝수의 집합을 의미한다. 필요에 따라서는 짝수들의 집합을 아래와 같이 표현할 수 있다. S={i:i>0, i is even} 이를 읽을때는 "S는 0보다 크고 짝수인 모든 i들의 집합"라 한다. 많이 사용되는 집합연산 합집합: A∪B={x:x∈A or x∈B} 교집합: A∩B={x:x∈A and x∈B} 차집합: A-B={x:x∈A and x∈B} 드모르간 법칙 부분집합: 어떤 집합..

• format_list_bulleted 계산이론
• · 2021. 3. 16.
• textsms

백준 2798번 블랙잭(Java)

구할수 있는 모든 경우의 수를 구해, 그 수중에서 목표인 수에 가장 가까운 수를 출력하는 문제. 반복문으로 n번째 카드를 기준으로 삼고 그 카드를 더할수 있는 모든 경우의 수를 더해 배열에 저장후, 목표값과 가장 가까운 수를 출력하도록 했다. import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner=new Scanner(System.in); int card_num=scanner.nextInt(); int[] card_list=new int[card_num]; List card_sum=new..

• format_list_bulleted Algorithm/백준
• · 2021. 3. 15.
• textsms

백준 11729번 하노이탑 이동순서(Java)

유명한 문제. 복잡하게 생각할 수록 어려운 문제다. 장대의 개수가 3개보다 많을시 난이도역시 오르는 문제. 하지만 3개여서 매우 쉽다. 분할정복을 사용해서 풀면 매우 간단하다. 가장 큰 원판을 3번째 장대로 옮기는걸 n번 반복하면 된다. 즉 n번째의 원판을 이동시키려면 n-1번째까지의 원판을 모두 2번째 장대로 옮겨야 된다. 그 후 2번째 장대로 옮겨놓은 판을 다시 3번째 장대로 옮기기만 하면 끝. import java.util.Scanner; public class Main { static void hanoi(int n,int start,int middle,int to){ if(n==1) { System.out.println(start + " " + to); return; } hanoi(n-1,star..

• format_list_bulleted Algorithm/백준
• · 2021. 3. 13.
• textsms

백준 2447번 별찍기-10(Java)

재귀를 이용한 별찍기다. 2시간정도 낑낑거리면서 풀었다. 누구나 규칙을 찾을수 있지만, 그것을 알고리즘으로 구현하는게 어려운 문제다. 일단 밑의 코드로 실행을 시키면 실행은 된다만, 시간초과가 뜬다. 3^6(729) 입력시 걸리는 시간이 1초가 넘어간다. 문제에서는 3^7 까지가 조건이니 시간초과. 풀이방법 * * * * * * * * 크기가 3인 패턴은 가운데 하나만 비어있는 패턴이다. * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 크기가 9인 패턴을 보자. 규칙성이 보인다. 크기가 3인 패턴과 같은 규칙이다. 다른점은 *..

• format_list_bulleted Algorithm/백준
• · 2021. 3. 12.
• textsms

백준 10870번 피보나치 수 5(Java)

피보나치의 수를 구하는 문제. f(n)=f(n-1)+f(n-2)가 성립하기에 이를 기반으로 풀면되는 쉬운 문제이다. 이때 재귀의 특징상 메모리의 낭비가 심한데 낭비를 줄이는 방법은 위 사진에 나와있듯이 f(19)=f(17)+f(18)이다. 그런데 f(18)을 구하는데 f(17)의 값을 계산한 적이 있으므로 f(17)의 값을 어딘가로 빼놓고 f(19)를 계산할 때 f(18)과 f(17)을 더해 계산하면 메모리를 절반가량 아낄 수 있다. 다만 이 풀이법에서는 아직 구현하지 않았다. import java.util.Scanner; public class Main { int fibo(int count){ if(count==0) return 0; if(count==1) return 1; return fibo(cou..

• format_list_bulleted Algorithm/백준
• · 2021. 3. 12.
• textsms