[charter1] 선형 알고리즘 기초

---

반복 알고리즘 이해하기

 

반복문은 프로그래밍의 가장 중요한 패러다임 중 하나 입니다. 바로 컴퓨터의 빠른 연산 속도를 활용하여 사람과의 차이점을 만들어주기 때문이죠. 이 챕터에서 우리가 깨달아야 하는 점은 for나 while같은 반복문은 단순히 똑같은 명령어를 여러 번 실행하는 것 이상의 의미가 있다는 것입니다.

반복문은 반복되는 횟수를 가변적으로 결정할 수 있으며, 규칙적으로 순차적인 갱신 작업을 수행할 수 있습니다.

반복문 안의 코드 블럭에 가정과 의미부여를 함으로써 귀납적으로 새로운 알고리즘을 설계 할 수 있습니다.

이 강의에서는 각 문제를 통해서 문제의 전체 과정을 순차적으로 나누고 반복문을 통해 귀납적으로 답을 찾아낼 수 있는 방법을 다룹니다.

 

느낀점

파이썬과 자바의 반복문을 같이보니 신기했고 반복문은 중요하다..

사실 느낀점 별로 없음 ..

 

---

최대값 함수

 

import java.io.*;
import java.lang.*;
import java.util.*;

public class Main {
	public static final Scanner scanner = new Scanner(System.in);

	/**
	 * 두 정수 a와 b중 더 큰 값을 반환하는 함수
	 *
	 * @param a
	 * @param b
	 * @return a와 b중 더 큰 값
	 */
	public static int getMax(int a, int b) {
		return a > b ? a : b;
	}

	public static void main(String[] args) throws Exception {
		int p = scanner.nextInt();
		int q = scanner.nextInt();
		int answer = getMax(p, q);
		System.out.println(answer);
	}
}

 

느낀점

일치 완료 !

 

---

원소의 합 구하기

 

import java.io.*;
import java.lang.*;
import java.util.*;


public class Main {
	public static final Scanner scanner = new Scanner(System.in);

	/**
	 * 정수 배열의 모든 원소의 합을 계산하는 함수
	 *
	 * @param data
	 * @param n
	 * @return data[0] ~ data[n-1]의 합
	 */
	public static int getSum(int[] data, int n) {
		int answer = 0;

		for ( int i = 0; i < n; i++ ){
			answer += data[i];
		}

		return answer;
	}

	public static void main(String[] args) throws Exception {
		int n = scanner.nextInt();
		int[] data = new int[n];
		for (int i = 0; i < n; i++) {
			data[i] = scanner.nextInt();
		}
		int answer = getSum(data, n);
		System.out.println(answer);
	}
}

 

느낀점

느낀점 별로 없음 ,,,,, ㅠㅠ

---

배열의 최대값

import java.io.*;
import java.lang.*;
import java.util.*;


public class Main {
	public static final Scanner scanner = new Scanner(System.in);

	/**
     * 배열의 최대값을 계산하는 함수.
     *
     * @param data
     * @param n
     * @return data[0] ~ data[n-1]중 최대값.
     */
	public static int getMax(int[] data, int n) {

		int max = 0;
		for( int i = 0; i < n; i++ ){
			max = max > data[i] ? max : data[i];
		}
		return max;
	}

	public static void main(String[] args) throws Exception {
		int n = scanner.nextInt();
		int[] data = new int[n];
		for (int i = 0; i < n; i++) {
			data[i] = scanner.nextInt();
		}

		int answer = getMax(data, n);

		System.out.println(answer);
	}

}

 

느낀점

느낀점 없음 ,,,

---

카운팅하기

 

import java.io.*;
import java.lang.*;
import java.util.*;


public class Main {
	public static final Scanner scanner = new Scanner(System.in);

	/**
     *
     * @param data 각 사람들의 키를 저장한 배열
     * @param n     사람들의 수
     * @param m     미주의 키
     * @param s     지수의 키
     * @return      미주 혹은 지수와  키가 일치하는 사람의 수
     */
	public static int getCount(int[] data, int n, int m, int s)
	{
		int count = 0 ; //확인해보아야 할 후보의 수

		for( int i = 0; i < n; i++ ){
			if(data[i] == m || data[i] == s){
				count++;
			}
		}
		return count;
	}

	public static void main(String[] args) throws Exception {
		int n = scanner.nextInt();
		int m = scanner.nextInt();
		int s = scanner.nextInt();
		int[] data = new int[n];
		for (int i = 0; i < n; i++) {
			data[i] = scanner.nextInt();
		}

		int answer = getCount(data, n, m, s);

		System.out.println(answer);
	}

}

 

느낀점

느낀점 없음 ,,,,

새미콜론 안찍어서 ,,,, 자꾸 에러남 ,,,,,, 다음부터 안그러겠음 ,,,

---

합 구하기2

 

import java.io.*;
import java.lang.*;
import java.util.*;


public class Main {
	public static final Scanner scanner = new Scanner(System.in);

	/**
     * 동아리 멤버들의 탑승 가능 여부를 출력하는 함수
     *
     * @param data 각 멤버들의 몸무게 data[0] ~ data[n-1]
     * @param n    멤버들의 수
     * @param p    놀이기구 탑승 가능 체중 제한
     * @param q    놀이기구 최대 하중
     */
	public static void solve(int[] data, int n, int p, int q){
		
    	int S = 0; //탑승 가능한 사람의 몸무게 총 합
		int C = 0; //탑승 가능한 사람의 수
		
		for( int kg : data ) {
			if(kg <= p) {
				S += kg;
				C++;
			}
		}

		System.out.printf("%d %d\n", C, S);
		System.out.printf (  (S <= q) ? "YES" : "NO");
	}
}

 

느낀점

값을 비교할 때 매번 느끼지만 같다와, 크거나 같다의 차이는 한끗차이지만 매번 실수를 하는 구간이다.

 

---

탐색하기1

 

/**
 * 배열에서 특정 원소의 위치를 찾는 함수
 * @param data 중복 없는 정수 배열 data[0] ~ data[n-1]
 * @param n    배열의 크기 n
 * @param m    배열에서 찾고자 하는 원소
 * @return     원소가 존재한다면 인덱스를, 존재하지 않으면 -1을 반환한다.
 */
public static int findIndex(int[] data, int n, int m)
{
    for( int i = 0; i < n; i++) {
        if( data[i] == m) {
            return i;
        }
    }   
    return -1;
}

 

느낀점

이번에도 ... 흑 ......... 같거나 작다,,,,,,, 너왜그래 ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ

---

탐색하기2

 

/**
 * 배열에서 소속이 "AJOU"인 첫 원소와 마지막 원소를 출력하는 함수
 * @param school 각 사람들의 소속학교 정보 배열
 * @param n      사람들의 수
 */
public static int[] getIndexes(String[] school, int n)
{
    int firstIndex = -1; //존재하지 않으면 -1
    int lastIndex = -1;  //존재하지 않으면 -1

    for( int i = 0; i < n; i++) {
        if( school[i].equals("AJOU")) {
            if(firstIndex == -1) {
                firstIndex = i;
            }
                lastIndex = i;
        }
    }

    return new int[]{firstIndex+1, lastIndex+1};
}

 

느낀점

마지막에 반환시 firstIndex+1 lastIndex+1 을 해주지 않아 문제가 되었다.

생각해보니 내가 틀렸다 힛

 

---

탐색하기3

 

/**
* 평균과의 차가 가장 작은 데이터의 번호를 반환하는 함수
* 여러 가지라면 가장 빠른 번호를 반환한다.
*
* @param data 
* @param n 
* @return int  가장 평균과 가까운 데이터의 번호 (1번부터 시작)
*/
public static int findIndex(int[] data, int n)
{
    int S = 0;
    int X =0;

    for( int i = 0; i < n; i++ ){
        S += data[i];	
    }

    for( int i = 0; i < n; i++ ){

        int di = Math.abs( S - n * data[i]);
        int dx = Math.abs( S - n * data[X]);

        if(di < dx){
            X = i; 
        }
    }

    return X+1;
}

 

느낀점

 

평균 때문에 그런가 솔직히 잘 이해 안감 ..... 

그래서 console 찍고 이해감 .....

---

선택정렬 구현하기

 

/**
 * 주어진 범위의 최소값의 위치를 반환하는 함수
 * 
 * @param data  데이터 배열
 * @param begin 탐색 할 가장 첫(왼쪽) 인덱스
 * @param end   탐색 할 가장 마지막(오른쪽) 인덱스
 * @return data[begin] ~ data[end] 중 가장 작은 원소의 인덱스
 */
public static int getMinIndexInRange(int[] data, int begin, int end) {

    int minIndex = begin;
    for (int i = begin; i <= end; i++) {
        if (data[i] < data[minIndex]) {
            minIndex = i;
        }
    }
    return minIndex;
}

public static void selectionSort(int[] data, int n) {
    for (int i = 0; i < n; i++) {
        // 주어진 범위에서 가장 작은 원소의 위치를 찾는다.
        int minIndex = getMinIndexInRange(data, i, n - 1);

        int temp = data[i];
        data[i] = data[minIndex];
        data[minIndex] = temp;
    }
}

 

느낀점

ㅋㅋㅋㅋㅋ 오마이갓 이걸로 한시간 풀었다 ....................

n 을 대입이라고 생각해서 나는 .... 느낀게 많음

 

선택정렬은 모든 데이터에서 작은 수를 구한 후 index 0 부터 작은 수를 채워 넣는다.

---

합 구하기3

 

/**
 * 1부터 M까지의 자연수의 합을 계산하는 함수
 * @param M
 * @return
 */
public static int getRangeSumFromOne(int M) {

    int sum = 0;

    for( int i = 1; i <= M; i++ ) {
        sum += i;
    }

    return sum;
}

/**
 * N에 대한 정답을 계산하는 함수
 * @param N
 * @return
 */
public static int getAnswer(int N) {

    int sum = 0;

    for( int i = 1; i <= N; i++ ) {
        sum += getRangeSumFromOne(i);
    }

    return sum;
}

 

느낀점

 

이번에도 for 문에서 같거나 크다 ㅎ 여기서 낚일뻔했지만 !!!!!! 잘 해결했지롱 ~~!!!

 

10 이 입력되었을 경우 아래 숫자를 모두 다 더한다. 

 

1

1 2

1 2 3

1 2 3 4

1 2 3 4 5

1 2 3 4 5 6

1 2 3 4 5 6 7

1 2 3 4 5 6 7 8

1 2 3 4 5 6 7 8 9

1 2 3 4 5 6 7 8 9 10

---