이 자료는 부경대학교 권오흠 교수의 'Java로 배우는 자료구조론' 수업 PPT입니다. 시간 날 때마다 틈틈히 복습하기 위해 블로그에 업로드 하는 것이며, 저작권은 권오흠 교수님께 있습니다.
출처: http://alg.pknu.ac.kr/t/2016-2017-java/342
강의 가이드. 나는 2강까지는 그냥 읽어보기만 하고 본격적인 영상 강의는 3강부터 들을 예정이다.
메인 함수와 출력에 대한 기본 설명
클래스 이름은 대문자로 구성되는 것이 관습이다. main 메소드가 왜 저렇게 생겼는지는 일단 넘어가도록 하자.
변수는 메서드 내부, 외부 다 가능하지만 클래스 외부에는 선언될 수 없다.
타입은 C와 거의 유사하다.
뭘 import 해야할지 모르겠다면 source > OrganizeImports를 실행해보자. ctrl+shift+O를 하면 자동으로 import를 시켜준다.
Scanner로 입력값을 받는다. 이때, System.in은 키보드를 의미한다. 키보드에서 정수값을 받으려면 nextInt()를 사용한다.
일반 String을 입력받으려면 next(), 한 줄 전체를 받고 싶다면 nextLine()을 사용한다. 위의 코드를 테스트 해보면 올바르게 입력해도 'do not match'만 뜬다.
왜냐하면, String은 == 연산자가 아니라 equlas 메서드로 비교해야 하기 때문이다. 이 메서드는 true나 false로 결과를 반환한다.
if else를 이용해 분기할 수 있다.
package lesson01;
public class code05 {
public static void main(String[] args) {
// TODO Auto-generated method stub
// 배열을 일단 선언해놓고
int[] grades;
// 배열의 크기를 지정하면서 생성한다. 실제 배열은 이때 만들어진다.
// int[] grades = new int[5]; 라고 한 번에 할 수도 있다.
grades=new int[5];
grades[0]=100;
grades[1]=200;
grades[2]=300;
grades[3]=400;
grades[4]=500;
for(int i=0; i<grades.length; i++) {
System.out.println(i+" "+grades[i]);
}
System.out.println();
int i=0;
while(i<grades.length) {
System.out.println(i+" "+grades[i]);
i++;
}
}
}
배열은 두 가지 방법으로 선언할 수 있다.
for문을 사용하면 반복을 피할 수 있다.
while 또한 for문과 기능이 같은데, 일반적으로 반복 횟수가 정해져 있다면 for, 그렇지 않다면 while을 사용한다.
n개의 정수를 입력받아 합과 최대값을 구한다.
그냥 다음 칸으로 옮겨버리면 기존의 원소는 지워진다.
import java.util.Scanner;
public class code07 {
public static void main(String[] args) {
// TODO Auto-generated method stub
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();
// 맨 마지막 원소만 따로 빼서 저장하면 뒤로 밀려도 지워지지 않는다.
int tmp=data[n-1];
// 맨 뒤부터 땡겨서 저장한다.
for(int i=n-2; i>=0; i--) {
data[i+1]=data[i];
}
data[0]=tmp;
for(int i=0; i<n; i++) {
System.out.println(data[i]);
}
}
}이를 해결하려면 맨 마지막 숫자를 따로 저장한 뒤, 뒤에서 앞으로 index를 이동하며 원소를 뒤로 미룬다. 그럼 자연스레 0번 인덱스가 비게 되고, 여기에 임시로 저장해놓았던 맨 마지막 원소를 넣으면 된다.
소수를 구하는 데에는 여러 가지 방법이 있다.
public class code08 {
public static void main(String[] args) {
// TODO Auto-generated method stub
int n= 10111;
boolean isPrime=true;
// 소수란 1과 자신 외의 약수를 갖지 않는 수이다.
// 2, 3, ..., n-1 사이의 정수로 나누어 떨어지면 소수가 아니다.
// 하지만 굳이 n-1까지 갈 필요가 없다. 약수는 n/2 보다 클 수 없기 때문이다.
for(int i=2; i<=n/2; i++) {
if(n % i == 0) { // not prime number
isPrime=false;
// 이미 소수가 아닌 것으로 판정났다면 불필요한 반복을 피하기 위해 빠져나온다
break;
}// for
///////////////////////////////////////////////
// 혹은 빠져나올 조건을 for문에 추가한다.
for(int i=2; i<=n/2 & isPrime; i++) {
if(n % i == 0) { // not prime number
isPrime=false;
}
} // for
////////////////////////////////////////////////
if(isPrime) { // 소수이면 출력
System.out.println(n);
}
}
}
public class code08 {
public static void main(String[] args) {
// TODO Auto-generated method stub
int n= 10111;
boolean isPrime=true;
// 루트 n까지만 계산하는 방법.
// 루트니까 i랑 i를 곱해서 n보다 작거나 같아야 한다는 조건을 넣는다.
for(int i=2; i*i <= n && isPrime; i++) {
if(n % i == 0) { // not prime number
isPrime=false;
}
} // for
if(isPrime) { // 소수이면 출력
System.out.println(n);
}
}
}하지만 사실 n/2까지 돌 필요도 없다. 루트 n까지만 돌아도 충분하다. n의 약수 중에 루트 n보다 더 큰 게 있다면 루트 n보다 작은 약수도 존재한다는 규칙이 있다. 루트는 n과 n을 곱해야 하는데 둘 다 루트 n보다 커버리면 성립되지 않기 때문이다. 루트는 sqrt(n)으로 표현한다.
public class code08 {
public static void main(String[] args) {
// TODO Auto-generated method stub
// 1~100,000 사이의 숫자 입력
// 1은 소수가 아니므로 굳이 하지 않고 2부터 시작한다.
for(int n=2; n<=100000; n++) {
boolean isPrime=true;
// 루트 n까지만 계산하는 방법.
// 루트니까 i랑 i를 곱해서 n보다 작거나 같아야 한다는 조건을 넣는다.
for(int i=2; i*i <= n & isPrime; i++) {
if(n % i == 0) { // not prime number
isPrime=false;
}
} // for
if(isPrime) { // 소수이면 출력
System.out.println(n);
}
}
}
}이제 n이 1~100,000까지라는 조건을 넣어준다. 1은 소수가 아니므로 2부터 for문을 시작하면 된다.
중복된 정수 쌍이라는 것은 서로 같은 값을 가진 쌍을 의미한다. 예를 들어 (2, 2) (4, 4)가 있다.
public class code09 {
public static void main(String[] args) {
// TODO Auto-generated method stub
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();
// n개의 데이터에 대해 모든 쌍을 비교한다. 같은 값이면 무시하도록 한다.
// 쌍을 검사하는 것은 항상 두 개의 중첩 for문을 사용한다.
int count =0;
for(int i=0; i<n; i++) { // 쌍의 첫번째
for(int j=0; j<n; j++) { // 두번째
// data[i] data[j]
if(data[i]==data[j]) {
count ++;
}
}
} // for
// 하지만 이렇게 하면 1, 2, 3을 넣어도 3이 출력된다.
// i가 0일 때 j가 0 인 상황 등 꼭 겹쳐지게 되기 때문이다.
System.out.println(count);
}
}하지만 이렇게 코드를 짤 경우 에러가 난다. i와 j가 같아지는 순간은 꼭 있기 때문이다.
public class code09 {
public static void main(String[] args) {
// TODO Auto-generated method stub
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();
int count =0;
for(int i=0; i<n; i++) { // 쌍의 첫번째
for(int j=0; j<n; j++) { // 두번째
// data[i] data[j]
// 따라서 인덱스가 다르더라도 원소가 같은 경우라는 조건을 넣어준다.
if(i!=j && data[i]==data[j]) {
count ++;
}
}
} // for
System.out.println(count);
}
}첫 번째 이슈는 해결이 되었다. 하지만 이 코드를 실행하면 또 다른 오류가 생긴다. 1, 1, 2를 입력하면 1이 아니라 2가 출력된다. 항상 중복 검토하게 되기 때문이다. i=1 j=2 / i=2 j=1 처럼.
public class code09 {
public static void main(String[] args) {
// TODO Auto-generated method stub
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();
int count =0;
// j를 i+1부터 시작하면 해결된다.
// 순서쌍은 i보다 j가 클 경우만 검사해도 충분하기 때문이다.
for(int i=0; i<n; i++) { // 쌍의 첫번째
for(int j=i+1; j<n; j++) { // 두번째
// 인덱스에 대한 조건도 없어진다.
if(data[i]==data[j]) {
count ++;
}
}
} // for
System.out.println(count);
}
}i보다 j가 클 경우, 즉 j=i+1일 때만 검사해도 충분히 순서쌍의 중복을 피할 수 있다.
import java.util.Scanner;
public class code10 {
public static void main(String[] args) {
// TODO Auto-generated method stub
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();
// 그냥 처음부터 끝까지 더하면 되는 것 아니냐 할 수 있지만
// 음수가 존재하므로 그렇지 않다.
/*
제일 먼저 생각해볼 수 있는 방법은 많은 경우의 수로 다 더해보는 것이다.
더할 구간 각각의 시작점과 끝점을 구해보자.
일단 최대값을 0으로 초기화 해놓는다. 0개 이상을 선택할 수 있으므로 최대값을 0으로 초기화해도 무방하다.
또한 어떤 값을 더해도 최대값이 0보다 작아질 수는 없기 때문이다.
*/
int max = 0;
// 시작점은 i가 된다.
for(int i=0; i<n; i++) {
// 끝점은 j가 된다. 이때 끝점은 반드시 i보다 크거나 같으므로 0이 아니라 i부터 시작한다.
for(int j=i; j<n; j++ ) {
int sum = 0;
// 위에서 시작과 끝을 설정해줬으니 이제 data[i]부터 [j]까지 더하기 위한 for문이 필요하다.
for(int k=i; k<=j; k++) { // i부터 j까지 반복
sum += data[k];
}
if(sum > max) { // 만약 지금 더한게 더 크다면
max=sum; // 지금 sum이 최대값이 된다.
}
}
} // for
System.out.println(max);
}
}하지만 위의 방법은 불필요한 중복을 포함하고 있다. 앞에 구했던 최대값에 다음 원소만 더해주면 되는데, 반복문을 또 수행해야 하기 때문이다.
import java.util.Scanner;
public class code10 {
public static void main(String[] args) {
// TODO Auto-generated method stub
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();
int max = 0;
for(int i=0; i<n; i++) {
// i가 바뀔 때 sum이 초기화 되도록 한다.
int sum = 0;
for(int j=i; j<n; j++ ) {
// j가 바뀌는 동안에는 새로 sum을 구하지 않고
// 같은 시작점에서 계속 더하는 동안 생긴 sum에 추가만 한다.
sum += data[j];
if(sum > max) { // 지금 sum이 최대값이 된다.
max=sum;
}
} // for
} // for
System.out.println(max);
}
}하나의 시작점에서 끝점을 하나씩 추가할 때마다 max인지 구분하도록 변경했다.
package section01;
import java.util.Scanner;
public class Code13
{
public static void main(String[] args)
{
// TODO Auto-generated method stub
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();
/*
* 먼저 해당 구간을 붙여 정수를 만들고 그것이 소수인지 판단한 후,
내가 갖고있는 max보다 큰지 판단하면 된다.
*/
int max = 0;
for (int i = 0; i < n; i++) // 구간의 시작
{
// 구간의 끝점인 j는 i보다 왼쪽에 있을 수 없으므로 i부터 시작
for (int j = i; j < n; j++)
{
int val = 0;
for (int k = i; k <= j; k++)
{
// convert data[i]...data[j] into an integer
// 원래의 val를 10의 자리로 보내고 지금의 data를 더한다.
val = val * 10 + data[k];
}
// test if it is a prime
boolean isPrime = true;
for (int k = 2; k * k <= val && isPrime; k++)
{
if (val % k == 0)
{
isPrime = false;
}
}
// if yes, compare to the max
if (isPrime && val > max)
{
max = val;
}
}
}
// 소수가 하나도 없어서 모든 조건을 다 통과하고 max가 0으로 나올 수도 있으므로
if (max > 0)
{
// 적어도 하나의 소수를 가질 때만 출력을 해주고
System.out.println(max);
} else
{
// 없을 경우 없다고 출력한다.
System.out.println("No prime number");
}
}
}
하지만 만약 아래와 같은 값을 넣으면, 결과는 1이 나온다.
하지만 1은 소수가 아니다. 따라서 이 코드에는 오류가 있다. 소수인지 구분하는 2번 코드에 문제가 있는 것이다. 즉, k=2, val=1일 때 for문을 한 번도 실행하지 않아서 isPrime이 true인 채로 끝나기 때문이다.
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();
int max = 0;
for(int i=0; i<n; i++) {
for(int j=i; j<n; j++) {
int val=0;
for(int k=i; k<=j; k++) {
val = val*10 + data[k];
}
boolean isPrime = true;
for(int k=2; k*k<=val && isPrime; k++) {
if(val%k==0) {
isPrime = false;
}
}
// val이 1보다 크다는 조건을 추가한다.
if(isPrime && val > max && val > 1) {
max=val;
}
}
}
if(max>0) {
System.out.println(max);
}
else {
System.out.println("No prime number.");
}
}이렇게 val에 대한 조건을 if문에 추가해주면 된다.
또 다른 문제는 입력값이 많을 경우다. val은 정수이고 받을 수 있는 데에 한계가 있으므로, n=100처럼 늘어나면 overflow가 생긴다. long으로 바꾼다면 더 큰 정수로 표현할 수 있지만 그것이 근본적인 해결책은 아니다. 일단 참고만 해두자.
이번에 구현할 것은 버블 소트 알고리즘이다.
버블 소트는 가장 큰 값을 찾아서 맨 뒤로 보낸다. 그 자리에 있던 2는 다른 곳으로 보낸다. 중요한 키 포인트는 가장 큰 값을 맨 뒤로 보낸다는 사실이다. 옮기고 나면 13을 제외한 나머지 숫자에 대해 똑같이 반복한다.
그 마지막 자리에 넣기 위해서 맨 처음부터 하나씩 숫자를 살펴본다. 해당 숫자와 다음 숫자를 비교하고 지금 숫자가 더 크면 둘의 자리를 바꾼다. 더 큰 숫자가 있으면 멈춘다. 그 숫자를 다시 다음 숫자와 비교한다.
예를 들어, 맨 앞의 8을 계속 비교하다가 11을 만나면 멈춘다. 11은 다시 뒤의 숫자와 비교한다. 13이 더 크므로 13으로 넘어가서 13과 다음 숫자를 비교한다. 13보다 작은 수이므로 13을 뒤로 보낸다. 결국, 다른 값이 어떻게 되든 가장 큰 값이 뒤로 가게 된다.
한 스텝, 한 스텝 넘어갈 수록 처리할 데이터가 하나씩 줄어든다. 그림을 보면 맨 마지막 데이터를 가리키는 인덱스를 i라고 표시했다. 그리고 n-1, n-2...해서 n=1이 될 때까지 앞으로 넘어간다. 따라서 코드로 표현하면 다음과 같다.
import java.util.Scanner;
public class code12 {
public static void main(String[] args) {
// TODO Auto-generated method stub
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();
// bubble sort
// 맨 뒤에서 i=1까지만 i--를 반복한다.
// for문 한 번이 그림에서의 한 스텝이다.
for (int i=n-1; i>0; i--) {
// data[0]에서 data[i] 사이에서 제일 큰 값을 data[i]로 몰아간다.
// 0에서 i-1까지 쭉 스캔하면서 최대값을 찾아낸다.
for(int j=0; j<i; j++) {
if(data[j] > data[j+1]) {
// swap data[j] and data[j+1]
// 일단 data[j]값을 다른 곳에 옮겨두고
int tmp = data[j];
// 이제 data[j]에는 마음대로 값을 쓸 수 있으니 data[j+1]을 넣고
data[j] = data[j+1];
// 임시로 저장해뒀던 값을 data[j+1]에 넣으면 된다.
data[j+1] = tmp;
}
}
}
// 정렬된 값을 출력한다.
System.out.println("Sorted data: ");
for(int i=0; i<n; i++) {
System.out.println(data[i]);
}
}
}
입력받을 때마다 버블 소트 알고리즘으로 정렬해도 되지만 비효율적이다. 이미 버블 소트를 한 상태에서 입력된 하나의 값 때문에 모든 값을 다시 정렬해야 하기 때문이다.
그럼 입력받은 값을 어떻게 특정 자리에 집어넣을 수 있을까? 두 가지 방법이 있다.
1. 앞에서부터 저장된 수를 쭉 비교한 다음 처음으로 입력값보다 크거나 같은 수가 나오면 바로 그 앞에 넣는다.
2. 1번의 방법을 뒤에서 부터 수행하며 입력값보다 작은 값을 찾고 그 뒤에 넣는다.
어떻게 보면 둘은 같아보인다. 하지만 조금 다르다. 만약 값이 5라면 1번 방법의 경우 처음부터 쭉 보다가 4와 6 사이로 가기 위해 6부터 뒤의 값을 다 뒤로 미뤄야 한다.
하지만 만약 2번처럼 뒤에서 부터 한다면, 5가 어디로 갈 지는 모르지만 어쨌든 9는 5보다 크므로 한 칸씩 물러난다. 7은 9가 이미 뒤로 가서 칸이 비어있으므로 쉽게 뒤로 가면 된다. 4를 만나면 비어있는 칸에 5가 들어가면 되므로 어떤 숫자가 지워질 위험이 없다. 또한, 3부터는 볼 필요가 전혀 없어진다. 물론 최악의 경우에는 끝까지 탐색해야 한다.
이러한 방법을 Ordered List에 새로운 값을 insert 한다고 한다. 두 번째 방법, 즉 뒤에서 스캔하는 방법으로 코드를 짜보자.
public class code13 {
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++) {
// 배열에 바로 넣지 않고 임시로 갖고 있다가 비교한다.
int tmp = kb.nextInt();
// 배열 데이터가 i개라면 인덱스는 i-1이므로
int j=i-1;
// tmp보다 작거나 같은 애가 나타날 때까지
while(data[j] > tmp) {
// data j를 뒤로 보낸다.
data[j+1] = data[j];
// i는 현재까지 입력된 데이터의 개수이다.
// 입력된 값이 6개면 i=6이다.
// 그럼 인덱스는 5부터 쭉 감소해간다.
j--;
}
// data[j]가 tmp보다 작아지면 while을 빠져나온다.
// 비어있는 j+1에 tmp를 넣는다.
data[j+1] = tmp;
// 출력하는 코드
// i개에서 1개를 더 추가했으므로 데이터의 개수는 i+1이다.
// 따라서 인덱스 i까지 반복한다.
for(int k=0; k<=i ;k++) {
System.out.print(data[k] + " ");
}
System.out.println();
}
kb.close();
}
}이렇게 하면 코드가 잘 돌아갈 것 같지만 사실 문제가 하나 있다. tmp가 만약 -1이라면 배열에 있는 1보다도 작으므로 제일 앞으로 가게 될 것이다. 그럼 더 이상 비교할 값이 없으므로 while 문을 멈춰야 한다.
따라서 아래와 같이 while문을 수정한다.
public class code13 {
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++) {
// 배열에 바로 넣지 않고 임시로 갖고 있다가 비교한다.
int tmp = kb.nextInt();
// 배열 데이터가 i개라면 인덱스는 i-1이므로
int j=i-1;
// tmp보다 작거나 같은 애가 나타날 때까지
while(j>=0 && data[j] > tmp) {
// data j를 뒤로 보낸다.
data[j+1] = data[j];
// i는 현재까지 입력된 데이터의 개수이다.
// 입력된 값이 6개면 i=6이다.
// 그럼 인덱스는 5부터 쭉 감소해간다.
j--;
}
// data[j]가 tmp보다 작아지면 while을 빠져나온다.
// 비어있는 j+1에 tmp를 넣는다.
data[j+1] = tmp;
// 출력하는 코드
// i개에서 1개를 더 추가했으므로 데이터의 개수는 i+1이다.
// 따라서 인덱스 i까지 반복한다.
for(int k=0; k<=i ;k++) {
System.out.print(data[k] + " ");
}
System.out.println();
}
kb.close();
}
}
과제는 홈페이지에 게시된다고 한다. 일단 혼자 풀어보고 확인해봐야겠다.
'개발새발 개발자 > 자료 구조' 카테고리의 다른 글
| [Java로 배우는 자료구조] 1-2. 메서드 호출과 프로그램의 기능적 분할 (0) | 2019.05.03 |
|---|---|
| [자료구조] 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 |
