문제 못풀어서 진도가 안나간다
자살할까
종만북 보는데
익명(211.36)
2020-02-21 00:19
추천 0
댓글 65
다른 게시글
-
주변에서 병신들을 제거해라 [3]익명(1.240) | 20.02.21추천 0
-
도배기 구합니다익명(121.147) | 20.02.21추천 0
-
세상이 멸망해서 전 이세계를 가는겁니다. [2]익명(61.77) | 20.02.21추천 0
-
복소해석 ->현대대수+정수론인공무현(wjjong5) | 20.02.21추천 0
-
난게속놀거애요 [2]처절한여학..(antinatalism) | 20.02.21추천 0
-
노는사람애개 죄인취급 왜해요 [3]처절한여학..(antinatalism) | 20.02.21추천 0
-
여러분 저같은 사람을 응원해야죠처절한여학..(antinatalism) | 20.02.21추천 0
-
내일은 도서관 안가니 조금 늦게 일어나야겠어요 ㅎㅎ익명(61.77) | 20.02.21추천 0
-
자야지..마호로(dcmohoro) | 20.02.21추천 0
-
어서 내게 달아나 놔줄 때 날 떠나가치카냥(bluelip) | 20.02.21추천 0
어려운거부터 시작하는게 잘못아닐까? - dc Cpp
족보탐험 문제 구간트리 안쓰는 풀이는 떠오르는데, 인덱스를 어캐줘야 하는거지 ㅇㅅㅇ
정보) 본인 종만북 본적없음 - dc Cpp
세그먼트 트리는 알거 아냐. 좀 풀어주라
세그먼트 트리? 검색하고온다 - dc Cpp
https://algospot.com/judge/problem/read/FAMILYTREE
이 문제인데 난 인덱스 받아서 height 반환하는 함수를 O(n) 전처리해서 얻고 h(a)<h(b) 일 때, f(a,b) = 1 + f(a, father[b]); 이렇게 하면 시간안에 할 수 있을거 같긴한데 구간트리로 어캐 풀 수 있을까
어후 문제 다읽었다 - dc Cpp
굿. 그냥 촌수 따지는 문제
트리 굳이 써야함?.. 그냥 입력받은 족보에서 해당 인원 인덱스엔 부모가 있을테고, 둘중 인덱스 더 높은놈 부모인덱스로 옮겨주면 되잖음 - dc Cpp
그렇게 계속 반복하다가 공통조상 나오면 인덱스 옮긴횟수로부터 촌수 계산가능하고 - dc Cpp
인덱스가 높다는게 먼소리고, 노드의 높이 말하는거지? 내가 그렇게 푸니깐 시간초과뜬다 야
그렇다고 dp도 못함. 메모리 제한 넘김
음. 입력값을 배열 arr에 저장한다고 하면 if(arr[ascend1] == arr[ascend2]) break;else if(as1 > as2) as1 = arr[as1]; else as2>arr[as2]; 반복하면 되지않느냔거였음 - dc Cpp
세그트리로 어캐 풀 수 있을까. 보면 젤 깊은 노드 둘에서부터 시작하면 올라갈 때 분기가 두개니깐 구간트리로 할수 있나? 싶기도 한데 그러면 젤 깊은 리프가 3개 이상일 땐 어캐해야하나 싶기도하고 ㅇㅅㅇ
이런경우 시간복잡도는 최악의 경우 O(n)이겠네. 오버나겠구나 - dc Cpp
sc1 sc2 인덱스 단순 비교는 머냐 ㅋㅋ height[sc1] height[sc2] 비교해야지
귀찮아서 쓴거니까 대충 알아먹으셈 - dc Cpp
ㅇㅇ 시간복잡도 최악의 경우 O(트리의 높이)이고 가계도 일자면 O(n) ㅇㅅㅇ
나도 너처럼 풀었음. 근데 구간트리 챕터인데. 구간트리 써서 풀어야 할 듯
각 노드마다 자신의 직계후손을 전부 저장하면 어떨까 - dc Cpp
아니다 음.. - dc Cpp
입력받을때 자기 선조를 전부 알고있으면 되겠다야 - dc Cpp
0 1 1 3 3 0 6 0 8 9 9 8 순서로 들어오면 1은 0뿐이고, 2, 3은 0, 1을 선조로 저장. 4 5는 0 1 3을 저장, 6은 0을 저장... - dc Cpp
? 입력 다받고 O(n) 전처리하면 높이는 O(1)에 구할 수 있다니깐
트리 관련문제 오늘 처음봤다 이해좀해줘라 - dc Cpp
구간트리 RMQ 구현한번 해보면 구간트리 풀이 생각날 수도 있으니 한번 해봐
아마도 자고일어나서 - dc Cpp
나는 구간트리로 어캐 빠르게 풀 수 있는지 궁금함.
근데 선조 다 저장하고나면 촌수 구하는건 logN으로 될거같은데 - dc Cpp
우리가 바로 떠올린 풀이는 dp하면 속도는 올릴 수 있지만 메모리가 터짐. 근본적으로 다른 풀이가 필요함. 최초공통조상을 빠르게 찾아 내는 알고리즘을 생각해내야 할 듯?
공부좀 해야겠다 - dc Cpp
선조 다 저장하면 lg N임? 우째서어
최초공통조상을 찾아야하는데 공통조상중 숫자가 가장 높은놈임. 그럼 이진탐색하면서, 둘이 숫자가 같다면 자손쪽, 다르다면 더 숫자가 큰쪽을 조상쪽으로 옮김 - dc Cpp
2logN에 상수무시하면 logN - dc Cpp
아 lg N이 아니라 트리의 높이였네
아 ㅈㅅ - dc Cpp
그럼 시간복잡도 같지 않냐 원래풀이랑
log붙었다는 차이가 잇숴요 - dc Cpp
노드의 높이를 O(1)에 구할 수 있으면 선조저장 안해도 O(트리높이)임
트리높이는 최악의 경우 logN 아님.
log트리높이 아닌가? 내가 지금 졸려서 헷갈리나 - dc Cpp
가계도니깐 자식이 한명만 있다 생각해봐 그럼 트리높이는 N
그러니까 탐색횟수가 트리 높이만큼이 아닐거다 이말임 - dc Cpp
선조 저장하면 무조건 트리 높이보다 길이가 짧은 배열이 만들어질테고 그걸 이진탐색하면 최악의경우 log(트리높이) 지 - dc Cpp
흠 두 배열 A B 에서 공통원소 찾는게 lg N이 됨?
아 되지요, 이진 탐색하면 되지요 - dc Cpp
최악의경우 2logN니까 O(logN)이지요 - dc Cpp
배열에서 한원소 찾는게 이진탐색으로 lg N인데, 한배열에서 다른배열의 각 원소 찾으면 NlgN 아님? 어렵누
두 배열이 다 정렬돼있기 때문에 logN으로 가능합니다 위에 써놨ㄱㅎ - dc Cpp
시발 이해가 안가노. 숫자가 높다고 한게 오타 아니었음? 인풋에 주어지는 숫자는 트리에 들어가는 위치랑 상관없다. 정렬은 height로 한다는 거겠고 한번만 더 설명해줘
예를들어 8번놈의 조상 목록이 0 1 2 4 5, 13번놈이 0 1 2라고 하면 2를 찾는게 목표고 - dc Cpp
각 배열의 중간값부터 탐색 시작함. 예시가 너무 짧은배열인데 암튼, 각각을 비교해서 공통조상을 찾을때까지, 예시에선 13번놈의 배열에서 탐색 한번 진행함 - dc Cpp
이진탐색하다보면 공통조상을 찾거나 하겠지. 그럼 이제 공통조상중에 최초 공통조상을 찾아야하니까, 예시에선 둘다 1번을 가리킬거임. 둘다 숫자를 높이는거임 - dc Cpp
그런식으로 공통 조상이면서 다음 인덱스의 숫자가 다른 인덱스. 그 숫자를 찾는거임 - dc Cpp
야 정렬된 두 배열의 가장 큰 공통 원소 O(lg N)으로 찾기. 로 글 다시 써줘 보기 힘들다
콤퓨타로 그림그려서 올릴게 - dc Cpp
난 보다가 중고로 팔아버림
문제가 어려울 뿐 내용은 조아요
화석아조씨 저거 좀 풀어줘요
해당 댓글은 삭제되었습니다.
아니, 너 가짜지. 찐 초코냥이 저걸 모를리가 없잖아
님 이거 목소리의 형태 맞죠 ㅇㅅㅇ; 여동생 걔 - dc App
ㅇㅇ
글새로씀 - dc Cpp