전체 글(168)
-
graph, dfs 1
문제는 더블릿 16 graph, dfs에 있는 dfs입니다.문제 사이트 주소입니다.http://183.106.113.109/30stair/dfs/dfs.php?pname=dfs 그래프가 주어졌을 때 시작 정점부터 시작해서 dfs 방식으로 모든 정점을 돌며 각 정점을 출력하는 문제입니다. 문제를 풀기위해 가장 먼저 생각나는건 입력 예처럼 입력이 주어졌을 때 앞 -> 뒤로 갈 수 있는 것 뿐만 아니라 뒤 -> 앞으로도 방향성을 알 수 있어야 하고 이전에 방문했던 정점의 위치를 표시해야한다는 것입니다. 그러기 위해 2차원 배열 하나와 1차원 배열 하나씩 선언해 줍니다.1차원 배열은 해당 정점을 인덱스로 보고 방문은 했는지 표시하며 2차원 배열은 앞 -> 뒤, 뒤 -> 앞의 방향성을 표시합니다. 입력이 끝이 아..
2014.12.30 -
윈도우 커널 드라이버 개발 디버깅 환경 구축
윈도우 커널 드라이버(NDIS) 개발을 하기위한 디버깅 환경 구축 과정을 정리하려합니다. 찾아보면 옛날 ddk와 순수 windbg를 이용한 디버깅 환경이 많이 나옵니다. 저는 최신 비주얼 스튜디오인 2013과 윈7, 그리고 vmware를 이용한 디버깅 환경을 설명하겠습니다. 이렇게 구축을 해놔도 어떤 윈도우 프로그래밍 혹은 웹 프로그래밍보다도 개발 속도가 느립니다. 안드로이드보다도 느리다고 자부할 수 있습니다. 드라이버 개발에 특별한 디버깅 환경이 필요한 이유는 커널에 수정, 작업을 반영하기 때문에 운영체제가 불안정해질 수 있습니다. 본래의 노트북이나 데스크탑에 설치된 운영체제에 그대로 디버깅을 수행하면 개발한 드라이버에 문제가 있을 시 컴파일 에러, 런타임 에러만 내놓고 끝나는게 아니라 해당 운영체제를..
2014.12.26 -
옥상 3
문제는 더블릿 옥상에 있는 koi_Ebishop입니다.문제 사이트 주소입니다.http://183.106.113.109/pool/koi_Ebishop/koi_Ebishop.php?pname=koi_Ebishop 판 위에 비숍을 놓을 수 있는 최대 자리수를 구하는 문제입니다. 비숍은 대각선에 같은 비숍을 놓을 수 없으며 대각선의 비숍 유무와 관계없이 비숍을 놓을 수 없는 자리가 있습니다.우선 이 문제는 백트래킹으로 풀었습니다. 일단 알아두면 좋은 것들은 한쪽 대각선방향(오른쪽 위에서 왼쪽 아래)으로 겹치지 않고 놓을 수 있는 수는 2*한쪽칸의 개수-1로 4*4 칸의 경우 7칸이 됩니다. 재귀함수 탈출조건으로 쓰일겁니다. 예의 5*5인 경우 0, 0부터 4, 4까지 대각선으로 검사를 할 때 9번의 검사면 끝납..
2014.12.08 -
문자와 문자열 1
문제는 더블릿 12 문자와 문자열에 있는 isbn입니다.문제 사이트 주소입니다.http://183.106.113.109/30stair/isbn/isbn.php?pname=isbn 문제 자체는 문제에서 설명해주는대로 구현하면 간단합니다.입력을 받아 ?를 제외한 합을 구하고 그 값을 11로 나눈 후 (?의 위치 가중치) * (0~10) + (11로 나눈 값)이 0이 될 때의 0~10의 값을 출력하면 됩니다.여기서 얻어갈 건 15688?111X를 입력 받은 후 이 문자열을 숫자로 처리할 때인데 저는 char 배열을 선언후 cin을 이용해 한번에 입력받은 후 각 인덱스에 대하여 처리하였습니다.각 인덱스의 문자 값을 정수로 바꿔 계산할 때에는 -'0'을 해주면 됩니다.예)int i=ar[1]-'0'; //ar[1..
2014.12.03 -
divide and conquer 3
문제는 더블릿 10 divide and conquer에 있는 mod_fibo입니다.문제 사이트 주소입니다.http://183.106.113.109/30stair/mod_fibo/mod_fibo.php?pname=mod_fibo 엄청 큰 피보나치 수를 구하는게 문제입니다.피보나치 수열의 단순한 방법(전전값과 전값의 합)으로는 시간초과가 뜹니다. 나눗셈을 미리 해주는 방법도 마찬가지로 시간초과가 납니다.풀기 위해서는 행렬을 이용해주는 방법이 있습니다.1 11 0을 피보나치 수열의 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55...에서 첫번째 1에 해당하는 행렬로보고 값은 0행 0열의 값을 봅니다.이 행렬을 제곱하면 2 11 1이 나오고 이 값은 2에 대항하는 행렬입니다.이 행렬을 제곱하면5..
2014.11.25 -
backtracking 2
문제는 더블릿 25 backtracking에 있는 door입니다.문제 사이트 주소입니다.http://183.106.113.109/30stair/door/door.php?pname=door 열린 문 2곳이 있고 앞으로 열어야 하는 문을 열린 문으로 이동하면서 이동한 거리를 카운트합니다. 이 때 이동한 거리가 가장 적은 회수를 구하는 문제입니다.다음에 열어야 할 문은 열린 문 2군데중 한 군데와 바꿀 수 있습니다.무조건 가까운 거리와 바꿨다가는 다음 경우의 수에서 더 많은 거리를 이동해야 할 수 있습니다.이번에 열어야 할 문을 열린 문 2곳 중에 왼쪽문과 바꾼 경우, 오른쪽문과 바꾼 경우를 모두 트리를 타듯이 타고 내려갑니다.열린 문이 2와 5이고열어야 할 문이 3 4 6 5 인 경우첫 번째 문 교체 (2-..
2014.11.20