Hee's Story

문제 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망에서 사람들의 친구 관계는 그래프로 표현할 수 있는데, 이 그래프에서 사람은 정점으로 표현되고, 두 정점을 잇는 에지는 두 정점으로 표현되는 두 사람이 서로 친구 관계임을 표현한다. 예를 들어, 철수와 영희, 철수와 만수, 영희와 순희가 서로 친구 관계라면 이를 표현하는 친구 관계 그래프는 다음과 같다. 친구 관계 그래프를 이용하면 사회망 서비스에서 어떤 새로운 아이디어가 전파되는 과정을 이해하는데 도움을 줄 수 있다. 어떤 새로운 아이디어를 먼저 받아들인 사람을 얼리 아답터(early adaptor)라고 하는데, ..

문제 전대프연 대회에서 문제를 푼 팀은 풍선을 받게 된다. 풍선은 사람이 직접 달아주기 때문에 자원 봉사자가 필요하다. 풍선은 방 A와 방 B에 보관되어 있다. 대회에 참가한 팀의 수는 총 N개이고, 앉아있는 자리는 서로 다르다. 어떤 팀은 방 A에 가깝고, 어떤 팀은 B에 더 가깝다. 각 팀에게 달아줘야 하는 풍선의 수와 방 A와 B로부터의 거리가 주어진다. 이때, 모든 풍선을 달아주는데 필요한 이동 거리의 최솟값을 출력한다. 대회에서 풍선을 달아주는 사람은 매우 많고, 풍선은 한 가지 색상을 여러 개 달아준다고 가정한다. 풍선을 달기 위해 이동해야하는 거리는 팀이 A와 B로부터 떨어진 거리와 같다. 풍선을 달아주는 사람은 한 번에 풍선 하나만 들고 이동할 수 있다. 입력 입력은 여러 개의 테스트 케이..

문제 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라인을 정하였다. 문제 번호데드라인컵라면 수 1 2 3 4 5 6 7 1 1 3 3 2 2 6 6 7 2 1 4 5 1 위와 같은 상황에서 동호가 2, 6, 3, 1, 7, 5, 4 순으로 숙제를 한다면 2, 6, 3, 7번 문제를 시간 내에 풀어 총 15개의 컵라면을 받을 수 있다. 문제는 동호가 받을 수 있는 최대 컵라면 수를 구하는 것이다. 위의 예에서는 15가 최대이다. 문제를 푸는데는 단위 시간 1이 걸리며, 각 문제의 데드라인은 N 이하이다. 또, 각 문제를 풀 때 받을 수 있는 컵라면 수와 최대로 받을 ..

문제 수열이 주어졌을 때, M을 수열의 모든 두 원소의 차이 중 가장 큰 값이라고 한다. m은 그 차이 중 가장 작은 값이라고 한다. 크기가 N인 수열 V가 주어진다. 여기서 K개 수를 적절히 제거해서 M+m을 가능한 작게 만드는 프로그램을 작성하시오. 입력 첫째 줄에 N(3 ≤ N ≤ 1,000,000)과 K(1 ≤ K ≤ N-2)가 주어진다. 둘째 줄에 V의 원소가 공백으로 구분되어 주어진다. (-5,000,000 ≤ Vi ≤ 5,000,000) 출력 첫째 줄에 가장 작은 M+m을 출력한다. 예제 입력 5 2 -3 -2 3 8 6 예제 출력 7 풀이 참고로 compareTo를 잘못구현하면 런타임 오류가 난다.. 코드 import java.io.BufferedReader; import java.io.I..

문제 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저의 배치는 다음 조건을 만족한다. 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다. 각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다. 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다. 아래 그림은 위 조건을 만족하는 예를 보여준다. 수평으로 그려진 굵은 실선은 쇠막대기이고, 점은 레이저의 위치, 수직으로 그려진 점선 화살표는 레이저의 발사 방향이다. 이러한 레이저와 쇠막대기의 배치는 다음과 같이 괄호를 이용하여..

문제 알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오. 길이가 짧은 것부터 길이가 같으면 사전 순으로 https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1≤N≤20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 입력 첫째 줄에 단어의 개수 N이 주어진다. (1≤N≤20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. 출력 조건에 따라 정렬하여 단어들을..