지난 글 : [알고리즘/Do it 알고리즘] - 반복
자료구조 정의하기
자료구조는 아래와 같이 정의할 수 있다.
데이터 단위와 데이터 자체 사이의 물리적 또는 논리적인 관계
배열 다루기
시험 점수를 집계해 처리하는 프로그램을 생각해보자. 여러 명의 학생과 그들 각각의 점수를 각각 변수로 만들면 코드가 길어지고 효율도 떨어진다. 이런 경우 학생들의 점수를 저장할 변수 이름을 '몇 번째'라고 지정하면 편리하다. 이때 사용하는 기본적이고 간단한 자료구조가 배열(array)이다. 배열은 같은 자료형의 변수인 구성 요소(component)가 모인 것이다. 배열 구성 요소의 자료형은 int나 double 등 어떤 형이든 상관없다. 시험 점수는 정숫값이므로 자료형이 int형인 배열을 예로 들어 살펴보자. 먼저 배열의 형식은 아래와 같다.
int[ ] score;그런데 배열 선언에서 만들어지는 score는 배열 변수(array variable)라 하는 특수한 변수일 뿐 배열 그 자체는 아니다. 배열 본체는 연산자 new를 사용해 생성한다.
score = new int[5];
인덱스 식과 구성 요소
배열 본체 안의 구성 요소에 접근(access)하려면 정수형 인덱스를 연산자 [ ] 안에 넣은 인덱스 식을 사용한다.
배열 변수 이름 [인덱스]첫 번째 배열 요소의 인덱스는 0이다. 각 구성 요소에 접근하는 인덱스 식은 처음부터 순서대로 score[0], score[1], score[2], score[3], score[4]이다.
배열 score의 모든 구성 요소는 int형이고 각각의 요소는 배열이 아니라 단일로 선언한 int형 변수와 성질이 같다. 그러므로 각 요소에 자유롭게 int형의 값을 대입하거나 꺼낼 수 있다.
구성 요솟수(길이)
배열 본체와 함께 구성 요소의 개수인 구성 요솟수를 나타내는 length라는 변수가 만들어진다. 배열의 구성 요솟수는 배열의 길이(length)라고도 한다. 배열의 구성 요솟수는 아래와 같은 식으로 구할 수 있다.
배열 변수 이름.length
기본값
출력 결과에서 알 수 있듯 값을 대입하지 않은 배열의 구성 요소는 자동으로 0으로 초기화되는 규칙이 있다. 배열을 생성할 때 각 구성 요소에 넣는 초깃값을 기본값(default value)이라 한다.
배열의 요솟값을 초기화하며 배열 선언하기
배열 본체는 new 연산자뿐 아니라 배열 초기화(array initializer)에서도 생성할 수 있다. 배열 초기화를 사용하면 배열 본체의 생성과 동시에 각 구성 요소를 특정값으로 초기화할 수도 있다.
배열 변수를 선언하며 동시에 배열 a를 초기화했다. 각 구성 요소의 기본값을 맨 앞부터 순서대로 쉼표(,)로 구분해 나열하고 { } 로 둘러싼 부분이다. 이리 하면 배열 a의 구성요소 a[0] ~ a[4]는 각각 처음부터 순서대로 1 ~ 5로 초기화된다.
배열 요소의 최댓값 구하기
배열 a의 요소가 3개일 때 세 요소 a[0], a[1], a[2] 중 최댓값은 아래 코드처럼 구할 수 있다.
먼저 배열의 요솟수와 관계없이 첫 번째 요소 a[0]의 값을 max에 대입한다. 그런 후 if문을 실행하는 과정에서 필요에 따라 max값을 새로 대입한다. 요솟수가 n이면 if문 실행은 n - 1번 필요하다. 이때 max와 비교하거나 max에 대입하는 요소의 인덱스는 1씩 증가한다. 그러므로 아래처럼 코드를 수정할 수도 있다.
프로그램 실행 중 배열의 요솟수 결정하기
배열의 요소를 구하는 절차를 별도의 메서드 maxOf로 구현했다. 이 메서드는 인수로 받은 배열 a의 최댓값을 구하고 그 값을 반환한다.
난수를 사용해 배열의 요솟값 설정하기
배열의 요소에 값을 하나씩 입력하는 것이 귀찮으면 각 요소에 난수를 대입하면 된다.
난수를 생성할 때 java.util 패키지의 Random 클래스를 사용한다. 위 코드에 박스 친 부분 rand.nextInt(90)은 0부터 89(n-1)까지의 난수를 반환한다.
배열 요소를 역순으로 정렬하기
이번에는 배열 요소를 역순으로 정렬하는 알고리즘이다. 예로 배열 a의 요솟수가 5이고, 순서대로 {2, 5, 1, 3, 9}가 들어가 있다면 이것을 {9, 3, 1, 5, 2}로 바꿔본다. 먼저 맨 앞의 요소 a[0]과 맨 뒤 요소 a[4]의 값을 교환한다. 이어서 a[1]과 a[3]의 값도 교환한다. 교환 횟수는 '요솟수 / 2'이며 이 나눗셈에서 나머지는 버린다. 변수 i값을 0, 1...로 증가시키는(increment)방법을 통해 요솟수가 n인 배열의 처리 과정을 나타내면 아래와 같다.
1. 왼쪽 요소의 인덱스 ... i //n이 5면 0 -> 1 -> 2
2. 오른쪽 요소의 인덱스 ... n - i - 1 //n이 5면 4 -> 3 -> 2그러므로 요솟수가 n인 배열 요소를 역순으로 정렬하는 알고리즘을 코드로 나타내면 아래와 같다.
for(int i = 0; i < n / 2; i++)
//a[i]와 a[n - i - 1]의 값을 교환
}
두 값의 교환
배열을 역순으로 정렬하려면 배열 안의 두 요소를 교환해야 한다. (교환 값은 x, y로 한다.)
이 메서드는 추후에 굉장히 유용할 것 같다. 그리고 코드 너무 이쁜 것 같다. 이렇게 간결하고 이쁘니 볼수록 기분이 좋다.
기수 변환하기
정숫값을 특정 기수로 변환하는 알고리즘이다. 본 작성자도 기수가 뭔지 몰라서 인터넷에 검색해봤다.
이런 뜻이라는데 잘 모르겠다. 그냥 책에서 나오니 따라하자.
10진수 정수를 n진수 정수로 변환하려면 정수를 n으로 나눈 나머지를 구하고, 그 몫을 n으로 나누는 과정을 반복해야 한다. 이 과정을 몫이 0이 될 때까지 반복하고, 이런 과정을 통해 구한 나머지를 거꾸로 나열한 숫자가 기수로 변환한 숫자다. 쓰면서도 뭔 말인지 모르겠다.. 휴..
소수 나열하기
어떤 정수 이하의 소수를 모두 나열하는 알고리즘이다. 소수는 자신과 1 이외의 어떤 정수로도 나누어떨어지지 않는 정수다. 예로 소수인 13은 2,3 ~ 12 중 어떤 정수로도 나누어떨어지지 않는다. 그러므로 어떤 정수 n이 아래의 조건을 만족하면 소수임을 알 수 있다.
2부터 n - 1까지의 어떤 정수로도 나누어떨어지지 않는다.아래는 1,000 이하의 소수를 나열하는 프로그램이다.
알고리즘 개선하기 1
위 프로그램에서는 n이 2 또는 3으로 나누어떨어지지 않으면 2 x 2인 4 또는 2 x 3인 6으로도 나누어떨어지지않는다. 그러므로 위 프로그램은 불필요한 나눗셈을 하고 있다. n이 소수인지 판단하는 것은 아래 조건만 만족하는지 조사하면 된다.
2부터 n - 1까지의 어떤 소수로도 나누어떨어지지 않는다.예로 7이 소수인지는 7보다 작은 소수 2, 3, 5로 나눗셈을 하면 충분하다. 이를 바탕으로 개선한 프로그램을 구현한다. 소수를 구하는 과정에서 그때까지 구한 소수를 배열 prime의 요소로 저장한다. 이때 n이 소수인지 아닌지 판단하려면 그때까지 저장해 둔 소수로 나눗셈을 진행한다. 프로그램의 진행에 따라 배열에 저장되는 값이 변화한다. 먼저 2는 소수이므로 값 2를 prime[0]에 저장한다. 3 이상의 소수는 이중 for문으로 구한다. 바깥쪽 for문은 n값을 2씩 증가시켜 3, 5, 7, 9,...999로 홀숫값만 생성한다. 4 이상의 짝수는 2로 나누어떨어지므로 소수가 아니기 때문이다. 안쪽 for문은 i값을 1부터 시작해 ptr - 1회 반복한다.
알고리즘 개선하기 2
1 x 100을 제외한 100의 약수를 그림으로 나타내면 정사각형 10 X 10을 중심으로 모든 직사각형은 대칭 형태를 이룬다. 이는 넓이가 같은 정사각형 한 변의 길이까지만 소수로 나눗셈을 시도하고, 그 과정에서 한 번도 나누어떨어지지 않으면 소수라고 판단해도 좋다는 것을 의미한다. 즉, 어떤 정수 n은 아래 조건을 만족하면 소수라 판단할 수 있다.
n의 제곱근 이하의 어떤 소수로도 나누어떨어지지 않는다.이 조건을 바탕으로 프로그램을 개선해보자.
확장 for문
지금까지 프로그램에서 본 배열은 다룰 때 거의 대부분 for문을 사용했다. 이 for문을 기본 for문(basic for statement)이라 한다. 또 다른 for문인 확장 for문(enhanced for statement)을 사용하면 배열의 스캔을 매우 간결히 구현할 수 있다.
코드를 구현하며 해석하다 보니 잘 모르겠던 말도 이해가 된다. 확실히 직접 코드를 작성해보는 것이 굉장히 중요한 것 같다. 아직 고등학생이라 취업을 위한 코딩 학원을 다니지는 못하지만 얼른 졸업하고 학원에 가보고 싶다. 그곳에서 팀원들과 함께 프로그램을 만들고 아이디어를 제시하며 공부하고 싶다.
참고 서적 :
