배열 2개를 비교하는거 말고 배열 하나 안에 원소중에 같은 원소 2개가 있는지 알아내는법이요..
for(i=0;i<sizeof(array);i++) { for(j=i+1;j<sizeof(array);j++) { if(arr[i] == arr[j]) break; } }
Naive approach: 시간 복잡도 O(n^2). 방법 설명은 생략. n이 작다면 뭐 그냥 이렇게 쉽게 가는 것도 방법일 수 있어요. n이 좀 크면 좀 곤란할겁니다.
Sorting: 배열 원소에 total order가 있는 편리한 상황일 땐 아싸리 O(n log n)으로 정렬한 뒤, 쭉 읽으며 인접한 요소끼리만 비교 (O(n))해서 찾는 방법도 있습니다.
이 방법은, 애초에 데이터를 미리 정렬해 둘 필요가 있었을 경우에 특히 유리합니다.
Hashing: 배열 원소에 적절한 hash 함수를 정의해서, 배열 앞에서부터 차례로 hash table을 구성해보면 됩니다. 해시값이 같은 두 원소가 발견되면 실제로 같은 원소인지 확인해 봐야겠지요.
텍스트 포맷에 대한 자세한 정보
<code>
<blockcode>
<apache>
<applescript>
<autoconf>
<awk>
<bash>
<c>
<cpp>
<css>
<diff>
<drupal5>
<drupal6>
<gdb>
<html>
<html5>
<java>
<javascript>
<ldif>
<lua>
<make>
<mysql>
<perl>
<perl6>
<php>
<pgsql>
<proftpd>
<python>
<reg>
<spec>
<ruby>
<foo>
[foo]
for(i=0;i
for(i=0;i<sizeof(array);i++)
{
for(j=i+1;j<sizeof(array);j++)
{
if(arr[i] == arr[j])
break;
}
}
Naive approach: 시간 복잡도 O(n^2)
Naive approach: 시간 복잡도 O(n^2). 방법 설명은 생략. n이 작다면 뭐 그냥 이렇게 쉽게 가는 것도 방법일 수 있어요. n이 좀 크면 좀 곤란할겁니다.
Sorting: 배열 원소에 total order가 있는 편리한 상황일 땐 아싸리 O(n log n)으로 정렬한 뒤, 쭉 읽으며 인접한 요소끼리만 비교 (O(n))해서 찾는 방법도 있습니다.
이 방법은, 애초에 데이터를 미리 정렬해 둘 필요가 있었을 경우에 특히 유리합니다.
Hashing: 배열 원소에 적절한 hash 함수를 정의해서, 배열 앞에서부터 차례로 hash table을 구성해보면 됩니다. 해시값이 같은 두 원소가 발견되면 실제로 같은 원소인지 확인해 봐야겠지요.
댓글 달기