📢 개요

코딩테스트를 준비하면서, 파이썬으로 코드를 구현할 일이 많이 생겼다.

근데, 얼마가 지나지 않아서, 같이 공부하는, 파이썬으로 구현을 하는 몇몇 사람들, 코드를 보다가..

예를들어, 두 수의 합과 곱을 구하는 코드를 구현한다고 치면

  • case.1
n,m = map(int,input().split())

print(n + m)
print(n * m)
  • case.2
def sum(self,a,b):
	return a + b
def mul(self,a,b):
	return a * b

if __name__ == '__main__' :
	n,m = map(int,input().split())
	print(sum(n,m))
    print(mul(n,m))

위와 같이, 두가지 케이스로 구분됐다.

case.1이 파이썬으로 갈아탄지 얼마안된, 내 코드구현방식
case.2가 몇몇 분들의 코드구현방식

결론만, 먼저 정리하면, case.2 방식으로, 앞으로 선호하는것이 이상적(?)이다.
(물론, 위에 예시는, 아주~~간단한 예시다보니, case.1방식이 "더 보기에도, 간단해 보이지않느냐" 할 수 있지만, 그것의 문제가 아니다.

작은 기능을 하는 프로그램이라도, 각각을 메소드화 시키고, main(메인)에서 해당 로직이 실행되게 작성하는 습관을 들여야 한다.

후에, 코딩테스트용이 아니고, 프로젝트개념으로, 접근을 하게 되면, 우리는 또한,
스크립트파일로 실행하는 방식 VS 모듈로 사용하는 방식을 구분해서 알고 있어야한다.

📢 if __name__ == '__main__' :

일단, 그럼 다시 주제로 돌아와보자.

if __name__ == '__main__':

파이썬 코드들을 보면, 여러 메소드나, 클래스가 구현되어있고, 마지막에는, 위에 코드가 항상 보이는데, 이게 뭘까.

👉 이 코드의 의미는, 현재 스크립트 파일이 실행되는 상태를 파악하기 위해 사용

예를 들어보자.

📝 hello.py

print('hello 모듈 시작')
print('hello.py __name__:', __name__)    # __name__ 변수 출력
print('hello 모듈 끝')

📝 main.py

import hello    # hello 모듈을 가져옴
 
print('main.py __name__:', __name__)    # __name__ 변수 출력

📝 실행결과

hello 모듈 시작
hello.py __name__: hello
hello 모듈 끝
main.py __name__: __main__

👉 실행을 해보면, hello.py 파일과, main.py파일의 __name__ 에 변수 값이 출력됩니다.

파이썬에서 import로 모듈을 가져오면, 해당 스크립트 파일이 한 번 실행이 됩니다.
위에 예시를 보면, hello모듈을 가져오면, hello.py안에 코드가 실행되고, 따라서, hello.py의 __name__ 변수에는 'hello'가 들어가고, main.py의 __name__ 변수에는 '__main__' 이 들어가는 것이고, 이를 출력으로 확인 할 수 있죠 ?

이런 상황입니다.

즉, __name__ = 모듈의 이름이 저장되는 변수이고

import로 모듈을 가져왔을 때, 모듈의 이름이 들어가는 것이죠.

"파이썬 인터프리터"로 스크립트 파일을 직접 실행했을 때도 (근데,,python도 스크립트 언어입니다.) 역시 같은 결과를 보입니다. 이것은, 콘솔(터미널, 명령프롬포트, cmd 다 같은말)에서 python으로 main.py을 실행한다고 해봅시다.

C:\project>python main.py
hello 모듈 시작
hello.py __name__: hello
hello 모듈 끝
main.py __name__: __main__

앞선, 스크립트파일 실행과 같이, hello.py 파일의 __name__ 변수의 'hello' 와 main.py 파일의 __name__ 변수의 '__main__' 이 들어가네요.

hello.py를 모듈로 가져왔을 때

하지만, 다음과 같이 python으로 이번에는, main.py가 아닌 !,  hello.py 파일을 실행해보면, 결과가 조금 다릅니다.

C:\project>python hello.py
hello 모듈 시작
hello.py __name__: __main__		// 이 부분
hello 모듈 끝

hello.py를 단독으로 실행했을 경우

이번에는, hello.py의 __name__ 의 변수값에 앞선 예시와 같은 'hello'가 아닌
모듈의 이름이 아니라( 즉, __name__ 이 아니라 ) __main__ 이 들어갑니다 ! 

즉, 어떤 스크립트파일이든, 파이썬 인터프리터가 최초로 실행한 스크립트 파일의 __name__ 변수에는 '__main__' 이 들어가는 것이죠. 이는 프로그램의 "시작점(entry point)"이라는 뜻입니다.

파이썬은 최초로 시작하는 스크립트 파일과 모듈의 차이가 없습니다.
어떤 스크립트 파일이든, 시작점이 될 수 있고, 모듈도 될 수 있는 것입니다.
그래서 __name__ 변수를 통해 현재 스크립트파일이 시작점인지 ? 모듈인지 ? 판단하는 것입니다.

계속 언급하고 있는,

if __name__ == '__main__' :

처럼 __name__ 변수의 값이 '__main__' 인지 확인하는 코드는 현재 스크립트파일이 프로그램의 시작점이 맞는지 판단하는 작업인 것입니다.

즉, 스크립트파일이 메인 프로그램으로 사용될 때와, 모듈로 사용될 때를 구분하기 위한 용도라 생각하면 됩니다.

 

📢 스크립트파일로 사용한 경우 vs 모듈로 사용한 경우

마지막으로, 그럼, python파일을 스크립트파일로 사용한 경우와 모듈로 사용한 경우의 예를 보고 마무리 합시다.

  • 스크립트파일로 실행한 경우

📝 calc.py

def add(a, b):
    return a + b
 
def mul(a, b):
    return a * b
 
if __name__ == '__main__':    # 프로그램의 시작점일 때만 아래 코드 실행
    print(add(10, 20))
    print(mul(10, 20))

📝 실행결과

// IDE에서 실행한 경우
30
200
====================================
// 명령프롬포트(cmd)에서 실행한 경우
C:\project>python calc.py
30
200

IDE에서 실행하거나, 명령프롬포트같은 파이썬 인터프리터로 실행하면 10,20의 합과 곱이 출력됩니다.

즉, "프로그램의 시작점" 일 떄는, if __name__ == '__main__' : 아래의 코드가 실행이 되는 것이죠.
( 이 예시에서는, print(add(10,20)) , print(mul(10,20)) 이 두 줄의 코드가 실행이 되는 것이죠. )

  • 모듈로 사용한 경우
>>> import calc
>>> 

모듈로 가져왔을 때는, 아무것도 출력이 되지는 않죠 ? 왜냐면 __name__ 변수의 값이 '__main__' 일 떄만, 10,20의 합과 곱을 출력하도록 만들었기 떄문입니다.

즉, 스크립트파일을 모듈로 사용할 때는, calc.add, calc.mul 처럼 "함수만 사용하는 것이 목적" 이므로, 10,20의 합과 곱을 출력하는 코드는 필요가 없습니다.

이럴때는, 위에처럼, 먼저 사용할 모듈을, import시킨다음, 다음과 같이 calc.add와 calc.mul 함수에 원하는 값을 넣어서 사용하면 됩니다.

>>> calc.add(50, 60)
110
>>> calc.mul(50, 60)
3000

 

📢 참고

  • 파이썬은 왜 프로그램의 시작점이 정해져 있지 않나요 ?
    ( C를 예로들면, int main(void) { } 같은 시작점이 있는데.. )

👉 파이썬이 처음에 개발 될 당시에는 리눅스(Linux/Unix)에서 사용하는 "스크립트언어" 기반이었기 떄문에, 프로그램의 시작점이 따로 정해져 있지 않았다고 합니다.
보통 리눅스/유닉스의 스크립트파일은 파일 한 개로 이루어진 경우가 많은데요.스크립트 파일 자체가 "하나의 프로그램" 이다 보니, 시작점이 따로 필요하지 않았다고 합니다.
하지만, 앞서말한 "C언어", "자바(Java)" 같은 프로그래밍언어는 처음 만들어질 때부터, 소스 파일을 여러 개 사용했기 때문에 여러 소스 파일의 함수들 중에서도 시작함수(main)을 따로 정해 놓은 것입니다.

 

📢 마무리

이렇게, "파이썬" = "스크립트언어" 이고, 이러한 스크립트언어의 특성 때문에, 전에 본인이 , C,Java 같은 언어로만 프로그래밍을 하고 있었다면, 오늘 정리한, 내용이 낯선 부분이 분명히 있을 것입니다.

아무 이유없이, 처음 파이썬을 프로그래밍언어로  사용해서, 잘 알고 있거나, 애초에 이런 스크립트언어의 특징을 이미 잘 알고 있던 사람이라면, 당연히 알고 있는 내용일 수 있지만, 한번 쯤은, 정리를 해야할 내용인 것 같습니다.

오늘 내용의 저의 생각을 정리하자면, 간단하게..

  • 파이썬 코드도 역시, 하나의 파이썬 파일 안에서도, "메소드" 나 "클래스" 등을, 작은 기능이여도 분리시키고,
    if __name__ == '__main__' : 을 통해서, 호출해서 사용하는 방식의 코드 구현을 지향하자.
  • 파이썬 프로그램도 역시, "스크립트파일을 실행하는 방식"과, 필요한 모듈의 기능만 가져와 쓰도록하는 "모듈을 import 해서 사용하는 방식" 이 있다는 것을 알고, 이 둘의 사용법의 차이를 알자.

이렇게 되는것 같습니다. 감사합니다. 🙂

728x90
반응형

📢 sort( )

파이썬으로 알고리즘문제를 풀다보면, 여러 조건으로 sort(정렬)해야하는 경우가 있습니다.

일반적으로, 파이썬에서 sort 하는 방법은

  • .sort( )
  • sorted( )

이렇게, 2가지 방식을 사용할 수 있습니다.

 

📢 정리

  • sorted(Iterator) 형태와 Iterator.sort( ) 방식은, 결과적으론 똑같이 정렬된다.
    따라서, 아래의 설명은 두 방식모두 동일한 방식으로 적용됩니다.
  • sorted( )의 key 인자로, 내가 커스텀할 비교함수를 보내주거나, lambda식을 적용해서 정렬기준을 정해주면 된다.
  • 비교함수는 비교할 아이템의 요소를 반환하면 됩니다.
  • 비교할 아이템의 요소가 복수 개일 경우, 튜플로 그 순서를 내보내주면 됩니다.
    • Ex) sorted( Iterator, key = lambda x : ( x[0], x[1] ) )
    • - 를 요소앞에 붙이면, 현재 정렬방식과 반대로 정렬하게 됩니다.
  • Iterator.sort(reverse=True) 를 설정하면, 내림차순으로 정렬을 합니다. (default는 reverse=Fasle, 즉, 오름차순 )
728x90
반응형

📢 개요

HTML/CSS/JavaScript(Js)

오늘날의 HTML, CSS, JavaScript(JS)는 "웹사이트", 즉 브라우저에서 동작하는 소프트웨어에만 국한되어 있지 않습니다. 

React Native나 Native Script처럼 혹은, 비슷한 변형들로, "모바일 앱"을 만드는 기술들이 이미 널리 사용되고 있습니다.

Electron.js 같은걸로 이젠, 웹사이트가 아닌, "컴퓨터 프로그램"까지 HTML/CSS/JS로 만들 수 있게 되었습니다. 😮

 

📢 HTML/ CSS / JavaScript

사실상, HTML(Hyper Text MarkUp Language) , CSS(Cascading Style Sheets)는 사실 프로그래밍언어에도 속하지 못합니다..

  • HTML은 "마크업(Markup)"언어입니다.

    👉 화면에 "어떤 요소들이 놓여 있어라 !" 하고 갖다놓는 수단

  • CSS는

    👉 HTML을 통해 띄어놓은 요소들이, "이렇모양, 저런 색 등으로 보여라 !"하고 정해주는 수단

  • JavaScript만이 그나마(?) 프로그래밍언어 속합니다. 

    👉 원래는 브라우저에서 웹사이트를 돌리는 목적으로 만듦, 그래서 그닥 대우를 못받는 언어였습니다.
    👉 그러나, 계속 발전을 하고, 특히 Node.js가 이것을 브라우저 바깥 세상으로 꺼내오면서, 위상이 아주 높아졌다.
    👉 웹사이트에서 돌아가는 JS는 브라우저에서 다양한 일을 수행하고, HTML로 올려놓은 요소들을 변형시키거나, 직접 만들어내기까지 합니다. !! 😮

📝 HTML / CSS / JavaScript 문서들이 합쳐져서, 하나의 웹페이지가 구동한다면,

  • HTML = "갖다놓고"
  • CSS = "꾸미고"
  • JavaScript = "시킨다."

라고 생각합시다. 

 

📢 마무리

HTML / CSS 는 배우는 건 쉽지만, 숙달이 되려면 시간이 좀 필요합니다.

같은 구조와 모습도, 구현하는 방법이 다양한데, 어느쪽이 효율적이고, 여러 환경이나 기기에 유연하게 적용 가능한지는 많이 만들어보고, 직접 봐야 느낄 수 있습니다.

매우 유명한 사이트, 예를 들면, "네이버" 나 "다음", "구글" 같은 사이트가, 어떻게 구성되어 있는지, "크롬 개발자 도구 같은 툴들로 분석해보면, 좋은 방법론들을 많이 얻을 수 있습니다. 👍👍👍

오른쪽화면이 "크롬 개발자 툴 (F12) 누르면 된다.

자바스크립트는 현재도 빠르게 변화해가고 있는 언어이다 보니, "끊임없이" 공부할 것이 생긴다고 합니다. 😂

예전에는 대부분이 "JQuery" 라는 강력한 "라이브러리" 로 순수 자바스크립트보다 훨씬 편하고, 쉽게 코딩을 하곤 했는데, 요즘은, 자바스크립트 자체가 파워풀해지고, JQuery의 성능문제도 있어서,,,

프론트엔드 프레임워크 같은 새로운 개발 방식들이 나오면서 "JQuery를 더 이상 쓰지말아야한다." , "없애야 한다" 라는 말이 나오고 있다고 합니다. 🙄

프론트엔트 Framework 들 ( 순서대로, React, Angular, Vue.js )

입문자들은, 우선 "JavaScript"를 탄탄히 먼저 배워놓은 다음, 위에서 언급한 라이브러리나 프레임워크를 필요에 따라, 배워나가면 좋을 것입니다.

웹 사이트를 만들 때, 기억해야 할 것은, HTML,CSS,자바스크립트의 최신 기술들을 전부 공부해서 이용하려면 곤란하답니다. 😅

웹사이트는 어디까지나, 크롬(Chrome), 사파리(Safari), 파이어폭스, 익스플로러  같은, "웹 브라우저"에서 구동하는데, 이 브라우저들 중, 일부에서 최신 기술들을 지원하지 않거나, 혼자 이상하게 돌아가는 경우( 익스플로러..🤬 )가 있기 때문에, 사람들이 어떤 버전의, 어떤 브라우저를 얼마나 사용하고, 그것들이 지원하는 기능들은 어디까지인지

즉, 📝 "호환성"확인하고, 테스트해가면서, 개발하는 것이 중요합니다. 

 

 

미흡하거나, 잘못된 정보가 있다면, 문의해주세요. 🙏


 

728x90
반응형

📢 개요

어떤 회사가, 직원들을 해외 출장을 파견 시키게 됬습니다.
파견기간동안 머물 공간이 필요할 것 입니다.

방법은 크게 2가지가 있습니다.

  • 일터와 숙소로 쓸 가건물 하나 전체를 빌리는 것
  • 가성비가 꽤 좋은 초대형 호텔을 이용하는 것

이 둘은 각각의 장단점이 있습니다.

  • 가건물 전체를 빌리는 것

    [ 장점 ]
    👉 우리 팀만의 넓은 공간이 확보된다.
    👉 호텔보단 평단가가 싸다

    [ 단점 ]
    👉 건물 전체를 빌리다보니, 필요 이상의 공간까지 값을 치르는 것이 된다.
    👉 결과적으로 내야하는 총 금액이 클 것이다. ( 전기,수도, 등 건물 관리비 포함, 청소,빨래 등 개인 작업 필요 )
    👉 어쩌다 현지 파견자 규모가 커지면, 현재 공간이 부족하게 되면, 곤란하다.

  • 반면, 초대형 호텔을 이용하는 것

    [ 장점 ]
    👉 팀에게 딱 필요한 공간만 방을 빌릴 수 있다.
    👉 상황에 따라, 건물의 공간을 더 대여하거나, 취소 할수도 있다.
    👉 건물 관리도, 호텔 측에서 해주고, 잡일(빨래,청소) 서비스도 제공해도 된다. ( 돈을 더 낼 여유가 있다면.. )
    👉 결과적으로, 내 주요 업무에만 집중할 수 있게 될 것이다.

    [ 단점 ]
    👉 단, 여러 서비스를 신청해서 받으려고 할수록, 지불해야할 총 금액은, 건물 렌트보다 비싸질 것이다.
    👉 남이 관리하는 시설이다보니, 보안 측면에서 불안해 할 수도 있고, 업무에 맞는 커스터마이징한 건물보다 효율이 떨지는 부분도 있을 것이다.

결과적으로, 회사의 재정적 상황과, 업무의 효율에 맞는 선택을 해야 할 것이다.

 

📢 클라우드 컴퓨팅(Cloud Computing)

앞선 건물 렌트를 비유해서, 인터넷을 기반으로 서비스를 제공하는 제품을 개발할 때, 서버를 두는 방식은 2가지

  • 회사가 자사의 시설, 혹은 IDC(Internet Data Center)에 "자체적으로" 컴퓨터 서버를 두고 운용방식

    👉 온-프레미스(On-Premise) 방식

  • AWS, Azure, GCP, 네이버 클라우드 플랫폼같은 "대기업 브랜드" 들에서 제공 서버를 사용하는 운용 방식이

    👉 클라우드 컴퓨팅(Cloud Computing) = 클라우드(Cloud)

클라우드 (Cloud)

클라우드 컴퓨팅도 역시, 자사의 거대한 데이터센터에 서로 연결된 수~많은 컴퓨터들을 운용하고 있습니다.

다만, 전통적인 방식처럼, 사용자들에게 컴퓨터를 하나씩 통째로 배당하는 방식이 X
필요한 만큼 떼어서 제공합니다. ( ??? )

  • 컴퓨터를 어떻게 떼어서 제공한다는 것인가 ?

    = "가상 컴퓨팅(Virtual Computing)" 이란 기술을 이용하면, 물리적 컴퓨터 한 대에 "가상의" 컴퓨터 여러 대를 띄울 수 있습니다.

    👉 예로 들면, 윈도우(Windows)에 "우분투 리눅스"를 깔아 쓰는 것입니다.

    즉, 컴퓨터의 물리적 자원을, 필요에 따라 분할해서 쓸 수 있는 것입니다.

    사용자는 원격접속 프로그램을 이용해서, 마치 한 대를 쓰는 것처럼, 인터넷으로 연결된, 가상 컴퓨터를 사용하는 것

  • 컴퓨터 자원이 많지 않거나, 수시로 변화하는 회사나 기관, 혹은 개인에게, "클라우드"는 아주 매력적일 것입니다.

    👉 예로 들어, 세일 시즌이나, 이벤트 기간에만 유독, 접속량이 폭주하는 앱의 경우, 클라우드에서 그 때마다,
    자원을 늘려주거나 줄여줄 수 있습니다.

    = 시간이나 접속량에 따른 "종량제" 개념으로, 필요한 만큼만 쓰고, 돈을 지불하면 됩니다.

가상 컴퓨팅(Virtual Computing)

 

📢 클라우트 컴퓨팅의 장점

  • 하드웨어도 클라우드에서 알아서 관리해주니까 걱정할 필요 없고
  • 비용을 더 지불하면, 원래는 회사에서 자체적으로 해야 했던, DB, 자료백업, 스토리지, 자동화 등을 검증된 최고급 프로그래머들이 구현해 놓은 것을 서비스로 이용할 수 있습니다.
  • 결과적으로, 그러한 것들을 직접 개발하고 관리하는데 써야 했던, 시간적, 인적, 물적 비용을 회사의 주요 업무에만 집중할 수 있도록 할 수 있다보니, 시스템 엔지니어, DB전문가 같은 고급 인력들을 고용하는데, 부담이 큰, 중소기업이나 벤처에게는 굉장히 유용한 서비스 일 것입니다.
  • 물론, 규모가 작은 기업만 쓰는 것이 아닙니다. 글로벌하게, 대기업에서도 클라우드 시스템을 사용합니다.
  • 다만, 보안상의 이슈때문에, 대기업류의 회사들은, 온-프레미스 vs 클라우드 중에 이것저것 따져보고 사용합니다.

📢 클라우드 서비스의 분류

  하드웨어 가상서버 소프트웨어
IaaS (Infra as a Service) O X X
PaaS (Platform as a Service) O O X
SaaS (Software as a Service) O O O
  • IaaS (Infra as a Service)

    👉 서비스로 제공되는 "인프라" , 가상컴퓨터, 즉 하드웨어 자원의 일부를 떼어주는 것
    👉 클라우드에서는 하드웨어만 관리, 내가 직접 가상서버를 본체 사서 원도 깔고, 드라이버 다운받고, 프로그램 깔고 하듯이 운영하고 관리한다고, 생각하면 됩니다.

  • Paas (Platform as a Service)

    👉 플랫폼이 서비스로 제공됩니다.
    👉 하드웨어관리, 가상서버(가상컴퓨터) 또한 내가 신경 쓸 필요 없습니다. 클라우드에서 관리해줍니다.
    👉 내가 짠 코드를 압축해서, 업로드하거나 "깃(Git)"으로 전송하면, 클라우드에서 알아서 서버에 넣고 돌려준다.
    👉 이를, "배포" 한다고 합니다. = 난 코드만 짜면 되니깐, 정말 편합니다.

  • Saas (Software as a Service)

    👉 아예 다 만들어진 소프트웨어를 서비스로 제공하는 것입니다.
    👉 드랍박스,SNS,이메일,에버노트,구글닥스,온라인페이, "유트브" 등이 예 입니다.

 

📢 마무리

우리가, 어느정도 코딩을 배우고,

  • "이제 내가 리눅스(linux) 좀 만져볼 수 있을 것 같다 !"
  • "서버나 웹사이트 한 번 직접 만들어서 직접 세상에 온라인에 열어보고싶다 한다면 !"

앞서 언급한, "AWS(아마존 웹서비스)" , "GCP(구글 클라우드 플랫폼)", "Azure", "네이버 클라우드 플랫폼" 같은 주요 클라우드 업체들 모두 새 가입자에게 "1년간 IasS(외 다수) 무료 이용권"을 제공한다고 합니다. 😮

대기업 클라우드 플랫폼

작은 서비스를 운영하기엔 충분한 리소스를 제공해주는 것이니까요 !
서버 관리 말고, 서비스 개발에만 집중해보고 싶다면, "히로쿠(heroku)" 나 "넷리파이" 같은 PaaS 서비스도  좋으니 참고해보길 바랍니다.

이렇게, 소개한, "클라우드" 서비스 덕분에, 내가 서비스를 제공함에 있어서 신경써야할, 관리,배포 적인 면들을 일정부분 무료로 제공해주고 하는 시대에 우리가 살고 있으니깐요 !!

오로지 개발자는, "개발"에만 집중해서, 자신이 생각해놓았던 서비스가 있다면, 개발해보는것도 좋을 것 같습니다. 😀

 

 

미흡하거나, 잘못된 정보가 있다면 문의주세요. 🙏


 

728x90
반응형

'알쓸 IT 지식' 카테고리의 다른 글

[알쓸 IT] Angular, React, Vue  (3) 2021.01.11
[알쓸 IT] MVC 웹 프레임워크  (0) 2021.01.11
[알쓸 IT] Static Web ? Dynamic Web ?  (0) 2021.01.11
[알쓸 IT] HTML/CSS/JavaScript  (1) 2021.01.03
[알쓸 IT] Server란 무엇인가 ?  (0) 2021.01.03

📢 개요

우리는 웹사이트를 이용할때나, 게임 같은 것을 이용하려다가도 잘 돌아가지않거나, 끊겨버리거나하면 흔히...

" 서버에 문제가 있나 ? 서버 터진거 아냐 ? " 말한다.


또, 우리가 유트브나 네이버같은 서비스를 이용해서, 온갖 영상이나, 정보들을 볼 수 있죠 ?
근데, 이것이 원래, 내 컴퓨터에 있는 영상이나 정보인가요 ?

👉 NO !! 아니죠 ?

다른 어딘가에 !! 우리가 흔히, "서버" 라고 부르는 어떤 "컴퓨터" 에 들어가 있는 것이에요.
맞다 !! 서버도, "컴퓨터"이다.

사실, 서버란 "역할(Role)"의 개념을 말한다.

예를 들어, 이 글이 있는 현재 블로그에서 글을 쓰는 필자는 이 블로그의 "주인" 입니다.
반대로, 내가 A군의 블로그에 접속해서 이용하면, 그때의 필자는 그 블로그의 "손님"이죠.

또 다른 예로, "A씨네 김밥집"에서는 "A씨"가 그 김밥집의 "사장님" 이지만, "B씨네 김밥집"에서 밥을 먹으면
A씨는 그때는 "손님" 이 됩니다.

IT 쪽으로 돌아와서 생각을 해보면..

한 컴퓨터가 네트워크로 연결된 다른 하나 또는 그 이상의 컴퓨터들에게 무언가를 해주게 되면, 이를테면...

  • 저장된 글이나 사진같은 정보를 보여주거나
  • 그런 글이나 사진같은 정보를 업로드받아서 보관해주거나
  • 한 컴퓨터에서 메시지를 보내면, 상대방 컴퓨터에서 알림을 보내주거나
  • 위치와 목적지를 받아서, 가는 길 사이에, 소요시간 등을 계산해주거나
  • 여러명이 참여할 수 있는, 온라인 게임을 열어주거나

하면 !! 그 "serve" = "제공하다" 해주는 것이 바로, "서버(Server)" 입니다.
그리고, 그 서비스를 받는 컴퓨터가 "손님", 바로, "클라이언트(Client)" 입니다.

서비스 제공(서버)  - 서비스 요청 (클라이언트)

 

📢 서버(Server) - 클라이언트(Client)

앞선 설명에서의 핵심은...

서비스를 제공하는 역할 (컴퓨터)  👉  서버(Server)
서비스를 받아 사용하는 역할 (컴퓨터)  👉  클라이언트(Client)

이, "서버 - 클라이언트" 관계상대적이라고 생각할 수 있다.

예를 들어서, 한 맛집 앱을 담당하는 내 컴퓨터가 하나 있습니다.
이 내 컴퓨터는,  앱이 깔린 폰들에게 맛집들의 정보를 전송해줍니다.

👉 이 때, 내 컴퓨터는 폰들에게 맛집 정보를 전송(제공)해주니깐 👉 "서버(Server)" 이죠 ?

그런데, 이 맛집 정보를, 사용자의 특정 지리의 지리 정보가 필요할 때에는, 네이버 지도 서버같은 곳에서, 지리 정보를 받아와야하겠죠 ?

👉 이때 내 컴퓨터는, 네이버에서 지리 정보를 받아오니깐 👉 "클라이언트(Client)" 가 되겠죠 ?

서버-클라이언트 상대적인 예시

 

즉, 서버 - 클라이언트 역할은, 그 때마다, 서비스를 제공하는 쪽고, 받는 쪽이 누구냐에 따라 달라집니다.

흔히 우리가 알고 있는 "서버"라고 알고있는 컴퓨터들은 보통

👉 IDC(Internet Data Center) 라는 말 그대로, 인터넷 데이터 센터란 시설에 있습니다.

IDC(Internet Data Center

냉각장치와 함께 수많은 컴퓨터들이 쫙~박혀서 인터넷에 연결되어 있습니다.
대부분 서버용으로 특수제작한 컴퓨터들이지만, 어떤것들은 그냥 "똥컴.."도 있다고 합니다.

 

📢 마무리

그럼 !! 서버가 "역할을 맡은 컴퓨터" 이면, 우리집에 있는 컴퓨터도 서버가 될 수 있는 거 아닌가 ?

👉 맞다 !! 우리들의 개인 컴퓨터에도, 서버 역할을 하는 "소프트웨어를 깔고" "외부에서 특정 주소로 접속해올 수 있도록 설정"하면 (어렵다..😂) 전 세계 사람들이 이용할 수 있는, "웹 서버" 나 "게임 서버"로 만들 수 있습니다.

다만, 서버이다 보니깐, 컴퓨터를 계속 틀어놔야 되겠죠 ? 전기세도 많이 들고, 통신의 질이나, 컴퓨터 다운 가능성 등의 한계가 있기 떄문에, 보통은 IDC에 있는 특정 컴퓨터를 사용하거나, "AWS" 와 같은 "클라우드 컴퓨팅 서비스"를 사용합니다. 😃

🧵 클라우드 컴퓨팅이 궁금하다면 ??

 

[알쓸 IT] 클라우드 컴퓨팅(Cloud)

📢 개요 어떤 회사가, 직원들을 해외 출장을 파견 시키게 됬습니다. 파견기간동안 머물 공간이 필요할 것 입니다. 방법은 크게 2가지가 있습니다. 일터와 숙소로 쓸 가건물 하나 전체를 빌리는

youngminieo1005.tistory.com

 

 

 

미흡하거나, 잘못된 부분이 있으면 문의부탁드립니다. 🙏


 

728x90
반응형

2020 정보처리기사 실기 기출_SQL_용어정리.PDF
0.39MB

 

필요한 사람은 시험 보기 직전에 참고해서 합격하길 바랍니다. 🙏


 

 

728x90
반응형

📢  탐욕법

  • 탐욕법(Greedy Method) : 일반적인 알고리즘 설계 기법 가운데 하나

    👉 구성(Configuration) : 다양한 선택, 모음, 또는 찾아야 할 값들
    👉 목표(Objective) : 구성에 할당된 점수가 존재하며, 이를 최대화 또는 최소화해야 하는 상황

  • 탐욕적 선택 속성(Greedy-Choice Property)을 가진 문제에 적용할 경우 가장 잘 맞는다.

    👉 출발 구성으로부터 시작하여 지속적인 지역적 향상을 통해, 전체 최적해를 항상 찾을 수 있다.

  • 예시

    👉 잔돈 거스르기
    👉 부분 배낭 문제
    👉 최소신장트리

📢  잔돈 거스르기 문제

  • 구성

    👉 거슬야 할 금액 정보
    👉 종류 여러 개의 동전들

  • 목표

    👉 동전 수를 최소화

  • 탐욕해

    👉 가능하 항상 제일 큰 동전으로 거슬러준다.

    만약, 이 문제가 탐욕적 선택속성을 가졌다면 탐욕해는 최적해가 된다.

  • 예시

    👉 예시 1. 동전 종류가 32원, 8원, 1원 인 경우

    탐욕적 선택 속성 : 있음(O) = 왜냐면, 32원 이상의 금액은 32원을 빼고는 최소 수의 동전으로 만들 수가 없기 때문
    ( 8원을 넘지만 32원에 못 미치는 금액에 대해서도 마찬가지 )

    👉 예시 2. 동전 종류가 30원, 20원, 5원, 1원인 경우

    탐욕적 선택 속성 : 없음(X) = 왜냐면, 40원은 두 개의 20원만으로 만들 수 있으나, 탐욕해는 세 개의 동전을 택하기 때문이다. ( 3개의 동전 = 30원 + 5원 + 5원 )

 

📢  부분적 배낭 문제

  • 구성 : N 항목의 집합 S = 각 항목 i는 다음을 가진다.

    👉 b(i) : 양수의 이득
    👉 v(i) : 양수의 부피

  • 목표

    👉 최대 부피 한도 V 내에서, 최대의 총 이득을 주는 항목들을 선택한다.

  • 부분적 배낭 문제(The Fractional Knapsack Problem) : 각 항목의 일부만을 취할 수 있는 문제

    👉 x(i)가 항목 i를 덜어 담는 양을 표시한다고 하면
    👉 목표 : (i∈S) ∑ b(i) ( x(i) / v(i) )를 최대화
    👉 제약 : (i∈S) ∑ x(i) ≤ V

  • 예시

    👉 구성 : n 항목의 집합 S = 각 항목 i는 다음을 가진다.

    b(i) : 양수의 이득
    v(i) : 양수의 부피

    👉 목표 : 최대 부피 한도 V 내에서, 최대의 총 이득을 주는 항목들을 선택
항목 A C D E 탐욕해(전체배낭 10ml)
이득 32 15 27 5 4 B ( 3ml )
부피 8ml 3ml 9ml 5ml 2ml A ( 7ml )
가치 (ml 당) 4 5 3 1 2 총이득 = 43 ml
  • 설명 : 각 항목의 최소단위인 1ml당 가치를 봤을 때, 우선적으로 가치가 높은 B부터 3ml을 다 담고, 나머지 A 전체 8ml 에서 7ml을 담은 것이 가장 최적의 이득을 취할 수 있다.
    이것이 가능한 이유는, 부분적으로, 항목을 나눌 수 있기 때문이다.

📢  0-1 배낭 문제

  • 0-1 배낭 문제 (또는 all-or-nothing knapsack problem) : 각 항목의 일부만을 취할 수는 없는 문제
  • 0-1 배낭 문제는 탐욕적 선택 속성을 만족하지 않는다.
  • 예 : 최적해는 이득 36을 가져다 주는 { A,E }지만, 탐욕해는 이득 = 24를 가져다 주는 { B,E,D }를 고른다.
항목 A C D E 탐욕해(전체배낭 10kg)
이득 32 15 27 5 4 B ( 3kg )
무게 8kg 3kg 9kg 5kg 2kg E ( 2kg )
가치 (kg 당) 4 5 3 1 2 D ( 5kg )
            총 이득 = 24 kg

 

728x90
반응형

📢  최단경로

  • 최단경로 문제(Shortest Path Problem)

    👉가중그래프와 두 개의 정점 u와 v가 주어졌을 때, u와 v사이의 무게의 합이 최소인 경로를 구하는 문제

  • 최단경로길이 : 간선들의 무게 합
  • 응용분야

    👉 인터넷 패킷 라우팅, 항공편 예약, 자동차 네비게이션 등등

 

📢  최단경로 속성

  • 속성 1

    👉 최단경로 부분경로(Subpath)역시 최단경로이다.

  • 속성 2

    👉 출발정점으로부터 다른 모든 정점에 이르는 최단경로들의 트리가 존재한다.
    = 단일점 최단경로(Single-Source Shortest Paths)
  • 최단경로는 최소신장트리와 달리

    👉 무방향뿐만 아니라 방향그래프에도 정의된다.
    👉 그래프에 음의 무게를 가진 싸이클이 있거나, 무방향그래프에 음의 무게를 가진 간선이 있으면 부정한다.
    👉 최단경로트리(Shortest Path Tree)는 루트트리

  • 가중 방향그래프에 음의 무게를 가진 싸이클이 존재

    👉 최단경로는 존재하지 X

  • 가중 무방향그래프에 음의 무게를 가진 간선이 존재

    👉 최단경로는 존재하지 않는다.

  • 최단경로 알고리즘
그래프 알고리즘 시간
음이 없는 무게를 가진
간선이 없는 그래프
Dijkstra(다익스트라) O(Mlog(N)) or O(N^2)
음의 무게를 가진
간선이 있는 방향그래프
Bellman-Ford(벨만-포드)(BFS에 속함) O(NM)
비가중그래프 BFS O(N + M)
DAG ( 방향 비싸이클 그래프) Topological Ordering(위상정렬) O(N + M)

 

📢  Dijkstra 알고리즘

  • 정점 s로부터 정점 v의 거리 : s와 v사이의 최단경로의 길이
  • Dijkstra 알고리즘은 출발정점 s로부터 다른 모든 정점까지의 거리를 계산한다.
  • 전제

    👉 그래프가 연결되있다.
    👉 간선들은 무방향이다.
    👉 간선의 무게는 음수가 아니다.

  • 정점 s로부터 시작하여 정점들을 차례로 배낭에 넣다가 결국엔 모든 정점을 배낭에 넣는다.
  • 각 정점 v에 거리 라벨 d(v)를 저장하여 배낭과 인접 정점들을 구성하는 부그래프에서 s로부터 v까지의 거리를 표현
  • 반복의 각 회전에선

    👉 배낭 밖의 정점 가운데 거리 라벨 d가 최소인 정점 u를 배낭에 넣는다.
    👉 u에 인접한 정점들의 라벨을 갱신한다.
  • 결과적으로, 최소신장트리의 Prim-Jarnik알고리즘과 매우 흡사한 것을 느낄 수 있다.
Alg DijkstraShortestPaths(G,s)
	input a simple undirected weighted graph G with nonnegative edge weights, vertex s of G
    ouput lable d(u), for each vertex u of G, s.t. d(u) is the distance from s to u in G

for each ∈ G.vertexs()	
    d(v) <- ∞					// 모든 정점의 거리는 0

d(s) <- 0						// 시작 정점 s의 거리는 0
Q <- a priority queue containing all the vertexs of G using d labels as keys

while(!(Q.isEmpty())
    u <- Q.removeMin()			// 힙으로 구현한, Q 에서, 최소힙의 루트키를 반환해서, 최소 값 정점 u를 반환
    for each e ∈ G.incidentEdges(u)	// u에 부착된 간선들 전부에 대해
        z <- G.opposite(u,e)			// z는 정점 u와 부착된 간선을 통한 반대편 정점
        if(z ∈ Q.elements())			// 그 정점 z가 아직 Q에 존재하는, 즉, 아직 배낭에 들어가지 못한 정점이면
            if(d(u) + w(u,z) < d(z))		// 간선완화진행 ( 기존의 정점 z의 distance보다 > 앞선 u정점과 이어진 간선 (u,z)의 distance의 합이 더 작으면 
                d(z) <- d(u) + w(u,z)		// d(z) 업데이트
                Q.replaceKey(z,d(z))		// 그리고, z정점의 가중치가 업데이트 됬으면, 전체, Q 구조 업데이트

 

  •  추가설명

    👉 배낭(Sack) : 가상이므로, 구현하지 않음 !!
    👉 우선순위 큐가, 배낭 밖의 정점들을 보관한다. = ( 키(distance)-원소(vertex) )
    👉 각 정점 v에 두 개의 라벨을 저장 = ( 거리( distance ) : d(v) , 부모 정점( parent ) : p(v) )

 

📢  간선완화

  • 간선 e = (u,z)에 대해 고려한다.

    👉 u는 가장 최근에 배낭에 들어간 정점
    👉 z는 배낭 밖에 존재하는 정점
  • 간선 e의 완화(relaxation)를 통해 거리 d(z)를 갱신한다. 즉,

    👉 d(z) <- min( d(z) , d(u) + w(u,z) )

간선 완화(edge relaxation) 예시

 

Dijkstra 알고리즘 예시 ( A부터 시작해서, 배낭에 추가되는 것, 동시에 주변 정점에 써있는 distance의 변화를 유의 )

 

  •  알고리즘 분석

    👉 우선순위 큐의 구현에, 두 가지 선택 가능

    1. 힙 구현
    2. 무순리스트 구현

  • 에 기초한 우선순위 큐를 사용할 경우

    각 정점은 우선순위 에 한번 삽입, 한번 삭제되며, 각각의 삽입과 삭제에 = O(log(N)) 시간 소요
    우선순위 큐 내의 정점 z의 키는 최대 deg(z)번 갱신되며 각각의 키 갱신에 = O(log(N)) 시간 소요

    👉 그래프 G가 인접리스트 구조로 표현된 경우, Dijkstra 알고리즘 = O((N+M)log(N)) 시간에 수행
    👉 그래프가 연결되어 있으므로, 실행시간 = O(Mlong(N)) 표현 가능
    👉 그래프가 단순하다고 전제하므로 = (최악의 경우) O(N^2log(N))

  • 무순리스트에 기초한 우선순위 큐를 사용할 경우

    각 정점은 우선순위 큐에 한번 삽입, 한번 삭제되며, 삽입과 삭제에 = 삽입( O(1) ), 삭제( O(N) ) 시간 소요
    우선순위 큐 내의 정점 z의 키는 최대 deg(z)번 갱신되며 각각의 키 갱신에 O(1) 시간 소요

    👉 그래프가 인접리스트 구조로 표현된 경우, Dijkstra 알고리즘 = O(N^2 + M) 시간에 수행
    👉 그래프가 단순하다고 전제하므로 = O(N^2)로 단순화 가능

  • 결과적으로, 두 가지 우선순위 큐 구현 비교 ( 힙 vs 무순리스트 )

    👉 힙으로 구현하면 = O(Mlog(N)) 시간 소요
    👉 무순리스트로 구현하면 = O(N^2) 시간 소요

    👉 두 구현 모두 : 코딩하기 쉽고, 상수적 요소로 보면 비슷하다.
    👉 (최악의 경우만을) 생각하면, 다음과 같은 선택지가 있다.

    1. 희소그래프( 즉, M < (N^2)/log(N) )에 대해서는 힙 구현이 유리
    2. 밀집그래프( 즉, M > (N^2)/log(N) )에 대해서는 구현이 유리

 

📢  Bellman-Ford 알고리즘

  • 음의 무게를 가진 간선이 있더라도 작동한다.
  • 방향간선으로 전제한다 = If ) 그렇지 않으면, 음의 무게를 가진 싸이클이 있게 되기 때문이다.
  • i - 번째 회전 시에 i 개의 간선을 사용하는 최단경로를 찾는다.
  • 실행시간 : O(NM)
  • BFS에 기초한다. = 음의 무게를 가지는 싸이클이 있는 경우, 이를 발견 가능하다.
  • 인접정보를 사용하지 않으므로, 간선리스트 구조 그래프에서 수행 가능하다.
Alg Bellman-FordShortestPaths(G,s)
	input a weighted digraph G with n vertexs, and a vertex s of G
    output label d(u), for each vertex u of G, s.t. d(u) is the distance from s to u in G

// 그래프 내의 모든 정점 distance = ∞
for each v ∈ G.vertexs()
    d(v) <- ∞
    
d(s) <- 0						// 시작 정점 s에 distance = 0
for i <- 1 to n - 1		
    for each e ∈ G.edges()			// 그래프 내의 모든 간선으로 부터
        // 간선완화
        u <- G.Origin(e)			// u는 간선 e에 저장된 origin(시작) 정점 
        z <- G.opposite(u,e)			// z는 정점 u와 간선 e로 부터 이어지는 반대편 정점
        d(z) <- min(d(z),d(u) + w(u,z))	// 현재 정점 z의 distance > u정점까지 거쳐 + u와 z정점으로 이어지는 간선 e의 거리의 합 중에 작은 것을 z의 거리로 업데이트

Bellman-Ford 알고리즘 예시 ( BFS 특징 : 한 칸식 늘려가면서 업데이트 하는 느낌 유의 )

 

📢  모든 쌍 최단경로

  • 모든 쌍 최단경로(all-pair shortest paths) 문제 : 가중 방향그래프 G의 모든 정점쌍 간의 거리를 찾는 문제
  • 그래프에 음의 무게를 가진 간선이 없다면, Dijkstra 알고리즘 N번 호출할 수도 있다. = O(NMlog(N))
  • 그래프에 음의 무게를 가진 간선이 있다면, Bellman-Ford 알고리즘 N번 호출할 수도 있다 = O((N^2)M)
  • 대안

    👉 동적프로그래밍(Dynamic Programming)을 사용 = O(N^3) 시간에 수행 가능하다.
    ( Floyed-Warshall 알고리즘과 유사한 방식으로 수행한다. )

Alg allPairsShortestPaths(G)
	input a simple weighted digraph G without negative-weight cycle	// 음의 가중치 싸이클 그래프
    output a numbering V1,V2,....,Vn of the vertexs of G and a matrix D 
    (s.t D[i,j] = distance of Vi,Vj in G

Let V1,V2,.....,Vn be an arbitrary numbering of the vertexs of G

for i <-1 to n
    for j <- 1 to n
        if(i == j)
            D[i,j] <- 0			// 자기 자신 distacne = 0
        elseif((Vi,Vj) ∈ G.edges())
            D[i,j] <- w(Vi,Vj)
        else
            D[i,j] <- ∞

for k <- 1 to n
    for i <-1 to n
        for j <- 1 to n
            D[i,j] <- min( D[i,j], D[i,k] + D[k,j] )

동적프로그래밍 기법을 이용한 최단경로 수행 예시

728x90
반응형

'Algorithm Theory' 카테고리의 다른 글

탐욕법(Greedy Method)  (0) 2020.12.15
최소신장트리(Minimum Spanning Tree)  (0) 2020.12.15
동적프로그래밍(Dynamic Programming)  (0) 2020.12.14
방향 그래프(Directed graph)  (0) 2020.12.14
그래프 순회(Graph Traversal)  (0) 2020.12.14

📢  가중그래프

  • 가중그래프(Weighted Graph) : 각 간선이 무게(weight)라 부르는 수치값을 가지는 그래프
  • 무게가 될 수 있는 것들은 거리,비용,시간 등 다양하다.

가중그래프의 예시

 

📢  최소신장트리

  • 신장 부그래프(Spanning Subgraph) : 그래프 G의 모든 정점들을 포함하는 부그래프
  • 신장트리(Spanning Tree) : (자유)트리인 신장 부그래프
  • 최소신장트리(MST, Minimum Spanning Tree) : 가중그래프의 총 간선 무게가 최소인 신장트리
  • 응용분야

    👉 교통망, 통신망 등등

최소신장트리 예시 ( 파란색 경로가 추가될 경우 Cycle 생성됨 X )

  • 최소신장트리 속성

    👉 1. 싸이클속성
    👉 2. 분할 속성

    이 두개의 속성은 알고리즘의 정확성 검증에 이용한다.

 

📢  싸이클 속성

f를 e로 대체하면 더 좋은 신장트리를 얻는다.

  • 싸이클 속성

    👉 T를 가중그래프 G의 최소신장트리라 가정하자.
    👉 e를 T에 존재하지 않는 G의 간선으로, C를 e를 T에 추가하여 형성된 싸이클로 가정하자.
    👉 그러면 C의 모든 간선 f에 대해, weight(f) <= weight(e) 이다.

  • 증명

    👉 모순법 : 만약 weight(f) > weight(e)라면, f를 e로 대체함으로써 무게가 더 작은 신장트리를 얻을 수 있기 때문

 

📢  분할 속성

  • 분할 속성

    👉 G의 정점들을 두 개의 부분집합 U와 V로 분할한다고 하자.
    👉 e를 분할을 가로지르는 최소 무게의 간선이라고 하자.
    👉 간선 e를 포함하는 G의 최소신장트리가 반드리 존재한다.

  • 증명

    👉 T를 G의 MST라 하자.
    👉 만약 T가 e를 포함하지 않는다면, e를 T에 추가하여 형성된 싸이클 C를 구성하는 간선들 가운데 분할을
    가로지르는 간선 f가 존재할 것이다.
    👉 싸이클 속성에 의해, weight(f) <= weight(e)
    👉 그러므로, weight(f) == weight(e)
    👉 f를 e로 대체하면 또 하나의 MST를 얻을 수 있다.

 

📢  최소신장트리 알고리즘

  • 크게 3가지 알고리즘이 존재한다.

    👉 1. Prim-Jarnik 알고리즘 ( 많이 씀 )
    👉 2. Kruskal 알고리즘 ( 많이 씀 )
    👉 Baruvka 알고리즘 ( 1번 + 2번 느낌 )

 

📢  Prim-Jarnik 알고리즘

  • 탐욕(Greedy) 알고리즘의 일종
  • 대상 : 단순 연결 무방향 그래프
  • 아이디어

    👉 임의의 정점 s를 택하여, s로부터 시작해서, 정점들을 (가상의)배낭에 넣어가며 배낭 안에서 MST T를 키워 나감
    👉 s는 T의 루트(root)가 될 것이다.
    👉 각 정점 v에 라벨 d(v)를 정의 = d(v)는 배낭 안에 정점과 배낭 밖 정점을 연결하는 간선의 weight
    👉 반복의 각 회전에서
    : 배낭 밖 정점들 가운데 최소 d(z) 라벨을 가진 정점 z를 배낭에 넣고, z에 인접한 정점들의 라벨을 갱신한다.
Alg PrimJarnikMST(G)
	input a simple connected weighted graph G with n vertexs and m edges
    output an MST T for G
    
for each v ∈ G.vertexs()
    d(v) <- ∞		// 여기서, d(v)는 각 정점들의 거리
    p(v) <- ∅		// 여기서, p(v)는 각 정점들의 MST로 이뤄지기위한 직계 부모 정점 정보

s <- a vertex of G
d(s) <- 0
Q <- a priority queue containing all the vertexs of G using d labels as keys

while(!(Q.isEmpty())	// 우선순위 큐를 비울 때까지 반복인데, 반복 작업은, 배낭(MST)에 정정을 하나씩 넓혀가는 것
    u <- Q.removeMin()	// 우선순위 큐에 들어가있는, 가장 거리 d 가 작은 정점 반환 u
    for each e ∈ G.incidentEdges(u)	// 정점 u에 부착된 간선 전부를 본다.
        z <- G.opposite(u,e)	// 정점 u와 이어진 간선 e를 통한 반대편 정점을 z라 한다.
        if((z ∈ Q) & (w(u,z) < d(z)))	// 정점 z가 우선순위 큐에 있는 것이고, 즉 아직 방문 안한 정점이고, 정점 u를 거쳐 정점 z로 가는 거리가, 아직 현재 정점 z거리보다 적으면
            d(z) <- w(u,z)		// 정점 z의 거리를 업데이트한다.
            p(z) <- e		// 그리고, 정점 z의 부모간선을 e로 업데이트한다.
            Q.replaceKey(z,w(u,z))	// 이렇게, 정점 z의 거리(d)가 우선순위가 바꼈을 수도 있으니, 우선순위큐 재배치를 진행한다.
            

 

  • 추가설명

    👉 (가상의)배낭 밖의 정점들을 우선순위 큐에 저장 : 키(거리)-원소(정점정보)
    👉 각 정점 v에 세 개의 라벨을 저장한다.

    1. 거리(distance) : d(v)
    2. 위치자(locator) : 우선순위 큐에서의 v의 위치
    3. 부모(parent) : p(v), MST에서 v의 부모를 향한 간선

ㅌPrim-Jarnik 알고리즘 예시

  • 알고리즘 분석

    👉 라벨 작업 : 점정 z의 거리, 부모, 위치자 라벨을 O(deg(z))시간 읽고 쓴다. 라벨을 읽고 쓰는데 O(1)시간 소요
    👉 우선순위 큐( 힙으로 구현할 경우 ) 작업

    1. 각 정점은 우선순위 큐에 한번 삽입되고 한번 삭제 : 삽입과 삭제에 각각 O(log(N))시간 소요
    2. 우선순위 큐 내의 정점 w의 키는 최대 deg(w)번 변경 : 각 키 변경에 O(log(N))시간 소요 (힙 이니깐)

    👉 그래프가 인접리스트 구조로 표현되어 있다면, Prim-Jarnik 알고리즘은 O((N+M)log(N))시간에 수행한다.
    👉 단순 연결그래프에서 N = O(M)이므로, 총 실행시간 : O(Mlog(N))

 

📢 Kruskal 알고리즘

  • 탐욕(Greedy) 알고리즘
  • 알고리즘을 위한 초기 작업

    👉 모든 정점을 각각의 독자적인 (실제의)배낭에 넣는다.
    👉 배낭 밖 간선들을 우선순위 큐에 저장한다. = 키(무게)-원소(간선)
    👉 비어 있는 MST T를 초기화

  • 반복의 각 회전에서
    : 두 개의 다른 배낭 속에 양끝점을 가진 최소 무게의  간선을 MST T에 포함하고 두 배낭을 하나로 합친다.
  • 반복이 완료되면
    : MST T를 포함하는 한 개의 배낭만 남게 될 것이다.
Alg KruskalMST(G)
	input a simple connected weighted graph G with n vertexs and m edges
    output an MST T for G

for each v ∈ G.vertexs()
    define a Sack(v) <- {v}		// Sack은 배낭을 의미, 이것은 실제 구현에서는 Parent(v)로 제어하면 편하다.

Q <- a priority queue containnig all the edges of G using weights as keys
T <- ∅

while(T has fewer than n - 1 edges)
   (u,v) <- Q.removeMin()
   if(Sack(u) ≠ Sack(v))
       Add edge (u,v) to T
       Merge Sack(u) and Sack(v)

return T

아Kruskal 알고리즘 예시

  • 알고리즘 분석

    👉 우선순위 큐 초기화 작업

    힙을 사용하여 우선순위 큐 Q를 구현하면, 반복적인 삽입 방식에 의해서는 O(Mlog(M))시간에,
    상항식 힙 생성 방식에 의해서는 O(M) 시간에 Q 생성이 가능하다.

    👉 반복의 각 회전에서는

    최소 무게의 간선을 O(log(M))시간에  삭제 가능 = 여기서, G가 단순그래프이므로, O(log(M)) = O(log(N))
    각 배낭을 위한 분리집합을 리스트로 구현하면, find(u) ≠ find(v) 검사에 O(1) 시간 ( 또는 parent 배열을 이용 ! )
    두 개의 배낭 Sack(u), Sack(v)를 합치는데 O(min( |Sack(u)|, |Sack(v)| )) 시간 소요 ( 더 작은 배낭을 옮김 )

    👉 총 반복 회수 : (최악의 경우) M번
    👉 그러므로, Kruskal 알고리즘은 O((N + M)log(N)) 시간에 수행
    👉 G가 단순 연결그래프인 경우 N = O(M)이므로, 실행시간은 O(Mlog(N)) 이다.

 

📢  MST 알고리즘 비교

알고리즘 주요전략 수행시간 외부 데이터구조
Prim-Jarnik 탐욕 O(Mlog(N)) 정점들을 저장하기 위한 우선순위 큐
Kruskal 탐욕 O(Mlog(N)) 1. 간선들을 저장하기 위한 우선순위 큐
2. 배낭들을 구현하기 위한 분리집합(리스트로 구현가능)
or 각 정점에 대해 부모정점(Parent배열)배열을 이용하는 방법

 

728x90
반응형

'Algorithm Theory' 카테고리의 다른 글

탐욕법(Greedy Method)  (0) 2020.12.15
최단경로(Shortest Path)  (0) 2020.12.15
동적프로그래밍(Dynamic Programming)  (0) 2020.12.14
방향 그래프(Directed graph)  (0) 2020.12.14
그래프 순회(Graph Traversal)  (0) 2020.12.14

📢 동적프로그래밍

  • 동적프로래밍(DP, Dynamic Programming) : 알고리즘 설계의 일반적 기법 중 하나
  • 언뜻 보기에 많은 시간( 심지어 지수 시간 )이 소요될 것 같은 문제에 주로 적용한다.
  • 적용의 조건은 :

    👉 부문제 단순성(Simple Subproblems) : 부문제들이 j,k,l,m 등과 같은 몇 개의 변수로 정의 될 수 있는 경우
    👉 부문제 최적성(Optimality Subproblems) : 전체 최적치가 최적의 부문제들에 의해 정의될 수 있는 경우
    👉 부문제 중복성(Overlap Subproblems) : 부문제들이 독립적이 아니라 상호 겹쳐질 경우 ( 즉, 상향식으로 구축 )

  • 대표적 예시

    👉 피보나치 수(Fibonacci progression)에서 N-번째 수 찾기
    👉 그래프의 이행적폐쇄 계산하기

  • 동적프로그래밍 vs 분할통치법

    공통점

    👉 알고리즘 설계기법의 일종
    👉 문제공간 : 원점-목표점 구조 ( 원점 : 문제의 초기 또는 기초지점 / 목표점 : 최종해가 요구되는 지점 )

    차이점

    👉 문제해결 진행 방향

    동적프로그래밍(단방향) : 원점 -> 목표점
    분할통치법(양방향) : 목표점 -> 원점 -> 목표점 ( 단, 해를 구하기 위한 연산을 진행, 방향은 원점->목표점 )

    성능

    👉 동적프로그래밍 : 단방향 특성때문에 종종 효율적
    👉 분할통치법 : 분할 회수(보통 2분할을 한다.) , 중복연산 수행 회수에 따라 다름
  • 이름은 "동적"프로그래밍이지만, 실제로 우리가 아는 "동적", 그때그때 사용하는 그런 의미는 아니다.
    하나 구한 것은, 다를 때, 사용하는 의미일 뿐이고, 이러한 기법의 이름을 지은 사람이 그냥 "동적프로그래밍"이라 작명한 것 일 뿐이다. 오해하지말자.

📢  동적프로그래밍 예시

  • N-번째 피보나치 수 찾기 : 피보나치 수열(Fibonacci Progression)은 i = 0,1에 대해 f(i) = 1이며, i >= 2 에 대해
    f(i) = f(i-1) + f(i-2)인 수열이다.
  • 즉, f(0) = 1, f(1) = 1, f(2) = 2, f(3) = 3, f(4) = 5, f(5) = 8, .......
  • f(n), 즉 피보나치 수열의 n-번째 수를 찾기 위해, 정의로부터 직접 재귀알고리즘 f를 작성할 수도 있지만,
    불행히도 지수시간(exponential time)에 수행하므로 너무나 비효율적이다 !!
  • 이를, 동적프로그래밍에 기초하여 f(n)을 찾는 비재귀, 선형시간 알고리즘을 다음 두 버젼으로 작성해보자.

    👉 1. 선형공간으로 수행하는 버젼
    👉 2. 상수공간으로 수행하는 버젼
Alg f(n)		// 선형 공간

if(n == 0 || n == 1)
    return 1

A[0] <- 1
A[1] <- 1
for i <- 2 to n
    A[i] <- A[i-1] + A[i-2]

return A[n]

=============================

Alg f(n)		// 상수 공간

if(n == 0 || n == 1)
    return 1

a <- 1
b <- 1
for i <- 2 to n
    c <- a + b
    a <- b
    b <- c

return c

 

728x90
반응형

'Algorithm Theory' 카테고리의 다른 글

최단경로(Shortest Path)  (0) 2020.12.15
최소신장트리(Minimum Spanning Tree)  (0) 2020.12.15
방향 그래프(Directed graph)  (0) 2020.12.14
그래프 순회(Graph Traversal)  (0) 2020.12.14
그래프(Graph)  (0) 2020.12.13

+ Recent posts