728x90 분류 전체보기138 그래프 알고리즘 - 1 그래프 - (무방향) 그래프 G=(V,E) - V : 노드(node) 혹은 정점(vertex) - E : 노드쌍을 연결하는 에지(edge) 혹은 링크(link) - 개체(object)들 간의 이진관계를 표현 - n=|v|, m=|E| - 방향 그래프(Directed Graph) G=(V,E) - 에지 (u,v)는 u로부터 v로의 방향을 가짐 - 가중치 그래프 : 에지마다 가중치가 지정 인접행렬 - n*n행렬 A = (aij) 연결되면 1, 안되면 0 연결리스트 - 정점 집합을 표현하는 하나의 배열과 - 각 정점마다 인접한 정점들의 연결 리스트 방향그래프 - 인접행렬은 비대칭 - 인접 리스트는 m개의 노드를 가짐 가중치 그래프의 인접행렬 표현 - 에지의 존재를 나타내는 값으로 1대신 에지의 가중치를 저장 .. 2021. 3. 16. hashing - 마지막 좋은 해쉬 함수란? - 현실에서는 키들이 랜덤하지 않음 - 만약 키들의 통계적 분포에 대해 알고 있다면 이를 이용해서 해쉬 함수를 고안하는 것이 가능하겠지만 현실적으로 어려움 - 키들이 어떤 특정한 (가시적인)패턴을 가지더라도 해쉬함수값이 불규칙적이 되도록 하는게 바람직 * 해쉬함수값이 키의 특정 부분에 의해서만 결정되지 않아야 함 Division 기법 h(k) = k mod m 예 : m = 20 and k = 91 => h(k) = 11 장점 : 한번의 mod연산으로 계산. 따라서 빠름 단점 : 어떤 m값에 대해서는 해쉬 함수값이 키값의 특정 부분에 의해서 결정되는 경우가 있음. 가령 m = 2^p이면 키의 하위 p비트가 해쉬 함수값이 됨. Multiplication 기법 0에서 1사이의 상수 A를 .. 2021. 3. 11. [백준10989] 수 정렬하기 - 3 [java] 이 문제는 수 정렬하기 3번째 문제인 만큼 더 생각해야할 부분이 있다. 바로 데이터의 양이 너무 많다는 것이다!! 따라서 Scanner를 사용해서는 문제를 통과할 수 없고 BufferedReader를 사용해야 한다. Scanner와 BufferedReader의 차이는 값을 입력받을 때 buffer로 한번에 통과시키면 많은 데이터를 받을 때 훨씬 빠르게 처리할 수 있다. 또한 배열과 리스트에서도 데이터를 처리할 때 차이가 많이 나게 된다. 따라서 같은 sort이고 Arrays.sort가 시간복잡도가 높고 Collection.sort가 시간복잡도가 작더라도 이 문제처럼 주어진 데이터가 많을 때는 Arrays.sort를 쓰는게 더 좋다. 따라서 Arrays.sort와 BufferedReader를 사용하면 문제.. 2021. 3. 10. [백준2751] 수 정렬하기-2 [java] 2751번 수 정렬하기 2번문제인데 앞의 문제인 2750문제보다 수의 범위가 훨씬 넓어졌다. 따라서 코드에 대해 좀 더 정교한 필요하다. 예를 들어 2750번에서는 가능했어 Arrays.sort를 사용하면 시간초과가 발생한다. 여기서 약간의 정리를 하자면 Arrays.sort()의 경우에는 dual-pivot quicksort 알고리즘을 사용한다. quciksort가 평균 시간복잡도 o(nlogn)으로 좋은 알고리즘이긴 하지만 최악의 경우에는 o(n^2)이라는 것을 알아야한다. 또한 이 문제에서는 일부러 최악의 경우를 배치시켜 시간초과 문제가 발생하도록 했다. 위의 문제를 해결하기 위해서는 Collections.sort()라는알고리즘을 사용해야 한다. 이 알고리즘은 반복합병 및 삽입 알고리즘을 사용하는데.. 2021. 3. 8. hashing-1 Hash table - 해쉬 테이블은 dynamic set을 구현하는 효과적인 방법의 하나 dynamic set : 탐색, 삽입, 삭제 3가지 연산을 지원하는 방법 - 적절한 가정하에서 평균 탐색, 삽입, 삭제시간 o(1) - 보통 최악의 경우 o(n) - 해쉬 함수(hash function) h를 사용하여 키 k를 T[h(k)]에 저장 - h : U -> {0,1,2,...,m-1} - 키 k가 h(k)로 해슁되었다고 말함 충돌 - 두 개 이상의 키가 동일한 위치로 해슁되는 경우 - 즉, 서로 다른 두 키 k1과 k2에 대해서 h(k1) = h(k2)인 상황 - 일반적으로 U >> m이므로 항상 발생 가능 -충돌이 발생할 경우 대처 방법이 필요 - 대표적인 두 가지 충돌 해결 방법 : chaining과.. 2021. 3. 8. 이진검색트리-3 delete - case 1 : 자식 노드가 없는 경우 -case 2 : 자식노드가 1개인 경우 - case 3 : 자식노드가 2개인 경우 - 지우려는 값의 successor을 찾는다 - 지우려는 값에 successor을 복사하고 successor의 값은 지운다. delete의 수도코드 - 처음 if는 자식이 1개 이하인 경우이다. if문안에 들어가면 y에 지우려는 값을 넣는다 - if문안에 못들어가면 y에는 지우려는 값의 successor값을 넣는다. - 다음 if문에는 y의 왼쪽 값이 있다면 x에 왼쪽 값, 오른쪽 값이 있다면 x에 오른쪽 값을 넣는다. - 만약 x의 값이 없다면 y의 부모를 x의 부모로 만들어준다. - 만약 y의 부모가 null 즉 y가 루트면 x를 트리의 루트로 만들어준다. - 만.. 2021. 3. 8. 이전 1 ··· 17 18 19 20 21 22 23 다음 728x90
