정리에 앞서, 저는 현재 지거국 3학년으로 재학 중인 공대생입니다. 여기에 나와있는 내용들은 제가 직접 공부하고 요약해서 쓰기 때문에 정확하지 않은 정보가 있거나, 원하는 정보를 얻지 못하실 수 있습니다. 최대한 객관적이고 다양하게 준비해서 올리도록 노력하겠습니다. 자료의 출처나 내용에 대한 질문은 댓글이나 hcbeom9635@gmail.com으로 보내주시면 감사하겠습니다.
교재는 Steven C. Chapra, Applied Numerical Methods with MATLAB for Engineers and Scientists (4 th edition), McGraw-Hill, 2019의 재본판을 사용했습니다.
근(Roots)을 찾는 방법(Method)들
수치해석은 기본적으로 '해를 찾아가는 방법'들을 배우는 과목입니다. f(x) = 0 을 만족하는 x의 값을 해 또는 근 이라고 부릅니다. 우리가 수학을 배울 때는 일반적인 함수들 (ex 1차,2차,3차 함수)을 주로 다뤄서 상대적으로 해를 구하기가 쉬웠습니다. 하지만 더 복잡한 함수의 근을 구해야 할 때는 기존의 방법이 비효율적일 수 있습니다.즉, f(x) = 0의 방정식으로 푸는 것이 아닌, 여러 과정을 통해서 근삿값을 구한 후, 점점 근에 점근하는 식으로 찾는 것입니다. 그것이 바로 수치해석의 목적입니다.
5장에서는 Bracketing Methods를, 6장에서는 Open Methods를 배웁니다. 앞선 글에서 말씀드렸지만, Bracketing Method와 Open Method는 각각 장단점이 있습니다. 그 내용은 아래 링크를 보시면 될 겁니다.
6장에서는 총 4가지 방법의 수치해법 과정을 배웁니다.
1. Simple Fixed-Point Method
2. Newton-Rapshon Method
3. Secant Method (Modified Secant Method)
4. Brent's Method -> Bracketing Method + Open Method
이번 장에서는 Simple Fixed-Point Method만 알아보겠습니다.
Simple Fixed-Point Method란?
x=g(x)의 함수 형태를 사용하여 근을 찾아내는 수치해법이다.
하나의 예시를 들어서 설명해보겠다.
f(x)의 형태가 주어질 때 x=g(x)의 형태로 변환한다. 그러면 f(x)=g(x)라는 방정식이 나오게 되고, 두 그래프의 교점의 x좌표가 근이 되는 것이다.
또한 Bracketing Method와는 다르게 구간이 필요없어서 적당한 초기값을 설정해서 근을 구하면 된다.
예시는 초기값을 0으로 두고 풀었을 경우이다.
또한 근사 오차와 참 상대 오차도 구했다.
여기서 좀 더 자세히 보면, 참 오차가 계속 비슷한 비율로 줄어드는 것을 볼 수 있습니다.
그 이유는 평균값 정리와 관계가 있습니다.
마지막으로 Open Method는 발산하는 단점이 있다고 했는데, Simple Fixed-Point Method에서 발산하는 경우를 알아보겠습니다. 첫 초기값인 X0에 대해서 도함수의 절댓값이 1보다 크면 발산하는 경향이 있습니다. 아래의 예시를 보면 더 와닫을 것입니다.
정리에 앞서, 저는 현재 지거국 3학년으로 재학 중인 공대생입니다. 여기에 나와있는 내용들은 제가 직접 공부하고 요약해서 쓰기 때문에 정확하지 않은 정보가 있거나, 원하는 정보를 얻지 못하실 수 있습니다. 최대한 객관적이고 다양하게 준비해서 올리도록 노력하겠습니다. 자료의 출처나 내용에 대한 질문은 댓글이나 hcbeom9635@gmail.com으로 보내주시면 감사하겠습니다.
교재는 Steven C. Chapra, Applied Numerical Methods with MATLAB for Engineers and Scientists (4 th edition), McGraw-Hill, 2019의 재본판을 사용했습니다.
근(Roots)을 찾는 방법(Method)들
수치해석은 기본적으로 '해를 찾아가는 방법'들을 배우는 과목입니다. f(x) = 0 을 만족하는 x의 값을 해 또는 근 이라고 부릅니다. 우리가 수학을 배울 때는 일반적인 함수들 (ex 1차,2차,3차 함수)을 주로 다뤄서 상대적으로 해를 구하기가 쉬웠습니다. 하지만 더 복잡한 함수의 근을 구해야 할 때는 기존의 방법이 비효율적일 수 있습니다. 즉, f(x) = 0의 방정식으로 푸는 것이 아닌, 여러 과정을 통해서 근삿값을 구한 후, 점점 근에 점근하는 식으로 찾는 것입니다. 그것이 바로 수치해석의 목적입니다.
5장에서는 Bracketing Methods, 6장에서는 Open Method를 배우고, Bracketing Methods + Open Methods = Brent's Methods도 뒤에 나옵니다.
우선 5장의 Bracketing Methods를 알아보겠습니다.
Bracketing Methods
Bracketing Methods는 구간을 정하고 근을 추정하는 방법입니다. 그렇기에 구간을 위한 2개의 초기값을 요구합니다.
장점은 정확하게 근을 추정할 수 있다는 것이고,
단점은 속도가 느리다는 것입니다.
뒤에서 배우겠지만 Open Methods는 반대로 속도가 빠르지만, 정확하지 않아서 발산할 가능성이 있습니다.
Bracketing Methods에는 Bisection Method와 False position Method가 있습니다.
근을 추정하는 구간을 정했을 때 나타는 여러 경우들
(a), (b) 경우
(c), (d) 경우
일반적으로 두 경계치 간의 함수값의 곱이 양수이면 근이 존재하지 않고, 함수값의 곱이 음수이면 근이 존재한다. 그러나 (e), (f)의 경우처럼 두 경계치의 값이 양수임에도 근이 존재할 수 있고, 음수여도 근이 존재하지 않거나 중근이 존재할 수 있다. 즉, 여러 경우에 대해 정확한 알고리즘 개발은 매우 힘든일이다. 그래서 수치해법을 사용해야 하는 것이다.
Bracketing Method에서는 주로 두 경계치를 알맞게 정했다는 가정하에 시작하므로, 두 경계치의 곱을 통해서 근을 찾아낼 수 있다. 그 방법을 Incremental search라고 한다.
(1). Bisection Methods
absolute error는 bisection method에서 나타나는 에러이다. 이것을 통해 원하는 횟수 n을 구할 수 있으며, 반대로 원하는 횟수 n번에 대한 에러를 찾아낼 수도 있다.
(2). False Position
근을 쉽게 찾기 위해 경계의 함수크기를 고려한다. 주로 Bisection보다 효과적이고, 오차가 빨리 감소하는 장점이 있다.
항상 bisection보다 좋은 것은 아닌데, 이렇게 심한곡률을 가진 함수는 너무 느리게 수렴하는 단점이 존재한다.
정리에 앞서, 저는 현재 지거국 3학년으로 재학 중인 공대생입니다. 여기에 나와있는 내용들은 제가 직접 공부하고 요약해서 쓰기 때문에 정확하지 않은 정보가 있거나, 원하는 정보를 얻지 못하실 수 있습니다. 최대한 객관적이고 다양하게 준비해서 올리도록 노력하겠습니다. 자료의 출처나 내용에 대한 질문은 댓글이나 hcbeom9635@gmail.com으로 보내주시면 감사하겠습니다.
저는 공부할 때 Discrete Mathematics - Richard Johnsonbaugh 7th 제본판을 사용했습니다.
이산수학 1장. Sets and Logic
연산자(Quantifier)
이산수학 1장에서는 두 가지의 연산자를 배웁니다.
Universal Quantifier ∀
Existential Quantifier ∃
입니다.
Universal Quantifier ∀xP(x)
"for every" , "for all" 즉, 모든 x에 대해 만족하는 명제를 나타낼 때쓰입니다. Universal Quantifier 명제가 참인지 거짓인지 판별하기 위해서는 반례(CounterExample)를 들어서 판별할 수 있습니다. 모든 x에 대해 만족하는 명제가 거짓이라면, 그 명제를 만족하지 않는 x를 찾으면 됩니다. 수식으로 설명해보겠습니다.
Ex)
Existential Quantifier ∃
"there exist" 즉, 명제에 해당하는 x의 값이 하나라도 '존재'하는지의 여부를 확인할 때 쓰입니다. 예시를 통해 확인해보겠습니다.
Ex)
그렇다면 이 두 가지를 동시에 쓸 수는 없을까요? 당연히 쓸 수 있습니다. 그런 경우를 Nested Quantifier라고 합니다.
Nested Quantifier
Ex)
모든 x에 대해 식을 만족하는 모든 y가 있다면 명제는 참입니다. Nested Quantifier에 드모르간 법칙을 사용하면 아래와 같이 됩니다.
드모르간 법칙을 사용할 때 주의할 점은, ∀이 not을 취하면 ∃이 되고, ∃이 not을 취하면 ∀가 되는 것이 핵심입니다. 또한 명제에도 Not을 포함해줘야 합니다.
정리에 앞서, 저는 현재 지거국 3학년으로 재학 중인 공대생입니다. 여기에 나와있는 내용들은 제가 직접 공부하고 요약해서 쓰기 때문에 정확하지 않은 정보가 있거나, 원하는 정보를 얻지 못하실 수 있습니다. 최대한 객관적이고 다양하게 준비해서 올리도록 노력하겠습니다. 자료의 출처나 내용에 대한 질문은 댓글이나 hcbeom9635@gmail.com으로 보내주시면 감사하겠습니다.
저는 공부할 때 Discrete Mathematics - Richard Johnsonbaugh 7th 제본판을 사용했습니다.
이산수학 1장. Sets and Logic
명제란?
명제(Proposition)이란 참인지 거짓인지 결정할 수 있는 문장을 뜻합니다. 우리는 일상 속에서 수많은 대화를 주고받습니다. 그 말 중에서는 명제인 것도 있고 아닌 것도 있습니다. 예를 들어서 확인해보겠습니다.
ex)
1) 7을 나눌 수 있는 양의 정수는 오직 2와 5이다. -> 거짓으로 판단되므로 명제가 맞다.
2) 모든 양의 정수 n에 대해, n 보다 큰 소수(prime number)가 있다. -> 참으로 판단되므로 명제가 맞다.
3) x + 10 = 14 -> x의 값에 따라 참 또는 거짓이 될 수 있으므로 명제가 아니다. 즉, 참인지 거짓인지 판명 불가.
p 와 q 가 명제 일 때,
conjunction (AND) : p ∧ q disjunction (Inclusive-OR) : p v q disjunction (Exclusive-OR) : p v q negation (NOT) : ~ p , ¬ p
Truth Table
명제는 다양한 연산자를 갖고 있는데, 이 연산자에는 '연산우선순위'가 존재합니다. 어려울 것 없습니다. 괄호가 없을 때 연산자 우선순위는 (not) -> (and) -> (or)의 순으로 연산하면 됩니다.
Conditional Proposition(조건 명제)
조건 명제에 대해 알아보겠습니다. 흔히 얘기하는 "p 이면 q 이다"라는 것이 조건 명제입니다. p는 가정이며, q 는 결론에 해당합니다. 이것을 수식으로 써서 표현하면 p -> q 가 됩니다. 그리고 또 한 가지, 영어로 표현하면 "if p, then q" 또는 "p only if q"인 경우도 모두 p->q와 같은 의미로 받아들이면 됩니다.
어떤 명제의 진리값이 같다면 명제 P와 Q는 logically equivalent하다고 하고, 수식으로는 방정식의 '='처럼 세 줄로 나타냅니다.
Biconditional Propositions
바이컨디셔널 프로포지션은 한국말로 '필요충분조건' 입니다. 어렵게 왜 영어로 썼냐구요? 대학가면 다 그렇답니다...
여튼 필요충분조건은 문제에서 " p if and only if q"라고 많이 씁니다. 논리식과 여기표는 다음과 같습니다.
역(Converse) & 대우(Contrapositive)
역과 대우는 아주 중요한 개념입니다. 주어진 명제가 참인지 거짓인지 판별할 때 역이나 대우를 이용하며 증명하는 경우도 있으니까요..! 역과 대우의 여기표는 다음과 같습니다.
Arguments
Deductive reasoning(연역적 추론) : 연속적인 명제들로부터 결론을 도출하는 과정
여기서 Argument는 가정들이 모두 참일 경우에 결론이 참이라는 것을 말합니다. 만약 가정에서 거짓이 존재한다면 결론은 거짓입니다. 수식으로 살펴보겠습니다.
Rules of Inference (추론의 규칙)
이산수학을 배웠다면 여기 부분에서 가장 골머리가 아플 것이다. 그러나 차근차근 공부하다보면 알게된다. 여기 부분은 나중에 더 자세하게 써야겠다... 일단 외워!
정리에 앞서, 저는 현재 지거국 3학년으로 재학 중인 공대생입니다. 여기에 나와있는 내용들은 제가 직접 공부하고 요약해서 쓰기 때문에 정확하지 않은 정보가 있거나, 원하는 정보를 얻지 못하실 수 있습니다. 최대한 객관적이고 다양하게 준비해서 올리도록 노력하겠습니다. 자료의 출처나 내용에 대한 질문은 댓글이나 hcbeom9635@gmail.com으로 보내주시면 감사하겠습니다.
저는 공부할 때 Discrete Mathematics - Richard Johnsonbaugh 7th 제본판을 사용했습니다.
이산수학 1장. Sets and Logic
집합(Set)이란?
Set(집합)은 서로 다른 물체들의 모음 입니다. 그리고 집합 안에 있는 것을 Elements(원소)라고 불립니다.
예를 들어 집합 A에 원소 x가 있다면 아래와 같이 간단하게 표현합니다.
x라는 원소를 조금 더 구체화 시켜서 예를 들어봅시다.
A안에 {1,3,5,7}라는 원소가 있어서 1은 A에 속한다고 볼 수 있습니다.
또한 B안에는 k가 0~5까지의 상수이므로 {1,3,5,7,9,11}라는 원소가 있어서 3또한 A에 속합니다.
이렇게 간단하고 유한한 집합을 Finite sets이라고 불립니다.
반대로 무한한 집합을 Infinite sets이라고 합니다. 무한한 집합은 무엇이 있을까요? 대표적인 예만 들어보자면
정수의 집합은 무한한 집합입니다.
이렇듯 사용자에 따라 여러 가지 종류의 집합을 만들 수 있습니다. X, Y라는 집합이 있을 때, X의 모든 원소가 Y에 포함된다면 X는 Y의 부분집합(subset)이며 기호로는 아래처럼 나타낼 수 있습니다.
또한 X가 Y의 부분집합일 때 X≠Y이면 X는 Y의 진부분집합(proper subset)라고 하며 기호로는 다음과 같습니다.
여기서 중요한 점은, 대부분 교육과정에서는 부분집합과 진부분집합의 표기를 혼용해서 사용하는 것입니다. 사실 중요한 부분은 아니므로 그냥 넘어가도 좋습니다. 만약 교수님께서 구분해서 사용하신다면 그렇게 쓰고, 아니면 아닌 대로 쓰면 됩니다..하하
예를 들어 아래와 같은 집합 A,B가 있으면 A는 B의 부분집합으로 볼 수 있습니다.
생소한 집합인 멱집합(Power Set)와 기수(Cardinality)라는 것을 알아보겠습니다.
멱집합은 집합 X의 모든 부분 집합의 집합입니다.
직관적으로 알 수 있도록 식으로 보면 아래와 같습니다.
기수(Cardinality)는 집합 안의 원소의 수를 뜻합니다. 기호로는 절댓값처럼(A의 기수 = |A|) 쓰면 됩니다.
집합 안에는 또 다른 집합이 있는 경우도 있습니다. 그런 경우를 벤다이어그램으로 나타내면 아래와 같고, 이러한 모음을 Pairwise Disjoint라고 합니다.
Partition이라는 것은 X가 nonempty subsets S의 모음일 때, X안의 모든 원소들이 S의 한 멤버 안에만 속해 있다면 S는 X의 partition이라고 합니다. 즉, S가 X의 partition이면 S는 pairwise disjoint하다고 볼 수 있습니다.
글로만 보면 확 와닿지 않는데, 예시를 보면 쉽게 이해할 수 있습니다.
마지막으로 Cartesian Product(데카르트 곱)에 대해서 알아보겠습니다. 데카르트 곱은 기호로 X x Y이며 정의는
x ∈ X and y ∈ Y 인 모든 순서쌍 (x,y)들의 집합이다. 데카르트 곱의 예시를 보고 이해해보겠습니다.
지금까지 집합에 대한 내용을 알아봤습니다. 사실 집합은 중학생 때부터 배운 것들이라서 이해하는데 큰 어려움이 없습니다. 그러나 생소한 용어와 영어로 나오니까 몰랐던 부분은 체크하는 게 좋습니다. 다음장에서는 명제를 알아보겠습니다.
이문제도 굉장히 쉬운 문제이다. 배열과 배열의 인덱스만 이해한다면 1분조차 안걸려서 풀 수 있다.
그러나... 처음 알고리즘을 공부하거나 배열에 익숙하지 않는다면 조금 힘들 수 있다!!
괜찮다. 지금부터 배우면 되니까.
나도 완벽하지 않은데 누굴 가르치겠냐만은... 같이 공부하는 느낌으로 해보는 거다!
1. 배열을 사용하면 쉽게 해결!
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner input = new Scanner(System.in);
int[] array = new int[9];
int max = 0;
int index = 0;;
for(int i = 0; i < array.length; i++){
array[i] = input.nextInt();
if(array[i] > max){
max = array[i];
index = i;
}
}
System.out.println(max);
System.out.println(index + 1);
}
}
여기서 마지막에 index + 1을 출력한 이유는, 배열의 번호는 0번부터 시작하기 때문이다.
문제의 출력 값을 보면 8번째의 수는 '8'번째의 위치에 있다고 했다. 만약 index를 그대로 출력했다면 7이 나왔을 것이다.
다른 블로그를 보니까 대부분 StringTokenizer를 사용하셨더라고요! 당연히 StringTokenizer 클래스가 간단하죠. 그러나 알고리즘에 대해 아직까지는 노가다가 더 편한 저는... charAt으로도 해봤습니다. 막상 풀어보니 메모리와 시간은 비슷하더라고요! 위에가 charAt, 아래가 StringToknizer 입니다!
천천히 파헤쳐보겠습니다~
1. StringTokenizer를 활용한 자바 코드
import java.util.StringTokenizer;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner str = new Scanner(System.in);
String s = str.nextLine();
str.close();
StringTokenizer st = new StringTokenizer(s, " ");
System.out.println(st.countTokens());
}
}
완전 간단하죠~? StringTokenizer가 띄어쓰기를 기준으로 단어를 분류하고, 그 분류된 단어들을 토큰이라고 합니다.
그 토큰의 개수만 출력해주면 바로 해결!
이번엔 charAt을 사용한 방법을 보여드리겠습니다.
2. charAt을 사용한 방법
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner input = new Scanner(System.in);
String str;
int cnt = 0;
str = input.nextLine();
for(int j = 0; j < str.length(); j ++){ //우선 공백의 개수를 먼저 세아린다
if(str.charAt(j) == ' '){
cnt++;
}
}
if(str.charAt(0) != ' ' && str.charAt(str.length()-1) != ' '){ //첫 번째와 마지막이 공백이 아닌 경우
cnt = cnt + 1;
}
if(str.charAt(0) == ' ' && str.charAt(str.length()-1) == ' '){ //첫 번째와 마지막이 공백인 경우
cnt = cnt - 1;
}
System.out.println(cnt);
}
}
어떤 알고리즘인지 감이 오시나요??
아래 그림처럼 이해하면 쉽습니다!
우선 for문을 사용하여 공백의 개수를 cnt에 입력합니다.
그리고
case1. 가장 첫 번째와 마지막이 공백이 아닌 경우 -> cnt = cnt + 1
case2. 가장 첫 번째와 마지막 중에서 하나만 공백인 경우 -> cnt 변화 없음
case3. 가장 첫 번째와 마지막이 모두 공백인 경우 -> cnt = cnt - 1
이렇게 예를 들어서 하면 쉽게 이해가 됩니다!
아직은 어려운 알고리즘은 아니어서 이렇게 노가다로 풀지만.... 코딩테스트나 프로그래머스에 나오는 문제들은 노가다로는 절대 안 풀리더라고요.. 하하
