공부방
JAVA::자바에서 형변환(Casting)하기
형변환(Casting) 알고리즘 문제를 해결하다 보면 종종 숫자를 string으로 변환해서 문제를 해결하거나 char형으로 변경해서 문제를 해결하는것이 더 유리한 경우도 있습니다. 그리고, 그 외에도 작업을 하다보면 여러 타입간의 연산을 수행하거나 특정 형식을 맞추기위해 형을 바꿔야하는 경우가 있습니다. 이러한 경우에 변수나 리터럴 타입들을 다을 타입으로 변환해주느데 이것을 형변환이라고 합니다. 정의(Definition) 변수나 리터럴 타입을 다른 타입으로 변환하는 것 형변환 종류(자동 vs 강제)?? 그렇다면 현변환은 어떻게 해야할까? 일반적으로 컴파일러에 따라 형변환을 생략하더라도 알아서 자동적으로 추가해서 형변환시켜주는데 이를 자동형변환(묵시적 형변환)이라고 한다. 그리고 그렇지 않은 경우 바꿀 타..
Data Structure::Queue(큐)
Queue(큐) 먼저 들어간 데이터가 먼저 나오는 FIFO(First In First Out) 형식의 자료구조(LILO이라고도 할 수 있다.) Queue 연산 큐 자료구조는 FIFO(First In First Out) 혹은 LILO(Last In Last Out)을 따르게 되며 먼저 들어간 데이터가 먼저 제거되는 구조가 된다. 해당 자료구조를 만족하기 위해서 여러 연산이 필요하다 Enqueue(Data) :스택에서의 Push와 같은 연산으로 데이터를 추가해주는 연산. Dequeue() : 제일 처음 추가된 데이터를 제거하는 연산 Peek() : 제일 처음 추가된 데이터를 얻는 연산(front에 위치한 데이터) isEmpty() : 큐에 데이터가 있는지 여부를 확인하는 연산 용어는 Enqueue를 Add,..
Binary Search Algorithm(이진 탐색 알고리즘)
Binary Search Algorithm 여러가지 탐색 알고리즘들을 보면 여러가지 알고리즘을 찾을 수 있다. 가장 기본적으로는 선형 탐색 방식으로 앞에서 부터 하나씩 비교하며 찾는 방법이다. 말그대로 탐색을 한 쪽 끝에서 다른 끝까지 탐색하기 때문에 탐색 대상이 뒤쪽에 위치해있으면서, 탐색 대상이 많은 경우 매우 비효율적일 수 있다. 하지만, 만약 탐색하고자 하는 데이터가 정렬이 되어 있는 경우 좀더 효율 적인 방법을 이용할 수 있는데 이것이 바로 이진 탐색 알고리즘이다. 정의(Definition) 정렬된 탐색대상에서 특정 대상을 찾고자 할때 사용 할 수 있는 탐색 알고리즘 정렬된 알고리즘으로 부터 탐색 중간값과 탐색대상을 비교후 탐색 범위를 절반으로 줄여가며 찾는 알고리즘 이렇게 정렬된 알고리즘으로 ..
Recursion Algorithm(재귀 알고리즘)
Recursion Algorithm 처음 재귀를 접하게 되면 이해가 안될 것이다. 다만 위 그림을 보면 대충 재귀가 무엇인지 감이 잡힐 것이다. 재귀에 대해서 알아보면 임의의 함수가 자기자신을 호출하는 재귀 호출을 이용하는 알고리즘이다. 같은 행동을 반복적으로 행할때 사용하는 알고리즘인 것이다. 그렇다면 재귀알고리즘은 반복문과는 어떠한 차이가 있을까? 그리고 재귀를 이용함으로써 얻을수 있는 이점은 무엇이고 단점은 무엇인가를 알아보고자한다. 정의(Definition) 임의의 함수가 자기자신을 호출하는 것으로 그 함수를 재귀함수라하며 그 호출을 재귀호출이라한다. 이렇듯 재귀알고리즘은 스스로를 호출하는 함수를 이용한 풀이를 재귀 알고리즘이라고 말한다. 재귀알고리즘을 이용하기 위해 재귀함수를 만들때는 중요한 점..
Euclidean algorithm(유클리드 호제법)
Euclidean Algorithm 유클리드 호제법은 두 수의 최대공약수를 구하는 알고리즘의 하나이다. 2개의 자연수 a,b에서 a를 b로 나눈 나머지를 r이라고 했을때 GCD(a,b) = GCD(b, r)과 같게 되고 r이 0이 될때의 b의 값이 최대공약수가 된다. 일반적으로 쉽게 생각할 수 있는 최대공약수를 구하는 방법은 모든 자연수를 나눠보는 것이다. 하지만 이경우 시간복잡도는 O(n)이 된다. 다만 이 유클리드 호제법을 사용할 경우 O(logN)이 되어 더 빠른 속도를 나타낼 수 있다. Greatest Common Divisor(GCD) 2개의 자연수의 공통된 약수인 공약수 중 가장 큰 공약수가 최대공약수이다. 소스코드 ※ 아래 코드는 a>b 를 만족함을 가정 > C++ int gcd(int a,..
Sieve of Eratosthenes(에라토스테네스의 체)
Sieve of Eratosthenes 수학에서 소수를 찾기 위한 방법중 하나로 고대 그리스 수학자 에라토스테네스가 고안한 방법이다. Prime(소수) 소수는 '양의 약수를 2개만 갖는 자연수' 즉, 자신보다 작은 두개의 자연수를 곱하여 만들수 없는 1보다 큰 자연수로 자기자신과 1의 곱으로만 나타낼수 있는 1보다 큰 자연수를 말한다. Algorithm 해당 에라토스테네스는 자신보다 작은 두개의 자연수를 곱하여 만들수 없다는 성질을 이용한다. 2는 명확히 소수임을 알수 있고 2의 배수는 모두 위의 소수조건을 만족하지 못하므로 소수가 아님을 알 수 있다. 3은 2로 인해 지워지지 않았으므로 3보다 작은수의 배수가 아님을 알 수 있고 즉 소수임을 확인할 수 있으며 3의 배수는 소수가 아니므로 3의 배수 또한..
Hanoi Tower(하노이의 탑)
Hanoi Tower(하노이의 탑) 프랑스 수학자 에두아르 뤼카가 클라우드 교수라는 필명으로 발표하였고 그 후 1년 후 헨리 드 파르빌이 다음과 같은 이야기로 하노이 탑을 소개하였다. 인도베나레스에 있는 한 사원에는 세상의 중심을 나타내는 큰 돔이 있고 그 안에 세 개의 다이아몬드 바늘이 동판 위에 세워져 있습니다. 바늘의 높이는 1 큐빗이고 굵기는 벌의 몸통만 합니다. 바늘 가운데 하나에는 신이 64개의 순금 원판을 끼워 놓았습니다. 가장 큰 원판이 바닥에 놓여 있고, 나머지 원판들이 점점 작아지며 꼭대기까지 쌓아 있습니다. 이것은 신성한 브라흐마의 탑입니다. 브라흐마의 지시에 따라 승려들은 모든 원판을 다른 바늘로 옮기기 위해 밤낮 없이 차례로 제단에 올라 규칙에 따라 원판을 하나씩 옮깁니다. 이 일..