[원격 강의] 쉽게 배우는 알고리즘(1)

우정·2022년 11월 9일
0

[내일배움캠프] TIL

목록 보기
3/50

이거 왤케 많지...?
왜 하루에 2주차 중반까지 들어야하지.....?ㅜ

객체지향언어

  1. 클래스

    • 개념 예시) 붕어빵 틀
    • 객체의 속성을 정의해 놓은 것(표현하고자 하는 대상의 공통 속성을 한 군데에 정의해 놓은 것)

  2. 인스턴스

    • 개념 예시) 붕어빵
    • 어떠한 클래스로부터 만들어진 객체
      • (= 그 클래스의 인스턴스 라고 부름)
      • instance는 한 번 생성되고 나면 그 자체의 상태를 가지고 그 자체로 변화하게 됨.
    class Phone {
    String model;
    String color;
    int price;
}

public class Main {
    public static void main(String[] args) {
        Phone galaxy = new Phone(); 
        galaxy.model = "Galaxy10";
        galaxy.color = "Black";
        galaxy.price = 100;
        
        Phone iphone =new Phone();
        iphone.model = "iPhoneX";
        iphone.color = "Black";
        iphone.price = 200;
        

        System.out.println("철수는 이번에 " + galaxy.model + galaxy.color + " + 색상을 " + galaxy.price + "만원에 샀다.");
        System.out.println("영희는 이번에 " + iphone.model + iphone.color + " + 색상을 " + iphone.price + "만원에 샀다.");
    }
}

  1. 메소드

    • 어떤 작업을 수행하는 코드를 하나로 묶어놓은 것

    • 어떤 일정한 작업의 단위, 중복된 코드, 프로그램의 재사용성과 구조화를 위해 메소드를 선언해 사용함

    • 메소드 선언시 지켜주면 좋은 코드 convention

      • 동사로 시작하자

      • camel case로 작성하자

        int [] heights = new int[]{10, 20, 30, 40, 50};  // 키가 저장되어 있는 배열

        intHeight(heights);
        sortHeight(heights);  // heights 오름차순으로 정렬
        printHeight(heights);  // heights에 있는 것을 하나하나 꺼내서 출력
        // 이러한 함수를 쓰지 않는다면 int[]에 초기화하는 로직{}을 적어줘야함
        // 더하기 함수
int add(int x, int y) { // 맨 앞 int는 함수의 결과값이 전달되는 타입을 말함(return type)
                        // 함수 이름 뒤에 ()오는 두 개(int x, int y)는 parameter라고 함
		return x + y
}  // return은 표현(x+y)도 가능하고 특정 값을 리턴할 수도, int result = x + y;같이 이 안에서 선언된 변수 자체를 넘겨줄 수도 있음
// 빼기 함수
int minus(int x, int y) { // 위의 ()안의 값이랑 별개임
		return x - y 
}

        parameter: 내가 원하는 만큼 여러 개를 선언해서 쓸 수 있음

      • 오류

        심볼 'x'를 해결할 수 없습니다.

        class Calculation {
    int add(int x, int y) {
        return x + y;
    }
    int subtract(int x, int y) {
        return x - y;
    }
}

public class Main {
    public static void main(String[] args) {
        // write your code here
        Calculation calculation = new Calculation();
        int addResult = calculation.add(x: 1, y: 2); // 오류
        int subtractResult = calculation.subtract(x: 5, y: 3); // 오류

        System.out.println(addResult);
        System.out.println(subtractResult);
    }
}

// 밑에처럼 숫자만 입력해야 오류 안 뜸...
int addResult = calculation.add(1, 2);
int subtractResult = calculation.subtract(5, 3);

  1. 생성자

    • instance가 생성될 때,

    • 정확히는 앞에서 new라는 키워드를 통해서 class의 instance를 생성할 때 불리는 초기화 method.

    • method의 일종인데 new를 할 때만 불리는 것

    • class의 이름이랑 똑같은 이름을 지어줘야함

    • return 값이 없음

      class Phone {
    String model;
    String color;
    int price;

		// Alt+Insert 누르면 아래 코드 쉽게 생성 가능
    Phone (String model, String color, int price) { // 위의 모델 컬러 프라이스랑은 다른 값
        this.model = model;
        this.color = color;
        this.price = price;
    }
}

public class Main {
    public static void main(String[] args) {
        Phone galaxy = new Phone("galaxy10", "black", 100);

        Phone iphone =new Phone("iphoneX", "black", 200);

        System.out.println("철수는 이번에 " + galaxy.model + galaxy.color + " + 색상을 " + galaxy.price + "만원에 샀다.");
        System.out.println("영희는 이번에 " + iphone.model + iphone.color + " + 색상을 " + iphone.price + "만원에 샀다.");
    }
}

    • 클래스 안에 멤버변수로 선언하게 되면 그것들을 세팅 안 해줬을 때 기본값을 갖는데

      class DefaultValueTest {
    byte byteDefaultValue;
    int intDefaultValue;
    short shortDefaultValue;
    long longDefaultValue;
    float floatDefaultValue;
    double doubleDefaultValue;
    boolean booleanDefaultValue;
    String referenceDefaultValue;
}

public class Main {
    public static void main(String[] args) {
        DefaultValueTest defaultValueTest = new DefaultValueTest();
        System.out.println("byte default: " + defaultValueTest.byteDefaultValue);
        System.out.println("short default: " + defaultValueTest.shortDefaultValue);
        System.out.println("int default: " + defaultValueTest.intDefaultValue);
        System.out.println("long default: " + defaultValueTest.longDefaultValue);
        System.out.println("float default: " + defaultValueTest.floatDefaultValue);
        System.out.println("double default: " + defaultValueTest.doubleDefaultValue);
        System.out.println("boolean default: " + defaultValueTest.booleanDefaultValue);
        System.out.println("reference default: " + defaultValueTest.referenceDefaultValue);
    }
}
      		> Task :Main.main()
		byte default: 0
		short default: 0
		int default: 0
		long default: 0
		float default: 0.0
		double default: 0.0
		boolean default: false
		reference default: null

2. 알고리즘

  • 알고리즘
    • 특정 문제에 대한 해결법 중에 어떤 것이 가장 효율적인지, 어느 경우에 효율적인지에 대해 고민하는 것
  • 최댓값 찾기
    • 기본 코드
      input = [3, 5, 6, 1, 2, 4]

def find_max_num(array):
    # 이 부분을 채워보세요!
    return 1

result = find_max_num(input)
print(result)
    • 방법 1 : 다른 숫자들과 비교하는 방식
      for num in array: # 배열의 숫자 꺼내는 반복문
        for compare_num in array:  # 비교할 변수들을 뽑기 위한 반복문
            if num < compare_num:
                break
        else: # for문이 다 끝날 때까지 break가 한 번도 나오지 않았다면 실행되는 것
            return num
    • 방법 2 : 지정변수
      max_num = array[0] # 이 변수에 가장 큰 수를 기록하도록 함
    for num in array:
        if num > max_num:
            max_num = num

    return max_num # 반복문이 끝났다면 가장 큰 수가 max_num에 저장되어 있을 것이기 때문에 max_num을 반환하면 됨
  • 최빈값 찾기
    • 아스키 코드를 이용해 문자 ↔ index 변환하기
      # 알파벳을 숫자로 변환하는 방법
a -> 0
a -> ord(a) -> 97 - ord(a) = 0
# 숫자를 알파벳으로 변환하는 방법(python number to char)
0 -> a
0 -> 0 + ord(a) -> 97 -> chr(97) -> a
    • 알파벳 별 빈도수 찾기 코드
      def find_alphabet_occurrence_array(string):
    alphabet_occurrence_array = [0] * 26  # 비트맵 자료구조

    for char in string:
        if not char.isalpha():
            continue
        arr_index = ord(char) - ord("a")
        alphabet_occurrence_array[arr_index] += 1
        # 각 차에 따른 arr_index를 구하고 그 arr_index를 가진 alphabet_..._array의 값을 하나하나 증가시켜 줌으로써 알파벳 별 빈도수를 업데이트 할 수 있음

    return alphabet_occurrence_array  # for문이 끝난 이후 반환하기

print(find_alphabet_occurrence_array("hello my name is sparta"))
    • 방법 1 : 각 알파벳마다 문자열을 돌면서 몇 글자 나오는지 확인하는 방법
      input = "hello my name is sparta"

def find_max_occurred_alphabet(string):
    alphabet_array = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s",
                      "t", "u", "v", "w", "x", "y"]
    max_occurrence = 0  # 최고로 많이 나왔던 횟수를 저장하기 위한 변수
    max_alphabet = alphabet_array[0]  # 최고로 많이 나왔던 알파벳을 저장하기 위한 변수

    for alphabet in alphabet_array:
        occurrence = 0
        for char in string:  # 문자열 안에 있는 문자와 동일하다면 ouccerrence를 하나씩 추가하자
            if char == alphabet:
                occurrence += 1

        if occurrence > max_occurrence:
            max_occurrence = occurrence
            max_alphabet = alphabet  # 마지막으로 반환하는 건 max_alphabet

    return max_alphabet

result = find_max_occurred_alphabet(input)
print(result)
    • 방법 2 : 지정변수
      input = "hello my name is sparta"

def find_max_occurred_alphabet(string):
    alphabet_occurrence_array = [0] * 26

    for char in string:
        if not char.isalpha():
            continue
        arr_index = ord(char) - ord("a")
        alphabet_occurrence_array[arr_index] += 1

    max_occurrence = 0
    max_alphabet_index = 0  # 가장 많이 나왔던 알파벳의 인덱스를 저장하는 변수
    for index in range(len(alphabet_occurrence_array)):  # for문을 돌면서 하나하나 비교해보자  # index를 알아야지 나중에 변환할 일이 있기 때문에 index in range를 사용하겠음
        # index 0 -> alphabet_occurrence 3  // a가 3번 나옴
        alphabet_occurrence = alphabet_occurrence_array[index]  # 알파벳 오쿼런스 어레이에서 인덱스 번째의 값은 바로 알파벳 별 빈도수

        if alphabet_occurrence > max_occurrence:
            max_alphabet_index = index  # 가장 큰 수라고 판단되었기 때문에
            max_occurrence = alphabet_occurrence  # 마찬가지
    # for문이 끝나고 나면 모든 알파벳 오쿼런스 어레이를 검사하면서 가장 큰 알파벳의 인덱스를 알 수 있음
    # print(max_alphabet_index)  # 0이 나옴. 왜냐면 a가 가장 많기 때문에
    return chr(max_alphabet_index + ord("a"))

result = find_max_occurred_alphabet(input)
print(result)
  • 시간 복잡도 판단하기

    • 입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계

    • 각 줄이 실행되는 것 = 1번의 연산이 된다

    • 최댓값 찾기 알고리즘의 시간 복잡도를 판단해보자

      • 첫 번째 방법

        for num in array:              # array 의 길이만큼 아래 연산이 실행
        for compare_num in array:  # array 의 길이만큼 아래 연산이 실행
            if num < compare_num:  # 비교 연산 1번 실행
                break
        else:
            return num
        • 위에서 연산된 것들을 더해보면,

          • array의 길이 X, array의 길이 X, 비교 연산 1번

            만큼의 시간이 필요함.

          • 여기서 array(입력값=여기선 배열)의 길이는 보통 N이라고 표현.

            N×NN \times N

            이 함수는 N2N^2 만큼의 시간이 걸렸겠구나! 라고 말할 수 있습니다.

      • 두 번째 방법

        max_num = array[0] # 연산 1번 실행
        for num in array:      # array 의 길이만큼 아래 연산이 실행
		    if num > max_num:  # 비교 연산 1번 실행
		        max_num = num  # 대입 연산 1번 실행
        • 위에서 연산된 것들을 더해보면,

          • max_num 대입 연산 1번, array의 길이 X (비교 연산 1번 + 대입 연산 1번) 만큼의 시간이 필요

            1+2×N1+2\times N

            이 함수는 2N+12N+1 만큼의 시간이 걸렸겠구나! 라고 말할 수 있습니다.

      • 비교하기

        1. NN 과 N2N^2 은 N 이 커질수록 더 큰 차이가 난다. N2N^2 이 비효율적임
        2. 그러므로, NN의 지수를 먼저 비교하면 됨

      • 그러나, 매 코드마다 확인이 불가능하므로 상수는 신경쓰지 말고 입력값에 비례해서 어느 정도로 증가하는지만 파악하면 됨.

        • 여기에선 NN과 N2N^2만큼의 연산량이 필요하구나~
        • 만약 상수의 연산량이 필요하면 그냥 1만큼의 연산량이 필요하다고 하면 됨.
  • 느낀점
    • 내일은 알고리즘 강의를 미리 보고 특강을 들어야겠다,,, 하나도 모른 상태로 보고 또 강의 속 강의 형태라 집중이 거의 안됐다ㅜㅜㅜㅜ 시간아까워!!
    • 강의 들을 게 많아서 무조건 머리에 집어 넣느라 이게 이해가 된 건지 아닌 건지도 모르겠다.. 이게 맞나 주말에 공부 더 해야할 거 같은데 나 왜 바쁘지?? 그래도 짬내서 TIL 훑어보고 해야겠다ㅜㅜㅠ
    • 내일은 꼭 진도에 맞게 들어야겠다.. 많이 부족해..~ 내일 완전 열심히 들어도 진도를 맞출 수 있을까? 하하..... 그래도 화이팅하자..!!!!
profile
우정
이전 포스트

[원격 강의] 파이썬 문법 기초

다음 포스트

[원격 강의] 쉽게 배우는 알고리즘(2)

0개의 댓글

관련 채용 정보