11. 15 JAVA 기초 강의/ 알고리즘 강의 + 그림으로 배우는 알고리즘

1. JAVA 기초 강의

인터페이스, 상속을 활용한 클래스 구현

public class Main {

    public static void main(String[] args) {
        Human grandParent = new GrandParent("할아버지", 70);
        Human parent = new Parent("엄마", 50);
        Human child = new Child("나", 20);

        Human[] humans = {grandParent, parent, child};
        for (Human human : humans) {
            System.out.println(human.name + ", 나이:" + human.age + ", 속도" + human.speed + ", 장소" + human.getLocation());
        }
        System.out.println("<활동 시작>");
        for (Human human : humans) {
            if (human instanceof Walkable) {
                ((Walkable) human).walk(1, 1); //각 인터페이스로 형변환된 (Human)human -> (Walkable)human
                System.out.println("- - - - - -");
            }
            if (human instanceof Runnable) {
                ((Runnable) human).run(2, 2);
                System.out.println("- - - - - -");
            }
            if (human instanceof Swimmable) {
                ((Swimmable) human).swim(3, -1);
                System.out.println("- - - - - -");
            }
        }
    }
}

instanceof 연산자 : 참조 변수의 형 변환(Casting) 가능 여부를 확인하기 위해 사용 ~객체지향: 다형성

(참조 변수 instanceof 타입(클래스명))

 

for each vs for

String[] numbers = {"one", "two", "three"};
for(int i=0; i<numbers.length; i++) {
    System.out.println(numbers[i]);
}

String[] numbers = {"one", "two", "three"};
for(String number: numbers) {
    System.out.println(number);
}
/*
for (type var: iterate(객체)) {
    body-of-loop
} 단, for each 문은 따로 반복회수를 명시적으로 주는 것이 불가능하고, 
1스탭씩 순차적으로 반복될때만 사용가능하다는 제약이 있다.
*/

*문제 해결 시 고려해볼 부분

- 문제에 제시된 클래스만 활용할 것이 아니라 전부를 아우르고 있는 공통점(ex: human)을 찾아 거기부터 시작하는 것도 방법이다

 

에러와 예외처리

펌: 강의자료

1) Try-catch(finally)

try {
    // 예외가 발생할 가능성이 있는 코드를 구현합니다.
} catch (FileNotFoundException e) {
    // FileNotFoundException이 발생했을 경우,이를 처리하기 위한 코드를 구현합니다.
} catch (IOException e) {
    // FileNotFoundException이 아닌 IOException이 발생했을 경우,이를 처리하기 위한 코드를 구현합니다.
} finally {
    // 예외의 발생여부에 관계없이 항상 수행되어야하는 코드를 구현합니다.
}

public class Main {
    public static void main(String[] args) {
        int number = 10;
        int result;

        for (int i = 10; i >= 0; i--) {
            try {
                result = number / i;
                System.out.println(result);
            } catch (Exception e) {
                System.out.println("Exception발생: " + e.getMessage());
            } finally {
                System.out.println("항상 실행되는 finally 구문");
            }
        }
    }

}

2) Try-with-resource

import java.io.FileOutputStream;
import java.io.IOException;

public class Main {
    public static void main(String[] args) {

        try (FileOutputStream out = new FileOutputStream("test.txt")) {
            // test.txt file 에 Hello Sparta 를 출력
            out.write("Hello Sparta".getBytes());
            out.flush();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

3) 메소드에서의 예외 선언

void method() throws IndexOutOfBoundsException, IllegalArgumentException {
    //메소드의 내용
}

 

JAVA.TIME 패키지

import java.time.LocalDate;
import java.time.LocalDateTime;
import java.time.LocalTime;

public class Main {
    public static void main(String[] args) {
        System.out.println("now()를 활용하여 생성"); //지금 현재
        LocalDate date = LocalDate.now();
        LocalTime time = LocalTime.now();
        LocalDateTime dateTime = LocalDateTime.now();

        System.out.println("of()를 사용하여 생성"); // 지정값 할당
        LocalDate newDate = LocalDate.of(2077, 11, 15);
        LocalTime newTime = LocalTime.of(12, 44, 30);

    }
}

 

2. 알고리즘 기초 강의 + 그림으로 배우는 알고리즘

알고리즘 = 데이터와 처리의 조합이다

 

정렬

버블 정렬

input = [4, 6, 2, 9, 1]


def bubble_sort(array):
    n = len(array)
    for num in range(n):
        for j in range(n - num - 1): #비교 후 줄어드는 비교군이 핵심
            if array[j] > array[j + 1]:
                array[j], array[j+1] = array[j+1], array[j]
    return array


bubble_sort(input)
print(input)  # [1, 2, 4, 6, 9] 가 되어야 합니다!

시간복잡도 : 이중 반복문 ~ N^2 -> O(N^2)

선택 정렬

input = [4, 6, 2, 9, 1]


def selection_sort(array):
    n = len(array)
    for num in range(n - 1):
        min_index = num
        for j in range(n - num):
            if array[num + j] < array[min_index]:
                min_index = num + j
        array[num], array[min_index] = array[min_index], array[num]
    return array


selection_sort(input)
print(input) # [1, 2, 4, 6, 9] 가 되어야 합니다!

print("정답 = [1, 2, 4, 6, 9] / 현재 풀이 값 = ",selection_sort([4, 6, 2, 9, 1]))
print("정답 = [-1, 3, 9, 17] / 현재 풀이 값 = ",selection_sort([3,-1,17,9]))
print("정답 = [-3, 32, 44, 56, 100] / 현재 풀이 값 = ",selection_sort([100,56,-3,32,44]))

vs 버블 정렬: 최솟값을 할당하기 위한 변수가 필요하다

시간복잡도 : 이중 반복문 ~ N^2 -> O(N^2)

 

삽입 정렬

input = [4, 6, 2, 9, 1]


def insertion_sort(array):
    n = len(array)
    for i in range(1, n):
        for j in range(i):
            if array[i - j - 1] > array[i - j]:
                array[i - j - 1], array[i - j] = array[i - j], array[i - j - 1]
            else:
                break
    return array

insertion_sort(input)
print(input)

print("정답 = [4, 5, 7, 7, 8] / 현재 풀이 값 = ",insertion_sort([5,8,4,7,7]))
print("정답 = [-1, 3, 9, 17] / 현재 풀이 값 = ",insertion_sort([3,-1,17,9]))
print("정답 = [-3, 32, 44, 56, 100] / 현재 풀이 값 = ",insertion_sort([100,56,-3,32,44]))

시간복잡도 : 이중 반복문 ~ N^2 -> O(N^2) (오메가표기법: Ω(N), 이중반복문이 실행되기 전 break하는 경우)

 

배열의 병합 + 정렬

array_a = [1, 2, 3, 5]
array_b = [4, 6, 7, 8]


def merge(array1, array2):
    result = []
    array1_index = 0
    array2_index = 0
    while array1_index < len(array1) and array2_index < len(array2):
        if array1[array1_index] < array2[array2_index]:
            result.append(array1[array1_index])
            array1_index += 1
        else:
            result.append(array2[array2_index])
            array2_index += 1

    if array1_index == len(array1):
        while array2_index < len(array2):
            result.append(array2[array2_index])
            array2_index += 1

    if array2_index == len(array2):
        while array1_index < len(array1):
            result.append(array1[array1_index])
            array1_index += 1

    return result


print(merge(array_a, array_b))

print("정답 = [-7, -1, 5, 6, 9, 10, 11, 40] / 현재 풀이 값 = ", merge([-7, -1, 9, 40], [5, 6, 10, 11]))
print("정답 = [-1, 2, 3, 5, 10, 40, 78, 100] / 현재 풀이 값 = ", merge([-1,2,3,5,40], [10,78,100]))
print("정답 = [-1, -1, 0, 1, 6, 9, 10] / 현재 풀이 값 = ", merge([-1,-1,0], [1, 6, 9, 10]))

스택

push(data) : 맨 앞에 데이터 넣기

pop() : 맨 앞의 데이터 뽑기

peek() : 맨 앞의 데이터 보기

isEmpty(): 스택이 비었는지 안 비었는지 여부 반환해주기

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class Stack:
    def __init__(self):
        self.head = None

    def push(self, value):
        new_head = Node(value) # [3]을 만들고
        new_head.next = self.head # [3] -> [4}로 만들어준 다음
        self.head = new_head # 현재 head의 값을 [3]으로 바꿔준다

    # pop 기능 구현
    def pop(self):
        if self.is_empty(): # 비어있을 경우 에러
            return "Stack is empty!"
        delete_head = self.head # 제거할 node를 delete_head 변수에 할당
        self.head = self.head.next # 그리고 head를 현재 head의 다음으로 대입합니다
        return delete_head # 그리고 스택에서 제거한 node를 delete_head 변수를 반환하며 제거완료

    def peek(self):
        if self.is_empty():
            return "Stack is empty"

        return self.head.data

    # isEmpty 기능 구현
    def is_empty(self):
        return self.head is None


stack = Stack()
stack.push(3)
stack.push(4)
print(stack.peek())

스택을 활용한 탑 문제

top_heights = [6, 9, 5, 7, 4]


def get_receiver_top_orders(heights):
    answer = [0] * len(heights) # 탑이 건설된 길이만큼의 배열을 생성하고 초기화한다
    while heights: # heights가 빈 상태가 되기 전까지, 길이 O(N)
        height = heights.pop() # 하나씩 꺼내서
        for idx in range(len(heights) - 1, - 1, - 1): #(시작값,종료값,증분)인덱스부터 시작, -1만큼 이동, [-1]에서 종료, 길이 O(N)
            if heights[idx] > height: #만약 현재 idx가 height보다 크다면, 레이저가 박힌다
                answer[len(heights)] = idx + 1 # 위치를 알려 주기 위해, answer 배열에서 인덱스 길이 해당 위치에 인덱스 + 1 값을 대입
                break #레이저를 박았다면 for 반복문 break
    return answer


print(get_receiver_top_orders(top_heights))  # [0, 0, 2, 2, 4] 가 반환되어야 한다!

print("정답 = [0, 0, 2, 2, 4] / 현재 풀이 값 = ",get_receiver_top_orders([6,9,5,7,4]))
print("정답 = [0, 0, 0, 3, 3, 3, 6] / 현재 풀이 값 = ",get_receiver_top_orders([3,9,9,3,5,7,2]))
print("정답 = [0, 0, 2, 0, 0, 5, 6] / 현재 풀이 값 = ",get_receiver_top_orders([1,5,3,6,7,6,5]))

그림으로 배우는 알고리즘

2장 변수와 배열

3장 자료 구조