본문 바로가기

개발새발 개발자/자료 구조

 (37)
[자료구조] 12-3. 그래프의 기본 연산 위와 같은 그래프는 오른쪽과 같이 엣지 리스트의 형태로 표현된다. 해석하자면 4개의 버텍스와 6개의 엣지를 가지고 있다는 것이다. 4개이므로 0에서 3 또는 1부터 4로 표현된다. 그리고 그 아래에 엣지들의 관계가 나온다. 이러한 형태는 많은 코딩 문제에서 출제된다. 그래프는 n*n의 행렬로 표현할 수 있다. 그리고 버텍스 간의 연결이 존재하면 1을 쓰고 아니라면 0을 쓴다. 0 1이 연결되어 있다면 0 1 뿐만 아니라 1 0에도 같이 1을 써줘야 한다. 그럼 이러한 결과가 나온다. 표를 살펴보면 a[i][j] = a[j][i]이므로 대칭 행렬이다. 따라서 무방향 그래프의 인접 행렬은 대칭 행렬이라고 할 수 있다. 방향 그래프는 어떨까? 역시 i에서 j로 가는 엣지가 존재할 때는 1이고 아니면 0이다. ..
[자료구조] 12-2. 그래프의 용어 하나의 개체를 표현하는 것을 노드 혹은 버텍스라고 부른다. 표현할 때는 원 내부에 숫자나 문자를 쓴다. 그 버텍스를 연결하는 선을 엣지라고 한다. 일대일 관계만을 나타낸다. 일대다는 할 수 없다. 또한, 방향성에 따라 대칭인 관계와 그렇지 않은 관계가 있다. 관계를 표현하는 것에는 adjacent와 incident가 있다. - adjecent: 버텍스에 대한 표현. 각 버텍스가 서로 연결되어 있다면, 즉 둘이 한 리스트에 포함되어 있다면 adjacent라고 쓴다. 그림을 보면 0과 1이 연결되어 있으므로 adjacent하다.- incident: 엣지에 대한 표현. 두 엣지가 같은 버텍스를 공유하고 있다면 incident 하다고 말한다. 그림에서 0,1과 0,2는 같은 버텍스를 공유하고 있으므로 incid..
[자료구조] 12-1. 그래프의 기본 개념 7 bridges problem이라고도 부르는 문제다. 2개의 섬을 연결하는 7개의 다리가 있을 때 다리를 한 번씩만 건너서 돌아오는 경로를 구하는 문제다. 문제의 답을 찾지 못한 사람들이 수학자 오일러에게 이 문제를 풀도록 부탁했다. 오일러는 문제를 오른쪽처럼 단순화시켰다. 섬은 node(vertex), 다리는 edge(link)로 추상화한 것이다. 홀수 개의 엣지에 연결된 버텍스 수가 4개 이상이면 한 붓 그리기가 불가능 하므로 답은 존재하지 않는다. 하지만 이 문제를 풀기 위해 썼던 방법 즉, 그래프는 지금까지 널리 이용되고 있다. 그래프는 버텍스와 엣지의 집합이다. 어떤 개체들 사이의 일대일 관계를 시각적으로 표현하는 수학적 모델이다. 이를 간략히 표현하면 G=(V,E) 즉, V와 E의 집합이라고..
[자료구조] 11-3. 해쉬 지금까지 배워온 탐색, 서치 알고리즘 중에 가장 안정적인 성능을 가진 것이 이진 탐색이었다. O(log n)이 나오는다는 의미를 생각해보면, 데이터의 개수가 10, 100, 1000, 10000...이렇게 증가해 나갈 때 성능은 밑이 10인 로그라고 가정할 때 1 2 3 4...이렇게 증가한다는 것이다. 매우 우수한 성능이지만 이 시간도 데이터의 크기에 의존한다. 데이터가 크면 클 수록 시간도 느려지는 것이다. 현실에서는 자료의 크기에 상관없이 실시간으로 특정 시간 내에 탐색이 수행되어야 하는 경우가 많다. 이용자나 데이터가 아무리 많아도 동일한 시간이 걸리는 즉, O(1)의 탐색 시간을 보장하는 자료구조 및 알고리즘이 해쉬다. 다시 정리하자면, 모든 키의 레코드를 산술 연산에 의해 한 번에 바로 접근할..
[자료구조] 11-2. 계층적 자료구조의 탐색 이번에는 계층적 자료 구조를 알아보자. 지금까지 배웠던 트리 구조가 계층적 자료구조에 속한다. 이진 트리의 탐색 연산은 중위, 전위, 후위 우선 탐색이 있었다. 일반적인 트리는 넓이 우선, 깊이 우선을 사용한다. 트리 구조에 저장되어 있는 원소를 찾는 검색 방법에도 두 가지가 있었다. 임의의 원소를 찾는 데엔 이진 탐색 트리, TOP을 찾는 데엔 heap을 사용했다. 트리 탐색의 세 가지 방법은 모두 시간 복잡도가 O(n)이다. 이진 탐색 트리에 대한 복습을 해보자. 이진 탐색 트리는 아래의 네 가지 조건을 만족해야 한다. 1. 각 노드에는 서로 다른 값이 저장된다.2. 왼쪽 부분 트리의 값은 루트 노드의 값보다 작다.3. 오른쪽 부분 트리의 값은 루트 노드의 값보다 크다.4. 왼쪽 부분 트리와 오른쪽 ..
[자료구조] 11-1. 선형 자료구조의 탐색 자료 구조에 대한 연산 중에 가장 중요한 것이 검색이다. 특히 위의 세 가지 종류의 검색을 알아볼 것이다. 1. Find arbitrary내가 원하는 임의의 원소를 찾기 2. Find first/last가장 처음/마지막으로 온 원소 찾기 3. Find top최대 또는 최소값 찾기 아까 말한 검색과는 다른 형태의 검색이 있다. search와 구분하기 위해 traversal 이라고 부른다. 주어진 집합 내에서 시작 원소로 부터 도달할 수 있는 모든 원소를 찾는 개념이다. 중위, 후위, 전위 우선 탐색과 그래프에서 배우는 깊이, 넓이 우선 탐색에 적용한다. 지금까지 배운 검색은 총 3가지 종류다. - arbitary1. 정렬된 배열1) 선형 검색2) 이진 검색3) interpolation 검색 2. 이진 탐색..
[자료구조] 10-2. Heap의 연산-추가와 제거 최대 힙에 원소를 추가해야 한다고 가정해보자. 최대 힙은 두 가지 조건을 만족해야 한다.1. 완전 이진 트리일 것2. 부모가 항상 자식보다 값이 클 것 어떤 힙에 새로운 원소를 추가하는 것은 새로운 노드를 추가하는 것이다. 그리고 1번 조건 때문에 항상 마지막 위치에 삽입되어야 한다. 그리고 2번 조건을 만족시키기 위해 히피파이를 수행해서 힙을 재구성해야 한다. 위의 그림은 완전 이진 트리이며 최대 힙이다. 여기에 32를 추가한다고 하면, 반드시 맨 마지막 자리에만 올 수 있다. 배열로 저장되어 있다면 맨 마지막 자리인 인덱스 12번에만 추가될 수 있다. 이렇게 추가되면 완전 이진 트리여야 한다는 조건을 만족한다. 하지만 아직 부모가 자식보다 커야 한다는 2번 조건은 만족시키지 못했다. 따라서 히피파이(..
[자료구조] 10-1. Heap의 개념 Heap에 대해 얘기하기 전에 먼저 자료구조를 복습해보자. 자료구조는 자료를 효율적으로 관리하는 기법이다. 관리 방법에는 추가, 검색, 제거 등등이 있다. 검색 연산은 또한 임의의 원소 찾기, 가장 먼저/늦게 온 원소 찾기, 가장 큰/작은 원소 찾기로 나눌 수 있다고 했다. 여기서 우리가 관심있는것은 가장 크거나 작은 원소를 찾는 것이다. 그 원소는 TOP이라고 부를 것이다. 정렬되지 않은 배열에서는 가장 큰 원소(TOP)를 찾기 위해 하나하나 다 봐야하므로 O(n)이 걸린다. 제거에도 마찬가지로 O(n)이 걸린다. 하지만 정렬된 배열에서는 가장 큰 원소(TOP)를 찾으라고 하면 맨 끝만 찾으면 된다. 즉, O(1)이 걸린다. 하지만 제거를하면 앞으로 하나씩 당겨줘야 하므로 O(n)이 걸린다. 우리가 원..

티스토리툴바