1. 문제 1708번: 볼록 껍질 (acmicpc.net) 1708번: 볼록 껍질 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다. x좌표와 y좌표의 범 www.acmicpc.net 2. 풀이 선물포장 알고리즘 1) 가장 왼쪽 아래인 점을 찾아 컨벡스헐에 포함시킨다. 2) 이 점을 기준점으로 삼는다 3) 컨벡스헐에 마지막에 넣은것을 기준으로 가장 왼쪽에 있는 점을 찾아 포함시킨다. 4) 이 점이 처음 정한 기준점이 될때까지 3번을 반복한다. 3번에서 모든점을 검사해야한다. 따라서 점 H개가 컨벡스 헐에 포함되면 O(NH) 의 시간복잡도를 가지게 된다. * hypo..

1. 문제 11689번: GCD(n, k) = 1 (acmicpc.net) 11689번: GCD(n, k) = 1 자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 2. 풀이 오일러 피 함수는 n과 서로소인 1부터 n까지의 정수를 리턴하는 함수이다. 오일러 피 함수 - 위키백과, 우리 모두의 백과사전 (wikipedia.org) 오일러 피 함수 - 위키백과, 우리 모두의 백과사전 오일러 피 함수의 그래프. ϕ(1)부터 ϕ(1000)까지의 값들을 나타낸다. 수론에서 오일러 피 함수(-函數, 영어: Euler’s phi (totient) function)는 정수환의 몫환의 가역원을 세는 함수이다. 즉,..

1. 문제 3015번: 오아시스 재결합 (acmicpc.net) 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net 2. 풀이 이 문제의 핵심은 같은 키를 가진 사람들이다. 문제의 정의에의해 같은 키를 가진 사람들이 연속적으로 줄을 서고 있을때 서로를 볼 수 있기 때문이다. 따라서 pair를 사용하여 같은 키인 사람의 수를 따로 저장하여 처리해야한다. 알고리즘은 다음과 같다 1) 앞에서부터 스택에 담는다 2) 스택에 담기전 스택의 top 보다 큰값이면 스택의 top이 더 큰값이 올때까지 p..

1. 문제 2533번: 사회망 서비스(SNS) (acmicpc.net) 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net 유사한 문제: [그래프] GALLERY 감시 카메라 설치 (tistory.com) [그래프] GALLERY 감시 카메라 설치 1. 문제 모든 방을 감시할 수 있게 감시 카메라를 최소한으로 설치해야한다. 이때 방은 모두 트리 간선을 이루고 있다고 한다. (연결되지 않은 방 또한 있다.) 어떤 방에 카메라를 설치했다고 하 nsgg.tistory.com 2. 풀이 이 문제는 탐욕법으로 문제를..

1. 문제 1275번: 커피숍2 (acmicpc.net) 1275번: 커피숍2 첫째 줄에 수의 개수 N과 턴의 개수 Q가 주어진다.(1 ≤ N, Q ≤ 100,000) 둘째 줄에는 처음 배열에 들어가 있는 정수 N개가 주어진다. 세 번째 줄에서 Q+2번째 줄까지는 x y a b의 형식으로 x~y까지의 합 www.acmicpc.net 2. 풀이 이 문제의 핵심은 수를 업데이트 시켜줘야한다는것이다. 배열을 사용하여 i번째까지의 합을 저장하여 psum[i] - psum[j] 로 구간합을 구하는 방식은 수를 업데이트하려면 최악의 경우 O(N) 의 시간 복잡도를 가진다. 하지만 이런 구간들을 이진 검색 트리 형태로 표현하게되면 그 수가 속하는 구간들을 업데이트하는데 O(lgn) 의 시간복잡도로 업데이트할 수 있다..

1. 문제 9466번: 텀 프로젝트 (acmicpc.net) 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 2. 풀이 이 문제는 간단히 그래프에서 순환하는 구간을 찾는것이다. 강결합 컴포넌트 의 타잔 알고리즘을 응용해서 문제를 해결하였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55..