Backjoon Online Judge 

"10216번 : Count Circle Groups" 문제입니다.


문제 링크 : https://www.acmicpc.net/problem/2667



문제 및 코드 설명입니다.


'10216번 : Count Circle Groups' 문제의 경우 모든 좌표쌍을 기준으로 그룹 여부를 판단해야 하는 문제로 조금 까다로울 수 있는 문제였습니다.

문제 풀이는 Union Find를 이용한다면 더 쉽고 빠르게 풀 수 있겠지만 DFS로 문제 분류가 되어있어 이번에는 DFS로 해결하였습니다.

(Union Find를 이용한 풀이도 추후 시도 할 예정입니다.)


먼저 적군의 진영을 저장하기 위한 벡터를 만들고 벡터에 4개의 정보(x,y,R,visit)를 저장하기 위해 pair를 이용하였습니다.


적군의 진영의 수는 N이므로 벡터의 첫번째부터 N번째까지 dfs 탐색을 진행했습니다.

이때 방문되지 않은 진영이라면 서로 다른 진영으로 분류하였고, 진영의 수(=group_num)을 더해주었습니다.

DFS는 위의 반복문에서 방문되지 않은 진영을 발견하였을 때 호출하였고, 그 진영으로부터 통신 가능한 진영을 모두 파악합니다.

DFS를 통해 현재 진영으로 부터 방문 될 수 있는 진영을 모두 파악하여 그 진영의 visit 값을 1로 설정합니다.

위 과정을 반복하여 N개의 진영을 모두 조사한다면 서로 다른 진영의 갯수를 출력하게 됩니다.


코드는 C++로 작성하였습니다.

 - pair문을 사용하면 (구버전)C++ 컴파일러에서 오류가 발생합니다. C++ 11 이상 컴파일러로 실행시 정상적으로 동작합니다.

 - 21번째 라인에서 i의 시작을 k+1로 설정하여 결과에 오류가 발생했습니다. 코드 작성 시 참고 하시면 좋을 듯 합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <vector>
#define Max 5001
 
using namespace std;
typedef pair<pair<int, int>, pair<int, int>> pair4;
 
int N, group_num;    //그룹 갯수
vector<pair4> enemy;    //순서대로 x, y, R, visit여부를 저장
 
//두 지점이 통신 가능한지를 비교 (가능하면 1)
int compare(int a, int b) {
    int r = enemy[a].second.first + enemy[b].second.first;
    int x = enemy[a].first.first - enemy[b].first.first;
    int y = enemy[a].first.second - enemy[b].first.second;
    return (((x * x) + (y * y)) <= (r * r)) ? true : false;
}
 
void dfs(int k) {
    //(mistake)양방향으로 확인하기!
    for (int i = 0; i < N; i++) {
        if (enemy[i].second.second) {
            continue;
        }
        //통신 가능 하다면
        if (compare(i, k)) {
            enemy[i].second.second = 1;
            enemy[k].second.second = 1;
            dfs(i);
        }
    }
}
 
int main() {
    int T, x, y, R;
    cin >> T;
    while (T--) {
        cin >> N;
        for (int i = 0; i < N; i++) {
            cin >> x >> y >> R;
            enemy.push_back(make_pair(make_pair(x, y), make_pair(R, 0)));
        }
 
        group_num = 0;
        for (int i = 0; i < N; i++) {
            if (!enemy[i].second.second) {    //방문하지 않았다면
                enemy[i].second.second = 1;
                dfs(i);
                group_num++;
            }
        }
        cout << group_num << endl;
        enemy.clear();
    }
}
 


저작자표시 비영리 변경금지

'Programming 문제풀이 > Backjoon Online Judge' 카테고리의 다른 글

2667번 : 단지번호붙이기  (0) 2018.05.29
2606번 : 바이러스  (0) 2018.05.28
2178번 : 미로탐색  (0) 2018.05.17
7569번 : 토마토  (0) 2018.05.17
7576번 : 토마토  (0) 2018.05.16

이번 프로그램은 패턴 매칭 프로그램입니다.


취약점이 존재하는 함수(strcpy, strcat, ...) 등을 db.txt에 작성하고 프로그램을 실행하면 특정 파일에 db.txt와 같은 텍스트가 있는지 파악해서 출력하는 기능을 수행합니다.


이를 통해 취약점이 있는 부분을 쉽게 파악하고, 취약한 부분을 보완할 수 있도록 지원하는 간단한 프로그램입니다.


파일 실행 시 db.txt 파일과 취약점을 찾고자 하는 파일이 한 디텍토리 내에 있어야 합니다.

또 프로그램 실행 시 취약점을 찾을 파일 이름을 argv[] 변수로 전달해야 합니다.


db.txt 예시입니다.

strcpy
strcmp


testfile 예시입니다. (이 문장안에 strcmp나 strcpy가 적혀 있는데 문장내에 있는 각 단어를 찾아줍니다.)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Lorem ipsum strcpy dolor sit amet, consectetur adipisicing elit,
sed do eiusmod tempor incididunt ut labore et dolore magna aliqua.
Ut enim ad minim veniam, quis nostrud exercitation strcmp
ullamco laboris nisi ut aliquip ex ea commodo consequat.
Duis aute irure dolor in reprehenderit in
voluptate velit strcmp esse cillum dolore eu fugiat nulla pariatur.
Excepteur sint occaecat cupidatat non proident,
sunt in culpa qui officia deserunt mollit anim id est laborum.
Lorem ipsum dolor sit amet, consectetur strcpy adipisicing elit,
sed do eiusmod tempor incididunt ut labore et strcmp dolore magna aliqua.
Ut enim ad strcpy minim veniam, quis nostrud exercitation
ullamco laboris nisi ut aliquip ex ea commodo consequat.
Duis aute irure dolor in reprehenderit in voluptate strcpy
velit esse cillum dolore eu fugiat nulla pariatur.
Excepteur sint strcmp occaecat cupidatat non proident,
sunt in culpa qui officia deserunt mollit anim id est laborum.


코드는 C++로 작성하였습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <vector>
#include <string>
using namespace std;
 
int main(int argc, char *argv[]) {
    if(argc != 2) {
        cerr << "usage error : <program name> <textfile>" << endl;
        exit(0);
    }
 
    vector<string> vulstr;
    ifstream db("db.txt", ios::in);
 
    if(!db) {
        cerr << "file open fail - db file" << endl; exit(0);
        string line;
        while(getline(db, line)) vulstr.push_back(line);
        db.close();
 
        ifstream tar(argv[1], ios::in);
        if(!tar) {cerr << "file open fail - target file" << endl; exit(0);}
        size_t line_count = 0;
        while(getline(tar, line)) {
            ++line_count;
            for(size_t i=0; i<vulstr.size(); i++) {
                size_t found = line.find(vulstr[i]);
                if(found != string::npos) {
                    cout << "[1:" << line_count << ", pos:" << found << "]" << endl;
                    for(size_t j=0; j<line.size(); j+= 100) {
                        cout << "\t" << line.substr(j,100) << endl;
                        if( j <= found && found < j+100) {
                            cout << "\t";
                            for(size_t k=0; k<found%100; k++) cout << " ";
                                cout << "^" << endl;
                        }
                    }
                    cout << endl;
                }
            }
        }
        tar.close();
        return 0;
    }
}



저작자표시 비영리 변경금지

'학교 수업 및 과제 > 컴퓨터 보안' 카테고리의 다른 글

1. ALZip Fuzzing Project  (0) 2018.05.29

[UNIX 시스템 프로그래밍 second Edition - KEITH HAVILAND저] 연습문제 풀이입니다.


(저작권에 저촉 될 우려가 있어 문제 내용은 생략합니다.)


연습문제 3.10 입니다.

선택한 파일이 변경되는지 여부를 파악하여, 변경 될 때 표준출력으로 파일의 내용을 출력하는 프로그램입니다.

먼저 파일의 변경 여부를 확인하기 위해 파일의 최종 변경 시간을 가져옵니다.

이후 파일의 최종 변경 시간이 갱신되었다면 이때 표준 출력으로 파일의 내용을 출력하게 됩니다.

코드를 보면 더 쉽게 이해할 수 있을것이라 생각합니다.


코드는 C++로 작성하였습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <fcntl.h>
#include <sys/stat.h>
 
#define BUFF_SIZE 1000
 
void slowwatch(const char*, time_t);
struct stat sb;
 
int main(int argc, char* argv[]) {
    int j;
    int fd;     
    time_t last_time;
    
    if(argc < 2) {
        fprintf(stderr, "usage : lookout filename ...\n");
        exit(1);
    }
    
    if(--argc > 1) {
        fprintf(stderr, "lookout : too many filenames\n");
        exit(1);
    }    
    
    fd = open(argv[1], O_RDWR | O_CREAT, 0644);
    fd = close(fd);
 
    if(stat(argv[1], &sb) == -1) {
        fprintf(stderr, "lookout: couldn't stat %s\n", argv[j]);
        perror("stat");
        exit(1);
    }
    last_time = sb.st_mtime;    
        
    for(;;) {
        slowwatch(argv[1], last_time);
        sleep(3);
    }    
}
 
void slowwatch(const char *name, time_t last) {
    if(stat(name, &sb) == -1 || sb.st_mtime != last) {
        printf("%s changed\n", name);
        char buff[BUFF_SIZE];        
        int fd;
        ssize_t rd_size;
        if( 0 < (fd = open(name, O_RDONLY))) {        
            while( 0 < ( rd_size = read( fd, buff, BUFF_SIZE-1))) {
                buff[rd_size] = '\0';
                puts(buff);        
            }
            close(fd);
        }
        else
            printf("file open fail\n");
 
        exit(1);
    }
}
 



저작자표시 비영리 변경금지

'학교 수업 및 과제 > 유닉스 프로그래밍' 카테고리의 다른 글

[UNIX 시스템 프로그래밍] 연습문제 3.8 풀이  (0) 2018.05.30
[UNIX 시스템 프로그래밍] 연습문제 3.7 풀이  (0) 2018.05.30
[UNIX 시스템 프로그래밍] 연습문제 3.6 풀이  (0) 2018.05.30
[UNIX 시스템 프로그래밍] 연습문제 3.3 풀이  (0) 2018.05.30
[UNIX 시스템 프로그래밍] 연습문제 2.15 풀이  (0) 2018.05.30

[UNIX 시스템 프로그래밍 second Edition - KEITH HAVILAND저] 연습문제 풀이입니다.


(저작권에 저촉 될 우려가 있어 문제 내용은 생략합니다.)


연습문제 3.8 입니다.

이번 문제의 경우 사용자가 unlink를 사용하며 파일을 제거하는 프로그램을 작성하는 것이 목표입니다.

먼저 사용자가 파에 쓰기 권한을 가졌는지 확인하기 위해 access 함수를 이용하였습니다.

이후 쓰기 권한을 가졌다면 unlink 함수를 이용하여 파일을 삭제하였습니다.


코드는 C++로 작성하였습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <stdlib.h>
#include <unistd.h>
#include <stdio.h>
 
int main(int argc, char *argv[]) {
    int check = 0;    
    if (argc !=2) {
        fprintf(stderr, "delete only one file\n");
        exit(1);    
    }
    if(access (argv[1], W_OK) == -1) {
        perror("cannot write");
        printf("\tyou don't have write permission.\n\tDo you want really delete file?\n\tif you want, input 1 : ");
        scanf("%d",&check);
        if(check == 1)
            printf("OK. delete file\n");
        else {
            printf("file delete cancel\n");
            exit(0);    
        }
    }
    if(unlink(argv[1]) == -1) {
        perror("unlink failed");
        exit(1);    
    }
    
    printf("Succeeded\n");
    exit(0);
}
 



저작자표시 비영리 변경금지

'학교 수업 및 과제 > 유닉스 프로그래밍' 카테고리의 다른 글

[UNIX 시스템 프로그래밍] 연습문제 3.10 풀이  (0) 2018.05.30
[UNIX 시스템 프로그래밍] 연습문제 3.7 풀이  (0) 2018.05.30
[UNIX 시스템 프로그래밍] 연습문제 3.6 풀이  (0) 2018.05.30
[UNIX 시스템 프로그래밍] 연습문제 3.3 풀이  (0) 2018.05.30
[UNIX 시스템 프로그래밍] 연습문제 2.15 풀이  (0) 2018.05.30

[UNIX 시스템 프로그래밍 second Edition - KEITH HAVILAND저] 연습문제 풀이입니다.


(저작권에 저촉 될 우려가 있어 문제 내용은 생략합니다.)


연습문제 3.7 입니다.

특정 파일의 권한을 바꾸기 위해 ls스타일로 권한 명령을 내리면 변환해 주는 프로그램입니다.

ls스타일을 이용하기 위해 연습문제 3.3 에서 작성한 코드를 이용하였습니다.

변환 과정은 연습문제 3.3과 거의 같으며 실제 권한 변경을 수행하기 위해 chmod 함수를 이용했습니다.


코드는 C++로 작성하였습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <sys/types.h>
#include <sys/stat.h>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
 
char oc[4] = "";
 
int lsoct(char* ls) {
    int check = 0;
    for(int i=0; i<=8; i++) {
        switch(ls[i]) {
            case 'r':
                check += 4;
                break;
            case 'w':
                check += 2;                
                break;
            case 'x':
                check += 1;                
                break;
            case '-':
                break;
            default:
                printf("signal error\n");
                return -1;            
        }
        
        if(i%3 == 2) {
            char c[1] = {check+48};
            strcat(oc,c);
            check = 0;
        }
    }
    return 0;
}
 
int main(int argc, char* argv[]) {
    if(argc != 3) {
        printf("error : not two factor\n");
        return -1;
    }
    else if(strlen(argv[2]) == 9)
        lsoct(argv[2]);
    else if(strlen(argv[2]) != 4) {
        printf("error : file permission\n");
        return -1;     
    }
    else
        strcpy(oc, argv[2]);
    
    long i = strtol(oc, 0, 8);
    if(chmod(argv[1], i) == -1)
        perror("call to chmod falled\n");
 
    return 0;
    
 
}


저작자표시 비영리 변경금지

'학교 수업 및 과제 > 유닉스 프로그래밍' 카테고리의 다른 글

[UNIX 시스템 프로그래밍] 연습문제 3.10 풀이  (0) 2018.05.30
[UNIX 시스템 프로그래밍] 연습문제 3.8 풀이  (0) 2018.05.30
[UNIX 시스템 프로그래밍] 연습문제 3.6 풀이  (0) 2018.05.30
[UNIX 시스템 프로그래밍] 연습문제 3.3 풀이  (0) 2018.05.30
[UNIX 시스템 프로그래밍] 연습문제 2.15 풀이  (0) 2018.05.30

티스토리툴바