Week03 (11.14-11.18)

221114 TIL

버블 정렬

자바_버블정렬

TIP : 파이썬에서 Swap하는 법

>>> a = 3
>>> b = 4
>>> a, b = b, a

def bubble_sort(array):
    for circle in range(len(array) - 1):
        for bubble in range(len(array)-circle-1):
            if array[bubble] > array[bubble + 1]:
                array[bubble], array[bubble + 1] = array[bubble + 1], array[bubble]
    return array

시간복잡도 : $O(N^2)$

선택 정렬

자바_선택정렬

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

        array[i], array[min_index] = array[min_index], array[i]
    return array

시간복잡도 : $O(N^2)$

삽입 정렬

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

시간복잡도 : $O(N^2)$

병합 정렬

병합 정렬은 배열의 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복하는 알고리이다.

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

병합 정렬_재귀

분할 정복 알고리즘을 이용하면, 재귀로 병합 정렬을 풀 수 있다.
분할 정복은 문제(Divide and Conquer)를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.

MergeSort(시작점, 끝점)이라 하면, MergeSort(0, N) = Merge(MergeSort(0, N/2) + MergeSort(N/2, N))
라고 할 수 있다.

즉, 0부터 N까지 정렬한 걸 보기 위해서는
0부터 N/2 까지 정렬한 것과 N/2부터 N까지 정렬한 걸 합치면 된다.

def merge_sort(array):
    if len(array) <= 1:
        return array
    mid = len(array) // 2
    left_array = array[:mid]
    right_array = array[mid:]
    return merge(merge_sort(left_array), merge_sort(right_array))
    
def merge(array1, array2):
...

시간 복잡도
merge 함수는 while 문이 len(array1) 과 len(array2)의 길이 만큼 반복하므로 최대 len(array1) + len(array2) 만큼의 연산량이 필요하다. 따라서 시간 복잡도는 $O(N)$이다.

merge_sort 함수는 1. 크기 $N$인 배열을 정렬하기 위해, 크기 $N/2$인 부분 배열 2개를 비교한다. 즉 $N/2\times2=N$이다 2. 크기 $N/2$ 인 부분 배열 2개를 정렬하기 위해
크기 $N/4$ 인 부분 배열 4개를 비교하므로 $N/4\times4 = N$이다 ... 즉 크기가 $N$ → $N/2$ → $N/2^2$ → $N/2^3$ → .... → $1$으로 $log_2N$이다.

두 개를 합치면 $N$만큼의 연산을 $logN$번 반복하니 $O(NlogN)$이 된다.

2211115 TIL

후기

오늘은 객체지향 개념을 다시 공부했다. 객체지향 개념은 해도 해도 부족한 것 같은 느낌이다. 실제 프로젝트 등에서 사용되는 코드를 작성해 본 적이 없다보니, 인테페이스와 추상클래스의 사용을 언제 어떻게 잘 활용해야하는지를 잘 알지 못 하는 것 같다. 다른 이들의 코드를 보는 게 왜 중요한지 알 것 같다.

이번주는 cs 공부도 다시 시작해야겠다.

221116 TIL

프로그래머스 _ 분수의 덧셈

import math

def LCM(n1, n2): 
    temp = math.gcd(n1, n2)
    return n1*n2/temp

def solution(denum1, num1, denum2, num2):
    top = denum1*num2 + denum2*num1
    bottom = num1*num2
    n = math.gcd(top, bottom)
    if n == 1:
        return [top, bottom]
    else:
        return [top/n, bottom/n]

sort() vs sorted()

sort 함수는 리스트명.sort() 형식으로 "리스트형의 메소드"이며 리스트 원본값을 직접 수정한다. 반명 sorted 함수는 sorted(리스트명) 형식으로 "내장 함수"이며 리스트 원본 값은 그대로이고 정렬 값을 반환한다.

오늘 알고리즘 타임어택이 있었다. 물론 프로그래머스 코딩 입문 단계라 어렵지는 않았다. 그런데도 충격적이게 ...3번이나 실패했다. 아무래도 형변환의 문제가 있었나? 싶다. 내가 바보 같이 실패한 코드를 저장해뒀어야 했는데,,,내가 어떻게 적었는지도 모른다. 진짜 이 부분이 가장 후회된다. 따로 작성해두고 무엇이 문제였는지 파악했어야 하는데...앞으로는 내가 맞다고 생각한 코드에서 문제가 생기면 따로 저장해두고 어디에서 왜 틀렸는지 분석해야겠다.

221117 TIL

JAVA 제네릭 작성

221118 TIL

튜터님과 Q&A

1. Q : 일반적으로 파이썬은 MongoDB, 자바는 msSQL, Orcle을 연동하여 사용하는데 자바에서 noSQL을 잘 다루지 않는 이유가 자바 자체가 안정성을 위한 언어가 DB 또한 안정성을 보장하는 관계형 DB를 사용하는 것인가요?
   A : 아니다. 고정관념. 자바에서도 MongoDB 사용할 수 있으며 noSQL 사용하는 경우도 많다.

2. Q: 자바에서 인터페이스로 다중상속 기능을 구현하는 경우가 거의 없다고 배웠는데 맞나요(한 클래스가 여러개의 인터페이스를 구현하는 경우가 없나요?)?
   A : 진리의 case by case

List를 ArrayList로 선언해 사용하는 이유

https://bibi6666667.tistory.com/236

프로세스

프로세스(Process)는 컴퓨터에서 실행되고 있는 프로그램을 말하며, CPU 스케줄링의 대상이 되는 작업(task)라는 용어와 거의 같은 의미로 쓰인다. 이 때 스레드는 프로세스 내 작업의 흐름을 의미한다.

프로그램이 메모리에 올라가면 프로세스가 되는 인스턴스화가 일어나고, 운영체제의 CPU 스케줄러에 따라 CPU가 프로세스를 실행한다.

프로세스의 상태값

1. 생성 상태
fork() : 부모 프로세스의 주소 공간을 그대로 복사, 새로운 자식 프로세스를 생성하는 함수. 부모 프로세스의 비동기 작업 등을 상속하지 않음.

exec() : 새롭게 프로세스를 생성하는 함수

2. 대기 상태
대기 중단 상태(ready suspended)는 메모리 부족으로 일시 중단된 상태

3. 실행 상태
실행 상태(running)은 CPU 소유권과 메모리를 할당받고 인스트럭션을 수행 중인 상태를 의미한다. CPU burst가 발생했다고 표현한다.

4. 중단 상태
중단 상태(blocked)는 어떤 이벤트가 발생한 이후 기다리며 프로세스가 차단된 상태다. I/O 디바이스에 의한 인터럽트로 중단 상태가 많이 발생하기도 한다.

5. 일시 중단 상태
일시 중단 상태(blocked suspended)는 대기 중단과 유사하다. 중단된 상태에서 프로세스가 실행되려고 했지만 메모리 부족으로 일시 중단된 상태다.

6. 종료 상태
종료 상태(terminated)는 메모리와 CPU 소유권을 모두 놓고 가는 상태를 말한다. 종료에는 부모 프로세스가 자식 프로세스를 강제시키는 비자발적 종료(abort)도 있다. 자식 프로세스에 할당된 자원의 한계치를 넘어서거나 부모 프로세스가 종료되거나 사용자가 process.kill등 여러 명령어로 프로세스를 종료할 때 발생한다.

프로세스 메모리 구조

스택

지역 변수, 매개 변수, 함수가 저장되고 컴파일 시에 크기가 결정되며 '동적'인 특징을 갖는다. 스택 영역은 함수가 함수를 재귀적으로 호출하면서 동적으로 크기가 늘어난다. 이때 힙과 스택의 메모리 영역이 겹치면 안 되기 때문에 힘과 스탭 사이의 공간을 비워 놓는다. 컴파일 시 크기가 결정된다.

힙

힙은 동적 할당할 때 사용되며 런타임 시 크기가 결정된다.

데이터 영역

전역 변수, 정적 변수가 저장되고, 정적인 특징을 갖는 프로그램이 종료되면 사라지는 변수가 들어 있는 영역이다. 데이터 영역은 BSS 영역과 Data 영역으로 나뉜다. BSS 영역은 초기화가 되지 않은 변수가 0으로 초기화되어 저장되며 Data 영역(Data segment)은 0이 아닌 다른 값으로 할당된 변수들이 저장된다.

코드 영역

프로그램에 내장되어 있는 소스 코드가 들어가는 영역이다. 수정 불가능한 기게어로 저장되며 정적인 특징을 갖는다.

스레드(Thread)

프로세스의 실행 가능한 가장 작은 단위.
프로세스는 여러 스레드를 가질 수 있다.

코드, 데이터, 스택, 힙을 각각 생성하는 프로세스와 달리 스레드는 코드, 데이터, 힙은 스레드끼리 공유한다.

멀티 프로세싱

하나의 프로그램을 여러 개의 프로세스로 구성하여 각 프로세스가 하나의 작업을 처리하도록 하는 것

멀티 프로세싱을 통해 하나 이상의 일을 병렬로 처리할 수 있으며 특정 프로세스의 메모리, 프로세스 중 일부에 문제가 발생되더라도 다른 프로세스를 이용하여 처리할 수 있어 신뢰성이 높다.

그러나 문맥 교환 과정에서 캐시 메모리 초기화 등 무거운 작업이 진행되고 많은 시간이 소모되는 등의 오버헤드가 발생하게 된다. 프로세스는 각 독립된 메모리 영역을 할당 받았기 때문에 하나의 프로그램에 속하는 프로세스들 사이의 변수를 공유할 수 없다. 따라서 IPC 방법을 사용해야 하며, 이는 어렵고 복잡한 통신 방법이다.

프로세스 간 통신 (IPC_Inter Process Communication)

IPC는 프로세스끼리 데이터를 주고받고 공유 데이터를 관리하는 메커니즘을 뜻한다.

멀티 프로세스는 IPC가 가능하다. 예를 들어, 클라이언트가 데이터를 요청하고 서버는 클라이언트 요청에 응답하는 것도 IPC다.

IPC의 종류로는 공유 메모리, 파일, 소켓, 익명 파이프, 명령 파이프, 메시지 큐가 있다. 이들은 메모리가 완전히 공유되는 스레드보다 속도가 떨어진다.

프로세스 제어 블록 (PBC_Process Control Block)

특정 프로세스에 대한 메타 데이터를 저장하고 있는 커널 내 자료구조이다.

프로세스는 CPU를 할당받아 작업을 처리하다가 프로세스 전환이 발생하면 진행하던 작업을 저장하고 CPU를 반환해야 한다. 이때 작업의 진행 상황을 모두 PCB에 저장한다. 그리고 다시 CPU를 할당받게 되면 PCB에 저장되었던 내용을 불러와 종료되었던 시점부터 다시 작업을 수행한다.

PCB에 저장되는 정보

• 프로세스 식별자(Process ID, PID) : 프로세스 식별 번호
• 프로세스 상태 : new, ready, running, waiting, terminated 등의 상태를 저장
• 프로그램 카운터(Program Counter, PC) : 프로세스가 다음에 실행할 명령어의 주소를 가리킨다.
• CPU 레지스터
• CPU 스케줄링 정보 : 프로세스의 우선순위, 스케줄 큐에 대한 포인터 등
• 메모리 관리 정보 : 페이지 테이블 또는 세그먼트 테이블 등과 같은 정보를 포함한다.
• 입출력 상태 정보 : 프로세스에 할당된 입출력 장치들과 열린 파일 목록
• 어카운팅 정보 : 사용된 CPU 시간, 시간 제한, 계정 번호 등

문맥 교환 (Context Switching)

문맥 교환은 PCB를 교환하는 과정을 말한다.

한 프로세스에 할당된 시간이 끝나거나 인터럽트에 의해 발생한다. CPU는 한 번에 하나의 프로세스만 처리할 수 있기 때문에, 많은 프로세스가 동시 구동되고 있는 거처럼 보이는 것은 다른 프로세스와의 문맥 교환이 아주 빠른 속도로 실행되고 있기 때문이다.

동작 중인 프로세스가 대기를 하면서 해당 프로세스의 상태(Context)를 프로세스 제어 블록(PCB)*에 보관하고, 대기하고 있던 다음 순서의 프로세스가 동작하면서 이전에 보관했던 프로세스의 상태를 복구한다.

그림처럼 한 개의 프로세스 A가 실행하다 멈추고, 프로세스 A의 PCB를 저장하고 다시 프로세스 B를 로드하여 실행한다. 그리고 다시 프로세스 B의 PCB를 저장하고 프로세스 A의 PCB를 로드한다.

멀티 스레딩

프로세스 내 작업을 여러 개의 스레드, 멀티 스레드로 처리하는 기법이다. 스레드끼리 서로 자원을 공유하기 때문에 효율성이 높다. 스레드 간 통신시 Data, Heap 메모리 영역을 이용해 데이터를 주고 받으므로 통신 방법이 간단하다. Context switching 시 PCB 및 캐시 메모리를 비울 필요가 없기 때문에 비용이 적고 더 빠르다.

그러나 서로 다른 스레드가 Data, Heap 영역 등을 공유하기 때문에 어떤 스레드가 다른 스레드에서 사용중인 변수나 자료구조에 접근하여 엉뚱한 값을 읽어오거나 수정할 수 있다. 즉, 자원 공유 동기화 문제가 발생한다. 또한 하나의 스레드에 문제가 생기면 전체 프로세스가 영향을 받는다.

Week03

아 진짜 머리에 넣는게 너무 많아서 쓸 것도 너무 많은데 쓸 시간이 없다 증말...막상 글 쓰면 또 이것저것 구글링하고 알아보느라 TIL 쓰는 데도 한 시간은 우습게 넘어간다. 글 쓸 시간이 없다면 좀 ㅎ 변명이려나~... 그치 변명이긴 한데 ㅠㅠ 이럽게 허접하게 TIL과 WIL을 넘기고 싶지 않으니, 내일의 나는 이걸 다 정리할거다. 이번주는 뭔가 공부가 재밌었다. 알고리즘은 잠깐 내려놔서 그런건지 몰라도 자바를 배우니 재밌다. 익숙해서 그런가. 그치만 한편으로는 나는 아직도 부족하고 부족하고 또 부족하다는 생각이 들었다. 아직 시간은 있으니 조급해 하지말고 천천히 차근차근 해 나가자.

그리고 튜터님들 진짜 너무 친절하시다. 젭 싫다 했던 나 나와. 머리 박아... 반성해. 젭 점점 정들고 캐릭터 귀여워ㅠ,ㅠ. 특히 저녁타임에 공부하다 궁금한 것들 모아두고 무려 10시까지 질문을 할 수가 있다. 게다가 우리 튜터님들 진짜..능력자들...성격도 너무 좋으셔. 튜터님들 보면서 여기 들어온 나 너무 칭찬해...굳이야 굳.