#알고리즘의 정의

 

 알고리즘이라는 용어는 문제를 해결하기 위한 절차나 방법을 의미하는 단어로 넒은 범위에서 사용된다. 조금 더 정확한 의미를 따져보자면 알고리즘은 어떠한 행동을 하기 위해서 만들어진 명령어들의 유한 집합(finite set)이다. 


#알고리즘의 조건

 

 입력 

 알고리즘은 0 또는 그 이상의 외부에서 제공된 자료가 존재한다.

 출력 

 알고리즘은 최소 1개 이상의 결과를 가진다.

 명확성 

 알고리즘의 각 단계는 명확하여 애매함이 없어야 한다.

 유한성 

 알고리즘은 단계들을 유한한 횟수로 거친 후 문제가 해결되고 종료되어야 한다. 알고리즘의 한 단계 이후 m의 값은 n 보다 작으며, m!=0이면 n의 값은 다음 번 단계에서 줄어든다.

 효과성 

 알고리즘의 모든 연산들은 사람이 종이와 연필을 이용하여 유한한 시간 안에 정확하게 수행할 수 있을 정도로 충분히 단순해야 한다



#좋은 알고리즘


 알고리즘이 위의 조건들을 모두 만족한다면 문제를 풀 수 있다고 할 수 있지만, '효과적으로' 풀어낸다고 할 수는 없다. 위에서 말한 유한한 시간이 몇 달 혹은 몇 년이 될 수도 있기 때문이다. 따라서 우리는 알고리즘을 효율성으로 평가하게 되고, 컴퓨터에서는 시간과 메모리라는 두 자원을 얼마나 소모하는지가 효율성의 중점이 된다.


평가기준

-시간 복잡도(time complexity) : 얼마나 적은 시간안에 문제를 풀어 내는가

-공간 복잡도(space complexity) : 얼마나 적은 공간(메모리)을 활용해서 문제를 물어 내는가



#공부할 사이트



https://www.digitalculture.or.kr/koi/StudyOnline.do


공부할 사이트는 한국 정보 올림피아드 라는 사이트로



정보올림피아드 대회를 위한 

문제해결을 위한 창인적인 알고리즘 강좌들을 

두루 제공하는데

강좌 내용이 아주 고급지고 알맹이만 있어서

이미 C언어에 익숙하고 알고리즘을 조금 짜본 사람에게는

매우매우 효과적인 사이트이다.


강좌는 중급과 고급편이 각각 12편씩 총 24편으로 구성되어있다.

(편당 약 20분 정도)



중급에는 주로 여러가지 자료 탐색 알고리즘을 배우고





고급에서는 재귀함수의 확장, 동적 테이블 응용, 이분 탐색, 자료구조를 이용한 알고리즘 고속화 및 문제해결 등이 있다.


알고리즘을 깊숙히 배워볼 생각이 있으면 꼭 한번 쯤 듣고 따라 쳐봤으면좋겠다.





reference:https://namu.wiki/w/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98



WRITTEN BY
Who1sth1s

,

# 프로그래밍

 
-알고리즘 사이트  강의 따라가기
 
-C  printf 와 scanf 의 응용 ( 파싱 )
 
-C 언어 문자열 다루기 응용
등등

# 해킹

-치트엔진 사용법
 
-어셈블리어, 핸드레이 등등

# 각종 유용한 사이트

-수학 그래프 그려주는 사이트

-알고리즘 강의 사이트 ( 중급, 고급 )

 
-무료 효과음 구하는 사이트


# 잡다한 글들

해외연수, 여행 등등


# 공부한 내용


등등등

'공지' 카테고리의 다른 글

게시물 관련해서 질문할 때 ( 연락처 )  (0) 2015.11.25

WRITTEN BY
Who1sth1s

,

# 13년 3회 2급 D형



06 13년3회2급D형.xlsm


난이도가 다소 어려웠다.



WRITTEN BY
Who1sth1s

,

#팀소개


선린 인터넷 고등학교 1학년 전현성 외 RGs (, 유병훈)

- 전현성, 서준혁, 노영진, 조화윤, 유병훈



#팀원 역할분담


전현성 : 게임 기획 및 스토리, 디자인 설계, 게임 코딩

서준혁 : 기획서, ppt, 발표, 지갑

노영진 : 게임 구조 설계 및 코딩

조화윤 : 게임 전체 디자인

유병훈 : UI 및 기타 작업




#게임 소개 및 요약







#이상한 나라의 별주부전 시연 영상




(게임을 직접 플레이하면서 말로 게임을 설명해줌)

다운로드




#구현방법 (소스)


-2.5D 구현 <- 카메라를 돌리고 y스케일을 줄임

-FMOD를 사용한 사운드 재생

-엑셀을 이용하여 맵 에디트 및 맵 가져오기

-움직이는 블럭 -> 블럭 생성 (id, 속도) -> 타겟을 여러개 줌 -> 타겟과 닿으면 다음 타겟으로 이동 -> 마지막 타겟 -> 다시 처음 타겟으로 이동

-포탈 -> 포탈마다 id를 부여, 이동할 포탈의 id 입력 -> 포탈에 닿으면 -> 이동할 포탈의 위치로 이동





#느낀점

 이번 작품을 만들면서 협업이 힘들다는 것을 알음. 그럼에도 불구하고 효율적으로 협업. 마감시간에 딱 맞추지 말고 여유있게 미리 완성해 둬야겠다.







WRITTEN BY
Who1sth1s

,

안녕하세요. 블로그 관리자입니다.

참고로 관리자는 선린 인터넷 고등학교를 재학중인 1학년 Layer7 학생입니다.

게시물에서 종종 연락처를 요청 하셔서 연락처 남깁니다.

개인적으로 궁금하신점이나 이상한부분 있으면 언제든지 연락해도 됩니다.


# 카톡


 카톡에서 skyoun97로 검색 -> 전현성 -> 질문

 => 답장속도 빠름


# 이메일


 skyoun97@naver.com ,  skyoun97@gmail.com -> 질문

 => 답장속도 느림, 못 읽을 수도 있음.


# 블로그 댓글


 해당 게시물 -> 질문

 => 답장속도 느림, 못 읽을 수도 있음.





'공지' 카테고리의 다른 글

공지 :: 앞으로 포스팅할 내용  (0) 2015.11.25

WRITTEN BY
Who1sth1s

,


# [ 최단경로 찾기 ] by Python


 스타크래프트를 하다가 유닛이 어떻게 장애물을 피해 최단경로를 찾아서 갈까 궁금해 하다가 최단경로 찾는 방법을 검색하던 중 가중치 그래프를 이용한 다익스트라 알고리즘을 설명하는 글을 보고 그대로 한번 파이썬으로 짜봤다.


다익스트라(Dijkstra) 알고리즘




① 지도상의 모든 건물들과 집에서 각 건물들까지의 최단 거리를 나타내는 표를 만든다.
② 집과 직접 길로 이어진 건물들까지의 최단 거리는 지도에 표시된 값으로 적고 그렇지 않은 건물들은 빈 칸으로 놓아둔다. 여기서 빈 칸의 값은 무한대를 뜻한다.
③ 거리가 가장 짧은 건물부터 긴 건물 순으로 방문하고 방문한 건물은 색깔로 칠해 구별한다. 이때 방문한 경로도 색칠한다. 
④ 새로운 건물을 방문하면 그 건물과 이어진 건물들까지의 거리를 새로 바꾼다. 단, 이전에 이미 최단 거리가 구해졌었다면 거리를 서로 비교해 작은 것으로 바꾸거나 유지한다.
⑤ 그래프의 모든 건물들을 방문할 때까지 ③,④의 과정을 반복한다.



출처 : http://playsw.naver.com/repo/cast/105


#대략적인 알고리즘 과정




#자세한 알고리즘 설명(영어)




# 구현소스



+)설명추가


#최단경로 알고리즘
#reference : http://navercast.naver.com/contents.nhn?rid=2871&contents_id=85293
import copy

#목적지와 도착지를 설정해준다
departure = 'home'
destination = 'school'
print "-----------[", departure, "->", destination,"]----------"


#① 지도상의 모든 건물들과 집에서 각 건물들까지의 최단 거리를 나타내는 표를 만든다.

landscape = {
    'home':             {'hairShop':5, 'superMarket':10, 'EnglishAcademy':9},
    'hairShop' :        {'home':5 ,'superMarket':3, 'bank':11},
    'superMarket' :     {'hairShop':3, 'home':10, 'EnglishAcademy':7, 'restourant':3},
    'EnglishAcademy':   {'home':9, 'superMarket':7, 'school':12},
    'restourant' :      {'superMarket':3, 'bank':4},
    'bank' :            {'hairShop':11, 'restourant':4, 'EnglishAcademy':7, 'school':2},
    'school' :          {'bank':2, 'EnglishAcademy':12}
    }

routing = {}
for place in landscape.keys():
    routing[place]={'shortestDist':0, 'route':[], 'visited':0}

#④

def visitPlace(visit):
    routing[visit]['visited'] = 1
    for toGo, betweenDist in landscape[visit].items():
        toDist = routing[visit]['shortestDist'] + betweenDist
        if (routing[toGo]['shortestDist'] >= toDist) or  not routing[toGo]['route']:
            routing[toGo]['shortestDist'] = toDist
            routing[toGo]['route'] = copy.deepcopy(routing[visit]['route'])
            routing[toGo]['route'].append(visit)
            

#② 집과 직접 길로 이어진 건물들까지의 최단 거리는 지도에 표시된 값으로 적고 그렇지 않은 건물들은 빈 칸으로 놓아둔다. 여기서 빈 칸의 값은 무한대를 뜻한다.
            
visitPlace(departure)

"""
③ 거리가 가장 짧은 건물부터 긴 건물 순으로 방문하고 방문한 건물은 색깔로 칠해 구별한다. 이때 방문한 경로도 색칠한다. 
④ 새로운 건물을 방문하면 그 건물과 이어진 건물들까지의 거리를 새로 바꾼다. 단, 이전에 이미 최단 거리가 구해졌었다면 거리를 서로 비교해 작은 것으로 바꾸거나 유지한다.
⑤ 그래프의 모든 건물들을 방문할 때까지 ③,④의 과정을 반복한다.
"""
while 1 :
    #③
    minDist = max(routing.values(), key=lambda x:x['shortestDist'])['shortestDist']
    toVisit = ''
    for name, search in routing.items():
        if 0 < search['shortestDist'] <= minDist and not search['visited']:
            minDist = search['shortestDist']
            toVisit = name
    #⑤
    if toVisit == '':
        break
    #④
    visitPlace(toVisit)

    print "["+toVisit+"]"
    print "Dist :", minDist

print "\n", "[", departure, "->", destination,"]"
print "Route : ", routing[destination]['route']
print "ShortestDistance : ", routing[destination]['shortestDist']


맵은 한 곳에서 갈 수 있는 모든 지점과 거리를 dict로 나태냄.





# 실행결과


-INPUT



위 그림에서 집에서부터 학교까지의 최단거리를 구하는 것.

출발점 - 집
도착점 - 학교

departure = 'home'
destination = 'school'

-OUTPUT


>>> ================================ RESTART ================================
>>>
-----------[ home -> school ]----------
[hairShop]
Dist : 5
[superMarket]
Dist : 8
[EnglishAcademy]
Dist : 9
[restourant]
Dist : 11
[bank]
Dist : 15
[school]
Dist : 17

[ home -> school ]
Route :  ['home', 'hairShop', 'superMarket', 'restourant', 'bank']
ShortestDistance :  17



최단경로 알고리즘.py




# 과제

동영상 처럼 지하철 노선도를 가지고 최단 경로 찾기 만들기



'Script언어 > 파이썬' 카테고리의 다른 글

Python :: Simple CPU Emulator ver 0.1  (0) 2015.09.21

WRITTEN BY
Who1sth1s

,


# [ CPU Emulator ] by Python


 어셈블리어를 공부하다가 어셈블리어를 외부로부터 읽어서 txt파일로 출력하는 프로그램이다.

# 구현소스

import sys
readFile = open('homework_3.s', 'r')
writeFile = open('output.txt', 'w')
orig_stdout = sys.stdout
sys.stdout = writeFile

regi = {'%eax':0, '%ebx':0, '%ecx':0, '%edx':0, '%esi':0, '%edi':0,'%esp':0, '%ebp':0}
stack = []

def argToValue(arg):
    if (arg[0] == '%'):
        for k, v in regi.items():
            if (k == arg):
                return v
    if (arg[0:3] == "$0x"):
        return int(arg[1:],16)
    return int(arg[1:],10)

def movFunc(arg):
    regi[arg[1]] = argToValue(arg[0])
def subFunc(arg):
    regi[arg[1]] -= argToValue(arg[0])
def addFunc(arg):
    regi[arg[1]] += argToValue(arg[0])
def xorFunc(arg):
    regi[arg[1]] = argToValue(arg[0]) ^ argToValue(arg[1])
def pushFunc(arg):
    stack.append({argToValue('%esp'):argToValue(arg[0])})
    regi['%esp'] -= 4
def popFunc(arg):
    regi[arg[0]] = stack.pop().values()[0]
    regi['%esp'] += 4
def nopFunc(arg):
    pass
def retFunc(arg):
    pass

operator = dict( mov = movFunc, sub = subFunc, add = addFunc, xor = xorFunc, push = pushFunc, pop = popFunc, nop = nopFunc, ret = retFunc)

while 1:
    line = readFile.readline().replace(",","").split()
    if not line:
        break
    print "=========input========="
    print line
    operator[line[0]](line[1:])
    print "-------stack info------"
    for x in stack[::-1]:
        print x
    print "-----register info-----"
    for key, value in regi.items():
        print key, value

readFile.close()
writeFile.close()


sys.stdout = orig_stdout




# 실행결과


-INPUT


	mov	$1000, %esp
	push	%ebp
	mov	%esp, %ebp
	mov	$0, %eax
	mov	$0x0, %ebx
	xor	%esi, %esi
	xor	%edi, %edi
	xor	%ecx, %ecx
	mov	%ecx, %edx
        mov     $0x100, %eax
        mov     %eax, %ebx
        sub     $0x10, %ebx
        sub     $10, %ebx
	mov	%ebx, %edx
	push	%edx
	add	%edx, %edx
	push	%edx
	pop	%ebx
	xor	$0x10, %ebx
	mov	$0x200, %edx
	sub	$0x20, %edx
	add	%edx, %edx
	mov	$10, %eax
	sub	%eax, %edx		
	push	%edx
	pop	%ecx
        nop
	pop	%ebp
	ret

-OUTPUT


=========input=========
['mov', '$1000', '%esp']
-------stack info------
-----register info-----
%ebp 0
%eax 0
%edx 0
%edi 0
%esp 1000
%ebx 0
%esi 0
%ecx 0
=========input=========
['push', '%ebp']
-------stack info------
{1000: 0}
-----register info-----
%ebp 0
%eax 0
%edx 0
%edi 0
%esp 996
%ebx 0
%esi 0
%ecx 0
=========input=========
['mov', '%esp', '%ebp']
-------stack info------
{1000: 0}
-----register info-----
%ebp 996
%eax 0
%edx 0
%edi 0
%esp 996
%ebx 0
%esi 0
%ecx 0
=========input=========
['mov', '$0', '%eax']
-------stack info------
{1000: 0}
-----register info-----
%ebp 996
%eax 0
%edx 0
%edi 0
%esp 996
%ebx 0
%esi 0
%ecx 0
=========input=========
['mov', '$0x0', '%ebx']
-------stack info------
{1000: 0}
-----register info-----
%ebp 996
%eax 0
%edx 0
%edi 0
%esp 996
%ebx 0
%esi 0
%ecx 0
=========input=========
['xor', '%esi', '%esi']
-------stack info------
{1000: 0}
-----register info-----
%ebp 996
%eax 0
%edx 0
%edi 0
%esp 996
%ebx 0
%esi 0
%ecx 0
=========input=========
['xor', '%edi', '%edi']
-------stack info------
{1000: 0}
-----register info-----
%ebp 996
%eax 0
%edx 0
%edi 0
%esp 996
%ebx 0
%esi 0
%ecx 0
.........(생략)

cpu emulator.pyhomework_3.soutput.txt

WRITTEN BY
Who1sth1s

,

1. Linux 버전별  메모리 보호 기법




메모리 보호 기법

1. ASLR(Address Space Layout Randomization)

2. DEP / NX(Not Excutable)

3. ASCII-Armor

4. Canary




2. 메모리 보호 기법


1) ASLR(Address Space Layout Randomization)

주소공간을 랜덤하게 배치하는 기법이다. 스택, 힙 등 데이터 영역의 주소를 랜덤으로 프로세스 주소 공간에 배치함으로써 실행할 때 마다 데이터의 주소가 바껴 메모리를 보호하게 된다.







2) DEP / NX(Not Excutable)

주메모리를 보호하기 위해 코드가 Stack이나 Heap영역에서 실행할 수 없게 하는 기법이다. DEP가 적용된 상태에서는 BOF공격을 하여도 실행권한이 없어 프로그램에 대한 예외처리후 종료가 되어 메모리를 보호하게 된다.








3) ASCII-Armor

Libc 영역을 보호하기 위한 기법이다. 상위주소를 \x00으로 시작하게 만들어 공격자가 라이브러리를 호출하는 BOF공격을 하여도 NULL바이트가 삽입된 주소로 접근할 수 없게 됨으로 메모리를 보호하게 된다.





4) Canary


| BUFFER | SFP | RET |
위 처럼 되있는 메모리 구조가
             

| BUFFER | SFP | CANARY | RET  

이렇게 SFP와 RET 데이터 사이에 CANARY가 추가되어 스택의 BOF를 모니터링하는 기법이다. BOF가 발생하면 CANARY 데이터값의 변조로 오버플로우에 대한 경고를 하고 프로그램을 종료시킵니다. 

CANARY 데이터는 다음과 같이 구성되어 있다.

1.  Terminator canaries
문자열 끝문자를 이용하여 canary 를 구성하는 방법으로 
canary 값으로 NULL, CR, LF, Oxff 값의 조합이 사용됩니다. 
공격자는 공격시, 종료문자로 구성된 canary 값에 접근을 할 수 없게됩니다.

2.  Random canary
프로그램을 실행할 때마다 임의의 canary 값을 삽입을 합니다. 이에 따라 공격자는
Canary 값을 예측불가능하므로 공격에 어려움이 발생합니다.

3.  Null canary(0x00000000)
메모리상의 공격을 막기위해 canary 값을 NULL로 구성합니다. 
공격자는 공격코드상에 NULL 값을 삽입할 수 없으므고 canary 값에 접근이 불가능합니다.





참조:

http://justine100.tistory.com/15

http://younges.tistory.com/639



WRITTEN BY
Who1sth1s

,

1. 필요성

 

 보통 운영체제에서는 커널모드와 유저모드 두가지 프로세서 접근모드를 지원한다. 그 이유는 유저 어플리케이션이 함부로 운영체제의 치명적인 데이터를 수정하거나 삭제하지 못하게 하기 위해서 이다. 커널모드는 모든 시스템과 메모리에 접근이 허가된 프로세스 실행 모드이다. 유저모드보다 커널모드에 더 높은 권한을 줌으로써 유저모드에서 에러가 발생했을 때 시스템 전체의 안전성을 보장해 준다.



2. 구조


.

 .커널모드와 유저모드의 구조는 위와 같다. 사용자가 직접적으로 하드웨어 장치를 제어한다면 큰 문제 발생할 수 있기 때문에 사용자 애플리케이션은 System Call 을 통해 직접적인 하드웨어 요청이나 중요한 시스템 요청을 한다. 요청을 하면 유저 애플리케이션은 유저모드에서 커널모드로 잠시 전환 되었다가 커널모드에서 작업을 실행한뒤 응답을 유저 애플리케이션에 반환하면서 다시 유저모드로 되돌아가게 된다.





 

이러한 구조를 갖춤으로써 사용자 프로세스가 운영체제와 데이터를 함부로 들여다보거나 변경하지 못하게 보호한다.



3. 특징


유저모드

1. 사용자 애플리케이션의 코드가 실행 됨.

2. 시스템 데이터에 제한된 접근만이 허용, 하드웨어 직접 접근 불가.

3. 시스템 서비스 호출 시 유저모드에서 커널모드로 잠시 전환됨.

4. 스레드는 자신만의 유저모드 스택을 가짐.


커널모드

1. 모든 시스템 메모리에 접근할 수 있고 모든 CPU명령 실행 가능.

2. 운영체제 코드나 디바이스 드라이버 같은 커널모드 코드를 실행한다.



참고 : 

http://lapislazull.tistory.com/

http://www.scitech.co.kr/upload/book_image/s_402/ESDP-Ch06.PDF




WRITTEN BY
Who1sth1s

,


# [ Layer7 ] 해킹대회


선린인터넷 고등학교 대표 해킹 동아리인 Layer7 에서 해킹 대회를 진행합니다. 중고등학생이면 누구나 참여 가능하고 우승하면 상금도 주어지니 많은 참여 부탁 드립니다. (성인은 참여 가능하나 상금은 수여할 수 없습니다.)




대회 사이트 (신청) : http://ctf.layer7.kr/ 에서 Join us here 클릭

대회시간 8월 28일 오후 10시 ~ 8월 30일 오전 10시 (36시간)

참가자격 : 중학생, 고등학생 (성)

대회상금 : 비공개

페이스북 https://www.facebook.com/pages/Layer7/434666036568315






WRITTEN BY
Who1sth1s

,