두 정수 a와 b를 받아 a의 b 제곱을 구하는 코드를 짜보자. 여기서 b는 음이 아니어야 한다. 당연히 0은 된다. 이번 장은 메소드가 주제이므로 b 제곱을 계산해주는 함수를 따로 만들어볼 것이다.
import java.util.Scanner;
public class Code16 {
public static void main(String[] args) {
Scanner kb = new Scanner(System.in);
int a = kb.nextInt();
int b = kb.nextInt();
// 지수는 영어로 power라고 부르므로 power라고 지어봄.
int result = power(a, b);
System.out.println(result);
kb.close();
}
// 함수가 받는 파라미터의 이름은 달라도 상관없다.
static int power(int n, int m)
{
int prod = 1;
// n을 m번 곱한다.
for(int i=0; i<m; i++) {
prod *= n;
}
return prod;
}
}
public class Code17 {
public static void main(String[] args) {
for(int n=1; n<=100000; n++)
{
// isPrime이라는 함수가 true일 때만 정수를 출력한다.
if(isPrime(n))
{
System.out.println(n);
}
}
}
static boolean isPrime(int k)
{
// 1은 소수가 아니므로 false 리턴하는 조건을 추가한다.
// main의 for문을 어떻게 짜느냐에 따르겠지만 흠이 없게 만드는 방법을 설명하는 것이므로 참고.
if(k<2) return false;
for(int i=2; i*i<=k; i++)
{
if(k%i == 0)
{
return false;
}
}
// for문이 끝나고 이 자리에 왔다는 것은
// 한 번도 나누어 떨어지지 않았다는 뜻이므로 true를 보낸다.
return true;
}
}
이번에는 저번 시간에 했던 버블 소트를 메인 함수가 아니라 따로 함수를 만들어 호출하도록 짜본다.
public class Code18
{
public static void main(String[] args)
{
Scanner kb = new Scanner(System.in);
int n = kb.nextInt();
int[] data = new int[n];
for(int i=0; i<n; i++)
{
data[i] = kb.nextInt();
}
kb.close();
// 배열을 한번에 넘긴다.
bubbleSort(n, data);
System.out.println("Sorted data");
for(int i=0; i<n; i++) {
System.out.println(data[i]);
}
}
static void bubbleSort(int n, int[] data)
{
for(int i=n-1; i>0; i--)
{
for(int j=0; j<i; j++)
{
if(data[j]>data[j+1])
{
int tmp = data[j];
data[j] = data[j+1];
data[j+1] = tmp;
}
}
}
}
}
참고로, 계속 함수에 static을 쓰는 것은 나중에 설명할 개념이기 때문이다.
이번 문제는 위의 Code 18을 약간 수정해보려고 한다. data[j]와 data[j+1]을 교환하는 부분을 메소드로 바꿔보도록 한다. 그런데 이 문제에는 이슈가 하나 있다. 위처럼 swap에 바로 집어넣으면 원래 입력했던 데이터가 정렬되지 않은 채 그대로 출력된다.
이유를 알기 위해서는 call by value를 알아야 한다. 흔히 호출문에서 넘겨주는 인자는 actual parameter, 호출된 메서드에서는 formal parameter라고 한다.
값에 의한 호출이란, actual parameter와 formal parameter가 별개의 변수라는 의미다. swap 메소드를 호출하는 순간, 배열에 담긴 숫자는 그저 복사가 될 뿐, 같은 변수가 아니다. 따라서 호출된 메서드 swap에서 값을 처리했다고 해도 원본에 반영되지 않는다.
값에 의한 호출의 반대는 참조에 의한 호출이다(call by reference). 하지만 C와 Java에서는 이 방법을 지원하지 않는다. 간단히 설명하면 실제로 동일한 변수를 이름이 두 개인 것처럼 취급해서 작동하는 것이다. 이것을 이용하면 실제로 swap이 가능하다.
그런데 맨 처음에 짰던 코드는 data라는 배열을 그대로 넘겨줬는데도 작동했다. 왜일까?
그 내용을 배우려면 2장까지 가야 하므로 일단 배열은 예외라고 알아두자. 배열은 프리미티브 타입이 아니어서 값에 의한 호출을 따르지 않는다.
이번엔 파일에 담긴 데이터를 입력받는 코드를 짜보자. Chaper01에 input.txt을 먼저 만들어놓는다.
파일 입출력을 하면 오류가 발생한다.
위의 방법대로 예외 처리를 하면 된다.
그럼 자동으로 예외 처리 문을 생성해준다.
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Code19
{
public static void main(String[] args)
{
// 파일에 있는 내용을 담을 변수
// 그런데 파일을 읽기 전까지는 배열 크기가 얼마가 될지 알 수가 없다.
// 그냥 일단 충분히 잡으면 된다.
String[] name = new String[1000];
// 전화번호가 꼭 숫자가 아니라 대쉬같은 기호가 들어갈 수도 있으므로 String으로 받는다.
String[] number = new String[1000];
// 사람 수를 담을 변수. 아직 모르므로 0으로 초기화한다.
int n = 0;
// file 입출력은 예외 처리가 필수적이다.
try
{
// 파일은 키보드 입력처럼 Scanner를 사용한다.
String fileName = "input.txt";
Scanner inFile = new Scanner(new File(fileName));
// 지금까지는 for문으로 불러왔지만 그때는 데이터의 개수를 알았기 때문에 가능한 거였다.
// hasNext는 읽을 내용이 남아있는지 확인하고 남아있으면 true를 리턴한다.
while(inFile.hasNext()) // detect End of File(EOF)
{
// 일단 배열 0번부터 저장하고
name[n] = inFile.next();
number[n] = inFile.next();
// n을 증가시킨다.
n++;
}
inFile.close();
} catch (FileNotFoundException e)
{
e.printStackTrace();
}
for(int i=0; i<n; i++) {
System.out.println(name[i] + ":" + number[i]);
}
}
}최종적으로 이렇게 나올 수 있다.
이번에는 받은 정보를 그대로 보내지 않고 알파벳 순으로 정렬해 출력한다.
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Code20
{
public static void main(String[] args)
{
String[] name = new String[1000];
String[] number = new String[1000];
int n = 0;
try
{
String fileName = "input.txt";
Scanner inFile = new Scanner(new File(fileName));
while(inFile.hasNext())
{
name[n] = inFile.next();
number[n] = inFile.next();
n++;
}
inFile.close();
} catch (FileNotFoundException e)
{
e.printStackTrace();
}
// 정렬할 함수 호출
// sorting할 데이터의 개수와 처리할 데이터를 넘긴다.
bubbleSort(n, name, number);
for(int i=0; i<n; i++) {
System.out.println(name[i] + ":" + number[i]);
}
}
static void bubbleSort(int n, String[] name, String[] number) {
}
}지금까지 해왔던 방식을 따르면 이런 식으로 전개가 될 것이다.
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Code20
{
// 메인 함수 밖으로 뺀다. 함수 밖일 때는 무조건 static으로 선언해야 한다.
// 아직 클래스를 배우기 전이니 이정도까지만 이해하자.
// 함수 밖에서 선언된 변수들은 어디든 사용이 가능하므로 굳이 함수에 파라미터로 넘겨줄 필요가 없다.
static String[] name = new String[1000];
static String[] number = new String[1000];
static int n = 0;
public static void main(String[] args)
{
try
{
String fileName = "input.txt";
Scanner inFile = new Scanner(new File(fileName));
while(inFile.hasNext())
{
name[n] = inFile.next();
number[n] = inFile.next();
n++;
}
inFile.close();
} catch (FileNotFoundException e)
{
e.printStackTrace();
}
bubbleSort();
for(int i=0; i<n; i++) {
System.out.println(name[i] + ":" + number[i]);
}
}
static void bubbleSort() {
for(int i=n-1; i>0; i--) {
for(int j=0; j<i; j++) {
// 정렬할 데이터가 String이므로 name[j] > name[j+1] 대신 아래처럼 표현한다.
// compareTo는 () 안에 있는 비교값보다 크면 양수, 같으면 0, 작으면 음수를 반환한다.
// 기억하는 꼼수: a.compareTo(b)일때 a>b 인지 궁금하면 > 0으로!
if(name[j].compareTo(name[j+1]) > 0) {
// swap
String tmp = name[j];
name[j] = name[j+1];
name[j+1] = tmp;
tmp = number[j];
number[j] = number[j+1];
number[j+1] = tmp;
}
}
}
}
}함수를 메인 함수 밖으로 빼서 처리하는 방법도 있다.
실제로 중요한 건 자바가 제공하는 함수를 이용해 구조화된 프로그래밍을 하는 것이다. 프로그램을 함수로 잘게 쪼개어 각각의 함수는 간단하고 짧게 구현해야 한다.
문제를 보자. 1차원 배열에 비해 복잡해 보인다. 방향도 다양하고, 거꾸로도 될 수 있기 때문이다.
하지만, 컴퓨터는 우리 생각보다 빠르다. 교묘하고 정확하고 능률적인 방법을 찾지 말고 일단 무식하지만 명료한 방법을 찾아보자.
해당 2차원 배열의 모든 가능한 수열에 대해서 소수인지 판별하고 출력하자. 소수를 어떻게 찾나 고민하지 말고 일단 모든 가능한 수열을 일단 정수로 환산하자.
정수로 환산하고 소수인지 판별하는 것은 저번에 배웠으므로 결국 알아내야 하는 것은 모든 수를 나열하는 것이다.
어떻게 모든 가능한 수열을 빼먹지 않고 검사할 수 있을까?
일단, 하나의 수열은 시작점, 방향, 길이에 따라 달라진다. 임의의 시작점을 두고 8가지의 방향에 번호를 붙인다. 길이의 경우, n까지 있다면 최대 n을 넘지 않을 것이다.
코드로 나타내면 위와 같다.
int x와 int y는 각각의 좌표를 의미한다. 출발점이 x, y로 정해지면 3번째 for문부터는 모든 가능한 수열을 구한다. 방향은 0부터 7까지 dir로 나타내고, 그 뒤에 수열의 length에 대해 구한다.
정수로 환산하고 소수를 판별하는 로직을 여기서 또 정의하려면 머리가 꼬이기 시작한다. 따라서 일단 함수를 만들어 따로 떼어놓자. 일단 computeValue()를 만들어서 이게 있다고 치고 넘어간다.
근데 만약 그런 수열이 존재하지 않는다면 어떻게 할까? 그럴 때는 그냥 -1을 반환하면 된다. 그리고 나서 if문에 -1이 아니면서 소수인 조건을 걸어주면 된다.
매우 무식한 방법이지만 이것보다 간단명료하기는 어렵다.
그럼 computeValue()를 구현해보자. 일단 수열을 정수로 환산하는 방법은 이전에 공부한 적이 있다. 10씩 곱하면서 앞 자리수로 밀어주는 것이다.
정수를 환산하는 방법에서 부터 출발할 것이므로 일단 value는 0부터 시작한다. 근데, 받아온 x, y위치에서 각각의 dir 방향으로 length만큼 떨어진 수를 계산하려니 머리가 복잡하다. 여기서 한 번에 해결하려 하지 말고 다시 getDigit()으로 떠넘긴다.
getDigit()도 마찬가지로 해당 수열이 존재할 수 없는 상황이라면 -1을 반환한다.
getDigit()은 x, y 자리에서 dir 방향으로 k칸 떨어진 자리에 저장된 숫자를 리턴한다. 만약 그런 자리가 존재하지 않으면, 즉 2차원 배열에 존재하지 않으면 -1을 리턴한다.
수열은 방향이 어디로 가느냐에 따라 달라진다. 예로, 거꾸로 가는 방향이면 x와 y가 바뀌어야 하기 때문이다. 따라서 newX와 newY를 먼저 정의한다.
switch문을 보자. 현재 우리는 x, y가 가운데에 있다고 가정하고 있다. 따라서 만약 4번 방향이면 y는 길이 k만큼 변화해야 한다. 이때, 수학과 달리 컴퓨터 프로그래밍에서는 아래로 갈 수록 y가 증가한다고 생각하므로 k만큼 + 한다.
또한, newX, Y가 0보다 작거나 n보다 크거나 같다면 해당 배열 범위를 벗어나므로 -1을 리턴한다. 이걸 통과했다면 2차원 배열의 이름을 grid라고 했다고 가정했을 때, grid[newX][newY]에 해당 배열 값을 리턴하면 된다.
getDigit()을 case로 나눠 처리하는 게 번거로울 수 있다. 다른 방법에는 뭐가 있을까?
미리 offsetX, offsetY 라는 배열을 만들어놓고 dir 0~7을 index로 생각한다. 따라서 dir=0일 때는 x엔 변화가 없고 y가 -1만큼 변화한다는 뜻을 가진다. 1번 방향이면 x는 1이 증가하고 y는 2만큼 감소한다. 다 해당 2차원 배열에서 가운데인 x, y를 기준으로 구한 기준값이다.
즉, offset[dir]은 dir 방향으로 한 칸 이동할 때 x와 y의 증가/증감 값이다. 그런데 나는 k만큼의 길이를 가질 것이므로 k를 곱한 뒤 원래의 x에 더하면 되는 것이다.
전체 코드는 다음과 같다.
n은 2차원 배열의 사이즈이며 grid는 이름이다.
슬라이드 내용은 절대로 최선의 방법은 아니다. 살펴보면 비효율적인 면이 많기 때문이다. 하지만 지금은 논리적으로 가장 간명한 방법을 쉽게 떠올리는 것이 중요하다.
아래는 문제가 더 필요한 사람들을 위한 task이다.
'개발새발 개발자 > 자료 구조' 카테고리의 다른 글
| [Java로 배우는 자료구조] 1-1. 변수, 배열, 반복문 (0) | 2019.03.15 |
|---|---|
| [자료구조] 14-3. 넓이 우선 탐색 알고리즘의 응용 (2) (2) | 2019.03.11 |
| [자료구조] 14-2. 넓이 우선 탐색 알고리즘의 응용 (1) (0) | 2019.03.11 |
| [자료구조] 14-1. 넓이 우선 탐색 알고리즘 (0) | 2019.03.11 |
| [자료구조] 13-3. 깊이 우선 탐색 알고리즘의 응용 (2) (1) | 2019.03.10 |
