문제 링크 https://www.acmicpc.net/problem/22254 22254번: 공정 컨설턴트 호석 거듭된 창업 성공을 이룬 류진국 사장은 이번에는 맞춤형 선물을 제작해주는 공장을 만들기로 했다. 현재 들어온 맞춤형 선물 주문은 총 $N$개이며, 각 맞춤형 선물마다 제작에 필요한 시간이 정 www.acmicpc.net 문제 풀이 - "모든 선물을 X 시간 내에 만들 기 위한, 공정 라인의 최소값" 으로 문제 해석하여 매개변수 탐색으로 풀이 - PriorityQueue 사용하여 공정 라인 수가 정해졌을 때 X 시간내 선물 생산 가능 여부 확인 (boolean) - 선물 개수 N =최대 10^5개, 제작 완료 X = 10^9 시간 제한 걸리고, 각 선물의 공정시간이 10^9일 때 공정라인은 10..

문제 링크 https://www.acmicpc.net/problem/22252 22252번: 정보 상인 호석 암흑가의 권력은 주먹과 정보에서 나온다. 주먹은 한 명에게 강하고, 정보는 세계를 가지고 놀 수 있기 때문에 호석이는 세상 모든 정보를 모으는 "정보 상인"이 되고 싶다. 정보 상인은 정보를 www.acmicpc.net 문제 풀이 - 해쉬맵, 우선순위 큐 사용하여 풀이 - 결과 최대치 long 최대치 생각해보기 - 쿼리 10만개가 주어지고, 고릴라가 10만 가치의 정보를 10만개씩 가지고 있고, 구매자가 10만개씩 구매한다면 .. 쿼리가 10만개 있을 때 5만개씩 상점에 정보 추가하고, 5만개씩 상점에서 구매자가 구매한다면 = 50,000 * 10^5 * 10^5 (int 범위 초과) - 고릴라 ..

문제 링크 https://www.acmicpc.net/problem/21278 21278번: 호석이 두 마리 치킨 위의 그림과 같이 1번과 2번 건물에 치킨집을 짓게 되면 1번부터 5번 건물에 대해 치킨집까지의 왕복 시간이 0, 0, 2, 2, 2 로 최소가 된다. 2번과 3번 건물에 지어도 동일한 왕복 시간이 나오지만 더 www.acmicpc.net 문제 풀이 다익스트라 풀이 건물 중 두 개를 뽑는 조합을 구하고 다익스트라 알고리즘으로 최단 거리를 구한다. - N : 건물의 개수, 노드 수, 최대 100 - M : 도로의 개수, 간선 수, 최대 N * (N-1)/2 = 4950 - 100개의 건물 중 2개를 뽑는 조합 : 100C2 = 100 * 99 / 2! = 4950 - 다익스트라 알고리즘 시간 ..

문제 링크 https://www.acmicpc.net/problem/21276 21276번: 계보 복원가 호석 석호촌에는 N 명의 사람이 살고 있다. 굉장히 활발한 성격인 석호촌 사람들은 옆 집 상도 아버님, 뒷집 하은 할머님 , 강 건너 유리 어머님 등 모두가 한 가족처럼 살아가고 있다. 그러던 어느 날 www.acmicpc.net 문제 풀이 - 한달 지난 후 두번째 풀이 - 배열/정렬/해시맵/인접행렬과 같은 자료 구조를 활용하는 문제였다 예제 입력 7 -- 사람 수 daeil sangdo yuri hoseok minji doha haeun 7 -- 정보의 개수 hoseok sangdo -- X 의 조상은 Y이다 yuri minji hoseok daeil daeil sangdo haeun doha do..

문제 링크 https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 문제 풀이 - 스택 자료 구조 응용 문제 - 시간 복잡도 : O(N) 절차 1) 스택 선언하고 "(" 인 경우 스택에 추가한다. 2) ")"는 괄호일 때 2-1) 이전 괄호가 "(" 인 경우 레이저가 되므로, pop() 후 stack.size() 를 결과에 합산한다. 2-2) 레이저가 아닌 경우(=쇠막대 하나가 끝나는 위치) pop() 후 +1 을 결과에 합산한다. 예제입력 2 (((()(()()..

문제 링크 https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 문제 풀이 - 다익스트라 알고리즘 - 시간복잡도 : O(ElogV) - s에서 출발하여 주어진 경로 g-h, h-g를 거쳐 최단 거리로 의심되는 노드에 도착하는지 파악하고, 경로를 거쳐 도착했을 경우 형식에 맞춰 출력하는 문제 처음 2차원 배열(int[][] dist = new int[노드][2]) 로 하여 풀이 하였는데 틀렸다 - 0번 인덱스에는 경로(g - h, h-g)를 거치..

문제 링크 https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 문제 풀이 - 다익스트라 알고리즘, bfs 수행하면서 방향 전환시 같은 방향이 아닌 경우 거울을 하나씩 추가한다 - 두 점을 이으면서 거울의 최소값을 구하면 되는 아주 Simple한 문제인 줄 알았으나 .. 중복 방문 처리에 대한 예외 케이스가 있었다 아래 예외 케이스를 참고하도록 하자 https://www.acmicpc.net/board/view/109356 글 읽기 - 데이..

문제 링크 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 문제 풀이 - 앞서 MST 문제 풀이하다가 '트리의 지름'에 대한 이론을 알게 되었고, 관련 문제 풀이함 '트리의 지름'에 대한 강의 영상을 찾아보니 초보 알고리즘이란다 (하하하.. 심플하긴하다) https://dev-ljw1126.tistory.com/369 [BOJ20010] 악덕 영주 혜유 (크루스칼, 프림, MST, 최소신장트리, 트리의 지름) 문제 링크 http..

문제 링크 https://www.acmicpc.net/problem/20010 20010번: 악덕 영주 혜유 FT온라인 게임에서 치열한 경쟁을 통해 영주가 된 혜유는 퀘스트를 받았다. 퀘스트의 내용은 자신이 관리하고 있는 마을 사이에 교역로를 건설하여 마을 간 교류를 활성화시키는 것이다. 이때, www.acmicpc.net 문제 풀이 최소 가중치를 가지는 MST는 구했는데, 두번째 값을 구하지 못해 3시간을 소비했다. 찾아본 결과 트리의 지름을 구하는 방법을 몰랐고, 문제 지문을 제대로 읽지 못해 MST 트리 정보를 활용하는 것을 파악하지 못했다..(반성) 문제 지문을 다시 보면 아래와 같다 마음이 괘씸한 혜유는 돈을 최대한 적게 쓰면서 퀘스트를 달성하려고 한다. 혜유를 도와서 (1)모든 마을과 마을을 ..

문제 링크 https://www.acmicpc.net/problem/1368 1368번: 물대기 첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다. 다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어 www.acmicpc.net 문제 풀이 문제를 접근할 때 우물을 무조건 하나 파야 한다고 생각해서 제일 적은 비용이 드는 우물을 기준으로 구했으나 '틀렸습니다' 만 나왔다 기술 블로그를 찾아본 결과, 우물을 하나 파는 행위를 간선(Edge) 정보로 추가해서 풀이해야 했다. - 임의 노드 0번에 {i번 논, 논을 파는 비용} 으로 정의해서 컬렉션에 담는다 - 그리고 0번 노드부터 시작하..

문제 링크 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 문제 풀이 - 별자리(노드)를 모두 연결하는 최소 비용을 구하는 문제 - 프림 알고리즘으로 풀이 (최소신장트리, MST) - 시간 복잡도 : O(ElogV) 1) 2차원 좌표로 입력 주어지는데 각각 노드 1, 2, .. 로 보고 노드별 거리 값을 계산하여 컬렉션에 담는다 (양방향 그래프) 2) 시작 노드는 1로 고정해서 프림 알고리즘 수행 - 방문한적 있으면 continue; - 방문한적..

문제 링크 https://www.acmicpc.net/problem/1414 1414번: 불우이웃돕기 첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선 www.acmicpc.net 문제 풀이 - 프림 알고리즘(최소 신장트리) 사용하여 풀이 - 시간 복잡도 : O(ElogV) 절차 1) 모든 컴퓨터(노드)를 연결하는 최소 랜선 길이(비용)을 구한다. 2) 다솜이가 가진 총 랜선 길이에서 최소 랜선 길이 뺀 나머지를 기부 한다 알파벳이 소문자인지, 대문자인지 구분하는 방법이 조금 애매했는데 이번 문제를 통해 Character 클래스에 유용한 메서드를 알게 되었다..

문제 링크 https://www.acmicpc.net/problem/6497 6497번: 전력난 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들 www.acmicpc.net 문제 풀이 그러나 만약 어떤 두 집을 왕래할 때, 불이 켜져 있지 않은 길을 반드시 지나야 한다면 위험하다. 그래서 도시에 있는 모든 두 집 쌍에 대해, 불이 켜진 길만으로 서로를 왕래할 수 있어야 한다. 위의 지문이 조금 이해가 안되었는데, 사이클이 발생하는 경우에 대해 설명하는 것으로 이해했다. - 크루스칼/프림 알고리즘 (최소 신장트리,MST) 사용하여 최소 비용을 구한 후 전체 비용과의 차..

문제 링크 https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 문제 풀이 크루스칼 알고리즘을 사용하기 위해 노드와 노드 사이의 비용 정보가 필요한데, 2차원 좌표(X, Y)가 주어질 때 노드로 생각하지 못했고, 거리 계산 또한 생각을 하지 못했다. 해당 문제를 통해 시야가 또 좁아진 점을 반성한다.. 입력 예시 4 1 // 노드 수, 연결된 노드 수 1 1 // 노드 1 3 1 // 노드 2 2 3 // 노드 3 4 3 ..

문제 링크 https://www.acmicpc.net/problem/2617 2617번: 구슬 찾기 모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 www.acmicpc.net 문제 풀이 문제 지문에 " 무게가 중간이 절대로 될 수 없는 구슬의 수 " 키워드 였다. 풀어서 적어보자면 자기보다 크거나 작은 구슬의 개수가 중간 개수가 넘어가면 절대 중간이 될 수 없는 구슬이다. - 플로이드 워셜 풀이 - 시간 복잡도 : O(N^3) + O(N^2) // 플로이드 워셜 알고리즘 + 각 구슬별로 크거나 작은 구슬 카운팅 - 구슬 절반 개수 : ( N..

문제 링크 https://www.acmicpc.net/problem/11780 11780번: 플로이드 2 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 문제 풀이 - 시간 복잡도 : O(N^3) - 플로이드 워셜 공식 활용하여 각 노드별 최단 경로는 구한다 floyd[i][j] = min(floyd[i][j], floyd[i][k] + floyd[k][j] i -> j로 바로가는 비용과 k 를 거쳐 가는 i -> k -> j 비용 중 작은 값을 구한다 경로 추적 - (1,1) ~ (N, N) 까지 경로 추적하는 부분에서 시작과 끝 ..

문제 링크 https://www.acmicpc.net/problem/13424 13424번: 비밀 모임 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 방 www.acmicpc.net 문제 풀이 - 플로이드 워셜 기본 문제 - 시간 복잡도 = 플로이드 워셜 수행 + 친구 별 방에 대한 최단 거리 합산 + 최소 비용 가지는 방 번호 구하기 = O(N^3) + (N^2) + (N) (최대 친구 수는 N 이하, N번 방) 절차 1) 각 노드별 다른 노드에 대한 최단 경로를 플로이드 워셜 알고리즘으로 구한다, 시간 복잡도 O(N^3) 2) 친구별 방에 대한 최단 거리 비용을..

문제 링크 https://www.acmicpc.net/problem/17182 17182번: 우주 탐사선 우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위 www.acmicpc.net 문제 풀이 플로이드 워셜로 각 노드별 다른 노드에 대한 최단 경로를 구할 수 있었다. 그런데 출발 행성 K 위치가 주어졌을 때 다른 행성을 탐색하는데 걸리는 시간을 어떻게 구할 지에서 삽질을 여러번 하였다. 결국 재귀 함수 사용한 완전 탐색으로 구하면 방문 여부 체크하며 구하면 되는 문제였다. "이미 방문한 행성도 중복해서 갈 수 있다"는 문제 지문이 함정이 아니었나 싶다 스스로 ..