03_쉽게 배우는 Java 알고리즘 입문

 

1. 근삿값 알고리즘(Near Algorithm)

// [?] 원본 데이터 중에서 대상 데이터와 가장 가까운 값

/**
 * 근삿값 알고리즘(Near Algorithm) : 차잇값의 절대값의 최솟값
 */
public class NearAlgorithm {

  public static int Abs(int numbers) {
    // [0] 절댓값 구하기 로컬 함수
    return (numbers < 0) ? -numbers : numbers;
  }

  public static void main(String[] args) {
    // [1] Initialize
    int min = Integer.MAX_VALUE;  // 차잇값의 절댓값의 최솟값이 담길 그릇
    
    // [2] Input
    int[] numbers = { 10, 20, 30, 27, 17 };
    int target = 25;  // target과 가까운 값
    int near = 0;   // 가까운 값
    
    // [3] Process
    for(int i=0; i<numbers.length; i++){

      int abs = Abs(numbers[i] - target);   //차잇값의 절댓값

      if(min > abs){
        min = abs;    // MIN : 최솟값 알고리즘
        near = numbers[i];  // NEAR : 차잇값의 절댓값의 최솟값일 때의 값
      }

    }

    // [4] Output
    System.out.println(target + "와/과 가장 가까운 값 : " + near + " 차이는 " + min);
  }
}

 

 

2. 순위 알고리즘(Rank Algorithm)

// [?] 주어진(지정한 범위) 데이터의 순위(등수)를 구하는 로직

/*
 * 순위 알고리즘(Rank Algorithm) : 점수 데이터에 대한 순위 구하기
 */
public class RankAlgorithm {
  public static void main(String[] args) {
    // [1] Input
    int[] scores = { 90, 87, 100, 95, 80 };   // 등수: 3, 4, 1, 2, 5
    int[] rankings = { 1, 1, 1, 1, 1};    // 모두 1로 초기화

    // [2] Process : Rank

    for(int i=0; i<scores.length; i++){
      rankings[i] = 1;  // 1등으로 초기화, 순위 배열을 매 회전마다 1등으로 초기화
      for(int j=0; j<scores.length; j++){
        if(scores[i] < scores[j]){    // 현재(i)와 나머지들(j) 비교
          rankings[i]++;    // RANK : 나 보다 큰 점수가 나오면 순위 1증가
        }
      }
    }

    // [3] Output
    for(int i=0; i < scores.length; i++){
      //System.out.println(scores[i] + "점: " + rankings[i] + "등");
      System.out.println(String.format("%3d점 : %1d등", scores[i], rankings[i]));
    }
  }
}

 

 

3. 정렬 알고리즘(Sort Alogrithm)

 

• 주어진 범위내에서 불규칙적으로 나열된 순서를 일정한 기준에 따라 순서대로 나열하는 알고리즘.
• 정렬 알고리즘의 종류 
  • 선택 정렬(Selection Sort)
    
    • 데이터 하나를 기준으로 나머지 데이터와 비교하여 가장 작거나 큰 데이터와 자리를 바꾸는 식으로 반복 비교하는 정렬 방법. 선택 정렬은 데이터의 개수가 n개이면 전체 회전수는 n-1회이다. 
  • 버블 정렬(Bubble Sort)
  • 퀵 정렬(Quick Sort) 등...

// [?] 무작위 데이터를 순서대로 [오름차순|내림차순] 정렬
/**
 * 정렬 알고리즘(Sort Algorithm) : 가장 [작은|큰] 데이터를 왼쪽으로 순서대로 이동
 */
public class SortAlgorithm {

  public static void main(String[] args) {
    // [1] Input : Data Structure(Array, List, Stack, Queue, Tree, DB, ...)
    int[] data = { 3, 2, 1, 5, 4 };
    int N = data.length;    // 의사코드(슈도코드) 형태로 알고리즘을 표현하기 위함

    // [2] Process : Selection Sort(선택 정렬) 알고리즘
    for (int i = 0; i<N-1; i++) {   // i = 0  to  N - 1
      for(int j=i+1; j<N; j++){     // j = i + 1  to  N
        if(data[i] > data[j]){      // 부등호 방향 : 오름차순(>), 내림차순(<)
          int tmp = data[i];
          data[i] = data[j];
          data[j] = tmp;  // SWAP
        }
      }
    }

    // [3] Output : Console, Desktop, Web, Mobile, ...
    for (int i = 0; i < N; i++) {
      System.out.print(data[i] + "\t");
    }
    System.out.println();
  }
  
}

 

 

4. 병합 알고리즘(Merge Algorithm)

 

// [?] 2개의 정수 배열 합치기 : 단 2개의 배열은 오른차순으로 정렬되어 있다고 가정

/**
 * 병합 알고리즘(Merge Algorithm) : 오름차순으로 정렬되어 있는 정수 배열을 하나로 병합
 */

public class MergeAlgorithm {
  public static void main(String[] args) {
    //[1] Input
    int[] first = { 1, 3, 5 };
    int[] second = { 2, 4 };
    int M = first.length; int N = second.length;    // M:N의 관행
    int[] merge = new int[M+N];     // 병합된 배열
    int i=0; int j=0; int k=0;      // i, j, k 관행

    //[2] Process : MERGE
    while (i < M && j < N) {    // 둘 중 하나라도 배열의 끝에 도달할 때까지
      if(first[i] < second[j]){   // 작은 값을 merge 배열에 저장
        merge[k++] = first[i++];
      } else {
        merge[k++] = second[j++];
      }
    }
    while (i < M){    // 첫 번째 배열이 끝까지 도달할 때까지
      merge[k++] = first[i++];
    }
    while (j < N){    // 두 번째 배열이 끝까지 도달할 때까지
      merge[k++] = second[j++];
    }

    //[3] Output
    for (int item : merge) {
      System.out.print(item + " ");
    }
    System.out.println();
  }
}

 

 

5. 최빈값 알고리즘(Mode Algorithm)

 

• Data -> Index -> Count -> Max -> Mode

// [?] 주어진 데이터에서 가장 많이 나타난(중복된) 값

/**
 * 최빈값 알고리즘(Mode Algorithm) : 인덱스(0점 ~ 100점)의 개수(COUNT)의 최댓값(MAX)
 */

public class ModeAlgorithm {
  public static void main(String[] args) {
    // [1] Input
    int[] scores = { 1, 3, 4, 3, 5 };   // 0~5까지만 들어온다고 가정
    int[] indexes = new int[5 + 1];   // 0~5까지 : 점수의 인덱스의 카운터
    int max = Integer.MIN_VALUE;    // MAX
    int mode = 0;   // 최빈값이 담길 그릇

    // [2] Process
    for(int i=0; i<scores.length; i++){
      indexes[scores[i]]++;   // COUNT
    }

    for(int j=0; j<indexes.length; j++){
      if(max < indexes[j]){
        max = indexes[j];   // MAX
        mode = j;           // MODE
      }
    }

    // [3] Output
    System.out.println("최빈값: " + mode + " - " + max + "번");
    
  }
}

 

 

6. 그룹 알고리즘(Group Algorithm)

 

import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;

// [?] 컬렉션 형태의 데이터를 특정 키 값으로 그룹화

/**
 * 그룹 알고리즘(Group Algorithm) : 특정 키 값에 해당하는 그룹화된 합계 리스트 만들기
 */
public class GroupAlgorithm {
    /**
     * 테스트용 레코드 클래스
     */
    public static class Record {
      private final String name;   // 상품명
      private final int quantity; // 수량

      public Record(String name, int quantity){
        this.name = name;
        this.quantity = quantity;
      }

      public String getName() {
        return name;
      }

      public int getQuantity() {
        return quantity;
      }

    }

    //[0][1] 테스트용 데이터 채우기용 로컬 함수
    public static List<Record> getAll() {
      return Arrays.asList(
        new Record("RADIO", 3),
        new Record("TV",1),
        new Record("RADIO", 2),
        new Record("DVD", 4)
      );
    }

    //[0][2] 컬렉션 데이터 출력용 로컬 함수
    public static void printData(String message, List<Record> data){
      System.out.println(message);
      for (Record item : data){
        System.out.println(String.format("%5s - %d", item.getName(), item.getQuantity()));
      }
    }

  public static void main(String[] args) {

  // [1] Input
  List<Record> records = getAll();  // 입력 데이터
  List<Record> groups = new ArrayList<Record>();  // 출력 데이터
  int N = records.size();   // 의사코드

  // [2] Process : Group 알고리즘(SORT -> SUM -> GROUP)
  // [A] 그룹 정렬 : SORT
  for (int i = 0; i < N - 1; i++) {
    for (int j = i + 1; j < N; j++) {
      if(records.get(i).getName().compareTo(records.get(j).getName()) > 0){
        Record t = records.get(i);
        records.set(i, records.get(j));
        records.set(j, t);
      }
    }
  }

  // [B] 그룹 소계 : GROUP
  int subtotal = 0;   // 소계
  for(int i=0; i < N; i++){
    subtotal += records.get(i).getQuantity();   // 같은 상품명의 판매량을 누적(SUM);
    if((i + 1) == N ||  // 단락(short circuiting)이면 아래 조건 무시
       (records.get(i).getName() != records.get(i + 1).getName())){
      // [!] 다음 레코드가 없거나, 현재 레코드와 다음 레코드가 다르면 저장
      Record r = new Record(records.get(i).getName(), subtotal);
      groups.add(r);  // 하나의 그룹 저장
      subtotal = 0;   // 하나의 그룹이 완료되면 소계 초기화
    }
  }


  // [3] Output
  printData("[1] 정렬된 원본 데이터:", records);
  printData("[2] 이름으로 그룹화된 데이터:", groups);

  }
}

 

 

https://me2.do/5grNjpcD