Son's Warehouse

출처 : https://www.acmicpc.net/problem/7571 행의 크기와 열의 크기가 각각 N인 격자공간에 M개의 점이 있다. N = 4이고 M = 4인 경우의 예가 아래에 있다. 격자공간 왼쪽의 숫자는 행 번호이며, 위의 숫자는 열 번호를 나타낸다. 그리고 격자공간내의 각 사각형의 위치는 (행 번호, 열 번호)로 표시한다 이제 격자공간에 있는 모든 점들을 하나의 사각형 안으로 모으려고 한다. 어떤 점을 움직일 때는 그 점이 들어있는 사각형에서 상하좌우로 인접한 사각형으로만 움직일 수 있다. 여기에서는 격자공간내의 한 사각형으로 모든 점들을 모을 때 각 점이 움직인 거리의 합을 고려한다. 예를 들어, 위의 점들을 (3,2)에 있는 사각형으로 모을 때 최단거리로 점들을 이동시킨다면 (1,2)..

문제 출처 : https://www.acmicpc.net/problem/2565 두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다. 예를 들어, 과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다. 전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위치의 번호가 주어질 때, 남아있는 모든 전깃줄이 ..

[2418] 단어 격자아래와 같은 단어격자가 주어진다.이 격자내에서 읽을 수 있는 단어가 주어지면 주어진 단어를 읽을 수 있는 경우의 수를 출력하는 문제이다.(중복해서 칸을 이동하며 읽을 수 있고, 칸은 대각선, 아래, 위, 좌, 우 를 포함 8방향을 이동할 수 있다) 1) 메모이제이션 + 완전탐색각 단어격자의 문자를 시작 문자로 하여 주어진 단어를 만들 수 있는지 모두 체크한다. 123456789101112131415161718192021222324252627282930313233343536373839#include using namespace std; char puzzle[201][201], word[101];long long ans = 0; int l;long long d[201][201][101]..

[2529] 부등호부등호 n개의 배열이 주어지면,해당 부등호 들을 만족시키는 숫자 n+1개의 배열 중 가장 작은 숫자 배열과 가장 큰 숫자배열을 찾는 문제.부등호 배열 A = {} 가 주어지면 이를 만족하는 숫자는 0 1 , 1 2 , 2 3, ... , 8 7 과 같다.이 중 가장 큰 숫자 배열은 897이고, 가장 작은 숫자배열은 021이다. 1) 그냥 다 보기부등호가 기껏해봐야 9개가 주어지고, 10개의 숫자로 이루어진 배열이므로 최대 10!의 경우를 모두 보면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142#include #include using namespace std;..

2의 거듭제곱 판단하기 "어떤 자연수가 2의 거듭제곱임을 판별하라." 주어진 숫자가 $2^{63}$이하의 자연수라고 하면 당연히 2, 4, 8, 16, ... 순차적으로 확인해서 2의 거듭제곱인지 아닌지 판별하려고 할 것이다. (물론 unsigned long long type으로 말이다.) 쿼리가 m개라면 $O(63m)$ 의 시간복잡도를 가질 것이다. 물론 이것만으로도 충분히 빠른 판단이라 생각되지만 특별한 방법을 찾게 되어서 블로그에 남기기로 하였다. 결론부터 말하면 어떤 자연수 $n$에 대해 $$(n\mathrm{\&}(-n))==n$$ 이면 그 수는 2의 거듭제곱이다. 결론을 알았으니 맞는지 잠시 생각해보자. 1) 우리가 찾고자 하는 2의 거듭제곱 수 $n$의 비트표현을 살펴보면 한 자리만..

Multi-Level Page Table의 필요성Page Table은 각 프로세스마다 가지고 있으며 Memory내에 OS가 관리할 수 있는 영역에 저장이 된다.따라서 Paging에서 고려해야 되는 것은 Page Table의 크기를 줄이는 것일 것이다. 예) PTE(Page Table Entry)의 크기가 4B로 가정할 때 32bit address spacePage는 4KB의 크기를 가지므로 entry는 약 $$2^{22}$$ 개의 entry가 필요하고, Page Table의 크기가 4MB가 된다.각 프로세스마다 4MB 크기의 Page Table을 Memory에 저장한다는 것은 적절하지 않아 보인다. (물론 swap공간의 얘기도 있지만, 여기서는 넘어가자.) Page Table의 크기를 줄이는 방법은 여러..

문제 출처 : https://www.acmicpc.net/problem/5397분류 : 시뮬레이션, 스택, 링크드리스트 백준 5397 키로거시뮬레이션, 스택을 이용구현 포인트1) 직접 구현 시 중간 삽입을 어떻게 할 것인가? 스택 또는 링크드리스트! 처음에 아무생각 없이 코딩했을 때는 중간 삽입에 대한 생각 없이 풀었다.. 결과는 물론 시간초과 1초이내에 해낼리가 없다;; 그래서 링크드 리스트와 같은 time complexity를 보이는 deque를 사용하였다. 다른 사람들 코드리뷰를 해보니 스택을 이용하는 다른 방법도 있어서 글을 남기기로 하였다. 우선 내가 푼 코드는 아래와 같다. 1234567891011121314151617181920212223242526272829303132333435363738..

참고1 : https://www.quora.com/What-is-Knuths-optimization-in-dynamic-programming참고2 : http://codeforces.com/blog/entry/8219 Knuth's Optimization다이나믹 프로그래밍 중에 다음과 같은 DP형태를 최적화 하는 방법입니다.$$DP[i][j] = \underset {i