say2

RB: Red Black tree

-every node has 2, 3, or 4 childeren except leaves

모든 노드는 2~4개의 자식을 가진다 leaves제외.

- all leaves are at the bottom level of the tree

모든 leaves는 tree의 가장 bottom level에 있다.

EX)    

Insertion(top-down)

1)    Whenever insert encounter a 3-key node, the middle key is ejected and is placed in the parent node

insert가 3-key노드를 만날때마다 중간 키가 꺼내져서 parent노드로 간다

2)    If the root is a 3-key node, a new node is created

(To make sure there’s room for the new key in the left node.)

root가 3-key node일때 새 노드가 만들어진다

 Deletion(top-down)

1)    When remove encounters a 1-key node (except the root) it tries to steal a key from an adjacent sibling

만난 1-key node(root제외)를 제거할때 인접한 형제로부터 key를 가져온다.

2)    If no adjacent sibling has more than one key, the 1-key node steals a key from its parent The sibling is also absorbed

어떠한 인접한 형제노드도 key를 하나이상 가지고 있지 않다면 1-key node는 이것의 부모로부터 키를 하나 가져온다. 그리고 형제노드는 흡수된다

3)    If the parent is the root and contains only one key, and the sibling contains only one key, then the current and the sibling contains only one key, then the current 1-key node, its 1-key sibling, and the 1-key root are fused into one 3-key node that serves as the new root

만약 부모노드가 root이고 오직 하나의 키만 가지고 있으면서 형제노드가 오직 하나의 키만 가지고 있다면, 그래서 현재노드와 형제노드가 오직 하나의 키만가지고 잇으면 현재의 1-key node와 이것의 1-key 형제노드 그리고 1-key root는 3-key node의 root로 융합된다.

To make sure that a key can be removed from a leaf without leaving it empty.

키는 leaf로 부터 제거될 수 있어야 하며 빈채로 놔둘 수 없음을 명심!

(제거는 항상 leaf에서만 가능 즉, 삭제할 노드를 leaf로 밀어줘야함)

수업시간에 썼던 필긴데 이해가 잘 가지 않는다!

그래서 펌!

http://coyagi.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-234-%ED%8A%B8%EB%A6%AC

http://thesoul214.tistory.com/103

http://dol9.tistory.com/134

여기가 더 잘되있는듯

from subprocess import check_output

>>> int(check_output(["pidof","-s","movie_talk"]))

from pwn import *

elf = ELF('./a.out')
#rop = ROP(elf)
libc = ELF("/lib/i386-linux-gnu/libc.so.6")

printf_system_offset = libc.symbols['printf'] - libc.symbols['system']

printf_plt = elf.plt['printf']
printf_got = elf.got['printf']

write_plt = elf.plt['write']
write_got = elf.got['write']

libc_start_main = elf.plt['__libc_start_main']

진짜 강력한 것 같다.

import subprocess

subprocess.popen(args, bufsize=0, executable=None, stdin=None, stdout=None, stderr=None, preexec_fn=None, close_fds=False, shell=False, cwd=None,env=None, universal_newlines=False, startupinfo=None, creationflags=0)

개사기 args에 command가 들어갈 수 있는데 shell=True로 하면 문자열로 전달도 된다고 한다

args는 [argc,argv[0],,,,]이렇게 전달

args ['/bin/sh','-c',args[0],args[1]...] 일케도 가능

나머지 옵션들에 관한 reference

출처는 docs.python.org 이다

bufsize, if given, has the same meaning as the corresponding argument to the built-in open() function: 0 means unbuffered, 1 means line buffered, any other positive value means use a buffer of (approximately) that size. A negative bufsize means to use the system default, which usually means fully buffered. The default value for bufsize is 0 (unbuffered).

The executable argument specifies a replacement program to execute. It is very seldom needed. When shell=False, executable replaces the program to execute specified by args. However, the original args is still passed to the program. Most programs treat the program specified by args as the command name, which can then be different from the program actually executed. On Unix, the args name becomes the display name for the executable in utilities such as ps. If shell=True, on Unix the executable argument specifies a replacement shell for the default /bin/sh.

stdin, stdout and stderr specify the executed program’s standard input, standard output and standard error file handles, respectively. Valid values are PIPE, an existing file descriptor (a positive integer), an existing file object, and None. PIPE indicates that a new pipe to the child should be created. With the default settings of None, no redirection will occur; the child’s file handles will be inherited from the parent. Additionally, stderr can be STDOUT, which indicates that the stderr data from the child process should be captured into the same file handle as for stdout.

If preexec_fn is set to a callable object, this object will be called in the child process just before the child is executed. (Unix only)

If close_fds is true, all file descriptors except 0, 1 and 2 will be closed before the child process is executed. (Unix only). Or, on Windows, if close_fds is true then no handles will be inherited by the child process. Note that on Windows, you cannot set close_fds to true and also redirect the standard handles by setting stdin,stdout or stderr.

If cwd is not None, the child’s current directory will be changed to cwd before it is executed. Note that this directory is not considered when searching the executable, so you can’t specify the program’s path relative to cwd.

If env is not None, it must be a mapping that defines the environment variables for the new process; these are used instead of inheriting the current process’ environment, which is the default behavior.

If universal_newlines is True, the file objects stdout and stderr are opened as text files in universal newlines mode. Lines may be terminated by any of '\n', the Unix end-of-line convention, '\r', the old Macintosh convention or '\r\n', the Windows convention. All of these external representations are seen as '\n' by the Python program.

If given, startupinfo will be a STARTUPINFO object, which is passed to the underlying CreateProcess function. creationflags, if given, can be CREATE_NEW_CONSOLE orCREATE_NEW_PROCESS_GROUP. (Windows only)

출처 백준 온라인 저지 11404 번

5
14
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
3 5 10
3 1 8
1 4 2
5 1 7
3 4 2
5 2 4

0 2 3 1 4
12 0 15 2 5
8 5 0 1 1
10 7 13 0 3
7 4 10 6 0

#include<stdio.h>

int map[101][101];

int n, m;

int main(){

int i, j,a,b,c;

scanf("%d %d", &n, &m);

for (i = 0; i <= 100; i++){

for (j = 0; j <= 100; j++){

map[i][j] = 2100000000;

if (i == j)map[i][j] = 0;

}

}

for (i = 0; i < m; i++){

scanf("%d %d %d", &a, &b, &c);

if (map[a][b]>c)

map[a][b] = c;

}

for (int k = 1; k <= n; k++){

for (i = 1; i <= n; i++){

for (j = 1; j <= n; j++){

if (map[i][j] > map[i][k] + map[k][j]&&i!=j&&map[i][k]!=2100000000&&map[k][j]!=2100000000)

map[i][j] = map[i][k] + map[k][j];

}

}

}

for (i = 1; i <= n; i++){

for (j = 1; j <= n; j++){

if (map[i][j] == 2100000000)

printf("0 ");

else

printf("%d ", map[i][j]);

}

printf("\n");

}

return 0;

}

i->j까지의 비용과 i->k->j까지 비용을 비교해서 작은값을 i->j 값에 넣는다

n^3의 시간이 걸리고

모든 i j 에 대해서 최소비용을 구할 수 있다.

단 큰 배열크기가 필요함

c언어 관련 reference 사이트

www.cplusplus.com