1.
x좌표의 절대값이 10억이하고
각 선분이 N(N<=100000)개 주어질때(단 x값은 정수가 아닐수도 있다)
특정 x값에서 가장많이 선분이 겹칠때
최대로 겹치는 개수를 구하는 법
2.트리를 순회할때 루트에서 자식노드가 없는 노드까지의 경로를 모두 출력하고싶어서 백트래킹돌릴때
시간복잡도는 O(노드개수)인가? (정확히는 2*노드개수)
x좌표의 절대값이 10억이하고
각 선분이 N(N<=100000)개 주어질때(단 x값은 정수가 아닐수도 있다)
특정 x값에서 가장많이 선분이 겹칠때
최대로 겹치는 개수를 구하는 법
2.트리를 순회할때 루트에서 자식노드가 없는 노드까지의 경로를 모두 출력하고싶어서 백트래킹돌릴때
시간복잡도는 O(노드개수)인가? (정확히는 2*노드개수)
1. 좌표압축 imos 또는 우선순위 큐 + 스위핑 2. 경로들을 실제로 다 출력하려고 하면 O(n^2)까지 소요될 수 있음 길이 x인 일직선 트리에 리프노드 y개가 붙어있으면 x*y번 출력해야하고 x+y = n일 때 x = y = n/2 에서 최대임.
아 출력을 생각 못했네