17780번 문제 링크 https://www.acmicpc.net/problem/17780 17780번: 새로운 게임 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 문제 풀이 우선, 말이 합쳐진 이후에는 가장 위, 가장 아래 2개의 말만 저장하면 된다. ( 가운데의 말은 아무리 위아래를 바꾸더라도 맨 아래에 와서 움직임에 관여 불가 ) 따라서 각 말이 합쳐질 때마다, 적절한 top&bottom을 유지시킨뒤 움직임을 지시했다. 처음에는 queue를 통한 bfs 탐색으로 수행하고, 말이 합쳐질 경우, queue에 추가하지 않아 분기점을 합..
dp는 상황을 나누고, 그 간의 관계를 파악하여 점화식 혹은 a=b와 같은 고정된 수식으로 표현하여 문제를 효율적으로 해결하는 방식이다. 예를 들어 동전이 연속으로 앞면이 나올 확률을 구한다고 생각해보자. 모든 상황은 결국 나누면 앞면, 뒷면 으로 나뉜다. 이를 수식으로 표현해보자. n-1 째까지 앞면 나올 확률 * 앞면 나올 확률 = n 째까지 앞면 나올 확률 즉 f(n-1)* 1/2 = f(n) 이라는 점화식을 구할 수 있다. dp는 이런 특정 행동 (동전을 던짐) 에 따른 관계의 변화를 수식으로 표현해서 구할 수 있다. (특정행동 n-1번 = 특정행동 n번 이런식으로 생각하면 쉽다.) 전에 knapsack 알고리즘에 대해서도 정리했었는데, dp라고 생각하고 식을 구해도 해결할 수 있다. 추가로 in..
분리집합 응용문제를 하나 들고 왔습니다. 분리집합에 관한 기본적인 지식은 생략하고 해당 문제의 핵심 아이디어만 아래 코드블럭의 주석에 구체적이게 달아 놓았으니 참고하세요! #include using namespace std; #include int n, m,cnt; int arr[1000000]; int find(int a) { if (arr[a] == a) return a; else return arr[a] = find(arr[a]); } void join(int a, int b) { a = find(a); b = find(b); if (a == b)return; arr[a] = b; //두번째 파라미터가 첫번째 파라미터의 부모가 된다. } int main() { scanf("%d %d", &n, &m..
비트 마스킹 (bit masking) 이란? 이진수와 관련된 개념이다 이진수 110 은 2^2+2^1 으로 십진수 6을 표현한다. 그리고 이진수는 또다른 원론적인 의미로 해석될 수 있는데 바로 true false다. 즉 110 은 단순 십진수 6 뿐 아니라, 첫째, 둘째 놈은 true, 셋째 놈은 false 로 의미 부여를 하고 갈 수 도 있는것. 이번엔 거꾸로 가보자. 눈앞에 10개 버튼이 있는데, 나는 각버튼을 누를 수 도, 누르지 않을 수도 있다. 내가 버튼을 누를 수 있는 경우의 수는? 간단한 수학이다. 누른다, 안누른다 = 2 2^10= 1024 가지 경우의 수가 나온다. 아래 이진수에 부여한 의미를 생각해보자 0000000000 == 십진수 0 >> 전부 버튼을 누르지 않는다 000000000..
lis는 10, 20, 10, 30, 20, 50 이런 길이 5의 수열중 10, 20 ,30 ,50 과 같이 계속해서 증가하는 수열들 중, 가장 긴 수열을 찾는 문제다. 우선 lcs는 푸는 방식이 정말 다양한데, 전부 시간 복잡도가 다르다. dp를 통해서 풀게되면 O(N^2) 이고, lower_bound를 통해서 풀게 되면 O(NlogN) 의 시간 복잡도가 발생한다. lis 문제는 시간초과를 가지고 장난을 많이 치기에 lower_bound 방식만 가지고 문제를 풀어보겠다. 자세한건 아래 문제를 보면서 알아보자..! 1.lis 의 길이는? lis의 길이를 구하는 문제로, 위 의 입력의 경우 10,20,30,50 이기에 4가 정답입니다. 흔히 전깃줄 문제로 응용 됩니다. 자세한 건 아래 문제를 확인 해봅시다..
knapsack은 "제한된 자원" 으로 "최적(최대 or 최소) 의 이득" 을 얻는 문제에서 사용된다. 아래는 대표적인 예시 중 하나다. n개의 보석이있다. 이중 1~ n번째 보석중 k 번째 보석의 무게를 w_k, 가격을 c_k 라고 정의한다. 내가 가방에 최대로 담을 수 있는 무게가 w_max일때, 내가 담을 수 있는 최대 가치는? 대충 이런 느낌이지만, knapsack도 상황에 따라 다양한 방식으로 나눠져 있으므로 지금부터 같이 하나하나 알아보자! 1) fractional knapsack - 보석을 쪼개서 가방에 담을 수 있다. >> 그냥 무게당 가치가 높은것들을 우선적으로 가방에 담으면 끝이다. 예를들어 무게3에 가치 9, 무게 2에 가치 4 무게 1에 가치 1인 보석이있다고하면 1번의 무게 1당 ..
우선 백준 1005번을 보고 오자. https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 이 문제에 대한 올바른 문제해결 방법은 '위상정렬' 이다. 위상정렬은 보통 어떤 작업에 순서가 정해져있을 때, 순서를 결정하기 위해 사용하는 알고리즘입니다. 예를들어 스타크래프트에서 어떤 상위 건물을 지으려면, 하위 건물들을 몇가지 지어야 하는 경우가 있는데, 이처럼 어떤 작업 진행전에 해야하는 '순서' 가 존재할시 위상정렬을 사용한다. 위상정렬을 사용하기..
경로를 탐색해나가는 것에 더 나아가, 경로를 저장한 후 출력하라는 문제들이 종종 있다. 오늘은 어떤 경우에, 어떤식으로 경로를 저장해나가는지 케이스 별로 알아보자 1. 다익스트라,벨만포드 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 백준 문제 11779 번을 풀어보며 알아보자. 이 문제는 다익스트라 문제이지만, 벨만포드도 "경로 추적" 은 동일한 메커니즘으로 돌아간다. 혹시 벨만포드로 된 문제를 풀고 싶다면 ..
