백준저지 1300번 문제 "K번째 수" 문제 풀이입니다.

https://www.acmicpc.net/problem/1300

 

1300번: K번째 수

첫째 줄에 배열의 크기 N이 주어진다. N은 105보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(109, n2)보다 작거나 같은 자연수이다.

www.acmicpc.net

 

바이너리 서치로 풀이하였습니다.

 

N이 주어졌을 때, 특정 수 x보다 작거나 같은 수의 개수를 O(N)만에 계산할 수 있는데, 이를 이용하여

x보다 작거나 같은 수의 개수가 K와 비슷해질때까지 바이너리 서치를 합니다.

 

x보다 작거나 같은 수의 개수를 num(x) 라 할 때

 

바이너리 서치와 약간 다른 점은, K와 완전히 같은 num(x)가 존재하지 않을 수 있습니다.

 

따라서 K보다 큰 num(x) 중 최소 값을 갖는 x를 구해야 하며, num(x) == num(x+1) == ... == num(x+a) 와 같이 같은 값들을 가지는 num(x)들이 있을 수 있습니다. 이들 중에서는 가장 작은 x값이 정답이 됩니다.

 

num(x) == num(x+1) == ... == num(x+a)와 같은 관계에서는 x는 실제 N*N 매트릭스에 존재하는 값이지만, x+1은 존재하지 않는 값이기 때문입니다.

 

코드는 아래와 같습니다.

 

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll num(ll v, ll N) {
    ll ret = 0;
    //v보다 작거나 같은 원소 개수를 리턴함
    for (int i = 1; i <= N; i++) {
        ret += min(N, v / i);
    }
    return ret;
}
ll solve(ll N, ll K) {
    //binary search 할 예정인데
    // K보다 크거나 같은 값 중 최소 값 구할 예정. (중복 수 있을 수 있으므로)
    // K와 같은 값이면 그중에 가장 작은 값
    ll l = 1, r = N*N;
    while (l < r) {
        ll m = (l + r) / 2;
        long long n = num(m, N);
        if (n == K) {
            ll v = m - 1;
            while (n == num(v, N)) {
                v--;
            }
            r = v + 1;
            break;
        }
        else if (n > K) {
            r = m;
        }
        else if (n < K) {
            l = m + 1;
        }
    }
    return r;
}

int main() {
    ll N, K; cin >> N >> K;
    cout << solve(N, K) << endl;

    return 0;
}

C++

'알고리즘 & Problem Solving' 카테고리의 다른 글

백준 1006번 습격자 초라기 문제 풀이  (0) 2019.04.19
백준저지 9465번 스티커 문제 풀이  (0) 2019.04.19
Google code jam 2019 Qualification Round 후기  (0) 2019.04.07
백준 17135번 캐슬 디펜스 문제 풀이  (1) 2019.04.06
전처리문을 이용한 printf 함수들 한꺼번에 소거하기 (가변인자 매크로)  (0) 2019.03.21

구글 코드잼 2019년도 예선전 후기다. 간단하게 작성해보고자 한다.

 

방금 글 쓰다가 한번 날아가서 조금 대충쓰고 싶어졌다.

 

 

퀄리피케이션 라운드는 절대평가(30점)에다가 27시간동안이나 대회를 하므로 간단하게 풀어버리고

약속에 가려고 했으나, 현실은 약속시간 내내 3번째 문제 솔루션을 생각했다.

 

가볍게 첫번째 문제 Foregone Solution 문제를 보았다. 히든케이스 10^100를 커버하기 위해 익숙하지 않은

파이썬으로 해결했다.

 

모든 4를 3으로 바꾸어 버리는 식으로 코드를 짰다.

 

tc=int(input())

def solve(n):
    a=int(str(n).replace('4', '3'))
    b=n-a
    return str(a) + " " + str(b)
for t in range(1, tc+1):
    n=int(input())
    ans=solve(n)
    print ("Case #" + str(t) + ": " + ans)
Python

 

두번째 문제 You can go your own way

 

대충 문제 읽어보니까 솔루션이 떠올랐는데, 너무 간단해서 함정이 있나 조금 생각했다. E와 S를 서로 바꾸어주면 간단히 해결된다.

요녀석은 빅인티저같은게 필요가 없어서 주력언어인 C++로 작성했다.

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    int tc;
    scanf("%d", &tc);
    for (int t=1; t<=tc; t++) {
        int n; scanf("%d", &n);
        string s;
        cin >> s;
        printf("Case #%d: ", t);
        for (size_t i=0; i < s.length(); i++) {
            if (s[i] == 'S') putchar('E');
            else putchar('S');
        }
        putchar('\n');
    }
	return 0;
}


C++

 

 

세번째 문제, 욕심부리다가 엄청 오랫동안 생각했다.

간단하게 gcd를 구해서 하면 될 거라 생각했는데, 같은 숫자가 나오는 것을 간과했어서  WA를 엄청나게 뿜었다.

파이썬으로 제출한 것은 RE도 자주나왔다. 이유는 아직도 모르겠다..

 

원문이 AAA ABA 형식으로 나오게 되면, 인접한 cipher int value 가 동일한 값이 나오기 때문에 그냥 gcd를 구하면 1이 나오게 된다.

이 점을 유의해야 한다는 것을 까먹었다.

 

Runtime Error 때문에 C++로 솔루션을 작성해 보고, 후에 Python 으로 바꾸어서 히든케이스를 대비했다.

 

사용된 소수들은 인접 값이 다를때만 gcd로 죄다 구하면 되고, 해독할때는 소수 하나만 찾아내서 양옆으로 propagation 시키면 됬던 풀이이다.

 

일단 씨쁠쁠 풀이이다.

 

#include <bits/stdc++.h>
using namespace std;

int N, L;  
int plainValue[105];

int main() {
    int tc; cin >> tc;
    for (int t=1; t<=tc; t++) {
        memset(plainValue, 0, sizeof(plainValue));
        cin >> N >> L;
        vector<int> ciphers;
        set<int> primes;
        map<int, char> int2char;
        map<char, int> char2int;
        ciphers.clear();
        primes.clear();
        int2char.clear();
        char2int.clear();
        for (int i=0; i < L; i++) {
            int tmp; cin >> tmp;
            ciphers.push_back(tmp);
        }
        for (int i=0; i< L-1; i++) {
            if (ciphers[i] != ciphers[i+1]) {
                int cd = __gcd(ciphers[i], ciphers[i+1]);
                primes.insert(cd);
                primes.insert(ciphers[i]/cd);
                primes.insert(ciphers[i+1]/cd);
            }
        }
        char c = 'A';
        for (auto& p : primes) {
            if (int2char.find(p) == int2char.end()) {
                char2int[c] = p;
                int2char[p] = c++;
            }
        }
        
        int idx, pval, ppval;
        for (idx=0; idx < L-1; idx++) {
            if (ciphers[idx] != ciphers[idx+1]) {
                int cd = __gcd(ciphers[idx], ciphers[idx+1]);
                plainValue[idx+1] = cd;
                pval = ciphers[idx+1] / cd;
                ppval = ciphers[idx] / cd;
                break;
            }
        }
        
        
        for (int i=idx; i >= 1; i--) {
            plainValue[i] = ppval;
            ppval = ciphers[i-1] / ppval;
        }
        plainValue[0] = ppval;
        
        for (int i=idx+2; i < L; i++) {
            plainValue[i] = pval;
            pval = ciphers[i] / pval;
        }
        plainValue[L] = pval;
        
        printf("Case #%d: ", t);
        for (int i=0; i <= L; i++) {
            putchar(int2char[plainValue[i]]);
        }
        putchar('\n');
    }
}
C++

 

이렇게 짠 녀석을 그대로 파이썬으로 옮기면 히든케이스도 커버할 수 있다.

 

def gcd(x,y):
    while(y):
        x,y=y,x%y
    return x
    
def make_unique(l):
    t = []
    for v in l:
        if len(t)==0 or t[-1] != v:
            t.append(v)
    return t
   
tc=int(input())
for t in range(1, tc+1):
    plainValue = [0 for i in range(0, 110)]
    N, L = map(int, input().split(' '))
    ciphers = list(map(int, input().split(' ')))
    primes = []
    int2char = {}
    
    for i in range(0, L-1):
        if ciphers[i] != ciphers[i+1]:
            cd = gcd(ciphers[i], ciphers[i+1])
            primes.append(cd)
            primes.append(ciphers[i]//cd)
            primes.append(ciphers[i+1]//cd)
            
    primes.sort()
    primes = make_unique(primes)
    c = 'A'
    for p in primes:
        if int2char.get(p) == None:
            int2char[p] = c
            c = chr(ord(c) + 1)
            
    idx = 0
    pval = 0
    ppval = 0
    
    for idx in range(0, L-1):
        if ciphers[idx] != ciphers[idx+1]:
            cd = gcd(ciphers[idx], ciphers[idx+1])
            plainValue[idx+1] = cd
            pval = ciphers[idx+1] // cd
            ppval = ciphers[idx] // cd
            break
    
    for i in range(idx, 0, -1):
        plainValue[i] = ppval
        ppval = ciphers[i-1] // ppval
    plainValue[0] = ppval
    
    for i in range(idx+2, L):
        plainValue[i] = pval
        pval = ciphers[i]  // pval
    plainValue[L] = pval
    
    
    ans = ""
    for i in range(0, L+1):
        ans += int2char[plainValue[i]]
    print ("Case #" + str(t) + ": " + ans)
Python

 

마지막 문제의 경우는 아직 풀지를 못했는데, 나중에 여유가 되면 한번 풀어보고 올려보도록 하겠다.

'알고리즘 & Problem Solving' 카테고리의 다른 글

백준저지 9465번 스티커 문제 풀이  (0) 2019.04.19
백준 1300번 문제 K번째 수 풀이  (0) 2019.04.16
백준 17135번 캐슬 디펜스 문제 풀이  (1) 2019.04.06
전처리문을 이용한 printf 함수들 한꺼번에 소거하기 (가변인자 매크로)  (0) 2019.03.21
백준 3090번 차이를 최소로 문제 풀이  (0) 2019.03.21

백준 17135번 문제 캐슬 디펜스 문제 풀이입니다.

https://www.acmicpc.net/problem/17135

 

17135번: 캐슬 디펜스

첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다.

www.acmicpc.net

N, M, D값이 크지 않으므로, 하나하나 다 따라가는 시뮬레이션 방식으로 풀이하면 됩니다.

 

test(a,b,c) 함수는 궁수의 위치가 각각 (N, a) (N, b) (N, c)일때 최대로 잡을 수 있는 적의 수를 리턴합니다.

 

choose_turn 함수는 각각의 턴마다 각각의 궁수가 공격할 적의 위치를 set에 추가합니다.

 

 

#include <bits/stdc++.h>
using namespace std;

int N, M, D;
int field[16][16];
typedef struct _Pos {
    int x, y;
    bool operator<(const struct _Pos& rhs) const {
        return x != rhs.x ? x < rhs.x : y < rhs.y;
    }
} Pos;
inline int dist(int x1, int y1, int x2, int y2) {
    return abs(x1-x2) + abs(y1-y2);
}
inline int dist(Pos p1, Pos p2) {
    return abs(p1.x - p2.x) + abs(p1.y - p2.y);
}
void choose_target(int mmap[][16], set<Pos>& kset, int turn, int archer_pos) {
    Pos archer = { N, archer_pos };
    Pos vic_pos = { 1000, 1000 };
    int pd = dist(archer, vic_pos); //previous dist
    for (int i=0; i< N - turn; i++) {
        for (int j=0; j < M; j++) {
            if (mmap[i][j] == 0) continue;
            Pos epos = { i + turn, j };
            int d = dist(archer, epos);
            if (d <= D) {
                if (d < pd || (d == pd && epos.y < vic_pos.y)) {
                    pd = d;
                    vic_pos = epos;
                }
            }
        }
    }
    if (vic_pos.x != 1000) kset.insert({ vic_pos.x - turn, vic_pos.y });
}
int test(int a, int b, int c) {
    //archer pos = (N, a) (N, b) (N, c)
    int kill = 0; //ret val
    int mmap[16][16];
    for (int i=0; i < N; i++)
        for (int j=0; j < M; j++)
            mmap[i][j] = field[i][j];
    
    set<Pos> kill_set;
    kill_set.clear();
    for (int t=0; t < N; t++) {
        //for each turn
        choose_target(mmap, kill_set, t, a);
        choose_target(mmap, kill_set, t, b);
        choose_target(mmap, kill_set, t, c);
        kill += (int)kill_set.size();
        for (auto& v : kill_set) {
            mmap[v.x][v.y] = 0;
        }
        kill_set.clear();
    }
    return kill;
}
int main() {
    cin >> N >> M >> D;
    for (int i=0; i < N; i++)
        for (int j=0; j < M; j++)
            cin >> field[i][j];
    
    int ans = 0;
    for (int i=0; i < M-2; i++) 
        for (int j=i+1; j < M-1; j++)
            for (int k=j+1; k < M; k++)
                ans = max(ans, test(i,j,k));
            
    cout << ans << endl;
	return 0;
}



C++

'알고리즘 & Problem Solving' 카테고리의 다른 글

백준 1300번 문제 K번째 수 풀이  (0) 2019.04.16
Google code jam 2019 Qualification Round 후기  (0) 2019.04.07
전처리문을 이용한 printf 함수들 한꺼번에 소거하기 (가변인자 매크로)  (0) 2019.03.21
백준 3090번 차이를 최소로 문제 풀이  (0) 2019.03.21
백준 1261번 문제 알고스팟 풀이  (0) 2019.03.07

프로그래밍 문제를 풀다가 보면, 간혹 특정 라이브러리 함수를 사용하지 못하게 하는 경우가 있습니다.

(삼성전자 SW Expert Academy에서 보는 상시 SW 역량 테스트 B형 문제라던지...)


이러한 경우 로컬에서 디버깅을 위해서 printf 함수 등을 사용하다가 제출 할 때에는 이 함수들을 다 제거를 해야 하는데, 이러한 일들이


엄청 귀찮게 되는 경우가 있는데 이러한 귀찮음을 없애줄 수 있는 전처리문 코드를 공유합니다.




 
#ifdef WIN32
#define log(...) printf(__VA_ARGS__)
#else
#define log(...) (void)0
#endif


C++


위와 같은 코드를 소스코드 파일 상단에 추가를 해 놓으면 log라는 함수를 이용해서 printf 함수 기능을 사용할 수 있습니다.


윈도우즈 환경에서는 printf 기능이 잘 동작하게 되고, 제출을 할 경우 (일반적으로 서버는 리눅스 환경인 경우가 많으므로), log 함수들이 (void)0으로 치환


되게 되므로 아무런 동작을 하지 않게 됩니다.


아니면 제출할 경우에만 #define 구문을 상황에 맞게 주석 처리를 하면, 엄청나게 남발해놓은 printf함수를 한두줄 코드 바꾸는 것으로 모두


비활성화 하거나 활성화 할 수 있습니다.


log함수는 printf함수와 동일하게 인자를 넣어서 필요한 시기에 호출하면 됩니다.

'알고리즘 & Problem Solving' 카테고리의 다른 글

Google code jam 2019 Qualification Round 후기  (0) 2019.04.07
백준 17135번 캐슬 디펜스 문제 풀이  (1) 2019.04.06
백준 3090번 차이를 최소로 문제 풀이  (0) 2019.03.21
백준 1261번 문제 알고스팟 풀이  (0) 2019.03.07
백준 2517 달리기 문제 풀이  (0) 2018.10.27

백준저지 3090번 문제 '차이를 최소로' 문제 풀이입니다.

https://www.acmicpc.net/problem/3090


인접한 수의 최대 차이값을 c라고 할때, 이 c를 최소로 만들어야 한다.


최대값의 최소값을 바로 구하기는 힘드므로 문제를 조금 변형한다.


인접한 수의 최대 차이값을 최소로 하는 값은 무엇인가 => '인접한 수의 최대 차이값을 c 값으로 만들 수 있는가(Y/N)'



또한 만약 최대 차이값을 c값으로 만들 수 있다면, c+1 으로도 물론 만들 수 있을 것이다. 이러한 특성을 이용하여


바이너리 서치로 문제를 해결할 수 있다.




 
#include <bits/stdc++.h>
using namespace std;

#define MN 100005
int n, T;
int a[MN];
int L[MN], R[MN];
bool ok(int v) {
    R[0]=a[0];
    L[n-1]=a[n-1];
    for (int i=1;i<n;i++) R[i] = min(R[i-1]+v, a[i]);
    for (int i=n-2;i>=0;i--) L[i] = min(L[i+1]+v, a[i]);
    long long inv = 0;
    for (int i=0;i<n;i++) inv += a[i] - min(L[i],R[i]);
    return inv <= T;
}
void ans(int v) {
    R[0]=a[0];
    L[n-1]=a[n-1];
    for (int i=1;i<n;i++) R[i] = min(R[i-1]+v, a[i]);
    for (int i=n-2;i>=0;i--) L[i] = min(L[i+1]+v, a[i]);
    for (int i=0;i<n;i++) {
        int s = a[i]-min(L[i],R[i]);
        printf("%d ", a[i] - s);
    }
}
int main() {
    cin >> n >> T;
    for (int i=0; i < n; i++) {
        scanf("%d", a+i);
    }
    int l = 0, r = MN;
    while (l < r) {
        int m = (l + r) / 2;
        if (ok(m)) r = m;
        else l = m + 1;
    }
    ans(r);
}


C++



ok 함수에서 인접 수 차이 최대값이 v이도록, T번의 감소 연산으로 가능한지 여부를 리턴해준다.


main문의 while문에서 바이너리 서치를 수행하고, 인접수 차이 최대값의 최소값이 r이 되므로,


해당 값이 되도록 감소시킨 배열 값을 ans함수에서 출력해준다.


이제 여기서 T번의 감소 연산으로 가능한지 여부는 O(N)로 체크를 한다.


어차피 감소하는 연산만 가능하므로, 인접 수 차이가 c값이 되도록, 상한선을 R[i] + c 로 정하고, 다음 값이 그 값보다 작으면 그 작의 상한선이 더 낮을 예정이므로 최소값을 취하면서 좌우로 상한선을 체크한다.


더 낮은 상한선을 기준으로 그 값을 초과하는 것들을 다 감소시켜야 한다. 그 감소시켜야 하는 값들이 T 개수 보다 많다면 불가능하다.

'알고리즘 & Problem Solving' 카테고리의 다른 글

백준 17135번 캐슬 디펜스 문제 풀이  (1) 2019.04.06
전처리문을 이용한 printf 함수들 한꺼번에 소거하기 (가변인자 매크로)  (0) 2019.03.21
백준 1261번 문제 알고스팟 풀이  (0) 2019.03.07
백준 2517 달리기 문제 풀이  (0) 2018.10.27
백준 16236번 아기 상어 문제 풀이  (0) 2018.10.23

https://www.acmicpc.net/problem/1261


백준저지 1261번 문제인 알고스팟 풀이입니다.


벽을 몇개를 부숴야 하는지를 알아야 하므로, 벽을 부술 때 만 값을 1 증가시키는 식으로 BFS를 합니다.


다만, 벽을 부수지 않는 경우들을 우선적으로 처리하도록 하기 위해서 큐 대신 우선순위 큐(벽 부순 값이 낮은 것 부터 리턴하도록 Min Heap 사용)를 활용


합니다.



 
#include <iostream>
#include <queue>
#include <string>
using namespace std;

string map[101];
struct State {
	int val, x, y;
	bool operator<(const struct State& rhs) const {
		return val > rhs.val;
	}
};
const int dx[] = { +1, +0, +0, -1 };
const int dy[] = { +0, +1, -1, +0 };
bool v[101][101];
int main() {
#ifdef WIN32
	freopen("in.txt", "r", stdin);
#endif
	int M, N;
	cin >> M >> N;
	for (int i = 0; i < N; i++) {
		cin >> map[i];
	}
	priority_queue<State> pq;
	pq.push({ 0, 0, 0 });

	while (pq.size()) {
		auto cur = pq.top();
		pq.pop();
		if (cur.x == N - 1 && cur.y == M - 1) {
			cout << cur.val << endl;
			return 0;
		}
		for (int i = 0; i < 4; i++) {
			int nx = cur.x + dx[i];
			int ny = cur.y + dy[i];
			if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
			if (v[nx][ny]) continue;
			v[nx][ny] = 1;
			pq.push({ cur.val + (map[nx][ny] == '1' ? 1 : 0 ), nx, ny });
		}
	}
}


C++


두번째 풀이법으로는 비슷한 방식이나 구현이 조금 다릅니다.


벽을 부수지 않고 이동할 수 있는 공간을 하나의 큰 정점으로 그룹핑합니다. 


N, M좌표에서 먼저 큰 정점으로 만들어서 2로 마킹하고, 정점간 이동으로 BFS 탐색을 하면서 2로 마킹된 정점을 찾습니다.


정점간 이동은 벽을 하나 부수는 것과 같이 동작하므로 최소 부수는 벽의개수를 알 수 있게 됩니다.



 
#include <iostream>
#include <queue>
#include <string>
#include <vector>
#include <cstring>
using namespace std;

string map[101];
struct State {
	int val, x, y;
};
struct Pos {
	int x, y;
};
const int dx[] = { +1, +0, +0, -1 };
const int dy[] = { +0, +1, -1, +0 };
bool v[101][101];
int M, N;
vector<Pos> edges[101][101];
void bfs(int sx, int sy) {
	memset(v, 0, sizeof(v));
	queue<Pos> q;
	q.push({ sx, sy });
	v[sx][sy] = 1;
	while (q.size()) {
		auto c = q.front(); q.pop();
		if ((map[c.x][c.y] == '1' || map[c.x][c.y] == '2') && !(c.x == sx && c.y == sy)) {
			edges[sx][sy].push_back({ c.x, c.y });
		}
		else {
			for (int i = 0; i < 4; i++) {
				int nx = c.x + dx[i];
				int ny = c.y + dy[i];
				if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
				if (v[nx][ny]) continue;
				v[nx][ny] = 1;
				q.push({ nx, ny });
			}
		}
	}
}
void dfs(int x, int y) {
	v[x][y] = 1;
	map[x][y] = '2';
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
		if (v[nx][ny]) continue;
		if (map[nx][ny] == '1') {
			continue;
		}
		map[nx][ny] = '2';
		dfs(nx, ny);
	}
}
int main() {
#ifdef WIN32
	freopen("in.txt", "r", stdin);
#endif

	cin >> M >> N;
	for (int i = 0; i < N; i++) {
		cin >> map[i];
	}

	dfs(N - 1, M - 1);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			bfs(i, j);
		}
	}
	memset(v, 0, sizeof(v));
	
	queue<State> q;
	q.push({ 0, 0, 0 });
	v[0][0] = 1;
	if (map[0][0] == '2') {
		cout << 0 << endl;
		return 0;
	}

	while (q.size()) {
		auto c = q.front(); q.pop();
		for (auto n : edges[c.x][c.y]) {
			if (v[n.x][n.y]) continue;
			v[n.x][n.y] = 1;
			if (map[n.x][n.y] == '2') {
				cout << c.val << endl;
				return 0;
			}
			q.push({ c.val + 1, n.x, n.y });
		}
	}
	
}


C++


'알고리즘 & Problem Solving' 카테고리의 다른 글

전처리문을 이용한 printf 함수들 한꺼번에 소거하기 (가변인자 매크로)  (0) 2019.03.21
백준 3090번 차이를 최소로 문제 풀이  (0) 2019.03.21
백준 2517 달리기 문제 풀이  (0) 2018.10.27
백준 16236번 아기 상어 문제 풀이  (0) 2018.10.23
백준 16235번 나무 재테크 문제 풀이  (2) 2018.10.22

pwnable.kr의 Toddler's Bottle 문제 중 input 문제를 풀려고 하였었다.

 

제공된 input.c의 소스 코드 중,

 

if (strcmp(argv['A'], "\x00")) return 0;

 

라는 부분이 있었는데, 이를 python process 생성 API를 이용하여 인자를 넘겨주려고 했다.

 

os.system, subprocess.Popen, subprocess.run 등의 API를 이용할 수 있었는데, \x00 의 NULL 바이트를 인자로 넘겨주자 항상 에러가 났다.

 

그래서 다른사람이 작성한 write up을 확인해보니 pwntools의 process API를 이용하여 풀이를 하였는데, 거기서는 NULL 바이트를 인자로 주어도 아무런 상관이 없었다.

 

그래서 궁금증이 발동한 나는 pwntools의 process API를 한번 확인해 보았다.

 

process.py 코드 링크는 다음과 같다.

 

https://github.com/Gallopsled/pwntools/blob/dev/pwnlib/tubes/process.py

https://raw.githubusercontent.com/Gallopsled/pwntools/dev/pwnlib/tubes/process.py

 

process class를 정의해서 사용하고 있는데, 생성자인 __init__ 부분을 확인해보니, subprocess.Popen()을 이용해서 프로세스를 생성하는 것을 확인할 수 있었다.

 

그런데 어떤 차이가 있길래 NULL Byte Argument를 넘겨주어도 잘 실행이 되는가 싶어서, Popen 실행하기 직전의 Argument 리스트를 찍어보니, "\x00"인 NULL Character included string을 ""인 Empty String으로 치환되어 Popen API 인자로 넘어가는 것을 확인할 수 있었다.

 

확인해보니 _validate 함수에서 해당 처리를 하는데, 각각인자의 rstrip("\x00")를 하는 과정에서 사라진 것이다.

 

뭐 다시 생각을 해 보면, C로 작성한 바이너리에서 main 함수의 argc, argv중 argv는 NULL terminated string들이고,

 

if (strcmp(argv['A'], "\x00")) return 0;

 

 

위 코드를 Pass하기에 단지 Empty string이기만 해도 strcmp 리턴값이 0이 될 것이긴 하다.

 

어쨋거나 이러한 삽질을 통해서 뭔가 잊고 있떤 사실을 하나 알게 되긴 하였다.

 

고로 subprocess.Popen과 같은 파이썬 API로 호출해서 pkr input 문제를 풀려면 'A' 번째 인자는 Empty string만 넣어도 된다는 것.

 

그리고 pwntools는 위대하다.

'해킹 & 보안' 카테고리의 다른 글

버프슈트 설정하기 (Burp suite configuration)  (0) 2019.06.18
[Lord of SQL Injection] Level 7 Orge 풀이  (0) 2019.05.17
[번역] 정보 보안 직종에 종사하고 싶은 사람에게 by Ivan Fratric (2)  (0) 2018.02.23
[번역] 정보 보안 직종에 종사하고 싶은 사람에게 by Ivan Fratric (1)  (0) 2018.02.22
백준저지에서 어셈블리어로 문제 풀기  (0) 2018.01.28

원문 URL

https://developer.apple.com/library/archive/referencelibrary/GettingStarted/DevelopiOSAppsSwift/index.html#//apple_ref/doc/uid/TP40015214-CH2-SW1


원문을 번역한 글입니다.


시작합시다


각각의 강의는 튜토리얼과 앱을 만들기 위해 알아야 하는 개념들이 포함되어 있습니다.

강의는 당신이 간단한 실제 iOS 앱을 만들기 위한 프로세스들을 차근차근 하나씩 알려줍니다.

당신이 강의를 따라서 앱을 만드는 동안, iOS 앱 개발의 개념들을 배우게 되고, 스위프트 언어에 대한 깊은 이해를 얻을 수 있으며, Apple의 IDE인 Xcode의 다양하고 유용한 기능들에 익숙해지게 될 것입니다.


강의 전에 알아야 할 사항들

이 강의에서는, 당신이 스위프트 언어에 익숙하다고 가정합니다. 강의를 잘 따라오기 위해서 스위프트의 마스터가 될 필요는 없지만 당신이 스위프트 언어를 쉽게 읽고 이해할 수 있다면, 이 강의에서 좀 더 많은 것을 가져갈 수 있을 것입니다.

당신이 만약 아직 스위프트언어가 익숙하지 않다면, 스위프트 운동장 앱에서 코드 연습(Code Exercise)들을 끝내고오세요. 또는 "The Swift Programming Language (Swift 3)"를 통해서 스위프트를 경험하고 오는것도 괜찮습니다. 위 두 방법들은 스위프트 언어의 기본기를 잘 다져줄 것입니다.


강의에 대해서

이 강의에서, 당신은 간단한 FoodTracker라고 불리는 식단 기록 앱을 만들것입니다. 이 앱은 음식의 이름, 점수, 사진을 포함한 음식 리스트를 보여줍니다. 사용자는 음식들에 대해서 추가, 삭제, 수정을 할 수 있습니다. 새로 추가를 하거나, 존재하는 앱을 수정하기위해서 사용자는 다른 화면으로 이동하여 특정 음식의 이름과 점수, 사진을 설정할 수 있습니다.


image: ../Art/IN_sim_navbar_2x.png

강의들은 Xcode 프로젝트로 진행되며, 강의가 끝날 때 완성물은 위와 같이 생길 예정입니다.

강의가 진행 된 뒤, 당신은 프로젝트를 다운받아서 직접 만든 코드와 비교할 수 있습니다.

당신이 강의를 진행하는 동안 배웠던 개념들을 다시 확인해야 하는 경우, 용어사전(Glossary)을 이용하세요.

용어사전에 있는 용어들은 강의들에 링크되어 있습니다.


개발 도구 구하기

iOS 앱을 개발하기 위해서, 이 강의에서는 최신버전의 기술을 사용할 것입니다. 일단 Mac 컴퓨터(macOS 10.11.5 또는 그 이후 버전)가 필요하고, 최신버전의 Xcode가 구동되어야 합니다. Xcode는 당신이 설계, 개발, 디버그 하는데 필요한 모든 기능들을 가지고 있습니다. Xcode는 또한 iOS SDK를 포함하며, 이 SDK는 Xcode가 iOS 개발을 위해 필요한 도구들과 컴파일러 및 프레임워크들을 확장해줍니다.

당신의 Mac 컴퓨터의 App Store에서 최신 버전의 Xcode를 무료로 다운받으세요.


최신 버전의 Xcode를 다운로드 받기 위해서

  1. 당신의 Mac 컴퓨터에서 App Store를 여세요(Dock에 기본적으로 있습니다.)

  2. 오른쪽 위에 있는 검색 필드에, Xcode라고 입력한 뒤 리턴 키(엔터 키)를 누르세요.

  3. Xcode 앱이 검색 결과 첫번째 창에 나타날 것입니다.

  4. Install App을 눌러서 Xcode를 다운받으세요.

  5. Apple ID와 패스워드를 입력하세요. Xcode는 /Applications 디렉토리에 다운받아질 것입니다.


--------------------------------------------------------------------
원문입니다.

Jump Right In

Start Developing iOS Apps (Swift) is the perfect starting point for learning to create apps that run on iPhone and iPad. View this set of incremental lessons as a guided introduction to building your first app—including the tools, major concepts, and best practices that will ease your path.

Each lesson contains a tutorial and the conceptual information you need to complete it. The lessons build on each other, walking you through a step-by-step process of creating a simple, real-world iOS app.

As you make your way through the lessons and build the app, you’ll learn about concepts in iOS app development, gain a deeper understanding of the Swift programming language, and familiarize yourself with the many valuable features of Xcode, Apple’s integrated development environment (IDE).

Prerequisites

In these lessons, it is assumed that you are familiar with the Swift programming language. You do not need to be a Swift master to complete the lessons, but you will get more out of the lessons if you can comfortably read and understand Swift code.

If you are not yet comfortable with Swift, complete the Learn to Code exercises in the Swift Playgrounds app. Alternatively, you can work through A Swift Tour from The Swift Programming Language (Swift 3). Both give you a solid foundation in the Swift programming language.

About the Lessons

In these lessons, you’ll be building a simple meal-tracking app called FoodTracker. This app shows a list of meals, including a meal name, rating, and photo. A user can add, remove, or edit a meal. To add a new meal or edit an existing one, users navigate to a different screen where they can specify a name, rating, and photo for a particular meal.

image: ../Art/IN_sim_navbar_2x.png

The lessons are each accompanied by an Xcode project file that shows an example of how your code and interface should look at the end of the lesson. After you go through a lesson, you can download the project and check your work against it.

If you need to refer to the concepts you’ve learned throughout the lessons, use the glossary to refresh your memory. Glossary terms are linked throughout the lessons.

Get the Tools

To develop iOS apps using the latest technologies described in these lessons, you need a Mac computer (macOS 10.11.5 or later) running the latest version of Xcode. Xcode includes all the features you need to design, develop, and debug an app. Xcode also contains the iOS SDK, which extends Xcode to include the tools, compilers, and frameworks you need specifically for iOS development.

Download the latest version of Xcode on your Mac free from the App Store.

To download the latest version of Xcode

  1. Open the App Store app on your Mac (by default it’s in the Dock).

  2. In the search field in the top-right corner, type Xcode and press the Return key.

    The Xcode app shows up as the first search result.

  3. Click Get and then click Install App.

  4. Enter your Apple ID and password when prompted.

    Xcode is downloaded into your /Applications directory.

Let’s get started!


'개발 & CS 지식' 카테고리의 다른 글

HLS를 이용한 라이브 라디오 방송 웹 앱 개발기 (4)  (0) 2019.07.17
HLS를 이용한 라이브 라디오 방송 웹 앱 개발기 (3)  (0) 2019.07.17
Node.js Async 이용하여 콜백 함수 풀어내기  (0) 2018.06.23
Node.js에 대하여  (0) 2018.04.21
HLS를 이용한 라이브 라디오 방송 웹 앱 개발기 (2)  (3) 2018.02.25

본 문서는 다음 링크의 문서를 번역한 것입니다.

https://docs.microsoft.com/ko-kr/windows-hardware/drivers/print/print-spooler-architecture


틀린 번역이나 어색한 표현이 있을 수 있습니다.


[번역]

프린트 스풀러 아키텍쳐


윈도우 2000버전과 그 이후버전의 프린터 스풀러는 마이크로 소프트가 제공한 것과, 밴저가 제공한 컴포넌트들로 이루어져 있습니다.

이 스풀러들은 다음 역할들을 수행합니다.


- 프린트 업무가 로컬로 처리되어야 하는지, 네트워크를 넘어서 처리되어야 하는지


- 프린터 드라이버와 함께 GDI로 부터 생성된 데이터 스트림을 받아들여서, 특정 타입의 프린터에서 출력하도록 한다.


- 스풀링이 활성화 되어 있다면, 데이터를 파일로 스풀링한다.


- 논리 프린터 큐에서 첫번째로 가용한 물리적 프린터를 고른다.


- 스풀된 포맷(EMF 와 같은)의 데이터 스트림을 프린터 하드웨어로 보낼 수 있는 데이터 형식(PCL와 같은) 형식으로 변환한다.


- 데이터 스트림을 프린터 하드웨어로 보낸다.


- 스풀러 컴포넌트와 프린터 폼을 위한 레지스트리 기반 데이터베이스를 관리한다.


- (윈도우 비스타의 경우) 프린터 서버에서 하는 것 대신, 클라이언트 컴퓨터에서 프린팅 작업을 한다. 클라이언트 사이드 랜더링은 프린터 서버의 업무 량을 줄여주고,

윈도우 비스타에서는 이 기능이 기본값으로 활성화 되어 있다.


- 윈도우 7에서 프린터 드라이버는 스풀러가 구동되는 프로세스와 다른 프로세스에서 별개로 구동 될 수 있다. 이 기능은 Printer Driver Isolation(프린터 드라이버 고립)이라고 불린다.




[원문]



Print Spooler Architecture

  • 읽는 데 2분
  • 참가자
    • Barry Golden

The Microsoft Windows 2000 and later print spooler is made up of a set of Microsoft-supplied and optional vendor-supplied components, with responsibilities that include:

  • Determining whether a print job should be handled locally or across a network.

  • Accepting a data stream created by GDI, in conjunction with a printer driver, for output on a particular type of printer.

  • Spooling the data to a file (if spooling is enabled).

  • Selecting the first available physical printer in a logical printer queue.

  • Converting a data stream from a spooled format (such as enhanced metafile (EMF)) to a format that can be sent to printer hardware (such as printer control language (PCL)).

  • Sending a data stream to printer hardware.

  • Maintaining a registry-based database for spooler components and printer forms.

  • (Windows Vista) Rendering print jobs on the client computer instead of on the print server. Client-side rendering eases the print server workload, is transparent to the print driver, and is enabled by default in Windows Vista.

  • For Windows 7, print drivers can run in a separate process from the spooler. This feature is called Printer Driver Isolation.


'팁 & 기타' 카테고리의 다른 글

Ubuntu 18.04에서 iptime A2000UA Wireless-LAN 드라이버 잡기(삽질기)  (0) 2019.06.27
쉘 코드와 쉘 스크립트의 차이(Shellcode vs Shellscript)  (0) 2019.06.25
윈도우즈 프린팅 관련 문서 번역(Introduction to Printing)  (0) 2019.01.07
간편한 한글 기반 일본어 입력기  (6) 2018.06.05
리눅스 부팅과정과 부팅시 마다 스크립트 실행(Startup Script)  (0) 2018.02.21

본 문서는 다음 링크의 문서를 번역한 것입니다.

https://docs.microsoft.com/ko-kr/windows-hardware/drivers/print/introduction-to-printing


틀린 번역이나 어색한 표현이 있을 수 있습니다.


[번역글]

프린팅 관련 설명


마이크로소프트 윈도우 프린팅 아키텍쳐는 프린트 스풀러와 프린터 드라이버들로 이루어져 있습니다.

어플리케이션은 장치의 종류와 상관없이 함수를 호출함으로서, 프린팅 잡을 만들고 그 잡을 다양한 장비로 보냅니다.

그 다양한 장비는 레이저 프린터가 될수도, 벡터 플로터가 될수도, 래스터 프린터가 될수도 있고 팩스 장비가 될 수도 있습니다.


프린터 드라이버에는 랜더링 컴포넌트와 설정 컴포넌트가 있습니다. 

랜더링 컴포넌트는 어플리케이션이 제공한 그래픽 명령어를 프린터가 이미지를 페이지에 그리는데 사용하는

데이터 포맷으로 변환시킵니다.

설정 컴포넌트는 유저 인터페이스 컴포넌트와 프로그램 인터페이스 컴포넌트가 있습니다.

유저 인터페이스 컴포넌트는 유저가 프린터에서 설정가능한 옵션들을 보여주고, 프로그램 인터페이스는 프린터의 설정값과 특징들을 어플리케이션과 소통하도록

해줍니다.


마이크로소프트    win32 gdi 어플리케이션이 프린트 할 때, 이 앱은   win32 api의 gdi 함수를 호출합니다. 이러한 함수들은  gdi 그래픽 엔진에 정보를 전달합니다.

GDI 그래픽 엔진은 그리는 명령어들을 EMF(enhanced metafile)로 스풀하거나, 프린터 드라이버와 함께 스풀러로 보낼 수 있는 프린팅 할 수 있는 이미지를 그립니다.

스풀러 컴포넌트는 EMF 파일을 해석해서, 페이지 레이아웃 정보와 작업 제어 명령을 데이터 스트림으로 변환합니다.

스풀러는 그때, 데이터 스트림을 직렬, 병렬 혹은 네트워크를 통해 관련된 타겟 프린터의 입출력 포트로 보냅니다. 게다가, XPS 장비에서 출력하면, GDI 프린트 명령어는 GDI 에서 XPS로 변환하는 컴포넌트를 통해 변환되어, 프린트 업무는 XPS 프린트 경로로 보내집니다.

XPS 프린트 경로에서는, 프린터 장비는 XPS(XML Paper Specification)을 기반으로 이루어집니다. 마이크로소프트 Win32 XPS 앱이 프린트하면, 앱은 XPS 프린트 API에 있는 XPS 함수를 호출합니다.

XPSDrv 프린터 드라이버와 함께 프린트를 하면, 스풀러는 XPS 스풀 파일을 곧바로 장비로 보내서 랜더링하고 출력하도록 합니다. XPS 파일이 GDI 장비에서 출력될때, EMF 파일은 XPS 에서 GDI로 변환하는 모듈을 통해 변환됩니다. 그러면 그때, GDI 프린트 경로로 보내지며 Win32 GDI 앱과 비슷한 방식으로 동작합니다.


WPF(Windows Presentation Foundation) 앱은 WPF 프린트 지원 함수를 호출해서 XPS 문서가 XPS 스풀 파일 포맷을 스풀러가 처리하도록 합니다. Win32 XPS 앱에서 프린팅을 할 때처럼, 스풀러가 XPSDrv 프린터 드라이버로 프린트 할 때, 스풀러는 스풀된 파일을 원본 형식으로 보내서 XPSDrv 프린터 드라이버가 프린터에서 출력하도록 합니다.스풀러가 GDI 기반을 가진 버전 3의 프린터 드라이버로 프린터 할때, 스풀러는 데이터를 XPS 스풀 파일 포맷을 EMF파일에서 GDI로 변환하는 모듈로 보냅니다.

그때 프린터를 하기 위해서 GDI 기반의 프린터로 데이터를 보냅니다. 데이터 경로에 대하여 더 많은 정보를 보기 위해서는 Windows Print Path Overview를 확인하세요.

XPS 에 대한 더 많은 정보를 확인하기 위해서는 XML Paper Specification Overview에 대하여 확인하세요.


스풀러와 드라이버 컴포넌트는 대체가능하며, 따라서 하드웨어 제조사는 쉽게 새 하드웨어에 대한 지원을 추가할 수 있습니다. 스풀러와 드라이버 컴포넌트에 대하여 더 많은 정보를 원한다면 다음 내용들을 참고하세요.


Print Spooler Architecture

Printer Driver Architecture


새로운 프린터를 사용하는 것은 일반적으로 새 데이터 파일을 만들어서 MS 지원 프린터 드라이버를 설치하는 것 만으로도 가능합니다.

MS 프린터 드라이버에 대한 더 많은 정보를 보시려면 Printer Driver Overview를 확인하세요.


마이크로소프트 범용 프린터 드라이버와 마이크로소프트 Postscript 프린터 드라이버의 동작을 커스터마이징 가능합니다. 더 많은 정보를 위해서는, Customizing Microsoft's Printer Drivers를 보세요. 프린터 스풀러도 커스터마이징이 가능합니다. 관련 정보는 Customizing Print Spooler Components를 확인하세요.


[원문]


Introduction to Printing

  • 읽는 데 2분
  • 참가자
    • Barry Golden

The Microsoft Windows printing architecture consists of a print spooler and a set of printer drivers. By calling device-independent functions, applications can create print jobs and send them to many devices. This includes laser printers, vector plotters, raster printers, and fax machines.

Printer drivers include a rendering component and a configuration component. The rendering component converts the graphics commands from the application into a data format that the printer uses to render the image on the page. The configuration component contains a user interface component that enables users to control a printer's selectable options and a program interface that communicates the printer's configuration and features to an application.

When a Microsoft Win32 GDI application prints, it calls GDI functions in the Win32 API. These functions pass the information to the GDI graphics engine. The GDI graphics engine either spools the drawing instructions as an enhanced metafile (EMF) file or, together with a printer driver, renders a printable image that can be sent to the spooler. Spooler components interpret EMF files, and they can insert page layout information and job control instructions into the data stream. The spooler then sends the data stream to the serial, parallel, or network port driver associated with the target printer's I/O port. In addition, if printing to an XPS device, the GDI print commands are converted through the GDI to XPS conversion component, and the print job is sent down the XPS print path.

In the XPS print path, printer drivers are based on the XML Paper Specification (XPS). When a Microsoft Win32 XPS application prints, the application calls XPS functions in the XPS Print API. When it prints to queues with XPSDrv printer drivers, the spooler passes the XPS spool file straight to the device for rendering and output. When the XPS file is printed to a GDI device, it is converted to an EMF file through the XPS to GDI Conversion Module. It is then sent through the GDI print path in a manner similar to Win32 GDI applications.

Windows Presentation Foundation (WPF) applications call WPF print support functions to spool XPS documents to the spooler in the XPS spool file format. As when printing from Win32 XPS applications, when the spooler prints to print queues with XPSDrv printer drivers, the spooler passes the spooled file in its original format to the XPSDrv printer driver for rendering and output to the printer. When the spooler prints to printers that have GDI-based, version 3 printer drivers, the spooler sends the data in the XPS spool file format to the GDI Conversion Module for conversion to an EMF file. It then sends the data to the GDI-based printer driver for printing. For more information about these data paths, see Windows Print Path Overview. For more information about XPS, see the XML Paper Specification Overview.

Spooler and driver components are replaceable, so hardware vendors can easily add support for new hardware. For more information about print spooler and driver components, see the following sections:

Print Spooler Architecture

Printer Driver Architecture

Support for a new printer usually requires only creating new data files for use with one of the Microsoft-supplied printer drivers. For more information about Microsoft printer drivers, see Printer Driver Overview.

You can customize the behavior of the Microsoft Universal Printer Driver and the Microsoft Postscript Printer Driver. For more information, see Customizing Microsoft's Printer Drivers. You can also customize the print spooler. For more information, see Customizing Print Spooler Components.

Other sections cover the following topics:

Terminal Server Printing

USB Printing

Bluetooth Printing

Printer Driver Testing and Debugging


'팁 & 기타' 카테고리의 다른 글

쉘 코드와 쉘 스크립트의 차이(Shellcode vs Shellscript)  (0) 2019.06.25
프린터 스풀러 아키텍쳐(Print Spooler Architecture)  (0) 2019.01.07
간편한 한글 기반 일본어 입력기  (6) 2018.06.05
리눅스 부팅과정과 부팅시 마다 스크립트 실행(Startup Script)  (0) 2018.02.21
KaTeX를 이용해서 블로그에 수학 수식 입력하기  (0) 2018.02.20

+ Recent posts

티스토리툴바