컴퓨터 언어에는 대부분 내장 정렬 함수가 있어 사용자가 스스로 구현하는 데 드는 시간과 노력을 아껴준다. 컴퓨터 언어 중 대다수가 내부적으로 채택한 정렬 알고리즘은 퀵 정렬(quick sort)이다. 퀵 정렬은 재귀를 사용한 알고리즘으로, 그 동작 방식을 알아보며 재귀를 사용해 어떻게 알고리즘의 속도를 향상시키는지 배울 수 있다. 퀵 정렬은 매우 빠른 정렬 알고리즘으로 특히 평균 시나리오에서 매우 효율적이다. 최악의 시나리오(역순 정렬된 배열)에서는 삽입 정렬이나 선택 정렬과 성능이 유사하나 대부분의 경우에서는 훨씬 빠르다. 퀵 정렬은 분할(partitioning)이라는 개념에 기반한다. 1. 분할 배열을 분할한다는 것은 배열로부터 임의의 수, 즉 피벗을 가져와 피벗보다 작은 수는 피벗의 왼쪽에, 큰 수..
11장에서는 재귀적으로 작성하는 법과 재귀로 보다 복잡한 문제를 해결하는 법을 배웠다. 그러나 재귀로 어떤 문제를 해결할 수는 있어도 제대로 사용하지 않으면 또 다른 문제가 발생하기도 한다. 재귀를 잘못 사용할 경우 알고리즘의 시간 복잡도가 O(2^N)과 같은 가장 느린 빅 오 카테고리에 속하게 될 수 있다. 12장에서는 재귀의 속도를 느리게 만드는 가장 흔한 걸림돌을 찾고 그러한 알고리즘을 빅 오 관점에서 어떻게 나타내는지, 어떻게 개선하는지를 배운다. 1. 불필요한 재귀 호출 동일한 하위 문제의 계산 결과를 여러 번 호출하는데, 동일한 인자를 넣었을 때 항상 동일한 결과가 나올 때 2. 빅 오를 위한 작은 개선 이러한 추가적인 재귀 호출을 전부 없앨 수 있는 방법이 있다. 코드에서 결과를 변수에 저장..
이 챕터에서는 “재귀적으로 작성하는” 법을 쉽게 익힐 수 있는 몇 가지 비법을 배우게 된다. 11장에서는 재귀의 효율성은 논하지 않는다. 사실 재귀는 알고리즘의 시간 복잡도에 몹시 부정적인 영향을 미친다. 1. 재귀 카테고리: 반복 실행 가장 쉬운 카테고리로, 반복적으로 한 작업을 실행하는 알고리즘이다. 10장에서 잠깐 훑어본 디렉토리 출력 알고리즘 역시 반복 실행 카테고리의 한 예다. 1.1 재귀 트릭: 추가 인자 넘기기 숫자 배열을 받아 배열 내 각 숫자를 두 배로 만드는 알고리즘을 수행하려고 한다. 단 새 배열을 만드는 것이 아니라 배열 자체에서 수정하겠다. 제자리(in-place) 수정 데이터를 조작(변경)하는 기본적인 방식은 일반적으로 두 가지다. 첫 번째 방법은 원래 배열은 그대로 두고 “두 ..
재귀는 함수가 자기 자신을 호출할 때를 뜻하는 용어다. 1. 루프 대신 재귀 루프를 사용할 수 있는 경우라면 거의 대부분 재귀도 쓸 수 있다. 재귀를 쓸 수 있다고 해서 무조건 재귀를 써야 한다는 것은 아니다. 재귀는 명쾌한 코드를 작성할 수 있는 하나의 도구다. 2. 기저 조건 기저 조건(base case): 함수가 반복되지 않는 경우 모든 재귀 함수에는 함수가 무한대로 호출되지 않게 하는 기저 조건이 적어도 하나 있어야 한다. 3. 재귀 코드 읽기 재귀 코드를 읽는 방법 기저 조건을 찾는다. 기저 조건에서 함수가 어떻게 동작하는지 살펴본다. “끝에서 두 번째” 조건을 찾는다. 곧 보이겠지만 이는 기저 조건 바로 전 조건이다. “끝에서 두 번째” 조건에서 함수가 어떻게 동작하는지 살펴본다. 방금 분석한..
Java Java의 가장 큰 특징이라고 한다면 플랫폼에 독립적인 언어라는 점을 꼽을 수 있겠다. 어느 하드웨어든, 어느 운영체제든 상관없이 컴파일된 코드(바이트코드)가 플랫폼 독립적이다. JVM(Java Virtual Machine)이라는 가상머신만 하드웨어에 설치되어 있다면 어떤 플랫폼이든 동일한 파일로 동일한 작업을 실행할 수 있다. Java의 컴파일부터 실행까지 컴파일 자바로 작성된 소스코드 (.java) Java Compiler가 자바 소스파일을 컴파일 → .java 파일에서 .class 파일로 변환됨 .class 파일은 컴퓨터가 읽을 수 없고, JVM이 읽을 수 있다. .class 파일은 바이트코드로 작성되어 있다. 실행 .class 파일을 JVM의 Class Loader에게 전달 Class L..
