문제 보기: https://www.acmicpc.net/problem/1432 문제 이해하기예제 입력이 예제 출력으로 이어지는 과정이 문제에서는 N개의 정점으로 이루어진 그래프에서 모든 간선이 V1 -> V2 형태로 주어질 때, 모든 간선이 V1 2 조건을 만족하도록 각 정점에 번호를 새롭게 부여한 뒤, 새로 정해진 번호들의 결과 수열을 출력해야 하는데요. 만약 여러 개의 답이 존재한다면 사전 순으로 가장 앞선 것을 출력합니다. 먼저, 문제의 조건을 만족하는 번호를 각 노드에 부여할 때 쉽게 떠오르는 아이디어는 간단한데요. 조건을 위반하는 간선이 있다면, 그 간선이 연결하는 두 노드의 번호를 서로 교환하면 된다는 생각을 할 수 있습니다. 하지만 이 접근 방식에는 근본적인 문제가 존재합니다. 특정 간선이 ..

문제 보기 : https://www.acmicpc.net/problem/10000 문제 이해하기이 문제는 바깥 영역을 포함하여 서로 교차하지 않는 원들이 만들어내는 총 영역의 개수를 구해야 합니다. 아래 그림처럼 원들이 바깥 또는 안으로 접해있을 수도 있고, 안에 포함하고 있을 수도 있습니다. 그러면서 각각의 원마다 영역이 하나씩 생기게 됩니다.이때, 아래 그림처럼 어떤 원(부모 원)의 내부에 있는 자식 원들이 연속적으로 이어져서 부모 원의 지름을 꽉 채우는 경우, 부모 원에 대한 영역이 기존의 한 개가 아닌 두 개가 생기게 됩니다.이런 식으로 최대 30만 개의 원이 저런 관계들을 가지며 존재하는 상태에서 만들어지는 총 영역의 개수를 구해야 합니다.  핵심 아이디어이 문제의 핵심은 부모-자식 원 간의 관..

정의무방향이면서 사이클이 없는 연결 그래프. 특징계층 형태로 이루어져 있고, 최상위 노드를 제외한 모든 노드가 하나의 부모 노드를 가지고 있는 특별한 그래프V개의 정점을 가졌을 때, V-1개의 간선을 가지고 있다.임의의 두 점을 연결하는 Simple Path(시작 노드부터 도착 노드까지 중복되는 노드가 없는 경로)가 유일하다.각 노드마다 최대 두 개의 자식을 가질 수 있는 트리를 이진 트리라고 한다. 이진 트리의 순회레벨 순회 : 계층 순으로 방문해 나가는 방법. BFS 순회와 동일하다.전위 순회(Preorder Traversal) : 현재 노드 - 왼쪽 서브트리 - 오른쪽 서브트리 순으로 방문해 나가는 방법. DFS 순회와 동일하다.중위 순회(Inorder Traversal) : 왼쪽 서브트리 - 현재..

정의정점과 두 정점을 잇는 간선으로 이루어진 자료구조. 자료 사이의 연결 관계를 설정해야 하는 상황에서 유용하게 활용된다. 특징방향성 : 방향성의 유무에 따라 무방향 그래프(Undirected Graph)와 방향 그래프(Directed Graph)로 나뉜다.무방향 그래프의 간선이 양방향 도로라면, 방향 그래프의 간선은 일방통행 도로이다.즉, 방향 그래프에서 A  -> B로의 간선이 있다면 B 차수(Degree) : 한 정점이 가진 간선의 개수.방향성 그래프에서는 나가는 방향인 진출차수(Outdegree), 들어오는 방향인 진입차수(Indegree)로 나뉜다.사이클(Cycle) : 임의의 한 정점에서 출발해 자기 자신에게 돌아올 수 있는 경로가 있는지 여부에 따라 순환 그래프(Cycle Graph)와 비순..

정의pop 연산에서 가장 먼저 들어온 원소 대신 우선순위가 가장 높은 원소가 내보내지는 큐. 일반적으로 힙(Heap)을 이용해 구현된다. 특징원소의 추가에 O(logN)의 시간이 걸린다.원소를 삽입한 후 우선순위 큐를 만족할 때까지 계층 이동이 일어나기 때문우선순위가 가장 높은 원소의 확인에 O(1), 우선순위가 가장 높은 원소의 삭제에 O(logN)이 걸린다.원칙적으로 가장 높은 원소의 확인과 삭제만이 가능하다.최상위 원소 삭제 후 다시 우선순위 큐를 만족할 때까지 계층 이동이 일어난다.이진 트리의 모양을 띠고 있다.이진 탐색 트리와 다른 점은 이진 탐색 트리가 왼쪽 자식이 자신보다 작고 오른쪽 자식이 자신보다 커야 한다면, 우선순위 큐는 왼쪽, 오른쪽 자식 모두 자신보다 우선순위가 낮으면 된다.최소 ..

정의왼쪽 서브 트리의 모든 값이 부모 노드보다 작고, 오른쪽 서브 트리의 모든 값이 부모 노드보다 큰 이진 트리서브 트리 : 자식 노드로부터 뻗어나가는 하위 트리이진 트리 : 자식이 최대 2개까지 있는 트리 구조 특징삽입, 삭제, 탐색, 갱신 모두 O(logN)의 시간이 걸린다.단, 한쪽 부분에 값이 몰리는 편향이 발생할 수 있는데, 이 편향이 심해질수록 성능이 저하된다.삽입 시 자동으로 원소가 크기 순으로 정렬되어 저장된다.특정 노드보다 작거나 큰 최초의 노드가 무엇인지 O(logN)에 알아낼 수 있다.편향된 이진 트리를 균형 있게 다시 배치해 편향을 해소한 트리를 자가 균형 트리라 한다.대표적으로 AVL트리와 Red Black 트리가 있다.O(N^2)보다 빠른 속도로 데이터의 대소 관계가 필요한 경우..

정의키에 대응되는 값을 저장하는 자료구조.해시 함수를 통해 키를 해시 값으로 변환한 뒤, 테이블에서 그 값에 해당하는 인덱스에 배치해 데이터를 관리한다. 특징삽입, 삭제, 검색, 갱신에 전부 O(1)의 시간이 걸린다.단, 서로 다른 키가 같은 해시 값을 갖게 되면 충돌이 발생하게 되는데 이 충돌이 빈번해질 경우 성능이 저하된다.모든 키의 해시 값이 같은 최악의 경우 O(N)의 시간이 걸리게 된다.때문에 합리적인 해시 함수를 사용해 각 키의 해시 값을 최대한 고르게 퍼뜨려야 성능을 향상시킬 수 있다일단 충돌이 발생한 경우에 대한 대표적인 대처 방법은 Chaining과 Open Addressing이 있다.Chaining : 각 인덱스마다 연결 리스트를 두고 충돌 발생 시 해당 연결 리스트에 삽입해 충돌을 회..

정의양쪽 끝 모두에서 데이터를 넣고 뺄 수 있는 자료구조 특징요소를 추가하고 제거하는 데 O(1)의 시간이 걸린다.무조건 한쪽 끝에서 요소를 넣거나 빼기 때문에한쪽 끝의 요소를 확인하는 데 O(1)의 시간이 걸린다.원칙적으로 양쪽 끝의 요소만 확인할 수 있다.