거북이처럼 천천히

1. 빠르게 2진수에서 10진수로 변환할 수 있는 방법은 없는가?2진수로 표현된 숫자들을 16진수로 변환하는 과정은 굉장히 쉽다.아래 표처럼 2진수를 4자리씩 끊어서 16진수로 변환할 수 있다.2진수16진수000000001100102001130100401015011060111710008100191010A1011B1100C1101D1110E1111F 하지만, 2진수로 표현된 숫자들을 10진수로 변환하는 과정은 위와 같이 쉽지 않다.10진수는 0 ~ 9까지만 표현이 가능하며, 1010(A) ~ 1111(F) 는 한 자리 숫자로 표현할 수 없기 때문에 2진수에서 16진수로 변환하는 것 처럼 쉽게 4자리씩 끊어서 읽을 수 없다.★ ★ ★ ★ ★ ★ ★ ★ ★ Q) 그럼, 2진수에서 4자리씩 끊어 10진수를 16..

1. Selection sort public class SelectionSort { public static void main(String[] args) { int[] list = {29, 10, 14, 37, 13}; printList(list, "Before"); for(int i=list.length; i>1; i--) { int max = 0; for(int j=1; j

1. Basic structure of recursion recursion의 기본적인 구조는 Base area, Recursion area로 나뉘며, 각각의 area는 다음과 같은 특성을 갖는다. Base area : Recursion 내에 적어도 하나의 base area가 존재해야 하며, 이 영역은 infinite loop를 순회하는 recursion을 종료시키는 역활을 한다. Recursion area : 모든 Case는 base case에 수렴하도록 설계해야 한다. 이번에는 Recursion을 더 잘 이해하고, 일반적인 반복문과의 차이점을 확인하기 위해서 1) 일반적인 반복문으로 구현 했을 때와 2) Recursion으로 구현했을 때을 비교해보도록 하겠다. 2. Sequential search 2...

1. What is binary search? 이진 탐색(Binart search)은 정렬된 배열안에서 특정 값을 찾아내는 알고리즘이다. 배열의 원소들 중에서 중간값을 찾아서 1) 찾고자 하는 값보다 클 경우, 타켓 값은 중간 값을 기준으로 왼쪽에 위치하고, 2) 작을 경우, 타켓 값은 중간 값을 기준으로 오른쪽에 위치한 것을 알 수 있다. 동일한 방법으로 다시 중간의 값을 선택하고 비교한다. 해당 값을 찾을 때까지 이 과정을 반복한다. 2. Example of binary search List = {1, 2, 3, 4, 5, 6, 7}, Target = {1} 시작점 인덱스는 0, 종점 인덱스는 6일 경우 중간 인덱스는 (시작점 인덱스 + 종점 인덱스) / 2 = 3이다. List[3]와 target ..

1. What is Recursion? Recursion은 자기 자신을 호출하는 메서드를 의미하며, Recursion을 번역하면 "순환, 재귀 메서드" 라 한다. Java를 통해 Recursion을 구현해보자. methodForTest 메서드를 main 메서드에서 호출했으며, methodForTest 메서드내에서 다시 한번 자기 자신을 호출하였다. 아래 코드와 같이 실행하면 어떤 결과가 발생하는가? public class Test { public static void main(String[] args) { methodForTest(); } private static void methodForTest() { System.out.println("Say Hello!"); methodForTest(); } } ..

버블정렬(Bubble sort) 인접한 두 개의 원소를 검사하여 정렬하는 알고리즘 버블정렬(Bubble sort) 알고리즘의 구체적인 개념 ▶ 첫 번째 원소(8)과 두 번째 원소(4)를 비교하여 둘 중 큰 값이 오른쪽으로 올 수 있도록 자리 교환을 한다. 예시인 경우 8이 4보다 크기 때문에 8과 4의 자리를 바꾼다. ▶이번에는 두 번째 원소(8)과 세 번째 원소(1)을 비교한다. 이번에도 8이 1보다 크기 때문에 8과 1의 자리를 서로 바꾼다. ▶ 이와 같은 과정을 배열의 마지막까지 진행하고나면 배열의 마지막 원소에는 배열 내에서의 최대값이 위치하게 된다. 예시에서 볼 수 있듯이 최대 값은 13이 나왔다. ▶ 이번에는 배열의 가장 오른쪽을 제외하고, 위 과정을 다시 실행한다. 이번에는 최대값은 11이 ..

이미 알고 있는 소수 판별법 이미 알고 있는 소수 판별법은 다음 두 가지 방법이었다. 문제 : 자연수 X이 소수인가? 반복문을 이용하여 자연수 X을 2 ~ X-1까지 나눠봐서 한 번이라도 나머지가 0인 경우가 나오면 자연수 X은 소수가 아니다. 약수는 쌍을 이룬다는 점을 이용하여 2 ~ X-1까지가 아닌 2 ~ X/2까지 나눠봐서 자연수 X이 소수인지 판별할 수 있다. 하지만, 2 ~ root(X)이하까지만 나눠봐도 해당 숫자가 소수인지를 효율적으로 판별할 수 있다고 한다. 직감적으로 "왜 root(X) 이하까지만 나눠도 되는가?"를 이해할 수 없어 수식적으로 증명해 보자 한다. 왜 root(X) 이하까지만 나눠도 되는가? 가정 : 자연수 X은 소수가 아닌 합성수이며, 자연수 X은 M * N으로 표현할 ..