2차원 Array
2차원 Array의 선언 : 세로길이(행의 개수), 가로 길이(열의 개수)를 필요로 함.
Array의 순회
- n X m 배열의 n&m개의 모든 원소를 조사하는 방법
- 행 우선 순회
- 열 우선 순회
- 지그재그 순회
행 우선 순회
- 행을 우선으로 Array의 원소를 조사하는 방법
int n = 5;
int m = 5;
int [][]arr = {
{1,2,3,4,5},{1,2,3,4,5},{1,2,3,4,5},{1,2,3,4,5},{1,2,3,4,5}};
int i,j;
for(i = 0 ; i < n; i++) {
for(j = 0; j < m; j++) {
System.out.println(arr[i][j]);
}
}
- 열을 우선으로 Array의 원소를 조사하는 방법
행 우선 순회와 달리 i와 j 의 위치를 바꾸어서 for문을 작성한다.
int n = 5;
int m = 5;
int [][]arr = {
{1,2,3,4,5},{1,2,3,4,5},{1,2,3,4,5},{1,2,3,4,5},{1,2,3,4,5}
};
int i,j;
for(j = 0 ; j < n; j++) {
for(i = 0; i < m; i++) {
System.out.println(arr[i][j]);
}
}
- 지그재그 순회
첫 행은 우측으로, 다음 행은 좌측으로 진행하여 Arrayㅡ이 원소를 조사하는 방법
-------->
<--------
-------->
int n = 5;
int m = 5;
int [][]arr = {
{1,2,3,4,5},{1,2,3,4,5},{1,2,3,4,5},{1,2,3,4,5},{1,2,3,4,5}
};
int i,j;
for(i = 0 ; i < n; i++) {
for(j = 0; j < m; j++) {
System.out.println(arr[i][j+(m-1-2*j)*(i%2)]);
}
}
이게 잘 이해가 안가면 그냥 if문 써서 따로따로 채워주면 되긴한다.
델타를 이용한 2차 탐색
- 2차원 Array의 한 좌표에서 네 방향의 인접 Array요소를 탐색할 때 사용하는 방법
- 델타값: 한 좌표에서 입력한 네 방향의 좌표와 x,y의 차이를 저장한 Array
- 델타값을 이용하여 특정 원소의 상하좌우에 위치한 원소에 접근
델타를 이용한 2차 Array 탐색의 예
전치 행렬
- 행과 열의 값이 반대인 행렬
부분 집합 문제
(각 원소가 부분 집합에 포함 관계를 0과 1로 표현한다면 , 비트 연산자를 이용하여 주어진 집합의 부분집합들을 2진수로 표현이 가능하다.)
부분 집합의 합 문제
-
유한 개의 정수로 이루어진 집합이 있을 떄, 이 집합의 부분집합 중에서 그 집합의 원소를 모두 더한 값이 0이 되는 경우가 있는지를 알아내는 문제
예 {-7, -3, -2 ,5,8}이 있을 때. 1.{-3,2,5}는 부분집합이면서 2.(-3)+(-2)+5 = 0 이므로 이 답은 참이다.
=> 1. 완전 검색기법으로 부분집합의 합 문제를 풀기 위해서는 우선 집합의 모든 부분집합을 생성한 후 각 부분 집합의 합을 계산한다
- 주어진 부분 집합을 생성하는 방법 생각해본다.
※ 집합의 원소가 n개일 때, 공집합을 포함한 부분집합의 수는 2^n개이다.
- 각 원소를 부분집합에 포함시키거나 포함시키지 않는 2가지의 예는 {1,2,3,4} => 222*2 = 16가지이다.
부분집합 알고리즘
bit[]란 비트로 이루어진 array이다.
부분집합 알고리즘(2)
i&(1<<j)
«연산자와 &연산자를 이용하여
- i의 j번째 Bit가 1인지 아닌지를 리턴하여 확인할 수 있다.
int i,j;
int []arr = {3,6,7};
int n = arr.length;
// System.out.println(1<<3); 1을 왼쪽으로 3번이동.
for(i = 0 ; i<(1<<(n));i ++) {//1<<n: 부분집합의 개수
for(j = 0; j < n; j++) {// 원소의 수만큼 Bit를 비교
// System.out.print(i & (1<<j));
if((i & (1<<j)) == 0) { // i의 j번째 bit가 1이면 j번째 원소 출력
System.out.print(" i : " + i + " j: " + j + " arr[j]: " + arr[j]);
}
}
System.out.println("\n");
}
검색
- 저장되어 있는 자료 중에서 원하는 항목을 찾는 작업 (원하는 항목 : 목적하는 탐색키를 가진 항목)
- 목적하는 탐색키를 가진 항목을 찾는 것 (탐색키 : 자료를 구별하여 인식할 수 있는 키)
- 검색의 종류 (순차 검색, 이진 검색, 인덱싱 등)
순차 검색
- 일렬로 되어 있는 자료를 순서대로 검색하는 방법
- Array, 연결 리스트 등 순차구조로 구현된 자료 구조에서 유용
- 구현이 쉽지만, 검색 대상이 많은 경우 수행시간의 증가로 비효율적
- 순차검색의 종류 (정렬된 경우/ 정렬되지 않은 경우)
정렬되지 않은 자료의 검색 과정
첫 번째 원소부터 순서대로 검색 대상과 키 값이 같은 원소가 있는지를 비교하여 찾음
키 값이 동일한 원소를 찾으면 그 원소의 인덱스를 반환
자료구조의 마지막에 갈 때까지 검색 대상을 찾지 못하면 검색 실패
=> 찾을 원소의 순서에 따른 비교 횟수 결정.
정렬된 자료의 검색과정
자료가 오름차순으로 정렬된 상태에서 검색을 실시한다고 가정
자료를 순차적으로 검색하면서 키 값을 비교함
원소의 키 값이 검색 대상의 키 값보다 크면 원소다 업다는 것이므로 더 이상 검색하지 않고 검색을 종료함
정렬되어 있으므로 검색 실패를 반환하는 경우 평균 비교 회수가 반으로 줄어듬 하지만 시간복잡도는 O(n)으로 동일. (없는 경우가 있기 때문에)
이진 검색
- 효율적인 검색 방법
- 자료의 가운데에 있는 항목의 키 값과 비교 후 다음 검색 위치 결정
- 목적 키를 찾을 때 까지 이진 검색을 순환적을 반복 수행함
- 검색 범위를 반으로 줄여가면서 빠르게 검색 수행
- 이진 검색을 하기 위해서는 자료가 정렬된 상태여야 함.
이진 검색의 검색 과정
- 자료의 중앙에 있는 원소를 선택
- 중앙의 원소의 값과 찾고자 하는 목표 값을 비교
- 목표값 < 중앙 원소 값 : 자료의 왼쪽 반에 대해서 새로 검색을 수행 목표 > 중앙 원소 값 : 자료의 오른쪽 반에 대해서 새로 검색을 수행
- 찾고자 하는 값을 찾을 때까지 1~3의 과정을 반복
재귀 함수 이용한 이진 함수 구현
인덱스 검색
인덱스의 의미
- 데이터베이스에서 유래
- 테이블에 대한 동작 속도를 높여주는 자료구조
- 데이터베이스 분야가 아닌 곳에서는 Look up table 등의 용어를 사용하기도 함
인덱스 저장 공간
- 테이블을 저장하는 데 필요한 디스크 공간보다 작음
- 인덱스는 키-필드만 갖고 있고, 테이블의 다른 세부 항목들은 갖고 있지 않기 때문임
- 배열을 사용 : 대량의 데이터 정렬 시 프로그램 반응이 느려질 수 있으므로 사용
정렬
선택 알고리즘의 의미
- 저장되어 있는 자료로부터 k번째로 큰 혹은 작은 원소를 찾는 방법
- 최소값, 최대값 혹은 중간값을 찾는 알고리즘을 의미하기도 함
선택 과정 -> 정렬 알고리즘을 이용하여 자료를 정렬 , 원하는 순서에 있는 원소 가져오기
ex) k번째로 작은 원소를 찾는 알고리즘
-
1번부터 k번째까지 작은 원소들을 찾아 Array의 앞쪽으로 이동시키고 , Array의 k번째를 반환
-
k가 비교적 작을 때 유용하며 O(kn)의 시간복잡도를 가짐.
선택 정렬
당구대 위에 있는 공 중 가장 작은 공부터 차례대로 정리
-
선택 정렬 의미 : 주어진 자료들 중 가장 작은 값의 원소부터 차례대로 선택하여 위치를 교환하는 방식
-
셀렉션 알고리즘을 전체 자료에 적용한 것
정렬 과정
- 주어진 리스트 중에서 최소값을 찾음
- 그 값을 리스트의 맨 앞에 위치한 값과 교환
- 맨 처음 위치를 제외한 나머지 리스트를 대상으로 위의 과정을 반복
시간 복잡도
- O(n^2)
선택 정렬 한번 짜보자.
public static void SelectionSort(int a[]) {
int i , j , min,temp;
int size =a.length;
for(i = 0 ; i < size-2; i ++) { //왜 size-2일까. 하나고르니 -1가능.아 그리고 가장 마지막은 굳이 해볼 필요 없음.
min = i;
for( j = i+1 ; j < size-1; j++) {
if(a[j] < a[min])
min = j;
}
temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}
public static void main(String[] args) {
int []arr = {2,5,1,8,9};
int size = arr.length;
SelectionSort(arr);
System.out.println(Arrays.toString(arr));
}
참고자료
소프트웨어 아카데미 S/W Problem Solving
배열의 모든 부분집합 https://bcp0109.tistory.com/17