이 문제에서 점프해서 이동할 수 있다는 것의 의미는 같은 집합 안에 들어갈 수 있는지 여부이다. 이를 활용하기 위해서 기본적으로 집합 안에 들어갈 수 있는지 여부를 판단해주면 된다. 따라서 시작 값을 기준으로 해서 정렬해주면 된다. 해당 집합의 마지막 끝자락이 판단할 직선의 시작점보다 더 뒤에 있으면 동일한 집합으로 간주할 수 있다. 크게 2가지 방법으로 처리할 수 있다. 1. DisjointSet 안에 start minimum, end maximum을 따로 저장 2. 그때그때마다 end maximum을 동기화 다만 아래의 풀이는 2번째 방법으로 코드를 구현하였다. #include #include #include #include #include #include using namespace std; typ..

전형적인 유니온-파인트(DisjointSet) 문제이다. 왜냐하면, 사이클이 형성된다는 것의 의미는 사실 상 점들의 집합에 속하는 것끼리 연결했다는 것을 의미하기 때문이다. 즉, 해당 집합에 속하는지 속하는지 않는지를 배타적으로 판단해주어야 한다. 이러한 측면에서 Disjoint Set(상호 배타적 집합)을 잡았어야 한다. 기본적인 알고리즘은 다음과 같다. 1. Union-Find algorithm을 사용한다. Init > find > merge 함수를 구현한다. 다만, 이 방법을 사용할 때 Union by rank, Path compression을 활용하여 Time complexity를 O(lg*n)로 낮춘다. 2. 사이클을 형성한다는 것의 의미는 두 점이 이미 같은 집합 안에 들어와있는 경우이다. 즉..

사실상 이 문제를 풀기위한 알고리즘 및 자료구조를 학습하고 문제를 풀게 되었다. 특히 이 문제를 풀기 위해서 유니온 파인트 자료구조가 필요한데, 해당하는 내용은 종만북 2권 25.1에 나와있으니 잘 복습하도록 하자. 이 문제를 상호 배타적 집합으로 간주해도 되는 이유를 이해하는 것이 훨씬 더 중요하다. 사실상 도킹이 되거나 안되거나 둘 중 하나의 상황으로 이어지므로 이를 상호적 배타 집합으로 이해할 수 있다. 이러한 측면에서 유니온 파인드 자료구조를 활용하는 느낌으로 이해하면 될 듯 싶다. 이 문제는 자주 복습하면서 종만북을 참고하도록 하자. #include #include #include using namespace std; int G, P; struct DisjointSet{ vector parent..

사실 이 문제를 잘못 독해해서 시간이 엄청 걸렸다.. 문제에서 다른 노선에 포함 되어있는 것을 지운다고 하였는데, 이 의미를 잘못 이해하였다. 접근 방법은 다음과 같다. 1. 제일 긴 노선을 찾는다. 2. 제일 긴 노선의 출발점을 원점으로 변경한다. (기준점 설정) 3. 출발이 빠른 순으로 정렬한다. 4. 노선들을 순차적으로 방문하되, 이전 도착점보다 도착점이 더 먼 경우에만 해당 노선을 남겨둔다. (그렇지 않으면 이전 노선에 포함된다는 의미이므로 지워도 무방하다.) 추가적으로 원형 노선에 대해서 살펴볼 필요성이 존재한다. 원형 노선의 경우, 강제로 직선 노선으로 변경해주면 된다. 예를 들어 N이 10이고 (5, 2)의 경우에는 강제로 (5, 12)로 만들어주면 직선 노선화시킬 수 있다. 이 문제에서는 ..

접근 자체는 잘했는데, 중복해서 셀 수 있는 것을 놓쳐서 많이 헤맸다. 종만북 6.5장처럼 이러한 배열 문제에서 중복을 피할 수 있는 가장 쉬운 방법은 조건을 만족하는 것 중 가장 왼쪽 상단을 잡는 방향으로 진행하는 것이다. (이 지점을 놓친 것에 대해서 매우 반성하도록 하자.) 일단 문제 접근 방법은 다음과 같다. 1. 퀸의 공격 방향은 상하좌우대각이다. 2. 행, 열, 대각 성분을 따로 DP형태로 저장해놓는다. 퀸의 공격 성질을 감안해보면 각 행, 열, 대각 성분에 1개씩만 들어갈 수 있다는 것과 동치이기 떄문이다. 3, 반복적으로 비어있는 최초의 행을 찾고 그것을 기준으로 어떠한 열에 넣을 수 있는지를 기준으로 분할하여 계산한다. (실질적으로 함수 내부에서 N^2이라고 생각하기 쉬우나 실질적으로는 ..

처음에 접근한 방식은 다음과 같다. # 처음에 접근한 방법 일단 문제를 이해하면 전체 트리의 부분 트리 중 원소의 갯수가 K인 것의 갯수를 구하라는 것과 동치라는 사실을 쉽게 이해할 수 있다. 또한 트리라는 것을 감안할 때 DFS를 이용하여 루트가 밑쪽에 위치한 트리의 원소의 갯수를 활용하여 루트가 위쪽에 위치한 트리의 원소의 갯수를 도출시킬 수 있다는 사실을 파악하였다. 따라서 이러한 속성을 활용하여 dp[i][j]를 i를 Root node로 하고 해당 트리에 속한 원소의 갯수가 j를 만족하는 갯수라고 설정하였다. 이를 바탕으로 DFS를 타고 위로 올라가면서 점화식을 도출하려고 시도하였다. 다만 이 방법의 문제는 점화식을 세우는 것에 무리가 많다는 점이다. dp[i][j]를 구하기 위해서는 i 노드의 ..

접근 방법은 다음과 같다. dp[i][j]를 i번째 자리일 때, j만큼의 1을 가지고 있는 갯수라고 잡았다. 따라서 해당 DP의 점화식을 dp[i][j] = sigma(dp[i - k][j - 1]) ( 1 > L >> check_num; memset(dp, 0, sizeof(dp)); int result_store[32] = {0}; dp_check(1); ll sum_store[32]; // 각 자리기준 몇개가 존재하는지 int check_count = 0; while(check_num){ for(int i = 1; i

좀 애먹기는 했다.. 처음에는 백준 12865번 소풍처럼 메모리를 기준으로 구획하려고 하였는데 메모리 초과가 되었다. 생각해보면 당연한 결과인게 dp[10000000]을 하고 숫자를 넣게되면 128mb는 금방 넘게 된다. 그래서 다양한 풀이방법을 고안하게 되었고 해당 접근 방법은 다음과 같다. 메모리를 쓸건지 말건지 2가지 케이스가 존재한다. 그리고 이전에 메모리 상태에 따라서 사용 여부의 효율성이 결정난다. 즉 이러한 측면에서 부분문제를 해결함으로써 전체 문제의 답에 접근하는 최적 부분 구조(Optimal substructure) 형태임을 파악했어야 한다. 다만, 탐욕적으로 선택하는 방향은 아니므로 그리디가 아닌 DP(동적 계획법)으로 접근했어야 한다. 다만, 착각하기 쉬운 지점이 총 앱의 갯수가 N이..