간단한 자료구조인 배열을 살펴보겠다.
자료구조 : 데이터 단위와 데이터 자체 사이의 물리적 또는 논리적인 관계
배열 : 같은 자료형(Type)의 변수인 구성 요소가 모인 것
선언법
int[] a 배열 변수, 이것은 특별한 변수일뿐 배열 그 자체가 아니며 new를 이용해 메모리의 힙 영역이라는 곳에 공간을 할당해 줘야 비로소 배열이 된다.
int[] a = new int[크기]; // 배열 초기화 1
int[] b = {1, 2, 3, 4, 5}; // 배열 초기화 2
배열 접근법 : 배열 변수 이름[인덱스]
길이 : 배열 변수 이름.length
난수 생성
난수의 생성은 seed를 임의로 생성하거나 seed를 지정할 수 있고, seed는 48비트를 사용한다.
이 seed는 '선형 합동법'이라는 계산법에 의해 난수로 바뀐다.
※ 선현 합동법 : 보편적으로 사용하는 의사 난수 생성기로 현재 난숫값을 A배 하고 C를 더한 다음, M으로 나눈 나머지를 의사 난수로 선택하는 방법이다.
배열 역순 정리
교환 횟수 '요솟수 / 2'이다. 이렇게 해주는 이유는 홀 수 일 때 가운데 요소는 교환할 필요가 없기 때문이다.
1. 왼쪽 요소의 인덱스 • • • i , n이 7이면 0 > 1 > 2
2. 오른쪽 요소의 인덱스 • • • n - i - 1 n이 7이면 6 > 5 > 4
알고리즘 코드로 나타내면 다음과 같다.
for(int i = 0; i < n / 2; i++)
// a[i]와 a[n - i - 1]의 값을 교환
두 값의 교환
배열을 역순으로 정렬하기 위해서 변수 3개가 필요하다. (x, y, tmp)
1. tmp = x;
2. x = y;
3. y = tmp;
역순 정렬 알고리즘 코드
import java.util.Arrays;
import java.util.Scanner;
public class ReverseArray {
static void swap(int[] a, int idx1, int idx2) {
int t = a[idx1]; a[idx1] = a[idx2]; a[idx2] = t;
}
static void reverse(int[] a) {
for(int i = 0; i < a.length; i++) {
System.out.println(Arrays.toString(a));
swap(a, i, a.length - i - 1);
System.out.println("a[" + i + "]와 a[" + (a.length - i - 1) + "]을 교환합니다.");
}
}
static int sumOf(int[] a) { // 합계를 구해 반환하는 메서드
int sum = 0;
for(int i = 0; i < a.length; i++) {
sum += a[i];
}
return sum;
}
static void copy(int[] a, int[] b) {
System.arraycopy(b, 0, a, 0, b.length); // arraycopy 사용한 것
}
static void rcopy(int[] a, int[] b) {
for (int i = 0; i < b.length; i++) { // 수동으로 복사한 것
a[i] = b[b.length - i - 1];
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("요솟수: ");
int n = sc.nextInt();
int[] x = new int[n]; // 요솟수가 n인 배열
for(int i = 0; i < n; i++) {
System.out.print("x[" + i + "]: ");
x[i] = sc.nextInt();
}
reverse(x); // 배열 a의 요소를 역순으로 정렬
System.out.println("요소를 역순으로 정렬했습니다.");
System.out.println("x = " + Arrays.toString(x));
System.out.println("모든 요소의 합 : " + sumOf(x));
System.out.println("배열 b에 모든 요소를 배열 a에 복사합니다.");
int[] tmp = new int[n];
copy(tmp, x);
System.out.println("복사 완료! tmp = " + Arrays.toString(tmp));
}
}
배열의 전체 요소 표시
Arrays.toString(배열 변수 이름)을 사용해도 되고 반복문을 돌려서 전체 요소를 표시해도 된다.
배열 복사
얕은 복사 vs 깊은 복사 차이점
얕은 복사 : 객체의 주소(참조값)만 복사한다. 즉, 원본과 복사본이 같은 객체를 참조한다.
ex) a = b 또는 a = b.clone()
깊은 복사 : 객체의 실제 내용까지 완전히 새로 복사한다. 원본과 복사본이 완전히 독립적이다.
ex) for문을 이용한 수동 복사 또는 System.arraycopy(A, A의 시작 index, B, B의 시작 index, 복사할 길이) 등이 있다.
위 코드에서는 깊은 복사가 필요하다. copy 메서드에서는 arraycopy를 사용했고 rcopy에서는 수동 복사를 이용했으니 참고 바란다.
기수 변환하기
정수값을 특정 기수로 변환하는 알고리즘 ex) 10진수 정수를 n진수 정수로 변환
n 진수 : n을 기수로 하는 수
※ 기수 : 수를 나타내는데 기초가 되는 수 ex) 일, 이, 삼 | 서수 : 사물의 순서를 나타내는 수 ex) 첫째, 둘째, 셋째
2진수 (0, 1)
각 자리는 아랫자리부터 2⁰, 2¹, 2² • • • 으로 2를 거듭 제곱한 값을 갖는다.
ex) 1011 = 1 x 2³ + 0 x 2² + 1 x 2¹ + 1 x 2⁰
8진수 (0 ~ 7)
각 자리는 아랫자리부터 8⁰, 8¹, 8² • • • 으로 8을 거듭 제곱한 값을 갖는다.
ex) 5306 = 5 x 8³ + 3 x 8² + 0 x 8¹ + 6 x 8⁰
10진수 (0 ~ 9)
각 자리는 아랫자리부터 10⁰, 10¹, 10² • • • 으로 10을 거듭 제곱한 값을 갖는다.
ex) 1234 = 1 x 10³ + 2 x 10² + 3 x 10¹ + 4 x 10⁰
16진수 (0 ~ 9, A ~ F)
각 자리는 아랫자리부터 16⁰, 16¹, 16² • • • 으로 16을 거듭 제곱한 값을 갖는다.
ex) 12A0 = 1 x 16³ + 2 x 16² + A x 16¹ + 0 x 16⁰
기수 변환 알고리즘 코드
import java.util.Scanner;
public class CardConv {
// 정숫값 x를 r진수로 변환하여 배열 d에 아랫자리부터 넣어 두고 자릿수를 반환
static int cardConv(int x, int r, char[] d) {
int digits = 0;
String dchar = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
do {
d[digits++] = dchar.charAt(x % r); // r로 나눈 나머지 저장
x /= r;
}while(x != 0);
for(int i = 0; i < digits / 2; i++) { // 배열 d의 숫자 문자열을 역순으로 정렬
char t = d[i];
d[i] = d[digits - i - 1];
d[digits - i - 1] = t;
}
return digits;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int no; // 변환하는 정수
int cd; // 기수
int dno; // 변환 후의 자릿수
int retry; // 다시 한번?
char[] cno = new char[32]; // 변환 후 각 자리의 숫자를 넣어 두는 문자 배열
System.out.println("10진수를 기수 변환합니다.");
do {
do {
System.out.print("변환하는 음이 아닌 정수: ");
no = sc.nextInt();
}while(no < 0);
do {
System.out.print("어떤 진수로 변환할까요? (2~36): ");
cd = sc.nextInt();
}while(cd < 2 || cd > 36);
dno = cardConv(no, cd, cno); // no를 cd진수로 변환
System.out.print(cd + "진수로");
for(int i = 0; i < dno; i++)
System.out.print(cno[i]); // 순서대로 출력
System.out.println("입니다.");
System.out.print("한 번 더 할까요? (1. 예 / 0. 아니요) : ");
retry = sc.nextInt();
}while(retry == 1);
}
}
소수 나열하기
어떤 정수 이하의 소수를 모두 나열하는 알고리즘
소수란?
자신과 1을 제외한 어떤 정수로도 나누어 떨어지지 않는 정수. 즉, 2부터 n - 1까지의 어떤 정수로도 나누어 떨어지지 않는다.
만약 나누어 떨어지는 정수가 하나 이상 존재하면 그것은 '합성수'이다.
소수 나열하기 알고리즘 1
public class PrimeNumber1 {
public static void main(String[] args) {
int counter = 0; // 나눗셈의 횟수
for(int n = 2; n <= 1000; n++) {
int i ;
for(i = 2; i < n; i++) {
counter++;
if(n % i == 0) // 나누어 떨어지면 소수가 아님
break; // 반복은 더 이상 불필요하다.
}
if(n == i) // 마지막까지 나누어 떨어지지 않으면 해당 n은 소수이다.
System.out.println(n);
}
System.out.println("나눗셈을 수행한 횟수: " + counter);
}
}
- n이 소수인 경우 : n과 같은 값 (for 문이 끝까지 실행됨)
- n이 합성수인 경우 : n보다 작은 값 (for문이 중단됨)
알고리즘 개선하기1
n이 2 or 3으로 나누어 떨어지지 않으면 2x2인 4 또는 2x3인 6으로도 나누어 떨어지지 않는다.
따라서 PrimeNumber1은 불필요한 나눗셈을 하고 있음을 알 수 있다. 따라서 정수 n이 소수인지의 여부 판단 조건은
`2부터 n - 1까지의 어떤 소수로도 나누어 떨어지지 않는다.'이다.
ex) 7은 n보다 작은 소수 2, 3, 5로 나눗셈을 하면 충분하다.
public class PrimeNumber2 {
public static void main(String[] args) {
int counter = 0; // 나눗셈의 횟수
int ptr = 0; // 찾은 소수의 개수
int[] prime = new int[500]; // 소수를 저장하는 배열
prime[ptr++] = 2; // 2는 소수다
for(int n = 3; n <= 1000; n += 2) { // 조사 대상은 홀수만
int i;
for(i = 1; i < ptr; i++) { // 이미 찾은 소수로 나누어 봄
counter++;
if(n % prime[i] == 0) // 나누어 떨어지면 소수가 아님
break; // 더이상 반복은 불 필요하므로 break
}
if(ptr == i) // 마지막까지 나누어 떨어지지 않으면
prime[ptr++] = n; // 소수이므로 배열에 저장
}
for(int i = 0; i < ptr; i++)
System.out.println(prime[i]);
System.out.println("나눗셈을 수행한 횟수: " + counter);
}
}
첫 번째 함수와 두 번째 함수를 비교하면 다음과 같은 결론을 내릴 수 있다.
- 같은 답을 얻는 알고리즘이 하나로 한정되지 않는다.
- 빠른 알고리즘은 메모리를 많이 필요로 하는 경향이 있다. (prime 배열을 이용해 메모리 공간을 할당 받는다.)
알고리즘 개선하기2
한 가지 예를 들어본다. 넓이가 100인 직사각형에서 4x25와 25x4는 가로, 세로 길이가 다르지만 같은 직사각형이다.
이는 넓이가 같은 정사각형 한변의 길이까지만 소수로 나눗셈을 시도하고, 그 과정에서 한번도 나누어 떨어지지 않으면 소수라고
판단해도 좋다는 것을 의미한다.
즉, 'n의 제곱근 이하의 어떤 소수로도 나누어 떨어지지 않는다.'
이를 위해 prime[i]의 제곱이 n이하인가?를 나타내는 코드가 필요하다.
public class PrimeNumber3 {
public static void main(String[] args) {
int counter = 0; // 나눗셈의 횟수
int ptr = 0; // 찾은 소수의 개수
int[] prime = new int[500]; // 소수를 저장하는 배열
prime[ptr++] = 2; // 2는 소수다
prime[ptr++] = 3; // 3은 소수다
for(int n = 5; n <= 1000; n += 2) { // 조사 대상은 홀수만
boolean flag = false;
for(int i = 1; prime[i] * prime[i] <= n; i++) { // 이미 찾은 소수로 나누어 봄
counter += 2;
if(n % prime[i] == 0) // 나누어 떨어지면 소수가 아님
flag = true;
break; // 더이상 반복은 불 필요하므로 break
}
if(!flag) { // 마지막까지 나누어 떨어지지 않으면
prime[ptr++] = n; // 소수이므로 배열에 저장
counter++;
}
}
for(int i = 0; i < ptr; i++)
System.out.println(prime[i]);
System.out.println("나눗셈을 수행한 횟수: " + counter);
}
}
이를 통해 알고리즘은 푸는 것도 중요하지만 얼만큼 시간을 아낄 수 있냐와 메모리 공간을 얼마나 적게 사용하느냐가 관건인 것 같다는 생각이 든다.
'알고리즘' 카테고리의 다른 글
| 6. 정렬 알고리즘 - 1 (0) | 2025.07.10 |
|---|---|
| 5. 재귀 알고리즘 (0) | 2025.07.06 |
| 4. 스택과 큐 (0) | 2025.07.02 |
| 3. 검색 알고리즘 (0) | 2025.06.29 |
| 1. 기본 알고리즘 (0) | 2025.06.24 |