게시 됨 업데이트 됨Algorithm / BOJ5분안에 읽기 (약 824 단어)

<13460> 째로탈출 2

문제 : https://www.acmicpc.net/problem/13460

처음 풀이 방향을 잘못 잡고, 풀이시 여러 예외 사향을 잘못 생각하는 바람에 시간이 오래 걸렸습니다.
코드가 조금 긴 편입니다… 저는 dfs를 활용해서 풀었습니다. 주의해야 할 사항이 몇가지 있었는데,
1. 이미 기울였던 방향과 그 반대방향으로 다시 기울여서는 안된다. (이미 기울였던 방향으로 다시 기울이게 된다면 결과는 같을 것 입니다. 또한 방금 기울였던 방향의 반대로 기울인다면 이전과 같은 상태로 돌아가게 됩니다.)
2. 기울인 후 파란공과 빨간공의 위치가 겹친다면 기울이기 전의 (1) 기울인 방향, (2) 파란공 위치, (3) 빨간공 위치 를 고려하여 다시 위치를 변경해주어야 한다.

위의 2가지 주의사항을 고려해서 푼다면 큰 문제 없이 풀 수 있을것 입니다.

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
#include <iostream>
#include <algorithm>

#define MAP_MAX_SIZE 10
#define ANS_MAX 11
using namespace std;

char map[MAP_MAX_SIZE][MAP_MAX_SIZE];
int N, M;
int ans = ANS_MAX;
int rx, ry, bx, by, hx, hy;
bool is_r_hall_in, is_b_hall_in;

void init_map() {
    char c;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> c;
            map[i][j] = c;

            if (c == 'R') {
                rx = i;
                ry = j;
            }
            else if (c == 'B') {
                bx = i;
                by = j;
            }
            else if (c == 'O') {
                hx = i;
                hy = j;
            }
        }
    }
}

int get_deposit_dir(int dir) {
    if (dir == 0) {
        return 1;
    }
    else if (dir == 1) {
        return 0;
    }
    else if (dir == 2) {
        return 3;
    }
    else if (dir == 3) {
        return 2;
    }
}

int get_priority(int dir) { // 0 = 빨간공, 1 = 파란공
    int priority = -1;

    // 상
    if (dir == 0) {
        priority = bx < rx;
    }
    // 하
    else if (dir == 1) {
        priority = bx > rx;
    }
    // 좌
    else if (dir == 2) {
        priority = by < ry;
    }
    // 우
    else if (dir == 3) {
        priority = by > ry;
    }

    return priority;
}

int move_x(int x, int y, int dir) {
    int nx = x;
    char type;

    if (dir == 0) {
        for (int i = x - 1; i > 0; i--) {
            type = map[i][y];
            if (type == '#') {
                break;
            }
            else if (type == 'O') {
                nx = i;
                break;
            }
            else {
                nx = i;
            }
        }
    }
    else {
        for (int i = x + 1; i < N - 1; i++) {
            type = map[i][y];
            if (type == '#') {
                break;
            }
            else if (type == 'O') {
                nx = i;
                break;
            }
            else {
                nx = i;
            }
        }
    }

    return nx;
}

int move_y(int x, int y, int dir) {
    int ny = y;
    char type;

    if (dir == 2) {
        for (int i = y - 1; i > 0; i--) {
            type = map[x][i];
            if (type == '#') {
                break;
            }
            else if (type == 'O') {
                ny = i;
                break;
            }
            else {
                ny = i;
            }
        }
    }
    else {
        for (int i = y + 1; i < M - 1; i++) {
            type = map[x][i];
            if (type == '#') {
                break;
            }
            else if (type == 'O') {
                ny = i;
                break;
            }
            else {
                ny = i;
            }
        }
    }

    return ny;
}

void move(int dir) {
    if (dir == 0 || dir == 1) { // 상, 하
        rx = move_x(rx, ry, dir);
        bx = move_x(bx, by, dir);
    }
    else { // 좌, 우
        ry = move_y(rx, ry, dir);
        by = move_y(bx, by, dir);
    }
}

void check_hall_in() {
    if (bx == hx && by == hy) {
        is_b_hall_in = true;
    }

    if (rx == hx && ry == hy) {
        is_r_hall_in = true;
    }
}

void priority_move(int priority, int dir) {
    if (dir == 0) {
        if (priority == 0) {
            bx = bx + 1;
        }
        else {
            rx = rx + 1;
        }
    }
    else if (dir == 1) {
        if (priority == 0) {
            bx = bx - 1;
        }
        else {
            rx = rx - 1;
        }
    }
    else if (dir == 2) {
        if (priority == 0) {
            by = by + 1;
        }
        else {
            ry = ry + 1;
        }
    }
    else if (dir == 3) {
        if (priority == 0) {
            by = by - 1;
        }
        else {
            ry = ry - 1;
        }
    }
}

void dfs(int pre_dir, int cnt) {
    if (cnt > 10) {
        is_b_hall_in = false;
        is_r_hall_in = false;
        return;
    }

    if (is_b_hall_in) {
        is_b_hall_in = false;
        is_r_hall_in = false;
        return;
    }
    else {
        if (is_r_hall_in) {
            is_b_hall_in = false;
            is_r_hall_in = false;
            ans = min(ans, cnt);
            return;
        }
    }

    int brx = rx;
    int bry = ry;
    int bbx = bx;
    int bby = by;

    // 상, 하, 좌, 우
    for (int dir = 0; dir < 4; dir++) {
        if (dir == pre_dir || dir == get_deposit_dir(pre_dir)) {
            continue;
        }

        int priority = get_priority(dir);

        // 이동 & 홀 인 체크
        move(dir);
        check_hall_in();

        // 공이 겹칠 경우, 우선순위에 따라 이동
        if (rx == bx && ry == by) {
            priority_move(priority, dir);
        }

        if (brx != rx || bry != ry || bbx != bx || bby != by) {
            dfs(dir, cnt + 1);
        }

        rx = brx;
        ry = bry;
        bx = bbx;
        by = bby;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin >> N >> M;

    init_map();
    dfs(-1, 0);

    if (ans == ANS_MAX) {
        cout << -1 << '\n';
    }
    else {
        cout << ans << '\n';
    }

    return 0;
}
 게시 됨 업데이트 됨Algorithm / BOJ1분안에 읽기 (약 201 단어)

<11054> 가장 긴 바이토닉 부분 수열

문제 : https://www.acmicpc.net/problem/11054

먼저 증가하는 수열의 최대 길이와 감소하는 수열의 최대 길이를 구해주었습니다.
그 후 각 자리의 최대 길이를 서로 더해준 후 max 값을 비교하여 해결했습니다.

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
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    int max_value = 0;
    int n;
    cin >> n;
    vector<int> a(n);

    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector<int> plus(n); // 증가하는 수열의 최대 길이
    vector<int> minus(n); // 감소하는 수열의 최대 길이

    for (int i = 0; i < n; i++) {
        plus[i] = 1;
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i] && plus[i] < plus[j] + 1) {
                plus[i] = plus[j] + 1;
            }
        }
    }

    for (int i = n-1; i >= 0; i--) {
        minus[i] = 1;
        for (int j = n-1; j > i; j--) {
            if (a[j] < a[i] && minus[i] < minus[j] + 1) {
                minus[i] = minus[j] + 1;
            }
        }
    }

    for (int i = 0; i < n; i++) {
        max_value = max(max_value, plus[i] + minus[i] - 1);
    }

    cout << max_value << '\n';

    return 0;
}
 게시 됨 업데이트 됨Algorithm / BOJ2분안에 읽기 (약 356 단어)

<2632> 피자판매

문제 : https://www.acmicpc.net/problem/2632

피자가 붙어있어야 한다는 조건 때문에 정렬을 할수가 없었습니다. 먼저 A와 B 각각의 피자판에서 만들어 질 수 있는 모든 합의 경우를 map을 사용해 저장한 후 목표하는 크기의 피자를 만들 수 있는 경우를 출력하는식으로 문제를 해결했습니다.

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
#include <iostream>
#include <vector>
#include <map>

#define MAX_SIZE 1000
using namespace std;

int target;
int m, n;
int a[MAX_SIZE], b[MAX_SIZE];
map<int, int> a_sum, b_sum;

void get_all_sum(int* arr, map<int, int>& sum_map, int size) {
    for (int i = 1; i < size; i++) { // 1개~suze-1개로 만들 수 있는 경우 모두 구하기
        for (int j = 0; j < size; j++) { // 시작하는 피자 순서
            int sum = 0;
            for (int k = 1; k <= i; k++) { // j번째 피자부터 i개 만큼 더하기
                if (j+k-1 < size) {
                    sum += arr[j+k-1];
                } else {
                    sum += arr[j+k-1-size];
                }
            }
            sum_map[sum] = sum_map[sum] + 1;
        }
    }

    int sum = 0;
    for (int i = 0; i < size; i++) { // 피자의 모든 조각(size) 합
        sum += arr[i];
    }
    sum_map[sum] = 1;

    return ;
}

int main() {
    ios_base::sync_with_stdio (false);

    cin >> target >> m >> n;

    for (int i = 0; i < m; i++) {
        cin >> a[i];
    }
    for (int j = 0; j < n; j++) {
        cin >> b[j];
    }

    get_all_sum(a, a_sum, m);
    get_all_sum(b, b_sum, n);

    int cnt = a_sum[target] + b_sum[target]; // a와 b 각각의 피자만 사용해서 만드는 경우
    for (int i = 1; i < target; i++) { // a와 b피자 같이 사용해서 만드는 경우
        if (a_sum[i] && b_sum[target-i]) {
            cnt += (a_sum[i] * b_sum[target-i]);
        }
    }

    cout << cnt << '\n';

    return 0;
}

 게시 됨 업데이트 됨Algorithm / BOJ1분안에 읽기 (약 204 단어)

<5014> 스타트링크

문제 : https://www.acmicpc.net/problem/5014

BFS를 사용해 쉽게 해결할 수 있습니다. 다만 if 문에서 visit 배열로 층의 방문 여부를 체크하기전에 배열의 index가 유효한 범위에 속해있는지 확인을 먼저해주어야 합니다.

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
#include <iostream>
#include <queue>
#include <vector>

#define MAX_SIZE 1000001
using namespace std;

bool visit[MAX_SIZE];
int cnt[MAX_SIZE];

int main() {
    int f, s, g, u, d; // 전체 층, 현재 층, 목표 층, 업 층, 다운 층
    cin >> f >> s >> g >> u >> d;

    queue<int> q; // 층수
    visit[s] = true;
    cnt[s] = 0;
    q.push(s);

    while(!q.empty()) {
        int now_floor = q.front();
        int now_cnt = cnt[now_floor];
        q.pop();

        int next1 = now_floor + u;
        int next2 = now_floor - d;

        if (next1 < MAX_SIZE && visit[next1] == false) {
            q.push(next1);
            visit[next1] = true;
            cnt[next1] = now_cnt + 1;
        }

        if (next2 > 0 && visit[next2] == false)  {
            q.push(next2);
            visit[next2] = true;
            cnt[next2] = now_cnt + 1;
        }
    }

    if (visit[g] == true) {
        cout << cnt[g] << '\n';
    } else {
        cout << "use the stairs" << '\n';
    }

    return 0;
}

 게시 됨 업데이트 됨Algorithm / BOJ1분안에 읽기 (약 165 단어)

<14501> 퇴사

문제 : https://www.acmicpc.net/problem/14501

N의 범위가 최대 15로, 작은 경우에 속해서 완전 탐색을 했습니다. 상담을 하는 경우와 하지 않는 경우를 나누어 해결합니다.
상담이 필요한 기간에 당일 부터 포함되는 것만 주의하여 범위를 계산하면 될 것 같습니다

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
#include <iostream>
#include <algorithm>

#define MAX_SIZE 16

using namespace std;

int day[MAX_SIZE];
int pay[MAX_SIZE];
int n;

int sum = 0;

void go(int d, int s) {
    if (d == n + 1) {
        sum = max(sum, s);
        return;
    }

    if (d + day[d] <= n + 1) {
        go(d + day[d], s + pay[d]);
    }
    if (d + 1 <= n + 1) {
        go(d + 1, s);
    }
}

int main(void) {
    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> day[i] >> pay[i];
    }

    go(1, 0);

    cout << sum << '\n';

    return 0;
}
 게시 됨 업데이트 됨Programming / Node14분안에 읽기 (약 2107 단어)

Android In-App Purchase Validation

얼마전 아랍어 번역을 마치고 몇개 국가에 앱을 출시하게 되면서 결제 관련 문제가 발생하기 시작했습니다. 앱과 서버의 결제 관련 코드를 모두 제가 맡아 작성했기 때문에 계속해서 발생하는 문제로 인해 정신적 충격이 상당했습니다…

“Android In-App Billing 보안 완벽 정리”의 글을 참고해 결국에는 앱내 구매(In-App Billing)시 프리덤(Freedom)과 같은 **결제 해킹 앱**에 의해 문제가 발생하게 된다는것을 알게 되었습니다.

이에 서버에서 **In-App Purchase Validation(앱내 구매 유효성 검사)**을 하는 코드를 추가했고 위의 문제를 해결할 수 있었습니다. 이번 포스팅에서는 In-App Purchase Validation에 대해서 알아보겠습니다. (In-App 결제 구현에 대한 내용은 다루지 않습니다!)

어떤 문제가 발생했는가?

어느날 이상한일이 벌어졌다. 분명 Admin을 통해 앱에서 결제한 내용을 확인했을때는 상당한 내역이 있었는데, Google Play Console의 주문 관리를 통해 확인했을 때는 결제 내역이 없는 것이다.

결제 관련된 부분에서 버그가 발생했기에 무척이나 마음이 심란했다. 반복되는 테스트에서도 재현할 수 없는 현상에 라이브 채팅을 통해 Google에 문의하였지만 돌아오는 답변은 사용자의 결제 관련 설정(예를들면 카드)이 잘못되어 있을 것이라는 말뿐, 정확한 해결 방법을 알려주지 않았다.

그러던 도중 결제 관련 DB를 살펴보다가 이상한 부분을 발견했다.

비정상적인 연속된 결제 내역

**한명의 사람이 말도 안되는 짧은 시간에 한 품목을 여러변 결제한 것이다. 그리고 이 결제 관련 내용은 Google Play Console의 주문 관리에서도 확인이 불가능했다. (기록이 남지 않았다.) **

결국 글의 도입부에서 말씀드렸던 것처럼 결제 해킹 문제임을 알게되었고 In-App Purchase Validation에 대해 알아보게 되었습니다.

Subscriptions and In-App Purchases API

Google에서는 **Subscriptions and In-App Purchases API**를 제공하고 있습니다. (전에는 이 API를 “Purchase Status API” 라고 불렀습니다.)

Document를 참고하면 해당 API를 인앱 상품과 구독으로 구성된 앱의 카탈로그를 관리할 수 있으며, 개별 구매에 대한 정보, 구매와 구독의 만료 확인 등, 여러 가지 용도로 사용할 수 있음을 알 수 있습니다.

따라서 실제 결제가 이루어졌고, Google Play Console의 주문 관리에 그 내역이 있는지 확인이 가능한 것입니다. 해당 API는 Google Play Developer API로서 허용되는 사용 할당량이 매일 200,000개의 요청으로 제한됩니다. 이 정도면 충분한 구독, 결제 유효성 검사 요구를 충족시킬 수 있으며, 만약 더 많은 요청이 필요하다면 Google Developer Console에서 요청할 수 있다고 합니다.

API 사용을 위한 서비스 계정 연결

API를 사용하기 위해서는 Google Developer Console에서 서비스 계정을 생성한 후 API 엑세스 권한을 부여해주어야 합니다. 몇가지 단계를 거쳐야 하는데 같이 해보겠습니다.

1.Google Play Console에 관리자 계정으로 로그인합니다.

2.설정 - API 액세스로 이동합니다. (서비스 약관은 수락합니다.)

3.새 프로젝트 만들기 후 하단의 서비스 계정 만들기를 선택합니다.

4.Google API 콘솔로 이동합니다.

5.서비스 계정 만들기를 선택한 후 다음과 같이 내용을 입력합니다.

6.서비스 계정을 생성하면 자동으로 .json 파일이 다운로드 됩니다. .json 파일에는 API 호출을 위한 인증 정보가 포함되어 있습니다. 관리 및 백업이 필요합니다.

7.Google Play Console로 돌아와, 완료 버튼을 클릭한 후 서비스 계정이 생성되었는지 확인합니다.

8.엑세스 권한 부여를 클릭합니다.

9.역할을 금융으로 선택한 후, 재무 데이터 보기 권한을 설정합니다.
(구매내역 및 영수증 검증을 하기 위해서는 재무 보고서 보기 권한이 필요합니다 . 역할을 금융으로 선택해 주면 해당 권한이 자동으로 선택됩니다. 영수증 검증을 위해서는 금융 역할을 갖는 서비스 계정이 필요합니다.)

API 사용하기 (With node-iap)

복잡하게 토큰을 관리하며 HTTP/REST API를 사용할것 없이 Google은 다양한 언어에 맞게 Client 라이브러리를 제공하고 있습니다. Access Google APIs more easily를 통해서 다양한 언어의 라이브러리를 찾아 사용할 수 있습니다.

google-api-nodejs-client를 사용하면 되지만, **다른 Platform(apple)**에도 대응할 수 있는 node-iap(In-app purchase verification for Apple App Store and Google Play)를 사용하겠습니다.

사용방법은 생각보다 정말 간단합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const iap = require('iap');

let platform = 'google';
let payment = {
	receipt: 'receipt data', // always required (purchaseToken)
	productId: 'abc',
	packageName: 'my.app',
	keyObject: '', // always required (user auth key)
	subscription: false,	// optional, if google play subscription
};

iap.verifyPayment(platform, payment, function (error, response) {
	/* your code */
});

node-iap는 google과 apple에서 모두 사용가능하기 때문에 platform을 명시해야 합니다. payment에는 확인하고자 하는 인앱결제 내역을 넣습니다.

Android In-App 결제를 하고나면 **purchaseToken**과 **productId**를 알 수 있습니다. payment의 receipt에는 purchaseToken 값을 넣습니다. productId와 packageName을 넣고 **KeyObject**에는 좀전에 사용자 계정을 추가하면서 다운로드 받았던 .json 파일의 값을 넣어주면 됩니다. (require 혹은 import하여 그대로 넣어주면 됩니다.)

Android 단말을 통해 테스트 결제 후 iap를 통해 purchase validation을 하면 다음과 같은 response를 얻을 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
{
        "receipt": {
                "kind": "androidpublisher#productPurchase",
                "purchaseTimeMillis": "1410835105408",
                "purchaseState": 1,
                "consumptionState": 1,
                "developerPayload": ""
        },
        "transactionId": "ghbbkjheodjokkipdmlkjajn.AO-J1OwfrtpJd2fkzzZqv7i107yPmaUD9Vauf9g5evoqbIVzdOGYyJTSEMhSTGFkCOzGtWccxe17dtbS1c16M2OryJZPJ3z-eYhEJYiSLHxEZLnUJ8yfBmI",
        "productId": "abc",
        "platform": "google"
}

여기서 중요한 부분은 **purchaseState**의 값이 **0**이면 결제가 완료된 상태를 뜻하며 **1**이면 환불이 완료된 상태를 의미합니다.

만약 사용자가 제대로 된 결제를 하지 않는다면 purchaseToken 값은 유효하지 않아 purchase validation 과정에서 err가 발생할 것입니다.

마치며

굉장히 큰 문제라고 생각했지만 생각보다 조치하는 과정에 있어서 큰 어려움은 없었습니다. 아직 제가 더 생각하지 못한 부분이 있을수도 있을거라 생각합니다. 혹시나 더 추가해야 하는 부분이 있다면 알려주세요!

저는 추가적으로 가짜 결제를 시도하는 유저들의 로그를 DB에 남기고 자동으로 block 처리를 해 게임을 못하도록 막았습니다. purchase validation 구현 후 바로 다음날 다시 또 가짜 결제가 이루어졌는데 유효성 검사가 제대로 이루어지는 것을 보고 정말 다행이라 생각했습니다.

제가 지금까지 회사에서 일하며 발생했던 가장 크리티컬했던 부분이라고 생각하는데 혹시나 이 글을 읽으시는 분중 아직 purchase validation을 하지 않고 계시다면 지금이라도 꼭 코드를 추가하셨으면 합니다.

참고

팔로우

카테고리

최근 글

광고

×