koenjazh-CNfresde
짬뽕얼큰하게의 맨땅에 헤딩 :: '분류 전체보기' 카테고리의 글 목록 (27 Page)

프로세스 간 통신(IPC) 개요

시스템 프로그래밍 2020. 4. 18. 12:15

1. IPC 방법의 분류

크게 3개의 기능적 분류로 나눌 수 있음.

  • 통신 : 프로세스 간에 데이터를 주고받는 방법

  • 동기화: 프로세스나 스레드 간에 동기화를 맞추는 방법

  • 시그널: 시그널은 다른목적으로 설계되었지만, 특정 상황에서 동기화를 맞추는 방법으로 사용 가능

    시그널 번호 자체가 하나의 정보 형태기때문에 통신목적으로도 사용 가능(연관된 정수, 포인터를 수반할 수 있음)

 

 

2. 통신 방법

  • 데이터 전송: 쓰기와 읽기 두가지 요소로 구분
    통신을 하려면 한 프로세스에서 IPC방법에 데이터를 쓰고 다른 프로세스는 이 데이터를 읽어야함
    이 기술에는 사용자 메모리와 커널 메모리 간에 통신하는 두가지 전송 모드가 있음
    - 쓰는 동안 사용자 메모리로부터 커널 메모리로 전송
    - 읽는 동안 커널 메모리에서 사용자 메모리로 전송
  • 공유 메모리: 특정 메모리 영역에 데이터를 저장해 프로세스간 데이터를 공유하는 방식
    사용자 메모리와 커널 메모리 사이에 시스템 호출이나 데이터 전송이 필요하지 않기 때문에 공유 메모리는 매우 빠른 통신을 제공

데이터 전송방법은 다음과 같이 하위 카테고리로 더 세분화 할 수 있음

  • 바이트 스트림: 파이프, FIFO, 스트림 소켓을 통해 전송되는 데이터는 제한되지 않은 바이트 스트림
    각 read 오퍼레이션은 전송자가 얼마만큼의 데이터를 섰는지에 상관없이 IPC방법으로부터 임의의 크기의 바이트를 읽어야 하는지 얻어와서 읽음
  • 메시지: 시스템 V 메시지큐, POSIX 메시지 큐, 소켓 데이터그램은 데이터를 전송할 때 한 번에 전송할 수 있는 크기에 제한이 있음. 각 읽기 오퍼레이션은 송신자의 프로세스가 쓴 데이터 전체를 한번에 읽게됨.
    IPC방법에 메시지의 일부를 놔두고 메시지의 일부분만을 읽을 수 없음
    한번의 읽기 오퍼레이션으로 여러개의 메시지를 읽는것도 불가능
  • 가상 터미널: 가상터미널은 통신 방법중 하나이며 특정 상황에서 설계됨. 이건 나중에 더 공부 필요...
    송신자, 수신자 프로세스 간의 동기화는 자동으로 이루어짐. 읽기시 수신한 데이터가 없다면 자동으로 블록

 

공유 메모리는 시스템 V 공유 메모리, POSIX 공유 메모리, 메모리 매핑 세가지 공유 메모리를 제공

공유 메모리가 빠른 통신 방법을 제공하지만, 이런 속도의 장점은 공유 메모리를 동기화하는 데 들어가는 시간과 상쇄될 수 있음. 하나의 프로세스는 다른 프로세스가 메모리상에서 작업을 하고 있을 때 접근 불가능.

메모리에 저장된 데이터는 같은 메모리를 공유하는 모든 프로세스에서 볼 수 있음.

 

 

3. 동기화 방법

세마포어: 리눅스는 시스템 v 세마포어와 POSIX 세마포어를 제공

 

파일 잠금: 같은 파일에 다중 프로세스가 작업을 할 때 이를 중재

읽기 잠금과 쓰기 잠금으로 사용. flock(), fcntl() 시스템 호출로 제공.

flock()은 전체파일 잠금. 거의 사용하지 않음.

fcntl()으로 레코드 잠금. 파일의 여러곳에 lock할수 있음.


뮤텍스: POSIX 스레드에서 일반적으로 사용

 

-> 통신 방법을 동기화에 사용할 수 있음. 

 

 

4. IPC 방법 비교하기

데이터 전송 방법 vs 공유 메모리

데이터 전송 방법(파이프, FIFO, 메시지)은 동기화를 커널이 자동으로 처리. 여러 응용프로그램 설계에 적합

공유메모리는 하나의 프로세스가 같은 메모리 공간을 공유해 다른 여러 프로세스에서 데이터를 볼수있게 할때 유용.

공유메모리는 동기화를 지원해야하므로 복잡한 설계를 추가해야 할 수 있음.

 

바이트 스트림(파이프, FIFO, 소켓) 전송 vs 메시시 전송(메시지 큐, 데이터그램 소켓)

응용프로그램이 바이트 스트림 방법의 메시지 중심 모델을 선호 할 수 있는데 구분문자를 사용, 고정 길이 메시지를 사용, 최종 메시지 길이를 헤더에 표시 등을 사용할 수 있기 때문

 

시스템V와 메시지 큐 VS 그밖의 데이터 전송 방법

시스템 V와 메시지 큐는 숫자형이나 우선순위를 메시지에 줄 수 있음. 보낸 순서와 다른순서로 도착 할 수 있음

 

파이프, FIFO, 소켓은 파일 디스크립터를 통해 구현됨.

I/O 모델의 대안으로 제시된 멀티플렉싱(select()와 poll() 시스템 호출), 시그널 기반 I/O, 리눅스 고유의 epoll API를 모두 지원. 동시에 다중 파일 디스크립터를 관찰해 I/O중 어떤 것이 사용 가능한지 파악 할 수 있음.

시스템 V 메시지 큐는 파일 디스크립터 기술을 사용하지 않고 이런 기술을 지원하지 않음. 

 

POSIX 메시지큐는 통지 방법을 제공, 프로세스나 새로운 스레드에 비어있는 쿠에 메시지가 도착하면 시그널을 전송

 

유닉스 도메인 소켓은 파일 디스크립터를 하나의 프로세스에서 다른 프로세스로 전달할 수 있는 기능을 제공

이 기능은 하나의 프로세스에서 파일을 열고 이를 파일에 접근할 수 없는 다른 프로세스가 사용 가능하게 함

 

레코드 잠금은 fcntl() 을 이용해 걸게됨 fcntl()을 사용할 경우 커널이 데드락을 감지하지만 시스템V와 POSIX 세마포어는 소유권 속성을 갖고있지 않아 세마포어의 데드락을 커널이 자동으로 감지 할 수 없음.

 

시스템 V IPC 설계 이슈

시스템 V IPC는 전통적인 유닉스 I/O 모델과는 독립적으로 설계됐기 때문에 결과적으로 기이한 프로그래밍 인터페이스가 존재, 사용하기 복잡 //  POSIX IPC는 이런 문제를 고려해 설계됨

시스템 V IPC는 비 연결형 : IPC를 열기 위해 사용하는 핸들 개념을 제공하지 않음. 커널은 프로세스가 객체를 열고있는지 기록하지 않기때문에 객체가 안전하게 제거되는지 알기 위해서는 추가적인 프로그래밍이 필요

 

 

 

출처: 리눅스 API의 모든것 고급 리눅스 API

'시스템 프로그래밍' 카테고리의 다른 글

리눅스 역사와 표준  (0) 2020.04.25
블로그 이미지

짬뽕얼큰하게

,

null과 undefined 차이

2020. 2. 8. 19:43

보호되어 있는 글입니다.
내용을 보시려면 비밀번호를 입력하세요.

Visual Studio Code (VS Code) PS용 환경설정

알고리즘 2019. 2. 7. 12:12

VS Code Problem Solving용 환경설정


작업 당시 운영체제: Ubuntu 18.04 64bit


VS Code를 활용하여 백준, 알고스팟, 코드 포스 등 여러 문제를 풀기위한 간단한 환경설정들이 검색해도 나오지 않아, 여기에 정리한다.


내가 VS 코드를 처음 설치하고 부딪힌 문제는 총 두개이다.

1. 어떻게 실행하지? -> Code Runner 이용

2. 인풋을 어떻게 입력하지? -> 설정 변경


1. VS Code 설치 : 생략


2. extension의 C/C++ 설치

   나는 C/C++ 를 사용하므로 해당 extension을 설치하였다.


3. code runner 설치

   빌드 및 실행하기 위한 code runner 설치


4. File -> preference -> setting에 들어 간 후

extensions -> Run Code configuration -> Run In Terminal checking!!!


5. 마우스 오른쪽 클릭, Run Code를 통해 실행


6. 터미널창에 입력이 가능한지 확인



VS Code를 사용하기위한 5분 설정 팁이다. Code Runner만 설치하여 사용할 시 output에 실행 결과가 나타나게 되는데, 이 output창에는 입력을 넣을 수가 없다.


따라서 PS를 위한 입력을 주기위해서는 위와 같은 세팅을 통해, 터미널에서 실행하는 것으로 변경 해야한다.


나도 시행착오 끝에 알아낸 방법인데, 

더 좋은 방법이 있다면 댓글로 정보 공유 부탁드립니다.  :D



'알고리즘' 카테고리의 다른 글

프로그래머스(programmers) N으로 표현  (0) 2021.01.11
[논리 오류] 한번의 for문으로 여러 데이터의 hash값을 처리시 한 실수  (0) 2020.12.28
알고스팟 (algospot) FORTRESS  (1) 2019.01.26
백준(BOJ) 16234 - 인구이동  (0) 2019.01.21
백준(BOJ) 16236 - 아기 상어  (0) 2019.01.21
블로그 이미지

짬뽕얼큰하게

,

알고스팟 (algospot) FORTRESS

알고리즘 2019. 1. 26. 18:34

못풀었다.

종만북 코드를 이해하고 책을 보지않고 따라해보았다.


leaf에서 leaf까지의 최대값과 leaf에서 root까지의 최대값의 최대값이 정답이 되는것으로 나눈것을 생각하지 못했다. 더 깊이 생각하는 습관을 가져야겠다.


트리 탐색시 다음노드들의 리턴값을 벡터에 저장하여 높이를 뽑아내는 패턴도 기억 해야겠다는 생각을 했다.


트리 탐색 기본 구조도 익혔고, 트리 생성 기본 구조도 익힐 수 있었다.


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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Pair{
    int y;
    int x;
    int r;
};
struct TreeNode{
    vector<TreeNode*> children;
};
 
 
Pair wall[101];
int longest;
int N, T;
 
int sq(int x){
    return x * x;
}
bool enclose(int a, int b){
    if(wall[a].r <= wall[b].r) return false;
 
    int y1 = wall[a].y;
    int x1 = wall[a].x;
    int r1 = wall[a].r;
    int y2 = wall[b].y;
    int x2 = wall[b].x;
    int r2 = wall[b].r;
    if(sq(r1 - r2) <= sq(x1 - x2) + sq(y1 - y2)){
        return false;
    }
    return true;
}
 
bool isChild(int parent, int child){
    if(parent == child) return false;
    if(!enclose(parent, child)) return false;
    for(int i = 0 ; i < N; i++){
        if(i == parent || i == child) continue;
        if(enclose(parent, i) && enclose(i, child)) return false;
 
    }
    return true;
}
TreeNode* getTree(int root){
    TreeNode* node = new TreeNode();
    for(int i = 0 ; i < N; i++){
        if(isChild(root, i)){
            node->children.push_back(getTree(i));
        }
    }
 
    return node;
}
 
 
int height(TreeNode* root){
    int s = root->children.size();
    vector<int> heights;
    for(int i = 0 ; i < s; i++){
        heights.push_back(height(root->children[i]));
    }
    if(heights.empty()) return 0;
    int h_s = heights.size();
    if(h_s >= 2){
        sort(heights.begin(), heights.end());
        longest = max(longest, heights[h_s - 1] + heights[h_s - 2] + 2);
    }
    return heights.back() + 1;
}
bool cmp(Pair a, Pair b){
    if(a.r < b.r) return false;
 
    return true;
}
 
int main(void){
    scanf("%d", &T);
    while(T--){
        longest = 0;
        scanf("%d", &N);
        for(int i = 0 ; i < N; i++){
            int x, y, r;
            scanf("%d %d %d", &x, &y, &r);
            wall[i] = {y, x, r};
        }
 
        sort(wall, wall + N, cmp);
 
 
        TreeNode* root = getTree(0);
        printf("%d\n", max(longest, height(root)));
    }
}
cs


'알고리즘' 카테고리의 다른 글

[논리 오류] 한번의 for문으로 여러 데이터의 hash값을 처리시 한 실수  (0) 2020.12.28
Visual Studio Code (VS Code) PS용 환경설정  (1) 2019.02.07
백준(BOJ) 16234 - 인구이동  (0) 2019.01.21
백준(BOJ) 16236 - 아기 상어  (0) 2019.01.21
백준(BOJ) 16235 - 나무 재테크  (0) 2019.01.15
블로그 이미지

짬뽕얼큰하게

,

백준(BOJ) 16234 - 인구이동

알고리즘 2019. 1. 21. 22:59

영역 구하기 응용문제였던 것 같다.

인접한 지역과의 차가 L이상 R 이하인 영역을 벡터에 담고,

담긴 벡터들 값의 평균을 구해 이동된 다음 맵을 만드는 방법을 선택했다.


때문에 맵을 map[50][50][2]형태로 선언하였고,  두맵을 번갈아 가며 사용하게된다.


 방문배열은 매번 초기화 하는 비용을 없애고 싶어서 int형으로 선언하여 이동한 날짜수를 기록해주었다.


사실 인접한 지역을 구하면서 sum값을 구하면 더 효율적인 코드게 되겠지만, 결국 시간복잡도에서는 차이가 없을 것 같아 편하게 답을 구하는쪽으로 코딩했다.


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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <vector>
using namespace std;
 
struct _pair{
    int y;
    int x;
};
int N, L, R;
int map[50][50][2];
int visited[50][50];
int k;
int dy[] = {1, 0, -1, 0};
int dx[] = {0, 1, 0, -1};
int abs(int a){
    if(a < 0) a *= -1;
    return a;
}
void check(int y, int x, vector<_pair>& v){
    visited[y][x] = k;
 
    for(int i = 0 ; i < 4; i++){
        int ny = y + dy[i];
        int nx = x + dx[i];
        if(ny < 0 || ny >= N || nx < 0 || nx >= N || visited[ny][nx] >= k){
            continue;
        }
        int n = abs(map[y][x][k%2] - map[ny][nx][k%2]);
        if(n >= L && n <= R){
            check(ny, nx, v);
            v.push_back({ny, nx});
        }
    }
}
int main(void){
    scanf("%d %d %d", &N, &L, &R);
    for(int i = 0 ; i < N; i++){
        for(int j = 0 ; j < N; j++){
            scanf("%d", &map[i][j][k]);
            visited[i][j] = -1;
        }
    }
 
    while(true){
        bool result = false;
        vector<_pair> v;
        for(int i = 0 ; i < N; i++){
            for(int j = 0 ; j < N; j++){
                if(visited[i][j] >= k) continue;
                check(i, j, v);
                int n = v.size();
                if(n > 0) result = true;
                int t_sum = map[i][j][k%2], t_cnt = 1 + n;
                for(int l = 0; l < n; l++){
                    int y = v[l].y;
                    int x = v[l].x;
                    t_sum += map[y][x][k%2];
                }
                int value = t_sum / t_cnt;
                for(int l = 0; l < n; l++){
                    int y = v[l].y;
                    int x = v[l].x;
                    map[y][x][(k + 1)%2] = value;
                }
                map[i][j][(k + 1)%2] = value;
                v.clear();
            }
        }
        if(!result) break;
        k++;
    }
 
 
    printf("%d", k);
 
}
cs


'알고리즘' 카테고리의 다른 글

Visual Studio Code (VS Code) PS용 환경설정  (1) 2019.02.07
알고스팟 (algospot) FORTRESS  (1) 2019.01.26
백준(BOJ) 16236 - 아기 상어  (0) 2019.01.21
백준(BOJ) 16235 - 나무 재테크  (0) 2019.01.15
백준(BOJ) 1475 - 방번호  (0) 2019.01.02
블로그 이미지

짬뽕얼큰하게

,

백준(BOJ) 16236 - 아기 상어

알고리즘 2019. 1. 21. 20:26

아기상어 문제를 풀었다.

하반기에 한번 풀어본 문제여서 같은 방법으로 접근했다.


bfs로 먹을수 있는 물고기를 탐색한 다음 소팅하여 가장 우선순위가 높은 물고기를 선택하였다.

조건들만 잘 넣어준다면, 어렵지 않게 풀수 있는 문제이다.


풀고 나서 생각이 든 것인데, 가장 우선순위가 높은 하나만 선택하면 되기때문에

덱을 사용하여  비어있거나 0번 인덱스 물고기보다 우선순위가 낮은 물고기는 뒤에 푸쉬하고 우선순위가 높은 물고기는 앞에 푸쉬를 한면, 소팅을 안해도 될 것 같다.



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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct _pair{
    int y;
    int x;
    int cnt;
 
};
 
bool cmp(_pair a, _pair b){
    if(a.cnt < b.cnt) return true;
    if(a.cnt == b.cnt){
        if(a.y < b.y) return true;
        if(a.y == b.y){
            if(a.x < b.x) return true;
        }
    }
 
    return false;
}
int N;
int shark_y, shark_x, shark_size, eat_cnt, total_second;
int map[21][21];
 
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
bool bfs(vector<_pair>& fishes){
    queue<_pair> q;
    bool visited[21][21];
    for(int i = 0 ; i < N; i++){
        for(int j = 0 ; j < N; j++){
            visited[i][j] = false;
        }
    }
    visited[shark_y][shark_x] = true;
    q.push({shark_y, shark_x, 0});
    while(!q.empty()){
        _pair p = q.front();
        q.pop();
        for(int i = 0 ; i < 4; i++){
            int ny = p.y + dy[i];
            int nx = p.x + dx[i];
            if(ny < 0 || ny >= N || nx < 0 || nx >= N
                || visited[ny][nx] || map[ny][nx] > shark_size){
                continue;
            }
            visited[ny][nx] = true;
            q.push({ny,nx,p.cnt + 1});
            if(map[ny][nx] > 0 && map[ny][nx] < shark_size){
                fishes.push_back({ny, nx, p.cnt + 1});
            }
 
        }
    }
    if(fishes.size() > 0) return true;
    return false;
}
 
int main(void){
    scanf("%d", &N);
    for(int i = 0 ; i < N; i++){
        for(int j = 0 ; j < N; j++){
            scanf("%d", map[i] + j);
            if(map[i][j] == 9){
                shark_y = i;
                shark_x = j;
                shark_size = 2;
                map[i][j] = 0;
            }
        }
    }
    vector<_pair> fishes;
    while(bfs(fishes)){
        sort(fishes.begin(), fishes.end(), cmp);
        shark_y = fishes[0].y;
        shark_x = fishes[0].x;
        total_second += fishes[0].cnt;
        eat_cnt++;
        map[shark_y][shark_x] = 0;
        if(eat_cnt == shark_size){
            eat_cnt = 0;
            shark_size++;
        }
        fishes.clear();
    }
    printf("%d", total_second);
 
}
cs


'알고리즘' 카테고리의 다른 글

알고스팟 (algospot) FORTRESS  (1) 2019.01.26
백준(BOJ) 16234 - 인구이동  (0) 2019.01.21
백준(BOJ) 16235 - 나무 재테크  (0) 2019.01.15
백준(BOJ) 1475 - 방번호  (0) 2019.01.02
백준(BOJ) 10250 - ACM 호텔  (0) 2019.01.02
블로그 이미지

짬뽕얼큰하게

,

백준(BOJ) 16235 - 나무 재테크

알고리즘 2019. 1. 15. 20:11

시뮬레이션 문제였다.

작년 하반기에 삼성 시험에서 이 문제를 풀때 스택을 사용하면, 최근에 추가한 나무가 가장 나이가 어리기 때문에 이 방법을 이용하여 넣었다 뺐다 하다가 시간초과가 났던 것이 기억났다.


이번에도 스택을 이용해서 풀자고 생각해서, 스택을 이용해서 깔끔하게 푼것 같았다. 예제케이스도 나와서 정말 깔끔하군! 생각했는데, AC를 받지 못했다.


스택을 사용하면 가장 어린놈을 순서대로 빼낼수 있다는 옜날 생각을 그대로 적용했던 것이 실수였다. 다시 생각해보니 시험당시에는 어린 순서를 맞춰주기 위해 스택하나를 더 두고 빼면서 임시스택에 넣고 결과값을 다시 스택에 저장하는 방법을 사용했다. 이 생각을 잊은채 걍 스택쓰면 되긴 했었는데? 라는 생각으로 스택을 썼고 계속 왜틀렸지만 반복했다.

이러니 그때 시간초과가 났지...


나이가 어린순을 유지하기위해 덱 자료구조를 이용했다.

가을에 추가되는 나무들은 push_back 으로 덱에 저장하고, 봄에 양분을 먹고 한살 더 자라날때에는 push_front로 앞에 추가해주어 나이 순서를 유지시켜주었다.


덱 자료구조를 tree[11][11][1001] 만큼 선언했는데, 사실 tree[11][11][2] 면 충분하다.

k를 %2연산하여 공간을 활용할 수 있지만 귀찮아서... 걍 했다.


tree변수에는 각 지역에 해당하는 나무들의 나이가 저장되어있다.

provide에는 입력으로 주어지는 겨울에 공급되는 양분의 양이 저장되어있다.

die[11][11] 에는 봄에 죽은나무 나이 /2 한값을 저장해 놨다가 여름에 더해준다.

fall[11][11]은 봄에 나이를 한살 먹고 5의 배수가 되는 나무들의 수가 저장되고, 가을에 이 수만큼 한살짜리 나무들을 주변에 추가해준다.


덱을 사용하니 200ms이 나왔다. 삼성은 통과할 수준이지만, 많이 느린 방법이다. 

정답을보니 갓님들의 풀이가 많이 보였다. 시간날때 하나씩 봐야겠다.




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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <iostream>
#include <cstdio>
#include <deque>
 
using namespace std;
int N, M, K;
int provide[11][11];
int map[11][11];
 
deque<int> tree[11][11][1001];
int die[11][11];
int fall[11][11];
int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
 
 
int main(void){
   scanf("%d %d %d", &N, &M, &K);
 
   for(int i = 1; i <= N; i++){
       for(int j = 1 ; j <= N; j++){
            scanf("%d", provide[i] + j);
            map[i][j] = 5;
       }
   }
 
   for(int i = 0 ; i < M; i++){
        int r, c, a;
        scanf("%d %d %d", &r, &c, &a);
        tree[r][c][0].push_front(a);
   }
 
 
   for(int k = 0 ; k < K; k++){
       for(int i = 1; i <= N; i++){
           for(int j = 1 ; j <= N; j++){
                while(!tree[i][j][k].empty()){
                    int age = tree[i][j][k].back();
                    tree[i][j][k].pop_back();
                    if(age <= map[i][j]){
                        map[i][j] -= age;
                        tree[i][j][k+1].push_front(age + 1);
 
                        if((age + 1) % 5 == 0){
                            fall[i][j]++;
                        }
 
                    }
                    else{
                        die[i][j] += age/2;
                    }
                }
 
 
           }
       }
       for(int i = 1 ; i <= N; i++){
           for(int j = 1 ; j <= N; j++){
               map[i][j] += die[i][j];
               die[i][j] = 0;
               for(int l = 0; l < fall[i][j]; l++){
                   for(int m = 0; m < 8; m++){
                       int ni = i + dy[m];
                       int nj = j + dx[m];
                       if(ni > 0 && ni <= N && nj > 0 && nj <= N ){
                            tree[ni][nj][k + 1].push_back(1);
                       }
                   }
               }
               fall[i][j] = 0;
 
               map[i][j] += provide[i][j];
           }
       }
 
 
   }
   int cnt = 0 ;
   for(int i = 1 ; i <= N; i++){
       for(int j = 1 ; j <= N; j++){
           cnt += tree[i][j][K].size();
       }
   }
    printf("%d\n", cnt);
 
 
}
 
cs


'알고리즘' 카테고리의 다른 글

백준(BOJ) 16234 - 인구이동  (0) 2019.01.21
백준(BOJ) 16236 - 아기 상어  (0) 2019.01.21
백준(BOJ) 1475 - 방번호  (0) 2019.01.02
백준(BOJ) 10250 - ACM 호텔  (0) 2019.01.02
백준(BOJ) 2293 - 동전1  (0) 2019.01.02
블로그 이미지

짬뽕얼큰하게

,

백준(BOJ) 1475 - 방번호

알고리즘 2019. 1. 2. 12:45

N이 0일경우 정답은 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
#include <iostream>
#include <cstdio>
 
int arr[11];
int maxx(int a, int b){
  return a > b ? a : b;
}
int main(void){
  int N;
  int m = 0;
  scanf("%d", &N);
  if(N == 0) m = 1;
  while(N){
    arr[N%10]++;
    N /= 10;
  }
  for(int i = 0 ; i < 9; i++){
    if(i == 6){
      m = maxx(m , (arr[6] + arr[9] + 1)/2);
    }
    else{
      m = maxx(m, arr[i]);
    }
  }
  printf("%d", m);
}
 
cs


'알고리즘' 카테고리의 다른 글

백준(BOJ) 16236 - 아기 상어  (0) 2019.01.21
백준(BOJ) 16235 - 나무 재테크  (0) 2019.01.15
백준(BOJ) 10250 - ACM 호텔  (0) 2019.01.02
백준(BOJ) 2293 - 동전1  (0) 2019.01.02
백준(BOJ) 13023 - ABCDE  (0) 2018.12.09
블로그 이미지

짬뽕얼큰하게

,

백준(BOJ) 10250 - ACM 호텔

알고리즘 2019. 1. 2. 12:29

나머지 처리만 잘해주면 크게 어려울게 없었다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <cstdio>
 
int main(void){
  int t;
  scanf("%d", &t);
    while(t--){
      int h, w, n;
      scanf("%d %d %d", &h, &w, &n);
      int f;
      int room;
      room = n % h == 0 ? n/h : n/h + 1;
      f = n % h == 0 ? h : n % h;
      printf("%d%02d\n", f, room);
 
    }
  }
 
cs


'알고리즘' 카테고리의 다른 글

백준(BOJ) 16235 - 나무 재테크  (0) 2019.01.15
백준(BOJ) 1475 - 방번호  (0) 2019.01.02
백준(BOJ) 2293 - 동전1  (0) 2019.01.02
백준(BOJ) 13023 - ABCDE  (0) 2018.12.09
알고스팟(algospot) ITES - 외계 신호 분석  (0) 2018.12.05
블로그 이미지

짬뽕얼큰하게

,

백준(BOJ) 2293 - 동전1

알고리즘 2019. 1. 2. 11:27

다이나믹 프로그래밍 문제다.

많은 사람들이 풀어서 많은 해법이 나와있었다.

하지만 이해하기 힘든 문제였다.


혼자서는 도저히 생각 할 수 없었고 정답을 보고 이해하는 방법을 택했다.

N개 종류의 동전을 가지고 K원을 만들때,

처음에는 한개종류의 동전을 가지고 0 ~ K원을 만들고

그다음에는 두개종류의 동전을 가지고 0~ K원을 만든다.

그다음에는? 당연히 3개의 동전을 가지고 0 ~ K원을 만든다.

이렇게 만들때에는 당연히 이전에 사용한 값을 이용한다.

만약 1을 이용해 0 ~ K원을 만들었다 치자.

그리고 1 과 2를 이용해서 다시 0~ K원을 만들때를 생각해보자.

1과 2원을 이용해 K가 2원인 경우까지 세었고, 

이제 3원을 만들고 싶다. 현재 1원으로는 만들어봤다.

1원으로 만든경우는 111일테니 이 경우를 더해주자.

2원을 활용해 3을 만들어야하므로 1과 2원을 활용해 1을만든거에 이번에 활용할 2를 추가해주면 3이된다.

그러면 1과 2를 활용하여 3을 만든 것이다.


다시해보자.

1로 0 ~ K 까지 만들었다 생각하자. 

1과 2를 이용해 3까지의 경우의 수를 세었고, 이제 4를 만들고싶다.

1만을 이용한 1111이 있을 것이다.

이 경우를 더해주자. ( + 1)

그리고 1~2를 이용해 2를 만든것에서 (11, 2)에서 2를 추가해주면 4가된다.  ( + 2)

총 세 경우가 저장된다.


다시 다시 다시 해보자.

1과 2원으로 0 ~ K원을 전부 만들었다.

이제 5원을 활용하여 0~ K원을 만들차례이고 K-1원까지 만들었다 생각해보자.

K원을 만들려면 일단 1~2원으로 K원을 만든 경우를 더해주면된다.

그리고 1,2,5로 K-5원까지 만든 경우(경우의 수가 아님)들은 5만 추가하면 K원이 되므로 그 경우의 수도 더해주면 된다.


처음에는 dp를 [100][10001] 을 선언하였었는데, 메모리 초과가 났다.

메모리 제한은 4MB로 4*100*10001에 이것저것 하면 4메가에 넘게된다.

따라서 dp를 dp[2][10001]로 선언하고, 토글변수 next로 이전 값만 저장하도록 구현하였다.



아래는 코드다.


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
#include <iostream>
#include <cstdio>
 
int arr[102];
int dp[2][10001];
int next = 0;
int main(void){
  int N, K;
  scanf("%d %d", &N, &K);
  for(int i = 0 ; i <N ; i++){
    scanf("%d", arr + i);
  }
  for(int i = 0 ; i< N; i++){
    int n = arr[i];
    for(int j = 0 ; j <= K; j++){
      dp[next][j] = dp[next ^ 1][j];
      if(n == j) dp[next][j]++;
 
      if(j - n > 0){
        dp[next][j] += dp[next][j-n];
      }
    }
    next ^= 1;
  }
  printf("%d", dp[next ^ 1][K]);
 
}
 
cs





'알고리즘' 카테고리의 다른 글

백준(BOJ) 1475 - 방번호  (0) 2019.01.02
백준(BOJ) 10250 - ACM 호텔  (0) 2019.01.02
백준(BOJ) 13023 - ABCDE  (0) 2018.12.09
알고스팟(algospot) ITES - 외계 신호 분석  (0) 2018.12.05
백준(BOJ) 2581 소수  (0) 2018.11.29
블로그 이미지

짬뽕얼큰하게

,

공지사항

글 보관함

달력

«   2025/04   »
일 월 화 수 목 금 토
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

티스토리툴바