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;
}