수업 13일차

2차원 배열

1. [4][3] 2차원 배열 -> [6][2] 2차원배열
   • 순서 : 2차원 배열 -> 1차원배열 -> 2차원 배열
   • 코드

     int [][] m = { {1,2,3}, {4,5,6}, {7,8,9}, {10,11,12} };
     int [][] n = new int[6][2];
     int m_cols = m[0].length;
     int n_cols = n[0].length;
     		
     // 2차원 -> 1차원 -> 2차원
     for(int i = 0,k=0; i < m.length; i++) {
     	for(int j = 0; j < m[i].length; j++,k++) {
     		int temp = m_cols*i+j;			
     		n[temp/n_cols][temp%n_cols] = m[i][j];	
     	}
     }​

2. 대각선 채우기

   1	2	4	7	11
   3	5	8	12	16
   6	9	13	17	20
   10	14	18	21	23
   15	19	22	24	25

   코드

   int [][] m = new int [4][6];
   int n = 0, k = 1,idx = 0 ;
   while(k <= m.length * m[0].length) {
   	m[idx][n-idx] = k++;
   	if(  n >= m[0].length-1 && (idx == m.length-1 || m.length > m[0].length && n - idx == 0) ) {
   		n++;		
   		idx = n - m[0].length;
   	}
   	else if( idx == m.length-1 || (n-idx == 0 && (n < m.length-1 || n < m[0].length-1) ) ) {
   		n++;
   		idx = -1;
   	}
   	idx++;
   }​

3. 마방진

   17	24	1	8	15
   23	5	7	14	16
   4	6	13	20	22
   10	12	19	21	3
   11	18	25	2	9

   •  원리
     • 첫 번째 행의 가운데 열 : 1
     • 출력 값이 5의 배수 일 때는 행만 증가
     • 열 증가, 행 감소
       1. 행 벗어나면 : 가장 큰 행값
       2. 열 벗어나면 : 가장 작은 열값
   • 코드

     int row = 0, col = m.length/2, n = 1;
     while(n <= 25) {
     	m[row][col] = n;
     	if(n % m.length == 0) row++;
     	else {
     		col++;
     		row--;
     	}
     	if(row < 0)	row = m.length-1;
     	else if(col > m.length-1)	col = 0;
     	n++;
     }​

4. 달팽이 채우기

   1	2	3	4	5
   16	17	18	19	6
   15	24	25	20	7
   14	23	22	21	8
   13	12	11	10	9

   코드

   int [][] m = new int [7][4];
   int k = 1, idxRow = 0, idxCol = 0, row = m.length, col = m[0].length, count = 0;;
   String direction = "right";
   while(k <= m.length*m[0].length) {
   	m[idxRow][idxCol] = k++;
   	count++;
   	switch(direction) {
   		case "right": 
   			idxCol++;
   			if(count == col) {
   				row--;	idxCol--;	idxRow++;	
   				count = 0;	direction = "down";
   			}
   			break;
   		case "down":
   			idxRow++;
   			if(count == row) {
   				col--;	idxRow--;	idxCol--;
   				count = 0;	direction = "left";
   			}
   			break;
   		case "left":
   			idxCol--;
   			if(count == col) {
   				row--;		idxCol++;	idxRow--;	
   				count = 0;	direction = "up";
   			}
   			break;
   		case "up":
   			idxRow--;
   			if(count == row) {
   				col--;	idxRow++;	idxCol++;
   				count = 0;	direction = "right";
   			}
   			break;
   	}
   }​

검색(search)

1. 순차 검색(Sequence Search)
   • 정의 : 데이터 집합에서 처음부터 순차적으로 비교하면서 찾는 방법
   • 탐색 방법 : 찾을 수를 데이터 집합 처음부터 하나 씩 비교하면서 수를 찾으면 해당 index를 반환
   • 만든 함수 – sequenceSearch (배열명, 검색할 수)
     • 기능 : 순차 검색할 함수 선언
     • 매개변수 : 검색할 대상(배열명), 검색할 숫자(searcjNumber)
     • 리턴 값 : 그 배열에서 검색할 수를 찾은 배열의 index값을 반환
                  만약 찾는 숫자가 없을 경우에는 –1을 반환
     • 코드

       private static int sequenceSearch(int[] m, int searchNumber) {
       	int idx = -1;
       	for (int i=0; i < m.length; i++)
       		if( m[i] == searchNumber) return idx;
       	return -1;
       }

2. 이진 검색(Binary Search)
   • 정의 : 정렬된 데이터 집합을 이분화 하면서 탐색하는 방법
   • 탐색 방법 : 정렬된 데이터 집합의 중간 값과 찾을 값을 비교하여 찾을 값보다 작으면 중간 값의 우측 값을 크면 좌측 값과 끝 값의 중간을 다시 잡고 찾는 것을 반복하여 해당 값의 위치를 찾는다.
   • 함수 : Arrays.binarySearch(배열명, 찾을 값);
   • 코드

     private static int binarySearch(int[] m, int n) {
     	int bottom = 0, top = m.length-1, middle;
     	while(bottom <= top) {
     		middle = (bottom + top)/2;
     		if(m[middle] == n) return middle;
     		else if(m[middle] > n) top = middle - 1;
     		else bottom = middle + 1;
     	}
     	return -1;
     }

정합 정렬(Merge Sort)

1. 정의 : 이미 정렬되어 있는 두 개의 배열을 합하여 한 개의 배열로 만드는 정렬 방식
2. 원리 : 두 개의 배열의 요소를 비교하면서 작은 것부터 순서로 넣고 한 개의 배열이 다 들어가면
            나머지 배열의 값을 다 넣는다.
3. 코드

   int [] m = {1,3,6};
   int [] n = {2,4,5,7,8,9};
   int [] mn = new int [m.length + n.length];
   int idx_m = 0, idx_n = 0, idx_mn = 0;
   while(idx_m < m.length && idx_n < n.length)
   	mn[idx_mn++] = m[idx_m]>n[idx_n] ? n[idx_n++] : m[idx_m++];
   for(;idx_mn < mn.length; idx_mn++)
   	mn[idx_mn] = idx_m >= m.length ? n[idx_n++] : m[idx_m++];

문제1 – ego(자아)

1. 문제 내용

   String n = "keNik";
   String m= "kKnie";
   위의 두 문자열 n, m 이 알파벳과 알파벳갯수가 똑같은지 비교하는 코딩
   결과는 같을 경우 true/ 다를 경우 false 로 출력.
   조건) 대소문자는 구분하지 않는다.

2. 코드

   public static void main(String[] args) {
   	String n = "keNik";
   	String m = "kKnei";
   
   	System.out.println(getEquals(n,m));
   }
   
   private static boolean getEquals(String n, String m) {
   	String [] nArr = n.toLowerCase().split("");
   	String [] mArr = m.toLowerCase().split("");
   	Arrays.sort(nArr);
   	Arrays.sort(mArr);
   	return Arrays.equals(nArr, mArr);
   }

문제2 - 막대기 자르기

1. 문제 내용

   각각 0이상의 정수를 길이로 하는 N개의 막대기가 있다.
   이 막대기들 중 가장 짧은 막대기의 길이로 모든 막대기를 자르는 것을 [cut operation]이라고 하자.
   예를 들어 6개의 막대기가 있고 그 길이가 다음과 같다면
   5 4 4 2 2 8 이 경우 [Cut Operation]을 한번 수행하면 다음과 같다.
   3 2 2 6 (가장 짧은 길이인 2로 6개의 막대기를 잘라내고 길이가 0이 되버린 2개의 막대기는 버려진다.)
   N개의 막대기와 그 각각의 길이가 주어졌을 때 [Cut Operation]을 모든 막대기가 
   버려질 때(길이가 0이 될때)까지 반복하고 수행 시 마다 남은 막대기의 수를 출력하는 프로그램을 작성하라.
   
   입력
   첫줄에 막대기의 수 N을, 다음 줄에 각각의 막대기의 길이를 공백으로 구분해서 입력한다.
   
   출력
   매 줄마다 [Cut Operation]이 수행 되 때 마다 남은 막대기의 수를 출력
   
   제한
   1 <= N <= 1000
   1 <= 막대기의 길이 <= 1000
   
   입력 예제 #1 		입력 예제 #2
   6 			8
   5 4 4 2 2 8 		1 2 3 4 3 3 2 1
   
   출력 예제 #1 		출력 예제 #2
   6 			8
   4 			6
   2 			4
   1 			1

2. 코드

   public static void main(String[] args) {
   	Scanner scanner = new Scanner(System.in);
   	int n = scanner.nextInt();
   	int [] m = new int [n];
   	for(int i = 0; i < n; i++)
   		m[i] = scanner.nextInt();
   	CutOperation(m);
   }
   private static void CutOperation(int[] m) {
   	int min = 1001 ,count ;
   	// 가장 작은 길이 선택
   	while(min != 0) {
   		min = 1001; count = 0;
   		for(int i = 0; i < m.length; i++) {
   			if(min > m[i] && m[i] != 0) min = m[i];
   			if(m[i] != 0) count++;
   		}
   		if(count == 1) break;
   		else if(min == 1001) min = 0;
   		count = 0;
   		// 가작작은 길이로 자르고 개수세기
   		for(int i = 0; i < m.length; i++) {
   			m[i] -= m[i] == 0 ? 0 : min;
   			if(m[i] > 0) count++;
   		}
   	}
   }