본문 바로가기

Algorithm

(4)
단절점 얼마 전에 후배에게 단절점과 SCC에 대한 질문을 받았는데 공부한지 오래되기도 했고 정리하는 시간이 필요할 거 같아서 글로 남기기로 하였다! 단절점은 우선 무향 그래프(Undirected Graph)에서 정의되는 개념이다. 단절점이란, 해당 정점을 그래프에서 지웠을 때 그래프의 전체 컴포넌트 수가 늘어나는 정점을 의미한다. 더 쉽고 풀어서 말해보자면 이쪽과 저쪽을 (혹은 그 이상을) 연결하는 점을 의미한다. 연결성을 중요하게 생각하는 상황에서(라우터의 연결을 나타낸 그래프 같은 거?) 단절점은 정말 중요한 점이다. 해당 정점에 (더 자세하게는 단절점에 연결된 간선이) 문제가 생긴다면 전체적인 연결 자체에 문제가 생긴다는 말이니까. 그렇다면 이 단절점은 어떻게 구할까? 제일 쉽고, 제일 빨리 생각나는 방법..
BOJ 16681 등산 역시나 오늘도 문제를 풀었고, 역시나 오늘도 고통을 받았다. (아니 왜 하던 걸 못해) 시간이 없으니(시계톡톡) 바로 오답을 시작한다ㅏㅏㅏ.... 1. 문제 설명 https://www.acmicpc.net/problem/16681 16681번: 등산 첫 번째 줄에 지도에 표시된 지점의 개수, 지점을 잇는 경로의 개수, 주환이의 거리 비례 체력 소모량, 높이 비례 성취감 획득량을 나타내는 정수 N, M, D, E가 공백을 사이에 두고 주어진다. (2 ≤ N ≤ 100,000, 1 ≤ M ≤ 200,000, 1 ≤ D ≤ 100, 1 ≤ E ≤ 100) 두 번째 줄에 N개의 정수 h1, ... ,hN이 공백으로 구분되어 주어진다. hi는 i 번째 지점의 높이를 의미한다. (1 ≤ hi ≤ 1,000, www..
BOJ 11581 구호물자 어제부터 IUPC를 대비해서 역대 IUPC 문제들을 풀어보고 있다. 어제는 1회를 풀었는데 컨디션이 안 좋았는지 실력이 안 좋았는지 둘 다 안좋았는지 여튼 생각만큼 많이 못풀었다. 이것저것 많이 틀리기도 하고 생각을 못했던 것도 있고, 여전히 못하는 것들도 있다. 어짜피 우승이 목적이 아니기 때문에 ^^ 오답의 순서는 내 맘대로다 ㅎ 1. 문제 설명 11581번: 구호물자 Description을 요약하면 1 → N까지의 길에 Cycle이 있는 지를 찾는 문제였다. 내가 선택한 경로가 Cycle이 없더라도, 일단 갈 수 있는 길에 Cycle이 있으면 Cycle이 있다고 판단해야 한다. 민지를 도와 어떠한 길을 선택하더라도 같은 교차로를 다시 방문하는 경우가 있는지 없는지를 판단하는 프로그램을 작성하자. 라..
Red-Black Tree 1. 설명 Dictionary ADT(Abstract Data Type; 추상 자료형)를 구현하는 방법은 여러 가지가 있다. 그중 하나인 Binary Search Tree(이하 BST)는 평균 O(logN)의 삽입, 삭제, 탐색 시간을 가지지만, 최악의 경우 O(N)의 시간 복잡도를 가진다. 이렇게 최악인 경우는 BST에서 원소들이 한 방향으로만 쏠리게 되면 생기게 된다. Best인 케이스는 Tree가 Complete Binary Tree이겠지만 현실은 그렇게 호락호락하지 않다. 그래서 편하게 BST로 구현하고 Worst가 O(N)인 상황을 기도로 피하기에는 여러 가지 애로사항들이 많다. Red-Black Tree는 BST가 가진 문제들을 해결해 줄 수 있다. Wikipedia에는 Red-Black Tr..