펜트하우스 블로그

프림 알고리즘 (Prim's algorithm)

특정 연결 노드를 선택 했을때 탐욕 알고리즘에 따라 진행하는 방법으로 현재 선택된 그래프 중에서 가장 작은 값을 선택하며 노드를 연결해 나가는 방식

1. 임의의 정점 선택
2. 연결된 노드 집합에 선택된 노드를 넣고 그 노드의 간선 중 가장 값이 적은 걸 선택함.
3. 선택해서 연결된 노드가 연결된 노드 집합에 없으면 그 간선을 채택 ( 사이클 체크 )
4. 간선 리스트에 간선이 없을 때까지 반복

코딩 팁 : 엣지 먼저 구현한다

from heapdict import heapdict
def prim(graph, start):
	mst, keys, pip, total_weight = list(), heapdict(), dict(), 0
    for node in graph_keys():
    	keys[node] = float('inf')
        pip[node] = none
    keys[start], pip[start] = 0, start

    while keys:
        current_node, current_key = keys, popitem()
        mst.append([pip[current_node], current_node, current_key])
        total_weight += current_key
        for adjacent, weight in mygraph[current_node], items():
            if adjacent in keys and weight < keys[adjacent]:
                keys[adjacent] = weight
                pip[adjacent] = current_node
return mst, total_weight

heapdict() 을 사용하면 pop할때 항상 자동으로 최소값이 갱신된다.

파이썬으로 작성하는 정렬

파이썬 정렬에 대해 코드로 정리하였습니다. 바로 컴파일해도 정상 작동합니다

datas=[21, 3, 1, 5, 4, 0, 9]

# 버블정렬
# 시간 복잡도 O(n^2)로 매우 느리다.
# n번 사이클 돌며 n-1번 비교
# 뒤 인덱스부터 정렬 된다.
def bubbleSort(x):
    length = len(x)-1
    swap = False
    for i in range(length):
        swap = False
        for j in range(length-i):
            if x[j] > x[j+1]:
                x[j], x[j+1] = x[j+1], x[j]
                swap = True
        if swap == False:  # 스왑이 없으면 정렬이 끝난것이므로 더이상 루프를 돌지 않게 한다.
            break            
    return x
#print(bubbleSort(datas))

# 선택정렬
# 1.주어진 데이터 중에 최소값을 찾음 2.최소값을 맨 앞 자리로 교체 3.시작 인덱스+1 로 반복
# 앞 인덱스부터 정렬 된다.
# n!*n번 반복 O(n^2)
# 버블정렬보다 빠르다.
def selectionSort(x):
    for i in range(len(x)-1):
        indexMin = i
        for j in range(i+1, len(x)):
            if x[indexMin] > x[j]:
                indexMin = j
        x[i], x[indexMin] = x[indexMin], x[i]
    return x
#print(selectionSort(datas))

# 삽입정렬
# 두번째 인덱스부터 시작, 왼쪽 데이터와 비교하여 더 작으면 그 인덱스로 삽입
# k번째 반복 후의 결과 데이터는, 앞쪽 k + 1 항목이 정렬된 상태
# (n-1)*(n-1)번 반복 O(n^2)
# 선택정렬, 버블정렬보다 빠르다.
def insert_sort(x):
    for i in range(len(x)-1):
        for j in range(i+1, 0, -1):
            if x[j] < x[j-1]:
                x[j], x[j-1] = x[j-1], x[j]
            else:
                break
    return x
#print(insert_sort(datas))

# 퀵정렬
# 1. 기준(pivot)을 정해서 작은것 left 큰것 right로 모으는 함수를 작성 2. 재귀로 반복 3. 왼쪽 + 기준점 + 오른쪽 리턴
# 재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장
# 임시로 캐시를 만들어서 정렬하므로 메모리 차지가 크지만 속도가 빠르다.
# n log n + n 번 O(n log n)
def quicksort(x):
    if len(x) <= 1:
        return x
    pivot = x[len(x) // 2]    # 중앙값을 찾음
    left, right, equal = [], [], []        # 임시 캐시
    for i in x:
        if i < pivot:
            left.append(i)
        elif i > pivot:
            right.append(i)
        else:
            equal.append(i)
    return quicksort(left) + equal + quicksort(right)
#print(quicksort(datas))

파이썬으로 만드는 이진법

직접 만드는 이진법 계산

def to_binary(decimal):
    binary = ""

    while decimal > 0:
        remainer = decimal % 2
        binary += str(remainder)
        decimal = decimal // 2
    return binary[::-1]

이진법에 많이 쓰는 함수

문자의 아스키 코드변환 함수 ord()
절대값 변환 함수 obs()
시프트 연산 >> 나누기
            << 곱하기

2진수 변환 math 내장 함수 bin 
      이 경우 문자열 맨 앞에 0b가 추가된다.

문자열 슬라이스

새로운 문자열 = 문자열 [start:end:step]

- start 잘라낼 문자열의 시작 인덱스를 정함. 생략 시 0
- end   잘라낼 문자열의 끝 인덱스를 정함.   생략 시 문자열의 끝
- step  문자열을 가져오는 구간              생략 시 1

ex)
message = "Hello World"
print(message[0:5])     # "Hello"
print(message[-11:-6])  # "Hello"
print(message[6:]       # "World"
print(message[-5:])     # "World"
print(message[::2])     # "HloWrd"
print(message[::-1])    # "dlroW olleH"

리눅스 셸 명령이 더 익숙하여 윈도우에서 작업 수행시 잦은 실수가 나타났다. 참지 못하고 zsh을 윈도우에 올리기로 했다.
방법은 간단했다. 윈도우 파워셸이 아닌 gitbash를 zsh를 사용하게 하는 방법이었다.
(gitbash가 설치된 상태)

zsh설치

https://gist.github.com/fworks/af4c896c9de47d827d4caa6fd7154b6b
위 링크에서 다운을 받는다. 현재 zsh는 zstd라는 특수한 압축방법을 사용해서 따로 압축해제를 해줘야 한다고 한다.
강제로 zstd 확장자를 지우고 tar로 압축을 풀었다.

압축 내용을 git 설치 폴더에 해제 (기본 설치경로 C:\Program Files\Git)
zsh 명령어를 이용해 확인한다.

Oh-my-zsh

추가로, Oh-my-zsh 설치한다. zsh를 사용하는데 이걸 사용안하면 개발력 -10 이나 다름없다!
sh -c " $( curl -fsSL https://raw.githubusercontent.com/robbyrussell/oh-my-zsh/master/tools/install.sh ) "

모두 수행했으면 bash 설정에서 zsh를 실행하도록 변경한다. ~/.bashrc

# Launch Zsh

if [ -t 1 ]; then
exec zsh
fi

퍼사드 패턴이란?

퍼사드는 클래스 라이브러리 같은 어떤 소프트웨어의 다른 커다란 코드 부분에 대한 간략화 된 인터페이스를 제공하는 객체이다.

퍼사드는 소프트웨어 라이브러리를 쉽게 사용할 수 있게 해준다. 또한, 쉽게 이해하기 위한 공통 작업에 대해 간편한 메소드를 제공한다.

라이브러리 밖 코드가 라이브러리 안 코드에 의존을 줄여준다.

예) class Cpu, class Memory, class HardDrive 를 class Computer에서 구현해서 밖에서는  class Computer만 이용한다.

이때, class Computer가 facade가 되는것이다.

데메테르의 법칙 == 최소지식의 원식

1. 프레임워크란?

개발에 필요한 구조를 이미 코드로 만들어 놓아 필요한 부분을 조립하는 형태의 개발 방식 또는 환경을 말한다.

2. 스프링 프레임워크 주요 특징

2.1. POJO (Plain Old Java Object)

객체간의 관계를 구성할 때 별도의 API를 사용하지 않고 일반적인 JAVA 코드를 이용해서 그대로 스프링에서 사용이 가능하다.
"개발자가 특정한 라이브러리나 컨테이너의 기술에 종속적이지 않다"

2.2. 제어의 역행 (IoC)

먼저 제어의 역행은 메서드나 객체의 호출작업을 개발자가 결정하는 것이 아닌 외부에서 결정하는것을 말한다.
ex) 컴퓨터 조립에서 메인보드를 결정 후 그에 맞는 부품을 개발하고 메인보드가 호출 하는것과 같이,
개발자는 프레임워크의 부품을 개발하고 조립하는 방식의 개발을 하는 방식이다. 최종호출은 프레임워크에 위임한다.

2.3. 의존성 주입 (DI)

2.3.1. 의존성 주입을 통한 객체간의 관계 구성

제어의 역전이 일어날 때 스프링 내부객체(스프링 빈)들간의 관계를 관리할 때 사용하는 기법이다.

• 생성자를 통한 주입
• set 메서드를 이용한 주입
• 애노테이션으로 처리가 가능함.
  API 종속성을 줄여준다. (XML만 바꿔주면 편리하게 개발가능)
  외부에서 생성한것을 생성자나 setter를 이용하여 가져오는 방식을 사용한다.2.3.2. 의존성 주입의 장점필수로 사용되어야만 하는 레퍼런스가 없을 경우 인스턴스의 생성 자체를 막아 오작동, 의도와 다른 개발을 막아준다.

3. 컨테이너

서블릿의 생명주기를 관리한다. JSP를 서블릿으로 변환하는 기능 수행함.
서블릿 컨테이너 : 표준 API에서는 추상 클래스와 인터페이스를 구현한 클래스를 제공하여 기본 동작과 API 호환성을 지원한다.
다른 컨테이너와 호환성을 보장하기 위해서.
JSP 컨테이너 : JSP -> 서블릿 변환 역할

4. ASP

동적으로 서버에서 작동하는 페이지

비쥬얼 베이직에서 나온것으로 비쥬얼베이직 스크립트 이후 나온것이 ASP.net
원도우에서 운영체제 기반으로 작동하기 때문에 윈도우 보안문제와 같이 연결되며 취약점이 동일하다.
클라이언트가 요청시 서버에서 처리를 하여 HTML로 바꾸어 응답한다.

5. JSP ( JAVA Server Page )

HTML내에 자바 코드를 넣어 웹서버에서 동적으로 웹페이지를 생성하여 브라우저에 돌려주는 언어이다.
Server side 스크립트 언어

6. 작동 순서

브라우저가 웹 서버에 요청 정보를 전달 -> 웹 서버는 WAS에 전달 -> Web Container에 의해서 JSP로 작성된 코드가 서블릿 코드로 변환

7. 서비스 추상화

스프링은 서블릿 애플리케이션을 만들지만 서블릿 코드를 사용하지 않는다. doPost, doGet 실행하지 않고 애노테이션을 이용해 Mapping 한다. 서블릿을 직접 사용하지 않아도 괜찮아서 편리한 장점이 있다.

여러가지 기술로 바꾸기가 용이하다. ex) 스프링부트 + 톰캣 -> 스프링부트 + 네티

스프링 부트는 웹 컨테이너가 있어 편하고 간편한 규모의 개발에 적합하다. / 일반 스프링에서는 MVC를 하여 WAS 배포를 진행

8. 스프링 MVC 구조

1. 사용자의 모든 요청은 스프링 MVC의 Front Controller에게 전달된다.
2. 전달된 요청은 적절한 Controller를 호출
3. Controller의 작업이 개발자의 몫이며, 적절한 서비스를 찾아 호출한다.
4. 서비스는 데이터 베이스의 작업을 담당하는 DAO를 이용해서 데이터를 호출한다.
5. DAO 객체는 MyBatis를 이용하는 Mapper를 통해서 원하는 작업 수행
6. 서비스가 처리한 데이터를 Controller에 전달.
7. Controller는 Front Controller에게 전달
8. Controller는 다시 스프링에 데이터를 전달

9. XML 파일의 역할

스프링 MVC 애노테이션 처리 설정을 XML에 하여 편리하게 변경 가능하다.
JSON 처리는 POM.xml에 jackson-databind 라이브러리를 추가

10. DataBase의 제어

DB 제어용으로 DAO를 만든다. 향후 DB 관련 기술이 변해도 DAO만 변경해서 처리한다.
SQL 문은 XML Mapper로 작성하고 DAO 인터페이스를 구현하는 클래스를 만들고, 그 클래스를 root-context.xml에 빈을 등록한다.
(애노테이션 설정)

11. REST

Representational State Transfer 의 약자 ( 자원의 표현에 의한 상태 전달 )
자원이란 소프트웨어가 관리하는 모든 데이터를 의미하며, 자원의 표현이란 데이터의 이름을 말한다.
ex) 유저 정보가 자원일 때, 'users'를 자원의 표현으로 하는 것

JSON 또는 XML를 통해 데이터를 주고 받는 것이 널리 알려진 방법
@RestController 스프링버전 4 부터 지원한다. 뷰를 안만들고 REST 방식 데이터를 처리 할 수 있다.

11.1. REST 방식 원칙

• URI 가 원하는 리소스를 의미한다.
• URI 에는 식별 할 수 있는 데이터를 같이 전달. HTTP의 전송 방식이 실제 작업의 종류를 의미한다.
  보통 URI는 정보의 목적지를 의미한다.

11.2. REST FULL

REST API의 설계 의도대로 지키는것을 REST FULL하다고 한다. 서버는 클라이언트에게 API만 제공

12. GET 방식 POST 방식

GET : 데이터 값을 URL 뒤 ? 다음에 붙여 통신하는 방식. URL 형식에 맞는 인코딩 필수
POST : 데이터를 HTTPBODY에 넣어 통신하는 방식. GET과 달리 브라우저에서 캐싱 불가능. 크기 제한X

GET 은 단순 조회용에 적합하며, 서버의 상태나 값 변경은 POST 를 이용

ClassNotFoundException 클래스를 찾지 못함
CloneNotSupportedException Cloneable 인터페이스 미구현
IllegalAccessException 클래스 접근을 못함
InstantiationException 추상 클래스 또는 인터페이스를 인스턴스화 하고자 할때 
InterruptedException 쓰레드가 중단 되었을때
NoSuchFieldException 지정된 필드가 없을때
NoSuchMethodException 지정된 메소드가 없을때

IOException

CharConversionException문자 변환에서 예외가 발생했을때

EOFException 파일의 끝에 도달했을때

FileNotFoundException 파일이 발견되지 않았을때

InterruptedIOException 입출력 처리가 중단 되었을때

SyncFailedException 시스템 버퍼를 동기시키는 FileDescriptor.sync()의 호출 실패시

UnsupportedEncodingException 지정된 문자 부호화 형식을 지원하고 있지 않을때

UTFDataFormatException 부정한 UTF-8 방식 문자열과 만났을때

[ObjectStreamException] InvalidClassException

시리얼라이즈 처리에 관한 문제가 클래스 안에 있을때

[ObjectStreamException] InvalidObjectException

시리얼라이즈된 오브젝트에서 입력 검증에 실패했을때

[ObjectStreamException] NotActiveException

스트림 환경이 액티브하지 않을 때 메소드를 호출했을때

[ObjectStreamException] NotSerializableException

오브젝트를 시리얼라이즈 할 수 없을때

[ObjectStreamException] OptionalDataException

오브젝트를 읽을때 기대 이외의 데이터와 만났을때

[ObjectStreamException] StreamCorruptedException

읽은 데이터 스트림이 파손되어 있을때

[ObjectStreamException] WriteAbortedException

기록중에 예외가 발생한 스트림을 읽었을때

RuntimeException

ArithmeticException 제로제산 등의 산술 예외 발생시

ArrayStoreException 배열에 부정한 형태의 오브젝트를 저장하고자 할때

IllegalMonitorStateException 모니터 상태가 부정일때

IllegalStateException 메소드가 요구된 처리를 하기에 적합한 상태에 있지 않을때

NegativeArraySizeException 음의 크기로 배열 크기를 지정하였을때
NullPointerException null 오브젝트로 접근했을때
SecurityException 보안 위반시 
UnsupportedOperationException 지원되지 않는 메소드를 호출했을때

[IllegalArgumentException] IllegalThreadStateException

쓰레드가 요구된 처리를 하기에 적합한 상태에 있지 않을때

[IllegalArgumentException] NumberFormatException

부적절한 문자열을 수치로 변환하고자 할때

[IndexOutOfBoundException] ArrayIndexOutOfBoundsException

범위 밖의 배열 첨자 지정시

[IndexOutOfBoundException] StringIndexOutOfBoundsException

범위 밖의 String 첨자 지정시

Error 

ClassCircularityError 클래스 초기화중에 순환 참조를 검출시

ExceptionInInitializerError  정적 이니셜라이저로 예외가 발생시

NoClassDefFoundError 클래스 정의가 발견되지 않았을때

UnsatisfieldLinkError 클래스에 포함되는 링크 정보를 해결할 수 없을때

VerifyError 클래스 파일안에 부적절한 부분이 있을때 ThreadDeath 쓰레드가 정지해야만 한다는 의미 

[ClassFormatError] UnsupportedClassVersionError

JVM이 지원되지 않는 버전 번호를 가진 클래스 파일을 읽고자 할때

[IncompatibleClassChangeError] AbstracMethodError

추상 메소드를 호출했을때

[IncompatibleClassChangeError] IllegalAccessError

접근할 수 없는 메소드와 필드를 사용하고자 했을때

[IncompatibleClassChangeError] InstantiationError

인터페이스 또는 추상 클래스를 인스턴스화하고자 했을때

[IncompatibleClassChangeError] NoSuchFieldError

지정한 필드가 존재하지 않을때

[IncompatibleClassChangeError] NoSuchMethodError

지정한 메소드가 존재하지 않을때

VirtualMachineError

InternalError 내부에러

OutOfMemoryError 메모리부족으로 메모리를 확보 못함

StackOverflowError 스택 오버 발생

UnknownError 심각한 예외발생

출처 oracle 문서 카피

람다를 이해를 위한 함수 객체 Functor
foo() 함수처럼 인자 업싱 호출되는 함수객체는 발생자 Generator 라고 부른다.
foo(x) 하나의 인자를 받는 것을 단항 함수 unary Function
foo(x,y) 두개의 인자를 받는것을 이항 함수 Binary Function
인자의 개수와 별개로 bool 값을 반환하는 함수포인터나 함수객체는 술어(Predicate)라고 부름
이항 술어 단항 술어

람다 함수
[변수 캡쳐](받을 인자)->리턴타입{함수}(넘길인자)

변수캡쳐   : 현재 함수에서 사용할것을 캡쳐하는것
            = 해당 함수의 모든 변수를 사용 
            & 모든 변수를 참조형으로 사용
받을인자   : 인자의 타입 지정
->리턴타입 : 리턴타입 지정 void의 경우 ->와 함께 생략
{함수}    : 함수의 몸체
(넘길인자) : 함수에서 사용하는 그 인자