[일반] 간단한 알고리즘 질문

[ㄴㅇㄹㅁㄴㅇ(163.152)]

(30000, 1000) 의 2차원 행렬이있는데

모든 행을 돌면서 각 열(1000개)에 대해 차이가 상수 threshold 이하인 원소의 쌍을 모두 찾고싶은데

for문 3개 쓰는거 말고 모르겠음

어케함? ㅠ

[EN_SA(encludingsalt)]

각 열마다 정렬해서 투포인터쓰던지

[ㄴㅇㄹㅁㄴㅇ(163.152)]

ㄱㅅㄱㅅ 근데 정렬이 O(N^2)이라 시간은 똑같지 않아? 아닌가

[EN_SA(encludingsalt)]

정렬은 O(NlogN)인데

[ㄴㅇㄹㅁㄴㅇ(163.152)]

호옹이

[익명(222.116)]

정렬이 O(n^2)이라 하더라도 정렬은 한번만 해주기에 n^2 + n^2으로 O(n^2) 풀이가 됨

[EN_SA(encludingsalt)]

3만 * 천^2은 좀 어질어질하지

[익명(222.116)]

그건맞지

[ㅁ(119.202)]

정렬 + 투포인터 or 이진 ㅏㅁ새

[ㄴㅇㄹㅁㄴㅇ(163.152)]

ㄱㅅㄱㅅ 근데 정렬이 O(N^2)이라 시간은 똑같지 않아? 아닌가