Be myself

import subprocess
import shlex

def run_command(cmd):
    p = subprocess.Popen(cmd, stdout=subprocess.PIPE)
    while True:
        output = process.stdout.readline()
        if output == '' and process.poll() is not None:
            break

        if output:
            print output
    rc = process.poll()
    return rc

def main():
    print "Catch go"
    cmd = "something"
    run_command(shlex.split(cmd))

if __name__ == '__main__':
    main()

1,2차를 운좋게 합격하고.. 3차테스트에 갔는데 약 140명? 정도 사람들이 있었던거 같다..

우선 다과나 커피등이 공짜로 무한 제공되었고 공책과 볼펜정도 받았다. 필기테스트 이후 코딩테스트를 실시했는데 필기테스트는 그냥 무난했고(전공자라면 쉽게 풀수있는 정도) 코딩테스트가 5문제정도 나왔는데.. 많이 못풀어서 카톡시험은 여기까지 인것 같다. 

카톡 2차 테스트가 rest api이용해서 서버에 값을 전달하는 간단한것 같지만 의외로 점수가 잘 안나오는 테스트부터.. 여러 새로운 시도들을 카톡이 많이 하고 있는것 같아 재밌었다. 이번 3차 테스트 문제 난이도는 단순한 구현 문제라 크게 어려운 부분은 없었지만 이상하게 틀린 테스트케이스들 4~5개 정도 때문에 풀이에 실패한 3,4번.. ㅂㄷㅂㄷ.. 5번은 자꾸 시간초과가 나서 여기서 시간을 많이 잡아 먹고..접미사 트리 이용이라는데 평소 PS를 공부하지 않아서 몰랐다. ㅠㅠ(삼성 덕분에 bfs,dfs,재귀, 완전탐색은 알고있다만..) 

비록 카톡과의 공채로 이어진 인연은 여기까지 인 것 같지만 ㅋㅋ 보안공부 한답시고 졸업할때 까지도 프로그래밍 자체에 대한 공부와 연습은 소흘히 했던 부분에 대해 반성하며.. 남은 기업들 면접에 최선을 다해야 겠구만!!

그냥 마음놓고 아무생각없이 backtracking으로 짰다가 시간초과를 맞은 문제.

처음엔 한 row마다 전부 A혹은 B로 바꾸는데 배열을 순회하며 O(W)의 시간이 걸리도록 짰지만.. 이를 더 빠르게 처리할 방법을 생각하다 포기했다가.. 알고리즘 관련 책을 뒤져보니 backtracking시 시간초과가 난다면 bitmasking을 이용하면 될 수도 있다는 문구를 보고 곰곰히 생각해봤다.

한 row를 bit로 표현하면 A, B로 바꿀때 O(1)로 줄일수 있다!!

이를 이용해 문제를 다시 풀었고 AC를 받아냄..ㅠㅠ 전체 시간은 O(w*d*3^d)

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>

#define INF 2e8
using namespace std;
int D, W, K;
int CheckArr[21];
bool Check();
int Count[1 << 13];
int solve(int row);
int main()
{
	int T;
	scanf("%d", &T);

	//bit counting
	for (int i = 0; i < (1 << 13); i++)
	{
		int z = i;
		int maxS = 0;
		int sum = 0;
		while (z != 0)
		{
			if ((z & 1) == 1)
			{
				sum += 1;
			}
			else
			{
				maxS = max(maxS, sum);
				sum = 0;
			}
			z /= 2;
		}
		maxS = max(maxS, sum);
		Count[i] = maxS;
	}

	for (int t = 1; t <= T; t++)
	{
		int ans = 0;
		memset(CheckArr, 0, sizeof(int) * 21);
		scanf("%d %d %d", &D, &W, &K);
		for (int i = 1; i <= D; i++)
		{
			for (int j = 1; j <= W; j++)
			{
				int tmp;
				scanf("%d", &tmp);
				if(tmp != 0)
					CheckArr[i] |= (1<<(W-j));
			}
		}
		
		ans = solve(1);
		printf("#%d %d\n", t, ans);
	}
	return 0;
}

int solve(int row)
{
	//기저조건 다 칠했을 때
	if (row == D + 1)
	{
		if (Check())
			return 0;
		else
			return INF;
	}

	//안칠하는 경우
	if (Check())
		return 0;
	int ans = INF;
	ans = min(ans, solve(row + 1));

	//case1 A로 바꾸는 경우
	int origin = CheckArr[row];
	CheckArr[row] = 0;
	ans = min(ans, solve(row + 1) + 1);
	CheckArr[row] = origin;

	//case2 B로 바꾸는 경우
	CheckArr[row] |= ((1 << W)-1);
	ans = min(ans, solve(row + 1) + 1);
	CheckArr[row] = origin;
	
	return ans;
}

bool Check()
{
	bool check = true;
	bool checkA = true;
	bool checkB = true;
	for (int k = 1; k <= W; k++)
	{
		int tmp = 0;
		checkA = true;
		checkB = true;
		for (int r = 1; r <= D; r++)
		{
			int current = (CheckArr[r] >> (k - 1)) & 1;
			tmp |= (current << (r-1));
		}
		
		if (Count[tmp] < K)
			checkA = false;
		
		int tmp2 = (~tmp) & ((1 << D) - 1);
		if (Count[tmp2] < K)
			checkB = false;

		if (!checkA && !checkB)
		{
			check = false;
			break;
		}
	}
	
	return check;
}

dp로 푼사람이 아무도 없어서 올려본다.

점화식을 세우면 다음과 같다

dp[s][k] = max(dp[s-X][k-1] * X) (1 <= X <= S-1)

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int S, K;
	scanf("%d %d", &S, &K);
	vector<vector<long long>> dp(S + 1, vector<long long>(K + 1));
	for (int i = 1; i <= S; i++)
	{
		dp[i][1] = i;
	}

	for (int k = 2; k <= K; k++)
	{
		for (int s = 1; s <= S; s++)
		{
			for (int x = 1; x <= s - 1; x++)
			{
				dp[s][k] = max(dp[s][k], dp[s - x][k - 1] * x);
			}
		}
	}

	printf("%lld\n", dp[S][K]);
}

간단한 dp문제이다. 길이가 N일떄 마지막 숫자를 하나의 상태로 두고 이차원 배열로 만들어서 상태dp로 풀어준다. 그래서 결과 값은 dp[N][i] (i는 0~9까지)값을 모두 더한 값이 되겠다.

코드도 단순하다.

#include <stdio.h>
#include <iostream>
using namespace std;

int dp[1001][10];
int main()
{
	int N;
	int ans = 0;
	scanf("%d", &N);
	dp[1][0] = 1;
	for (int i = 1; i <= 9; i++)
	{
		dp[1][i] = 1;
	}
	
	for (int i = 2; i <= N; i++)
	{
		for (int j = 0; j <= 9; j++)
		{
			for (int k = j; k >= 0; k--)
			{
				dp[i][j] +=  (dp[i-1][k]) % 10007;
			}
		}
	}
	
	for (int i = 0; i <= 9; i++)
	{
		ans += (dp[N][i]) % 10007;
	}
	printf("%d\n", ans % 10007);
	return 0;
}

간단하게 상태dp로 풀어줍니다.

n일 때, 하나의 칸의 상태는 총 4가지 입니다.  1) 비어있는 경우 , 2) 위에 칸이 채워진 경우 3) 아래 칸이 채워진 경우 4) 모두 채워진 경우

규칙을 찾으면 다음과 같습니다. (n일떄 n-1은 모두 채워야 합니다. 왜냐하면 사용 가능한 타일이 2*1, 2*2 뿐이기 때문에 n-1을 모두 채우지 않으면 n+1에서 채울 수가 없습니다.)

위와 같이 규칙을 찾을 수 있습니다. 위를 토대로 코드를 짜면 다음과 같습니다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;

int dp[1001][4] = { 0, };
int main()
{
	int N;
	scanf("%d", &N);
	dp[1][0] = 1;
	dp[1][1] = 1;
	dp[1][2] = 1;
	dp[1][3] = 1;
	
	for (int i = 2; i <= N; i++)
	{
		dp[i][0] = dp[i - 1][3] % 10007;
		dp[i][1] = dp[i - 1][2] % 10007;
		dp[i][2] = dp[i - 1][1] % 10007;
		dp[i][3] = ((dp[i - 1][0] * 2) % 10007 + dp[i - 1][3]) % 10007;
	}

	printf("%d\n", dp[N][3] % 10007);
	return 0;
}

Recently i am interested in crypto. so I enjoyed this challenge a lot.

Look at the problem below

enc27.py

If you look at enc27.py, you can see it's xor encryption. and 24 byte block padding.

png file is encrypted with key( original_png ^ key ) And as you know, A xor A = 0. so if we know original_png. then we can find key. I checked png sample files and file signature to figure out key. and enc27.py is padding 24 bit message block and xoring with key i guess key length is 24. So if I xor between png file signature and encrypted png,  it would reveals padding value..

Do it.

import itertools

def xoring(m1,m2):
	return ''.join(chr(ord(a)^ord(b)) for a,b in zip(m1,m2))

def decrypt(enc, key):
	key = itertools.cycle(key)
	dec = ''.join(chr(ord(a) ^ ord(b)) for a,b in zip(key,enc))
	return dec
	
def main():
	f = open("BITSCTFfullhd.png","r")
	f2 = open("tmp.png","wb")
	buf = f.read()

	#png signature
	png = "\x89\x50\x4E\x47\x0D\x0A\x1A\x0A\x00"
	
	key = xoring(buf[:9],png)	
	#unkown key
	key += "A"*(24-9)

	dec = decrypt(buf,key)
	f2.write(dec)

	f.close()
	f2.close()
		

if __name__ == '__main__':
	main()

we know 9 bytes key. And first 9 byte from each 24 byte of block was decrypted. You can see that "\x13" is repeated 4 times. Yeah~ padding value is "\x13". "\x13"*(15)^enc[-15:] would reveal left key values.

import itertools

def xoring(m1,m2):
	return ''.join(chr(ord(a)^ord(b)) for a,b in zip(m1,m2))

def decrypt(enc, key):
	key = itertools.cycle(key)
	dec = ''.join(chr(ord(a) ^ ord(b)) for a,b in zip(key,enc))
	return dec
	
def main():
	f = open("BITSCTFfullhd.png","r")
	f2 = open("tmp.png","wb")
	buf = f.read()

	#png signature
	png = "\x89\x50\x4E\x47\x0D\x0A\x1A\x0A\x00"
	
	key = xoring(buf[:9],png)	
	key += xoring(buf[-15:], "\x13"*15)

	dec = decrypt(buf,key)
	f2.write(dec)

	f.close()
	f2.close()
		

if __name__ == '__main__':
	main()

flag is BITSCTF{p_en_gee}