알고리즘 문제 풀이 일지 (64) 썸네일형 리스트형 백준 1040: 정수 https://www.acmicpc.net/problem/1040 이 문제는 생각 이상으로 어려운 문제였다.필자가 늘 푸는 DP 방식으로 해결한다면 숫자를 집어넣으면서, 그 숫자가 K개로 이루어져있고, N보다 큰 지 확인하면 된다.숫자가 K개로 이루어졌는지 확인하려면, 비트마스크를 사용하면 된다. 그래야 중복 여부를 금방 확인할 수 있다.그렇다면 대강의 DP는DP[자릿수][사용한 숫자 비트마스크][사용한 숫자 갯수] 이렇게 나타낼수 있다. 사용한 숫자의 갯수는 "사용한 숫자 비트마스크"를 통해 계산할 수도 있지만, 번거롭다고 생각했었고, 메모리 제한도 아직 넉넉해서 추가하였다. 구현을 하다 보니 깨달은 것이 있다. 앞에서부터 숫자를 집어넣을 때, 앞자리의 숫자가 N보다 크면 그 어떠한 숫자를 집어넣어도 .. 백준 1047: 울타리 https://www.acmicpc.net/problem/1047 이 문제의 해결책은 생각보다 간단하지만, 떠올리기엔 고전하였다. 그리디적으로 생각하면, 가장 많은 울타리를 만들수 있는 나무를 베는 것이 상책이다.하지만, 이것도 해당 나무의 위치에 따라 다르다. 따라서 다른 방법이 필요하다. N은 최대 40이다. 그렇다면 Bruteforce를 사용할 수 있지 않을까?직사각형은 두 개의 점만 있다면 구성할 수 있다.나무를 꼭짓점으로 둔 직사각형을 Bruteforce해서 찾아서 해당 직사각형 없는 나무를 활용해서 해당 직사각형 둘레를 만들 수 있는지 확인해서 자르는 나무의 최솟값을 구하면 되면 해결할 수 있을 것 같다. 직사각형 내의 나무를 자르는 경우의 수도 있다. 이런 경우엔 직사각형 안의 가장 많은 울.. 백준 15806: 영우의 기숙사 청소 https://www.acmicpc.net/problem/15806 이 문제는 처음 봤을 단순 BFS로 풀 수 있지 않을까? 란 생각을 했었다.그런것이라면 정답 비율이 16%로 낮을 이유가 없다.혹시 시간초과라도 나는 것일까? 다시 문제를 천천히 보니 이전에 있었던 곳은 없어진다.만약 BFS를 쓴다면 이전에 있던 곳을 지워야한다.그런데, 이러면 시간초과가 날 가능성이 있다. 그렇다면 어떻게 해야할까?사실 이 문제의 해결책은 금방 떠올랐다.곰팡이가 핀 곳에서 번식을 할 때, 다시 같은 위치에 번식을 언제 할까?2의 시간이 지났을 때이다.번식을 하는 방향은 그 반대 방향으로도 번식을 하기 때문이다.그렇다면, BFS의 visit 배열을 2차원에서 3차원으로 바꾸고,위치와 함께 해당 시간이 음수인지 짝수인지를 .. 백준 25549: 트리의 MEX https://www.acmicpc.net/problem/25549 이 문제를 접하게 된 건 약간 특이하다. 이전에 틀렸던 문제들을 둘러보다가, 해당 문제의 알고리즘 태그들 중에 오랜만에 보는 태그가 있었고, 기억이 별로 나지 않아서, 복습 겸 이 태그가 달린 문제 중 하나를 골라서 풀었다. 분리 집합을 공부하면 각 분리집합의 크기를 구하는 방법을 배우게 된다.int find(int a){ if (a == P[a]) return a; return P[a] = find(P[a]);}void merge(int a, int b){ a = find(a); b = find(b); if (a == b) return; P[b] = a; cnt[a] += cnt[b];}이 코드에서의 cnt가 바로 분리집합의 크기이다... 백준 1341: 사이좋은 형제 https://www.acmicpc.net/problem/1341 등비수열의 합?지금까지 알고리즘 문제를 풀면서 무한이란 개념을 접할 기회가 적었다. 그렇기에 처음 보았을 떄엔 많이 당황하였다.대학 1학년 시절 이후에 미분 / 적분, lim은 오랜만에 보았으니.. 그럼에도 문제의 표를 천천히 관찰한 결과, 등비수열의 합으로 문제를 해결할 수 있지 않을까? 란 가정을 하였다.아이디어는 다음과 같다. 처음의 영식이가 먹을 턴이 돌아올 때, 이전에 먹은 케이크의 양은 한 번 돌아올때까지의 길이의 반비례한다.즉, 양비수열이다. 그렇다면, 첫 턴에 먹은 케이크 양을 a, 패턴 반복 까지의 길이를 r이라 칭할 때,lim의 양비수열은 a / (1 - (1 / pow(2, r))) 이렇게 계산할 수 있다. 그렇다면 이.. 백준 19535: ㄷㄷㄷㅈ https://www.acmicpc.net/problem/19535 이 문제는 풀이가 꽤 재미있었던 문제였다.단순히 그림을 그대로 받아들였을 때엔 풀이법을 떠올리기 어려웠다.하지만, "ㄷ"과 "ㅈ"의 조건을 생각으로 옮기니 어느정도 해결책을 떠올리기 시작했다. 단순하게 생각을 하면된다."ㄷ"은 트리내에서 이어진 노드 4개의 갯수를 찾으면 된다."ㅈ"은 힌 노드와 이어지는 노드의 갯수가 3개 이상인것들을 찾으면 된다. 여기서 "ㅈ"의 갯수는 금방 계산할 수 있다.모든 노드를 돌며 연결된 노드 갯수가 3개 이상일 때, 그 노드들을 3개 씩 고르는 가짓수를 구하면 된다.즉, 조합을 사용하면 이어진 노드 갯수 C 3 이렇게 구할 수 있다. 그렇게 모든 노드에서 각각 계산해서 더한다. 문제는 "ㄷ"이였다. 단순.. 백준 3487: Copying Books https://www.acmicpc.net/problem/3487 핵심 아이디어 이 문제는 평소와 달리 핵심 아이디어는 금방 떠올렸지만, 구현과 너무 씨름을 해서 시간을 소비하게 된 문제였다. 일단 매개 변수 탐색 내지 이분 탐색을 사용하는 것은 금방 알아챘다.scriber에게 할당할 books의 최대 양을 최소화 하려면, books의 양을 이분 탐색해서, 해당 양이 K명 내에서 해결할 수 있는지 확인만하면 된다.bool solve(ll l){ ll s = 0; int cnt = 1; for (int i = M - 1; i >= 0; i--) { s += P[i]; if (s > l) { s = P[i]; ++cnt; } } return cnt > P[i]; l = max(l, P[i]);.. 백준 1023: 괄호 문자열 https://www.acmicpc.net/problem/1023 서두내가 풀 문제를 고를때는 다른 분들이 정리하신 문제집에 수록된 문제들을 살펴서 괜찮아 보이는 것을 잡아서 해결한다.그런데 이 문제는 약간 다르다. 내가 풀지 않은 문제 중 가장 작은 번호(1023)를 가지고 있었기에 이 문제에 관심을 가졌다. 분명 내가 가장 자신있는 알고리즘은 다이나믹 프로그래밍이다. 점화식을 잘 세우면 해결할 수 있기 때문이다.그런데, 이 문제는 태그가 다이나믹 프로그래밍을 가졌지만, 해결방안이 전혀 떠올려지지 않았다.결국 이 문제의 해결은 요원한채 끝날 뻔했다. 다른 문제에서 실마리를 얻다어느날 문제집을 뒤지던 중 문제 하나를 발견했다. https://www.acmicpc.net/problem/2248이 문제를 보.. 이전 1 2 3 4 ··· 8 다음
