2020/09(15)
-
ETC./Algorithm
2020.09.15
[Algorithm] 알고리즘 공간복잡도에 대하여
공간복잡도란? 공간복잡도(Space Complexity)란 프로그램의 성능을 분석하는 방법 중 하나로, 작성한 프로그램이 얼마나 많은 공간(메모리)을 차지하느냐를 분석하는 방법입니다. 하지만 최근에는 컴퓨터 성능의 발달로 인해 메모리의 여유 공간이 충분하다못해 넘치기 때문에 공간복잡도의 중요성이 예전에 비해서 많이 낮아졌습니다. 시간복잡도의 경우 알고리즘을 잘못 구성하였을 경우 결과값이 나오지 않거나 현저하게 느린속도가 나오기에 최근에는 공간복잡도보다는 시간복잡도를 우선시하여 프로그램을 작성합니다. [Algorithm] 알고리즘 시간복잡도에 대하여 공간복잡도 계산법 (빅-오) int a = 10; 일반적으로 공간이 하나씩 생성되는것을 1이라고 표현합니다. 위의 공간복잡도는 O(1)입니다. int get_..
-
ETC./Algorithm
2020.09.14
4
[Algorithm] 알고리즘 시간복잡도에 대하여
시간복잡도란? 시간 복잡도란 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 의미합니다. 같은 결과를 가져오는 프로그래밍 소스도 어떻게 작성하느냐에 따라 걸리는 시간이 달라질 수 있습니다. 같은 결과를 나타내는 소스라면 최대한 시간이 적게 걸리는 좋은 소스입니다. 그렇기에 더 효율적인 알고리즘을 구성하기 위해서 시간 복잡도의 측면을 고려하고 중요하게 봅니다. 특히 최근 알고리즘 문제 해결에서 대부분 실행시간을 정해놓고 그 시간안에 소스가 돌아가야 정답으로 체크하기에 시간복잡도의 중요성이 더더욱 커졌다고 볼 수 있습니다. [Algorithm] 알고리즘 공간복잡도에 대하여 빅-오 표기법 시간 복잡도에는 여러 개념이 있지만 그중에서 ‘아무리 많이 걸려도 이 시간 안에는 끝날 것‘의 개념이 제일 중요합니다..
-
ETC./Algorithm
2020.09.13
[Algorithm] 순열 조합 알고리즘 개념과 예제 (구현)
순열과 조합 실생활 예 순열과 조합의 차이는 순서를 정하느냐 그렇지 않느냐의 차이입니다. 순열 : 중국집 메뉴 5개 중 2개의 메뉴를 순서대로 먹는 경우의 수 조합 : 중국집 메뉴 5개 중 2개의 메뉴를 주문하는 경우의 수 순열이란? 순열이란 서로 다른 n개중 r개를 골라 순서를 고려해 나열한 경우의 수를 말합니다. 예를 들어 어느 중국집에 5개의 메뉴(a,b,c,d,e)가 있다고 해봅시다. 이때 5개의 메뉴(a,b,c,d,e)중 2개의 메뉴를 순서대로 먹는 경우의 수는 몇가지가 있을까요? 먼저 첫번째로 먹을 메뉴를 정하려면 이때 첫번째 메뉴가 될 수 있는 경우의 수는 5가지 입니다. 그리고 나서 첫번째 메뉴로 지정된 메뉴를 제외한 나머지 4가지의 메뉴로 두번째로 먹을 메뉴를 선택한다고 가정하면 이때의 ..
-
ETC.
2020.09.12
10
[수학] 순열, 조합 공식 총정리
팩토리얼 ( ! ) 팩토리얼이란 서로 다른 n개를 나열하는 경우의 수를 의미합니다. 기호로는 n! 이렇게 쓰고 계산은 n부터 1씩 줄여나가면서 1이 될때까지의 모든 수를 곱합니다. 순열 ( nPr ) 순열이란 서로 다른 n개중에 r개를 선택하는 경우의 수를 의미합니다. (순서 상관 있음) 조합 ( nCr ) 조합이란 서로 다른 n개중에 r개를 선택하는 경우의 수를 의미합니다. (순서 상관 없음) 중복 순열 ( nπr ) 중복 순열이란 중복 가능한 n개중에서 r개를 선택하는 경우의 수를 의미합니다. (순서 상관 있음) 중복 조합 ( nHr ) 중복 조합이란 중복 가능한 n개중에서 r개를 선택하는 경우의 수를 의미합니다. (순서 상관 없음) 같은 것이 있는 순열 순열이 같은 것이 포함된 원소들을 나열하는 ..
-
Languague/Java
2020.09.11
1
[Java] 큰 숫자(실수) 다루기 BigDecimal 사용법 & 예제 총정리
BigDecimal을 사용해야 하는 이유 Type 범위 float 1.4E-45 ~ 3.4028235E38 double 4.9E-324 ~ 1.7976931348623157E308 소수점을 저장할 수 있는 타입인 float과 double은 소수점의 정밀도가 완벽하지 않아 값의 오차가 생길 수 있습니다. 특히 소수점 이하의 수를 다룰 때 double과 float은 사칙연산 시 정확한 값을 출력하지 않을 수 있는데요. 그 이유는 내부적으로 수를 저장할 때 이진수의 근사치를 저장하기 때문입니다. 그렇기에 미세한 숫자의 변동도 허용하지 않는 특히 돈과 소수점을 다룬다면 BigDecimal을 사용하셔야 합니다. BigDecimal은 속도는 느리지만 숫자가 어긋날 가능성을 미연에 방지할 수 있습니다. BigDeci..
-
Languague/Java
2020.09.10
6
[Java] 큰 숫자(정수) 다루기 BigInteger 사용법 & 예제 총정리
BigInteger를 사용해야 하는 이유 Type 범위 int -2,147,483,648 ~ 2,147,483,647 long -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 int는 메모리 크기는 4byte로 표현할 수 있는 범위는 -2,147,483,648 ~ 2,147,483,647이고 long은 메모리 크기는 8byte로 표현할 수 있는 범위는 -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807입니다. 그 범위를 넘어서게 되면 모두 0으로 출력이 됩니다. 숫자의 범위가 저 범위를 넘을 경우는 잘 없겠지만 프로그램 개발 특히 돈과 관련된 개발이나 알고리즘 문제를 풀 때 항상 최악의 상황을 고려해야 하므로..
-
Languague/Java
2020.09.09
7
[Java] PriorityQueue(우선순위 큐) 클래스 사용법 & 예제 총정리
우선순위 큐(Priority Queue)란? 일반적으로 큐는 데이터를 일시적으로 쌓아두기 위한 자료구조로 스택과는 다르게 FIFO(First In First Out)의 구조 즉 먼저 들어온 데이터가 먼저 나가는 구조를 가집니다. PriorityQueue는 먼저 들어온 순서대로 데이터가 나가는 것이 아닌 우선순위를 먼저 결정하고 그 우선순위가 높은 엘리먼트가 먼저 나가는 자료구조입니다. 우선순위 큐는 힙을 이용하여 구현하는 것이 일반적입니다. 데이터를 삽입할 때 우선순위를 기준으로 최대힙 혹은 최소 힙을 구성하고 데이터를 꺼낼 때 루트 노드를 얻어낸 뒤 루트 노드를 삭제할 때는 빈 루트 노드 위치에 맨 마지막 노드를 삽입한 후 아래로 내려가면서 적절한 자리를 찾아서 옮기는 방식으로 진행됩니다. Priori..
-
Languague/Java
2020.09.08
2
[Java] 자바 Queue 클래스 사용법 & 예제 총정리
Queue란? Queue의 사전적 의미는 무엇을 기다리는 사람, 차량 등의 줄 혹은 줄을 서서 기다리는 것을 의미하는데 이처럼 줄을 지어 순서대로 처리되는 것이 큐라는 자료구조입니다. 큐는 데이터를 일시적으로 쌓아두기 위한 자료구조로 스택과는 다르게 FIFO(First In First Out)의 형태를 가집니다. FIFO 형태는 뜻 그대로 먼저 들어온 데이터가 가장 먼저 나가는 구조를 말합니다. Enqueue : 큐 맨 뒤에 데이터 추가 Dequeue : 큐 맨 앞쪽의 데이터 삭제 Queue의 특징 1. 먼저 들어간 자료가 먼저 나오는 구조 FIFO(First In FIrst Out) 구조 2. 큐는 한 쪽 끝은 프런트(front)로 정하여 삭제 연산만 수행함 3. 다른 한 쪽 끝은 리어(rear)로 정..
-
Languague/Java
2020.09.07
3
[Java] 자바 Stack 클래스 사용법 & 예제 총정리
Stack이란? 자료 구조 중 하나인 Stack의 사전적 정의는 '쌓다', '더미'입니다. 상자에 물건을 쌓아 올리듯이 데이터를 쌓는 자료 구조라고 할 수 있습니다. Stack의 가장 큰 특징은 나중에 들어간 것이 먼저 나오는 (Last In First Out)의 형태를 띈다는 것입니다. 이 방식을 가진 자료구조인 Stack을 활용하여 다양한 문제를 해결할 수 있습니다. 자바에서 Stack은 java.util.Stack을 import하면 바로 사용할 수 있습니다. Stack의 특징 1. 먼저 들어간 자료가 나중에 나옴 LIFO(Last In First Out) 구조 2. 시스템 해킹에서 버퍼오버플로우 취약점을 이용한 공격을 할 때 스택 메모리의 영역에서 함 3. 인터럽트처리, 수식의 계산, 서브루틴의 복..
-
ETC./Algorithm
2020.09.06
2
[Algorithm] 에라토스테네스의 체 - 소수 구하기 (범위)
에라토스테네스의 체란? 고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법이며 이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부릅니다. 특정 숫자의 배수는 소수가 아니라는 법칙에 착안하여 2 ~ N까지의 숫자에서 숫자들의 배수를 모두 제거한 뒤 제거되지 않은 숫자를 소수로 판별하는 방식이며 일종의 노가다 방식이라 상당히 무식한 방법이지만 이 방식이 프로그래밍에서는 상당히 효율적인 방법론이 됩니다. 에라토스테네스의 체는 반대로 2부터 배수들을 지워나가는 방식이기 때문에 숫자마다 일일이 약수가 있는지 검사할 필요가 전혀 없고, 이미 지워진 숫자는 바로 건너뛰면 되니 실행시간이 매우 짧습니다. 특정 범위에서의 모든 소수를 찾을때 가장 효율적인 알고리즘 에라토스테네스..
-
ETC./Algorithm 2020.09.15[Algorithm] 알고리즘 공간복잡도에 대하여 공간복잡도란? 공간복잡도(Space Complexity)란 프로그램의 성능을 분석하는 방법 중 하나로, 작성한 프로그램이 얼마나 많은 공간(메모리)을 차지하느냐를 분석하는 방법입니다. 하지만 최근에는 컴퓨터 성능의 발달로 인해 메모리의 여유 공간이 충분하다못해 넘치기 때문에 공간복잡도의 중요성이 예전에 비해서 많이 낮아졌습니다. 시간복잡도의 경우 알고리즘을 잘못 구성하였을 경우 결과값이 나오지 않거나 현저하게 느린속도가 나오기에 최근에는 공간복잡도보다는 시간복잡도를 우선시하여 프로그램을 작성합니다. [Algorithm] 알고리즘 시간복잡도에 대하여 공간복잡도 계산법 (빅-오) int a = 10; 일반적으로 공간이 하나씩 생성되는것을 1이라고 표현합니다. 위의 공간복잡도는 O(1)입니다. int get_..
-
ETC./Algorithm 2020.09.14 4[Algorithm] 알고리즘 시간복잡도에 대하여 시간복잡도란? 시간 복잡도란 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 의미합니다. 같은 결과를 가져오는 프로그래밍 소스도 어떻게 작성하느냐에 따라 걸리는 시간이 달라질 수 있습니다. 같은 결과를 나타내는 소스라면 최대한 시간이 적게 걸리는 좋은 소스입니다. 그렇기에 더 효율적인 알고리즘을 구성하기 위해서 시간 복잡도의 측면을 고려하고 중요하게 봅니다. 특히 최근 알고리즘 문제 해결에서 대부분 실행시간을 정해놓고 그 시간안에 소스가 돌아가야 정답으로 체크하기에 시간복잡도의 중요성이 더더욱 커졌다고 볼 수 있습니다. [Algorithm] 알고리즘 공간복잡도에 대하여 빅-오 표기법 시간 복잡도에는 여러 개념이 있지만 그중에서 ‘아무리 많이 걸려도 이 시간 안에는 끝날 것‘의 개념이 제일 중요합니다..
-
ETC./Algorithm 2020.09.13[Algorithm] 순열 조합 알고리즘 개념과 예제 (구현) 순열과 조합 실생활 예 순열과 조합의 차이는 순서를 정하느냐 그렇지 않느냐의 차이입니다. 순열 : 중국집 메뉴 5개 중 2개의 메뉴를 순서대로 먹는 경우의 수 조합 : 중국집 메뉴 5개 중 2개의 메뉴를 주문하는 경우의 수 순열이란? 순열이란 서로 다른 n개중 r개를 골라 순서를 고려해 나열한 경우의 수를 말합니다. 예를 들어 어느 중국집에 5개의 메뉴(a,b,c,d,e)가 있다고 해봅시다. 이때 5개의 메뉴(a,b,c,d,e)중 2개의 메뉴를 순서대로 먹는 경우의 수는 몇가지가 있을까요? 먼저 첫번째로 먹을 메뉴를 정하려면 이때 첫번째 메뉴가 될 수 있는 경우의 수는 5가지 입니다. 그리고 나서 첫번째 메뉴로 지정된 메뉴를 제외한 나머지 4가지의 메뉴로 두번째로 먹을 메뉴를 선택한다고 가정하면 이때의 ..
-
ETC. 2020.09.12 10[수학] 순열, 조합 공식 총정리 팩토리얼 ( ! ) 팩토리얼이란 서로 다른 n개를 나열하는 경우의 수를 의미합니다. 기호로는 n! 이렇게 쓰고 계산은 n부터 1씩 줄여나가면서 1이 될때까지의 모든 수를 곱합니다. 순열 ( nPr ) 순열이란 서로 다른 n개중에 r개를 선택하는 경우의 수를 의미합니다. (순서 상관 있음) 조합 ( nCr ) 조합이란 서로 다른 n개중에 r개를 선택하는 경우의 수를 의미합니다. (순서 상관 없음) 중복 순열 ( nπr ) 중복 순열이란 중복 가능한 n개중에서 r개를 선택하는 경우의 수를 의미합니다. (순서 상관 있음) 중복 조합 ( nHr ) 중복 조합이란 중복 가능한 n개중에서 r개를 선택하는 경우의 수를 의미합니다. (순서 상관 없음) 같은 것이 있는 순열 순열이 같은 것이 포함된 원소들을 나열하는 ..
-
Languague/Java 2020.09.11 1[Java] 큰 숫자(실수) 다루기 BigDecimal 사용법 & 예제 총정리 BigDecimal을 사용해야 하는 이유 Type 범위 float 1.4E-45 ~ 3.4028235E38 double 4.9E-324 ~ 1.7976931348623157E308 소수점을 저장할 수 있는 타입인 float과 double은 소수점의 정밀도가 완벽하지 않아 값의 오차가 생길 수 있습니다. 특히 소수점 이하의 수를 다룰 때 double과 float은 사칙연산 시 정확한 값을 출력하지 않을 수 있는데요. 그 이유는 내부적으로 수를 저장할 때 이진수의 근사치를 저장하기 때문입니다. 그렇기에 미세한 숫자의 변동도 허용하지 않는 특히 돈과 소수점을 다룬다면 BigDecimal을 사용하셔야 합니다. BigDecimal은 속도는 느리지만 숫자가 어긋날 가능성을 미연에 방지할 수 있습니다. BigDeci..
-
Languague/Java 2020.09.10 6[Java] 큰 숫자(정수) 다루기 BigInteger 사용법 & 예제 총정리 BigInteger를 사용해야 하는 이유 Type 범위 int -2,147,483,648 ~ 2,147,483,647 long -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 int는 메모리 크기는 4byte로 표현할 수 있는 범위는 -2,147,483,648 ~ 2,147,483,647이고 long은 메모리 크기는 8byte로 표현할 수 있는 범위는 -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807입니다. 그 범위를 넘어서게 되면 모두 0으로 출력이 됩니다. 숫자의 범위가 저 범위를 넘을 경우는 잘 없겠지만 프로그램 개발 특히 돈과 관련된 개발이나 알고리즘 문제를 풀 때 항상 최악의 상황을 고려해야 하므로..
-
Languague/Java 2020.09.09 7[Java] PriorityQueue(우선순위 큐) 클래스 사용법 & 예제 총정리 우선순위 큐(Priority Queue)란? 일반적으로 큐는 데이터를 일시적으로 쌓아두기 위한 자료구조로 스택과는 다르게 FIFO(First In First Out)의 구조 즉 먼저 들어온 데이터가 먼저 나가는 구조를 가집니다. PriorityQueue는 먼저 들어온 순서대로 데이터가 나가는 것이 아닌 우선순위를 먼저 결정하고 그 우선순위가 높은 엘리먼트가 먼저 나가는 자료구조입니다. 우선순위 큐는 힙을 이용하여 구현하는 것이 일반적입니다. 데이터를 삽입할 때 우선순위를 기준으로 최대힙 혹은 최소 힙을 구성하고 데이터를 꺼낼 때 루트 노드를 얻어낸 뒤 루트 노드를 삭제할 때는 빈 루트 노드 위치에 맨 마지막 노드를 삽입한 후 아래로 내려가면서 적절한 자리를 찾아서 옮기는 방식으로 진행됩니다. Priori..
-
Languague/Java 2020.09.08 2[Java] 자바 Queue 클래스 사용법 & 예제 총정리 Queue란? Queue의 사전적 의미는 무엇을 기다리는 사람, 차량 등의 줄 혹은 줄을 서서 기다리는 것을 의미하는데 이처럼 줄을 지어 순서대로 처리되는 것이 큐라는 자료구조입니다. 큐는 데이터를 일시적으로 쌓아두기 위한 자료구조로 스택과는 다르게 FIFO(First In First Out)의 형태를 가집니다. FIFO 형태는 뜻 그대로 먼저 들어온 데이터가 가장 먼저 나가는 구조를 말합니다. Enqueue : 큐 맨 뒤에 데이터 추가 Dequeue : 큐 맨 앞쪽의 데이터 삭제 Queue의 특징 1. 먼저 들어간 자료가 먼저 나오는 구조 FIFO(First In FIrst Out) 구조 2. 큐는 한 쪽 끝은 프런트(front)로 정하여 삭제 연산만 수행함 3. 다른 한 쪽 끝은 리어(rear)로 정..
-
Languague/Java 2020.09.07 3[Java] 자바 Stack 클래스 사용법 & 예제 총정리 Stack이란? 자료 구조 중 하나인 Stack의 사전적 정의는 '쌓다', '더미'입니다. 상자에 물건을 쌓아 올리듯이 데이터를 쌓는 자료 구조라고 할 수 있습니다. Stack의 가장 큰 특징은 나중에 들어간 것이 먼저 나오는 (Last In First Out)의 형태를 띈다는 것입니다. 이 방식을 가진 자료구조인 Stack을 활용하여 다양한 문제를 해결할 수 있습니다. 자바에서 Stack은 java.util.Stack을 import하면 바로 사용할 수 있습니다. Stack의 특징 1. 먼저 들어간 자료가 나중에 나옴 LIFO(Last In First Out) 구조 2. 시스템 해킹에서 버퍼오버플로우 취약점을 이용한 공격을 할 때 스택 메모리의 영역에서 함 3. 인터럽트처리, 수식의 계산, 서브루틴의 복..
-
ETC./Algorithm 2020.09.06 2[Algorithm] 에라토스테네스의 체 - 소수 구하기 (범위) 에라토스테네스의 체란? 고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법이며 이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부릅니다. 특정 숫자의 배수는 소수가 아니라는 법칙에 착안하여 2 ~ N까지의 숫자에서 숫자들의 배수를 모두 제거한 뒤 제거되지 않은 숫자를 소수로 판별하는 방식이며 일종의 노가다 방식이라 상당히 무식한 방법이지만 이 방식이 프로그래밍에서는 상당히 효율적인 방법론이 됩니다. 에라토스테네스의 체는 반대로 2부터 배수들을 지워나가는 방식이기 때문에 숫자마다 일일이 약수가 있는지 검사할 필요가 전혀 없고, 이미 지워진 숫자는 바로 건너뛰면 되니 실행시간이 매우 짧습니다. 특정 범위에서의 모든 소수를 찾을때 가장 효율적인 알고리즘 에라토스테네스..