본문 바로가기

알고리즘

(4)
단절점 얼마 전에 후배에게 단절점과 SCC에 대한 질문을 받았는데 공부한지 오래되기도 했고 정리하는 시간이 필요할 거 같아서 글로 남기기로 하였다! 단절점은 우선 무향 그래프(Undirected Graph)에서 정의되는 개념이다. 단절점이란, 해당 정점을 그래프에서 지웠을 때 그래프의 전체 컴포넌트 수가 늘어나는 정점을 의미한다. 더 쉽고 풀어서 말해보자면 이쪽과 저쪽을 (혹은 그 이상을) 연결하는 점을 의미한다. 연결성을 중요하게 생각하는 상황에서(라우터의 연결을 나타낸 그래프 같은 거?) 단절점은 정말 중요한 점이다. 해당 정점에 (더 자세하게는 단절점에 연결된 간선이) 문제가 생긴다면 전체적인 연결 자체에 문제가 생긴다는 말이니까. 그렇다면 이 단절점은 어떻게 구할까? 제일 쉽고, 제일 빨리 생각나는 방법..
Visual Studio에서 <bits/stdc++.h> 사용하기 처음에 알고리즘 문제를 풀다보면 귀찮?까다로운? 점이 include일 것이다. 어떤 헤더 파일에 어떤 함수가 들어있는지도 익숙하지 않고, 컴파일러는 include를 하라고 오류를 뱉어댄다. 어느 헤더 파일에 어떤 함수가 들어 있는지를 대략적으로 알고 있는지는 중요하지만, 어느 정도 실력이 생기고 난 다음에는 include를 하는 일이 귀찮게 느껴질 때가 있다. 이 라는 헤더파일에는 우리가 자주 쓸만한 헤더파일들을 몽땅 다 include 해놓은 헤더파일이다. 이 헤더파일은 gcc 계열의 컴파일러에는 미리 내장되어 있다. 그래서 대부분의 Online Judge 사이트에서는 저 헤더 파일을 사용할 수 있다. (Judge 서버가 대부분 Linux 계열이니까...?) 하지만, 대부분의 사람(나 포함)들은 Wind..
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..
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..