알고리즘/알고리즘 문제 [hard](20)
-
[그래프] [시도x] WORDCHAIN 단어 제한 끝말잇기
1. 문제 끝말잇기 참가자 = 원으로 앉아있음 시계방향으로 단어를 말함 단어의 첫글자 = 이전사람이 말한 글자의 끝 단어의 종류가 정해짐 한단어 두번X 단어들을 전부 사용가능한지 판단하고 어떤 순서로 단어를 사용해야하는지를 계산하는 문제 2. 오일러 트레일 이 문제는 각 단어의 첫부분과 끝부분으로 만들어진 간선을 가지는 그래프를 만들고 오일러 트레일과 오일러 경로 구하는 문제인것 같다. 하지만 책에서 구현한 오일러 경로를 아직 이해하지 못하겠다. 간선이 아닌 정점을 벡터에 집어넣는것, 아직 생각을 더해야 겠다. 또한 그래프를 생성하고 홀수점이 2개일때 오일러 트레일을 찾을려면 홀수점 두개중에서 시작점과 끝점을 찾아야하는게 문제이다. (책의 풀이를 보고, 방향그래프인점을 생각하지 못한 것을 알게되었다.) ..
2021.02.13 -
[트리] [시도x] MEASURETIME
1. 펜윅트리를 이용한 풀이 처음에 이 문제를 봤을때 펜윅트리를 어떻게 써야할 지 감을 못잡았다. 책에서는 수열의 입력값으로 이루어진 트리를 만들고 해당 입력값이 오게되면 그것을 포함하는 구간을 전부 +1을 해줘서 루트에 현재 수열의 길이를 저장하게 되고 입력값 까지의 부분합을 구하게 되면 현재 수열중에서 입력값보다 작은 것들의 개수를 알 수 있다. 이를 통해 자신보다 큰 원소의 개수를 알 수 있고, 앞으로 몇칸 이동 시켜야하는지 파악할 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 5..
2021.02.08 -
[트리] [시도x] FAMILYTREE 족보 탐험
FAMILYTREE algospot.com :: FAMILYTREE 족보 탐험 문제 정보 문제 촌수는 혈연관계의 멀고 가까움을 의미하는 숫자로, 고려 말에 들어와 조선 시대에 정착된 것으로 알려져 있습니다. 촌수를 세는 계촌법은 부모와 자식간이 1촌이 되 www.algospot.com 이 문제의 핵심은 '전위 탐색' 이다. 전위 탐색은 트리를 재구성하고, 부분 구간을 생성할 수 있게 해준다. 1. 생각. 이 문제를 풀기 위해서는 성벽 문제와 마찬가지로 두 사람의 두 노드간의 길이를 구하는 문제이므로 최소 공통 조상을 찾아야 할 거 같다. 최소 공통 조상을 찾으려면 일단 트리를 구현해야한다. 트리를 구현한뒤 depth를 구해 각 번호마다 따로 저장해놓는다. 그 후 2 * lgn 만에 두 노드를 찾은후 거슬..
2021.02.08 -
[트리] [x]INSERTION 삽입 정렬 뒤집기
1. 삽입정렬 11:38 삽입 정렬은 정렬된 부분 배열을 유지하며 이 배열에 새 원소를 삽입해나간다. void insertionSort(vector& A) { for(int i = 0; i 0 && A[j-1] > A[j]) { swap(A[j-1], A[j]); --j; } } } 삽입 정렬이 0~i-1 이 정렬된 배열을 가질때 i를 적절한 위치까지 한칸씩 옮긴다. 길이 N인 수열을 삽입 정렬했을 때 각 원소가 몇칸이나 앞으로 이동했는지 를 알고 있을 때 원래 수열을 찾아내야하는게 이 문제의 내용이다. 2. 트리 일단 1~n까지 임의로 원소를 만들어. 트리를 형성한다. 주어진 배열은 각 원소가 몇칸이나 앞으로 이동했는지 나타내는 배..
2021.02.06 -
[트리] [시도 x]FORTRESS 요새
1. 트리 생성 이 문제는 외벽안의 성벽들을 트리로 나타낸다음 각 잎에서 잎까지의 경로가 가장 긴 거리를 구하는 문제이다. 따라서 일단 주어진 성벽들의 정보를 가지고 트리를 구성해야한다. 이 트리를 생성하는데 약 n*n*n 이 걸릴 것 같다. 1. 서로 비교하여 노드의 벡터에 포함되어있는것을 넣는다 -> 두개를 비교하니 n*(n-1)/2 2. 각 비교할때마다 부모노드에서 자식노드벡터를 제거해야한다 -> n(점점 작아진다 생각보다 빨리 실행될 것이다) 3. 넣은것들 또한 트리로 정리해야하므로 남은 것들을 재귀호출해야한다. -> n 2번은 총 n(n-1)/2 번 실행될것이고 , 1번 또한 n(n-1)/2 번 실행될것이니 대략 n^2만에 트리를 정리하여 서브 트리만 남겨놓는다. 서브트리를 재귀로 정리해야한다...
2021.02.04 -
[수치 해석][삼분법][시도X] FOSSIL 꽃가루 화석
1. 기하 이 문제는 위와 같이 블록 껍질이 주어졌을 때 겹치는 다각형의 최대 수직 거리를 구하는 문제이다. 기하적으로 푸는 법은 다음과 같다. - 교차되는 직선들의 교차점을 포함하고 두 블록 껍질의 교집합인 점들을 포함하는 블록껍질을 구한다. - 구한 교집합 블록껍질의 꼭지점들을 X좌표에서 수직을 그어 최대인 수직 거리를 구한다. (블록 껍질에서의 최대 수직 거리는 항상 꼭지점에서 그은 수직선이다. 기울기가 꼭짓점에서 바뀌기 때문이다.) 먼저 블록껍질의 점 하나를 다른 블록껍질의 선분들에 대응하면서 포함되는지 확인 해야 한다. 교집합이 될 수 있는 점의 범위를 최소화 하여 포함되는지 확인하자. A와 B의 X값의 최대 최소를 비교하여 X값의 범위를 A와 B의 Y값의 최대 최소를 비교하여 Y값의 범위를 줄..
2021.01.23