전체 글
-
쿼드트리 (boj 1992)알고리즘 2020. 6. 5. 00:40
쿼드트리 문제는 Divide and conquer 를 활용하는 전형적인 문제입니다. 저의 경우에는 최초로 주어진 N을 size 로 두고, 반복문을 쭉 돌면서 다른 숫자가 있는지 찾아봅니다. 만약 다른 숫자가 발견되지 않고 모든 숫자가 같은 숫자라면 그 숫자로 압축이 가능합니다. (Best 케이스) 만약 다른 숫자가 발견된다면 이는 4등분해야하는 상황인 것이죠. 그렇다면 이들을 4등분한 지점을 left, top 으로 주고, size 를 절반으로 나눕니다. 그리고 위에서 했던 과정을 반복합니다. 코드 #include #include #include #include #include #define INF 987654321 int N; char map[70][70]; void DFS(int left, int to..
-
C/C++ setuid(2), setgid(2)C,C++ & Linux 2020. 6. 4. 02:21
함수 기능 사용자 ID와 그룹 ID 를 변경하는 함수입니다. setuid() 함수를 실행한 프로세스가 루트 권한을 갖고 있다면 Read User ID, Effective User ID, Saved User ID 모두를 uid 로 바꿉니다. 루트 권한은 갖고 있지 않으나 uid가 Real User ID 혹은 Saved User ID와 같다면 Effective User ID 만을 uid 로 바꿉니다. setgid() 함수는 그룹 아이디를 제어한다는 점만 다르고 setuid() 와 동일하게 동작합니다. 함수 원형 #include #include int setuid(uid_t uid); int setgid(gid_t gid); 매개변수 uid 새로운 uid gid 새로운 gid 반환값 성공 시 0 리턴 에러 시..
-
C/C++ wait3(2), wait4(2)C,C++ & Linux 2020. 6. 4. 01:51
함수 기능 자식 프로세스가 종료되는 것을 기다리며, 종료된 프로세스의 상태와 자원 사용량을 알려주는 함수입니다. 함수 원형 #include #include #include #include pid_t wait3(int *statloc, int options, struct rusage *rusage); pid_t wait4(pid_t pid, int *statloc, int options, struct rusage *rusage); 매개변수 statloc 자식 프로세스의 종료 상태를 나타내는 정보를 담아줍니다. 자세한 내용은 wait() 에 있습니다. options 프로세스의 종료 상태 체크 시 옵션을 걸 수 있습니다. wait() 참조 rusage 자식 프로세스의 리소스 사용량에 대한 정보가 담깁니다. p..
-
C/C++ execl(3), execv(3), execle(3), execve(2), execlp(3), execvp(3)C,C++ & Linux 2020. 6. 4. 01:43
함수 기능 현재 프로세스를 대신하여 새로운 프로세스를 실행하는 함수입니다. 함수 접미사 용도 l list 형태로 인자를 입력합니다. 인자의 끝을 0 으로 표시합니다. v vector 형태로 인자를 입력합니다. e 맨 마지막 인자로 환경 변수를 입력합니다. p 프로세스를 현재 디렉토리(pwd) 에서 찾습니다. exec() 함수는 입력 받은 경로가 '/'로 시작하지 않으면 환경 변수에서 파일을 찾습니다. 파일을 찾으면 실행 가능한 기계어 코드인지 판별하고, 그렇지 않으면 shell script 라고 판단하여 실행시킵니다. 함수 원형 #include int execl(const char *filepath, const char *arg0, ... /* (char *) 0 */); int execv(const c..
-
C/C++ waitid(2)C,C++ & Linux 2020. 6. 4. 00:43
함수 기능 프로세스의 종료 상태를 회수하는 함수입니다. waitpid 보다 유연한 함수이지만 그렇게 많이 쓰이지는 않는것 같습니다. 함수 원형 #include #include int waitid(idtype_t idtype, id_t id, siginfo_t *siginfop, int options); 매개변수 idtype id 의 역할이 idtype 에 따라 바뀝니다. options 용도 P_PID 특정 프로세스를 기다림 P_PGID 특정 프로세스 그룹에 속한 임의의 자식 프로세스를 기다림 P_ALL 임의의 자식 프로세스를 기다림 id 는 무시함 id idtype 에 맞추어서 pid 또는 pgid 를 적절하게 사용하면 됩니다. siginfop 자식 프로세스의 상태를 변화시킨 시그널에 대한 상세한 정보를..
-
C/C++ wait(2), waitpid(2)C,C++ & Linux 2020. 6. 4. 00:34함수 기능 자식 프로세스의 종료 상태를 회수하는 함수입니다. 부모 프로세스 입장에서는 자식 프로세스가 살아있는지 없는지 알 수 있는 방법이 없으므로 커널에서 시그널을 통해 부모 프로세스에게 알려줍니다. ( SIGCHLD 시그널 ) 함수 원형 #include #include pid_t wait(int *statloc); pid_t waitpid(pid_t pid, int *statloc, int options); 매개변수 pid wait 할 프로세스의 아이디 wait 의 경우 자식 프로세스 중 하나라도 종료된다면 리턴 -1 을 지정하면 wait()와 waitpid(-1) 은 동일한 기능을합니다. statloc 자식 프로세스의 종료 상태를 statloc에 담아줍니다. statloc 구조 statloc 에 사..
-
별 찍기 11 (boj 2448)알고리즘 2020. 6. 3. 22:04
별 찍기11 문제는 분할정복(Divide and conquer) 기법으로 문제를 해결할 수 있습니다. 삼각형 안에 작은 삼각형이 들어있는 꼴이기 때문입니다. 코드 #include #include #include #include #include #define INF 987654321 int N; char arr[5000][10000]; void drawTri(int y, int x) { sprintf(arr[y - 2] + x, " * "); sprintf(arr[y - 1] + x, " * * "); sprintf(arr[y] + x, "*****"); } void draw(int y, int x, int size) { if (size == 0) { drawTri(y, x); return; } int w..
-
트리의 높이와 너비 (boj 2250)알고리즘 2020. 6. 3. 17:52
트리의 높이와 너비 문제는 각 노드마다 자식 노드의 번호를 2개 주고, 이를 이진트리로 만든 뒤 DFS하는 문제에요 (Postorder search) 아래 코드를 보시면 children 배열에 자식노드를, parent 노드에 부모 노드를 저장하여 이진트리를 구성했어요. 그리고 빈 column 없이 트리를 구성해야한다는 점을 이용하면, 왼쪽 자식 서브 트리가 차지한 최대 column + 1 이 자기 자신의 노드 column index가 된다는 것을 알 수 있죠. 이후 오른쪽 자식노드의 maxIndex를 구하는 이유는 내 부모 노드의 위치를 결정해주어야 하기 때문이에요. DFS를 통해 재귀적으로 자식의 maxIndex 부터 알아가며 자기 자신의 위치를 결정하고, 그렇게 결정된 위치를 통해 레벨 별 최소 최대..