비검사 예외 : 예외 처리 강제하지 않음 → 사용자가 할 수 있는 일이 없거나 종료시키는 것이 바람직한 경우
비검사 예외로 만들기 위해서는 RuntimeException을 상속해야 한다.
Exception을 상속할 경우 try/catch 또는 throws를 통해 예외 처리를 한다.
[DivideException에서 RuntimeException을 상속]
package org.opentutorials.javatutorials.exception;
class DivideException extends RuntimeException {
DivideException() {
super();
}
DivideException(String message) {
super(message); // 부모 클래스의 생성자를 호출할 때 메시지 전달
}
}
class Calculator {
int left, right;
public void setOperands(int left, int right) {
this.left = left;
this.right = right;
}
public void divide() {
if (this.right == 0) {
throw new DivideException("0으로 나누는 것은 허용되지 않습니다.");
}
System.out.print(this.left/this.right);
}
}
public class CalculatorDemo {
public static void main(String[] args) {
Calculator c1 = new Calculator();
c1.setOperands(10, 0);
c1.divide();
}
}
[DivideException에서 Exception을 상속 : try/catch로 검사 예외를 처리]
package org.opentutorials.javatutorials.exception;
class DivideException extends Exception {
DivideException() {
super();
}
DivideException(String message) {
super(message); // 부모 클래스의 생성자를 호출할 때 메시지 전달
}
}
class Calculator {
int left, right;
public void setOperands(int left, int right) {
this.left = left;
this.right = right;
}
public void divide() {
try {
if (this.right == 0) {
throw new DivideException("0으로 나누는 것은 허용되지 않습니다.");
}
System.out.print(this.left/this.right);
}
catch(DivideException e) {
e.printStackTrace();
}
}
}
public class CalculatorDemo {
public static void main(String[] args) {
Calculator c1 = new Calculator();
c1.setOperands(10, 0);
c1.divide();
}
}
[DivideException에서 Exception을 상속 : try/catch로 검사 예외를 처리]
package org.opentutorials.javatutorials.exception;
class DivideException extends Exception {
DivideException() {
super();
}
DivideException(String message) {
super(message); // 부모 클래스의 생성자를 호출할 때 메시지 전달
}
}
class Calculator {
int left, right;
public void setOperands(int left, int right) {
this.left = left;
this.right = right;
}
public void divide() throws DivideException{
if (this.right == 0) {
throw new DivideException("0으로 나누는 것은 허용되지 않습니다.");
}
System.out.print(this.left/this.right);
}
}
public class CalculatorDemo {
public static void main(String[] args) {
Calculator c1 = new Calculator();
c1.setOperands(10, 0);
try {
c1.divide();
}
catch (DivideException e) {
e.printStackTrace();
}
}
}
equals() 메소드를 직접 구현해야 한다면 hashCode() 메소드도 함께 구현해야 한다.
자식이 부모가 될 때는 자동으로 형변환 된다.
Object obj = s2
부모가 자식이 될 때는 명시적으로 형변환해야 한다.
Student s = (Student)obj;
4.3 finalize
객체가 소멸될 때 호출되기로 약속한 메소드
사용할 일이 거의 없는 메소드이다. 사용을 권장하지 않는다.
4.4 clone
객체를 복제한다.
복제 가능한 객체라는 사실을 자바 가상 머신에 알려줘야 한다. 따라서 Cloneable이라는 인터페이스를 구현한다.
그러나 Cloneable은 비어있는 인터페이스로 클래스가 복제 가능함을 자바 가상머신에게 알려주기 위한 구분자에 불과하다.
clone() 메소드의 접근 제어자는 protected이기 때문에 반드시 메소드를 public 접근 제어자로 오버라이딩해야 한다.
clone() 메소드는 Exception을 상속해서 예외 처리가 필수적이다.
5. enum
enum은 열거형이라고도 한다.
열거형은 서로 연관된 상수의 집합이다.
package org.opentutorials.javatutorials.constant;
enum Fruit {
APPLE, PEACH, BANANA;
}
enum Company {
GOOGLE, APPLE, ORACLE;
}
public class ConstantDemo {
public static void main(String[] args) {
Fruit type = Fruit.APPLE;
switch (type) {
case APPLE:
System.out.println(57 + " kcal");
break;
case PEACH:
System.out.println(34 + " kcal");
break;
case BANANA:
System.out.println(93 + " kcal");
break;
}
}
}
enum은 사실상 클래스이므로 생성자를 가질 수 있다.
열거형에 포함된 상수를 values() 메소드를 통해 상수가 담긴 배열을 가져올 수 있다.
6. 참조
데이터 타입을 생성할 때 new를 통해 생성하는 것들은 기본 데이터 타입이 아니고 참조형 또는 참조 데이터 타입이다.
package org.opentutorials.javatutorials.reference;
class A {
public int id;
A(int id) {
this.id = id;
}
}
public class ReferenceParameterDemo {
static void _value(int b) {
b = 2;
}
public static void runValue() {
int a = 1;
_value(a);
System.out.println("runvalue, " + a);
}
static void _reference1(A b) {
b = new A(2);
}
public static void runReference1() {
A a = new A(1);
_reference1(a);
System.out.println("runReference1, " + a.id);
}
static void _reference2(A b) {
b.id = 2;
}
public static void runReference2() {
A a = new A(1);
_reference2(a);
System.out.println("runReference2, " + a.id);
}
public static void main(String[] args) {
runValue(); // runValue, 1
runReference1(); // runReference1, 1
runReference2(); // runReference2, 2
}
}
package org.opentutorials.javatutorials.generic;
import java.net.Inet4Address;
class EmployeeInfo {
public int rank;
EmployeeInfo(int rank) {
this.rank = rank;
}
}
class Person<T, S> {
public T info;
public S id;
Person(T info, S id) {
this.info = info;
this.id = id;
}
}
public class GenericDemo {
public static void main(String[] args) {
EmployeeInfo e = new EmployeeInfo(1);
Integer i = 10;
Person<EmployeeInfo, Integer> p1 = new Person<EmployeeInfo, Integer>(e, i);
// 제네릭을 명시적으로 언급하지 않고 생략할 수 있다.
// Person<EmployeeInfo, Integer> p1 = new (e, i);
}
}
7.1 제네릭의 제한
extends 키워드를 이용해 특정 데이터 타입만 오도록 할 수 있다.
package org.opentutorials.javatutorials.generic;
abstract class Info {
public abstract int getLevel();
}
class EmployeeInfo extends Info {
public int rank;
EmployeeInfo(int rank) {
this.rank = rank;
}
public int getLevel() {
return this.rank;
}
}
class Person<T extends Info> { // Info 클래스의 자식만 T로 올 수 있다
public T info;
Person(T info) {
this.info = info;
}
}
public class GenericDemo {
public static void main(String[] args) {
Person p1 = new Person(new EmployeeInfo(1));
// String은 Info의 자식이 아니기 때문에 에러 발생
// Person<String> p2 = new Person<String>("부장");
}
}
정의 : 객체에 속한 멤버를 사용하는 입장에서 누가 이것을 사용할 수 있는가에 대한 권한을 부여하는 역할
public : 언제나 접근 가능
private : 같은 클래스에서만 접근 가능
예시 코드
package org.opentutorials.javatutorials.accessmodifier;
class A{
public String y(){
return "public void y()";
}
private String z() {
return "public void z()";
}
public String x() {
return z(); // 같은 클래스 내부에서는 접근 가능
}
}
public class AccessDemo {
public static void main(String[] args) {
A a = new A();
System.out.println(a.y());
// System.out.println(a.z());
System.out.println(a.x());
}
}
추상 클래스는 반드시 그것을 상속받아 사용해야 한다. 즉 main메소드에서 직접 접근이 불가능하다.
추상 메소드를 사용하려면 메소드를 사용하는 쪽에서 반드시 오버라이딩하여 구체적인 로직을 정의해야 한다.
abstract가 지정된 메소드는 로직을 가지고 있으면 안된다.
클래스의 멤버 중 하나라도 abstract 키워드가 지정되어 있으면 해당 멤버를 담고 있는 클래스도 추상클래스가 된다.
abstract class A {
// 추상 메소드
public abstract int b();
// 본체가 있는 메소드는 abstract 키워드를 가질 수 없다.
public abstract int c(){System.out.println("Hello");}
// 추상 클래스 내에서는 추상 메소드가 아닌 메소드가 존재할 수 있다.
public void d(){
System.out.println("world");
}
}
6. final
final을 지정하면 바꿀 수 없는 상수가 된다.
7. 인터페이스
7.1 역할 및 사용 이유
역할 : 특정 클래스에서 특정한 인터페이스를 사용한다면 그 클래스가 반드시 해당 인터페이스에 포함된 메소드를 구현하도록 강제한다
사용 이유 : 어떤 클래스가 어떤 멤버(메소드)를 가지고 있는지 명세서와 같은 역할을 한다. 인터페이스에 명시된 대로 구현을 해야하기 때문에 커뮤니케이션의 착오를 방지한다.
// 인터페이스
interface I() {
public void z();
}
// A 클래스는 I 인터페이스를 '구현한다'
class A implements I {
public void z() {
// 구현이 되어 있지 않기 때문에 컴파일 에러
}
}
7.2 특징
인터페이스를 선언할 때 인터페이스에 정의되는 멤버의 접근 제어자는 반드시 public이어야 한다.
인터페이스는 한 번에 여러 개를 상속할 수 있다.
인터페이스끼리도 상속이 되고 상속된 인터페이스는 부모 인터페이스가 가진 기능을 그대로 자식들이 갖게 된다.
interface I1 {
public void x();
}
interface I2 {
public void z();
}
// 한 번에 여러 개의 인터페이스를 상속받을 수 있다.
class A implements I1, I2 {
public void x() {
}
public void z() {
}
}
interface I3 {
public void x();
}
// 인터페이스도 상속이 된다
interface I4 extends I3 {
public void z();
}
// 부모 인터페이스가 가진 기능도 구현해야 한다
class B implements I4 {
public void x() {
}
public void z() {
}
}
8. 다형성
정의 : 한 메소드나 클래스가 다양한 방식으로 동작하는 것
8.1 클래스와 다형성
B 클래스를 인스턴스화한 obj 변수가 현재 A 클래스 행세를 한다.
A obj = new B();
자식 클래스에서 오버라이딩한 메소드의 내용이 실행된다
A 클래스에서 구현된 내용("A.x")이 출력되지 않는다
부모 클래스에는 없지만 자식 클래스에 있는 메소드를 실행하려고 하면 부모 클래스에서 정의된 바가 없기에 존재하지 않는 메소드가 된다.
y() 메소드는 실행되지 않는다
package org.opentutorials.javatutorials.polymorphism;
class A {
public String x(){
return "A.x";
}
}
class B extends A {
public String x(){
return "B.x";
}
public String y(){
return "y";
}
}
class B2 extends A {
public String x() {
return "B2.x";
}
}
public class PolymorphismDemo {
public static void main(String[] args) {
A obj = new B();
A obj2 = new B2();
System.out.println(obj.x()); // B.x
System.out.println(obj2.x()); // B2.x
// System.out.println(obj.y()); -> error!
}
}
8.2 인터페이스와 다형성
어떤 클래스가 어떤 인터페이스를 구현하고 있다면 그 클래스의 인스턴스는 그 인터페이스일 수 있다.
어떤 클래스의 데이터 타입이 특정한 인터페이스일 경우 해당 클래스에서 특정 인터페이스에서 정의한 멤버만을 가진 클래스인 것처럼 사용할 수 있다.
package org.opentutorials.javatutorials.polymorphism;
interface I2{
public String A();
}
interface I3{
public String B();
}
class D implements I2, I3 {
public String A() {
return "A";
}
public String B() {
return "B";
}
}
public class PolymorphismDemo {
public static void main(String[] args) {
D obj = new D();
I2 objI2 = new D();
I3 objI3 = new D();
obj.A();
obj.B();
objI2.A();
// objI2.B(); error!
// objI3.A(); error!
objI3.B();
}
}
은닉화, 캡슐화 : 내부의 동작방법을 객체에 숨기고 사용자에게는 그 부품의 사용법만 노출하는 것을 정보 은닉화/캡슐화
인터페이스 : 서로 다른 두 개의 시스템, 장치 사이에서 정보나 신호를 주고받는 경우의 접점이나 경계면
2. 클래스와 인스턴스, 그리고 객체
클래스 : 객체를 만들기 위한 일종의 설계도
static 키워드가 붙음
인스턴스 : 그 설계도에 따라서 만든 구체적인 제품
static 이 붙지 않음
인스턴스 메소드는 클래스 멤버에 접근 가능
인스턴스 메소드는 인스턴스에 속한 메소들로서 static이라는 키워드가 지정되지 않은 메소드이다.
인스턴스 메소드 안에서 클래스 변수와 클래스 메소드에 접근할 수 있다
클래스 메소드는 인스턴스 멤버에 접근 불가능
클래스라는 것은 언제나 메소드보다 먼저 존재한다. 왜냐하면 설계도를 만들고 이 설계도에 따라 만들어진 구체적인 제품인 인스턴스를 나중에 만들기 때문.
클래스 메소드는 그 클래스를 기반으로 만들어진 인스턴스에 접근하는 것이기 때문에 아직 생성되지 않은 인스턴스에 접근하는 것이다.
어떤 변수에 인스턴스가 담겨 있는지 조차도 클래스 안에서는 알 수 없다.
3. 유효 범위
package org.opentutorials.javatutorials.scope;
class C{
int v = 10;
void m() {
int v = 20;
System.out.println(v);
System.out.println(this.v);
}
}
public class ScopeDemo {
public static void main(String[] args) {
C c1 = new C();
c1.m();
}
}
// 출력 결과
// 20
// 10
this : 인스턴스의 인스턴스 자신을 의미하는 값
4. 상속과 생성자
상속받은 하위 클래스의 인스턴스가 생성될 때 상속한 상위 클래스의 기본 생성자를 자동으로 호출한다.
만약 부모 클래스에서 매개변수가 있는 생성자를 선언하면 자동으로 기본생성자가 생성되지 않아서 오류 발생
4.1 super
super : 부모 클래스 의미
super() : 부모 클래스의 생성자
주의! : 하위 클래스의 초기화 코드를 super보다 먼저 등장시키면 안된다.
5. 오버라이딩
상속은 부모 클래스에 어떠한 기능을 추가만 하는 경우
오버라이딩은 부모 클래스의 메소드를 그대로 쓰지 않고 자식 클래스의 필요에 따라 메소드를 재정의. 이때 부모 클래스의 메소드는 무시된다.
5.1 오버라이딩 주의사항
부모 클래스의 메소드 형식과 자식 클래스의 메소드 형식이 불일치하는 경우 오버라이딩할 수 없다. 즉 오버라딩하기 위해서는 부모 클래스와 자식 클래스의 반환 타입이 일치해야한다.
메소드의 이름이 같아야한다
매개변수 개수와 반환 타입이 같아야한다
5.2 오버라이딩 조건 (메소드의 서명=signature)
메소드 이름
메소드 매개변수의 개수와 데이터 타입, 순서
메소드의 반환 타입
Tip! 자식 메소드에서 부모 메소드를 호출할 때는 super키워드를 사용한다.
6. 오버로딩
정의 : 클래스에 메소드를 정의할 때 이름이 같지만 서로 다른 매개변수 형식을 지닌 메소드를 여러 개 정의할 수 있는 방법
float 보다 double이 더 많은 데이터를 표현할 수 있기 때문에 데이터가 유실될 가능성이 있다.
결론 : 자동 형 변환의 원칙은 표현 범위가 좁은 데이터 타입에서 넓은 데이터 타입으로만 허용한다.
2.1.1 예시
int a = 3;
float b = 1.0F;
double c = a + b;
System.out.println(c);
a+b를 진행한다. int 와 float의 덧셈이므로 우선 형을 같도록 형 변환을 한다. 즉 int가 float형으로 변환된다. 따라서 a+b = 4.0F
4.0F를 c에 대입한다. c의 데이터 타입은 double형이고 double형에 float형을 대입하면 float형은 double형으로 형 변환이 일어난다.
2.2 명시적 형 변환
정의 : 수동으로 직접 형 변환
float a = (float)100.0;
int b = (int)100.0F;
3. 연산자
3.1 연산자의 우선순위
우선순위
연산자
결합 방향
1
[ ] () .
->
2
++ -- +(양수) -(음수) ~ ! (type) new
<-
3
* / %
->
4
+(더하기) -(빼기) +(문자열 결합 연산자)
->
5
<< >> >>>
->
6
< <= > >= instanceof
->
7
== !=
->
8
& &
->
9
^ ^
->
10
| |
->
11
&&
->
12
||
->
13
? :
<-
14
= *= /= += -= %= <<= >>= >>>= &= ^= !=
<-
3.2 비교와 불린
주의!문자열을 비교할 때는 ==(동등 비교 연산자)를 사용하는 것이 아니라 .equals()라는 메소드를 사용해야 한다.
4. 입력과 출력
package org.opentutorials.javatutorials.io;
public class InputDemo {
public static void main(String[] args) {
System.out.println(args.length);
}
}
String[] : 문자열로 구선된 배열을 의미
args : 문자열 데이터 타입을 담을 수 있는 배열
4.1 시작할 때 입력
Run Configuration 클릭Input 작성
4.2 실행 중에 입력
:자바에서 기본적으로 제공하는 라이브러리 가운데 Scanner라는 라이브러리를 이용해 실행중에 입력을 받는다.
package org.opentutorials.javatutorials.io;
// Scanner를 사용하려면 애플리케이션에 로드해야 한다.
// java.util 안에 있는 Scanner라는 객체를 사용하겠다
import java.util.Scanner;
public class InputDemo {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int i = sc.nextInt(); // 실행을 멈추고 입력을 기다리는 상태가 된다
System.out.println(i*1000);
sc.close();
}
}
글로벌 시대에 당연히 알고리즘의 영어 이름도 알아야겠다고 생각해서 검색해보았다. 그런데, 한국어로 검색했을 때는 대부분 트리 지름, 트리의 지름으로 키워드가 검색되었는데 영어로 검색했을 때는 Diameter of Binary Tree 였다. 트리의 지름 유형에서는 어쩌면 당연한 이야기일지도?
트리의 지름이란?
트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다.
그런데 왜 지름이라고 하는 거지? 가장 긴 트리 사이의 경로라던가
백준 1967번 문제의 설명을 보면 좀 더 직관적으로 받아들일 수 있다.
친절한 설명과 시각 자료..
풀이: 탐색 2번
1. 이진 트리가 있다. 2. 임의의 노드 p에서 DFS를 실행하여 p로부터 가장 먼 거리의 노드 a를 구한다. 3. 노드 a에서 DFS를 다시 실행하여 a로부터 가장 먼 거리의 노드 b를 구한다. 4. a→b 의 거리가 트리의 지름이다.
증명
(가정) 트리에서 $dis(u, v)$의 경로가 트리의 지름이다. 임의의 노드 x에서 가장 먼 노드는 y이다.
이때 케이스를 나눠보자.
$i.$ x가 u 또는 v인 경우 $ii.$ y가 u 또는 v인 경우 $iii.$ x, y, u, v가 서로 다른 경우
Case1. x가 u 또는 v인 경우
가정에 따라 x에서 가장 먼 노드인 y까지의 거리는 트리의 지름이다.
왜냐하면 x가 이미 트리 지름의 한 쪽 끝이기 때문에 dfs를 돌릴 경우 다른 트리의 끝 점으로 가는 것이 당연하다.
Case2. y가 u 또는 v인 경우
가정에 따라 x에서 가장 먼 노드인 y까지의 거리는 트리의 지름이다.
Case3.x, y, u, v가 서로 다른 경우
이 경우 다시 케이스를 두 가지로 나눌 수 있다.
$dis(u, v)$의 경로와 $dis(x, y)$의 경로가 한 점 이상 공유하는 경우
t는 여러 노드가 합쳐진 경로일 수 있지만 편의상 압축하여 한 노드로 표현
x에서 DFS를 수행할 경우 가정에 따라 가장 먼 노드는 y이다.
가장 먼 노드가 y라는 것은 $dis(x, t)$값은 고정되어 있으므로 d1, d2, d3를 비교하였을 때 최대값이 d3라는 의미이다.
이때, $d1 \neq d2$를 가정해보자.
$i.$ $d1 > d2$ 인 경우
우리는 위에서 $d3$가 최대임을 알아냈으므로 $d3 \geq d1 > d2$가 성립한다.
그런데 가정에 따라 $dis(u, v)$가 트리 지름이므로 $d1 + d2 > d1 + d3$임을 알 수 있다.
양변의 $d1$을 소거할 경우 $d2 > d3$이고 이는 위의 $d3 \geq d1 > d2$와 모순이다.
$ii.$ $d1 < d2$ 인 경우
마찬가지로 우리는 위에서 $d3$가 최대임을 알아냈으므로 $d3 \geq d2 > d1$가 성립한다.
그런데 가정에 따라 $dis(v, u)$가 트리 지름이므로 $d2 + d1 > d2 + d3$임을 알 수 있다.
양변의 $d2$을 소거할 경우 $d1 > d3$이고 이는 위의$d3 \geq d2 > d1$와 모순이다.
따라서 귀류법을 통해 $d1 = d2 = d3$임을 알 수 있다.
이미 방문한 노드 x는 고려하지 않는다
따라서 이후 y에서 두 번째 dfs를 수행할 경우 y에서 가장 먼 정점까지의 거리를 구하면 2d로 트리의 지름과 같아지게 된다.
즉즉 트리의 지름을 구할 수 있게 된다.
$dis(u, v)$의 경로와 $dis(x, y)$의 경로가 한 점 이상 공유하지 않는 경우
x에서 DFS를 수행한다. 이때 가장 먼 노드가 y이려면
$dis(x, a)$가 고정이므로 $dis(a, y) \geq dis(a, b) + dis(b, v)$여야 한다.
그럼 노드 u에서 가장 먼 정점을 찾아보자.
$dis(u, b)$가 고정이므로 $dis(b, v) \geq dis(b, a) + dis(a, y)$여야 한다. (by. 가정)
이때 두 부등식을 더해보면
$dis(a, y) + dis(b, v) \geq dis(a, b) + dis(b, v) + dis(b, a) + dis(a, y)$
양변을 소거해보면
$0 \ge dis(a, b) + dis(b, a)$
이므로 모순이다.
Case3의 결론 :$dis(u, v)$의 경로와 $dis(x, y)$의 경로가 최소 한 점 이상 공유한다. 그리고 이때 귀류법에 의해 겹치는 경로에서부터 y, u, v까지의 거리가 모두 같고 이때 두 번째 dfs를 통해 트리의 지름을 구할 수 있다.
C++ STL에서는 반복자로 범위를 표현할 때 첫 원소를 가리키는 반복자와 마지막 원소 다음 위치를 가리키는 반복자를
예시) begin() : 첫 번째 원소, end() : 마지막 원소 다음에 있는 가상의 원소를 가리킴
4. Off-by-one 오류
계산의 큰 줄기는 맞지만 하나가 모자라거나 하나가 많아서 틀리는 코드
방지하는 법 : 최소 입력이 주어졌을 때 코드가 어떻게 동작할지 되새겨 보면서 짜기
5. 컴파일러가 잡아주지 못하는 상수 오타
6. 스택 오버플로
주로 재귀 호출 깊이가 너무 깊어져서 발생
7. 다차원 배열 인덱스 순서 바꿔 쓰기
: 진짜 화남. i랑 j랑 잘못 쓴 게 한 두번이 아님
8. 잘못된 비교 함수 작성
9. 최소, 최대 예외 잘못 다루기
가능한 입력 중 최소 값과 최대 값이 예외가 되는 문제들이 많다
예시) 소수판정의 1과 2
10. 연산자 우선순위 잘못 쓰기
예시) if (b & 1 == 0)
예상 작동 순서 : if ((b & 1) == 0) -> b의 최하 비트가 0일 때 조건문 참
실제 작동 순서 : if (b & (1 == 0)) -> 항상 조건문이 거짓이 된다
11. 너무 느린 입출력 방식 선택
cin 같은 고수준 입출력 방식은 저수준 방식보다 두 배 이상 느리다
cin_sync_with_stdio(false); 를 수행하여 의 표준 입출력 함수들과의 동기화를 끄면 훨씬 빨라짐
12. 변수 초기화 문제
3.5 변수 범위의 이해
산술 오버플로
너무 큰 결과
32bit자료형을 넘어가면 64bit 쓰기
최종 결과 값은 64bit이나 중간 계산 값을 32bit 사용
너무 큰 중간 값
프로그램의 출력 값의 범위는 작지만 중간 과정에서 큰 값을 일시적으로 계산해야 하는 경우
너무 큰 '무한대' 값
최소 거리를 찾는 문제 중, 두 지점 사이의 길이 없는 경우 등고 같이 무한대에 가까운 큰 값을 이용하는게 이득일때가 있다.
문제는 해당 자료형이 처리할 수 있는 가장 큰 값을 무한대 값으로 쓰는 경우. 예를 들어 $2^{31}-1$을 사용할 경우 2를 더하면 오버플로우 발생
따라서 무한대 값을 선택할 때 이 무한대 값들이 서로 더해지거나 곱해지는 경우가 없는지 잘 살펴보고 오버플로가 나지 않을 크기의 값을 선택.
Tip! 987654321 애용.
오버플로 피해가기
더 큰 자료형 쓰기
오버플로가 나지 않도록 연산의 순서 바꾸기
자료형의 프로모션
프로모션이란? 피연산자의 자료형이 다르거나 자료형의 범위가 너무 작은 경우 컴파일러가 같은 자료형으로 변환하여 계산
정수형&&실수형 : 정수형이 실수형으로 변한다.
정수형&&정수형 || 실수형&&실수형 : 보다 넓은 범위를 갖는 자료형으로 변환
양쪽 다 int형보다 작은 정수형인 경우 : 양쪽 다 int형으로 변환
부호 없는 정수형과 부호 있는 정수형이 섞여 있을 경우 : 부호 없는 정수형으로 변환
3.6 실수 자료형의 이해
실수를 다루게 되면 무한의 세계로 날아가게 됩니다.
실수 표기법
이진수로 실수를 표기
부동 소수점 표기법
무한대, 비정규 수 등의 특수한 값이 존재
실수 비교하기
컴퓨터에서 실수 연산을 할 때 원하는 값이 나오지 않는 이유는 컴퓨터가 실수를 근사적으로 표현하기 때문이다.
두 가지 해결방법 : 비교할 실수의 크기들에 비례한 오차 한도를 정한다
1. 같다고 판단해야 할 큰 값 두 개를 비교할 경우
오차 한도 값이 |a-b|보다 항상 커야한다.
즉 |a-b|의 상한을 오차 한도 값으로 쓴다.
이 변수들이 가질 수 있는 최대 값의 $\frac{1}{10^{10}} \sim \frac{1}{10^{12}}$ 정도를 취한다.
2. 다르게 판단해야하는 작은 값 두 개를 비교할 경우
오차 한도 값이 |a-b|보다 항상 작아야 한다.
즉 |a-b|의 하한을 오차 한도 값으로 쓴다.
그러나 객관적인 기준은 없다. -> 상대 오차를 이용한다.
+ 상대 오차를 이용한다
비교하는 숫자들의 크기에 비례하여 오차를 정해야 한다.
상대 오차의 정의 : $relativeError(a, b) = \frac{|a-b|}{max(|a|,|b|)}$
두 수의 상대 오차가 일정 범위 이하면 같은 수로 판정한다
실질적인 오차 허용 범위는 a, b가 커지면 커질수록 커진다.
// 절대 오차와 상대 오차를 모두 이용해서 두 수가 같은지 판정
bool doubleEqual(double a, double b){
double diff = fabs(a - b);
// 절대 오차가 허용 범위 안일 경우 무조건 true 반환
if(diff < 1e-10) return true;
// 이 외의 경우에는 상대 오차를 사용
return diff <= 1e-8 * max(fabs(a), fabs(b));
}
절대 오차와 상대 오차를 모두 이용한 실수 비교
대소 비교
예시 상황) a=b가 되어야 할 두 수의 계산에서, 오차 때문에 a가 약간 더 작은 값으로 계산되었다. 그럼 a<b는 원래 거짓이어야했는데 참이 된다.
결론 : 실수 연산 아예 하지 않기
실수 연산을 제대로 하는 가장 좋은 방법은 아예 실수 연산을 하지 않는 것이다.
실수 연산이 필요해 보이면 문제에 변형을 가해 실수 연산을 없애자
곱셈과 나눗셈 순서 바꾸기
양변 제곱하기
실수 좌표를 써야 하는 기하 문제에서 좌표계를 가로 세로로 정수배 늘리면 정수만을 이용할 수도 있다
