인프라 엔지니어가 꾸는 꿈

문제 링크 https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net Test Case 문제 풀이 처음에는 단순한 크루스칼 문제로 풀면 될줄 알았는데, N 조건을 보면 최대 100,000이기 때문에 모든 노드를 연결하는 경우의 수인 N(N-1)/2개를 다 계산하면 시간초과가 나온다. 따라서 다른 방법으로 두 행성간의 거리를 확인해야 한다. 터널의 비용이 min(X좌표 차, Y좌표차, Z좌표 차)인 점을 생각해서, 주어진 각..

문제 링크 한 마을은 N개의 집과 m개의 도로로 구성되어 있습니다. 각 집은 0번부터 N-1번까지의 번호로 구분됩니다. 모든 도로에는 가로등이 구비되어 있는데, 특정한 도로의 가로등을 하루 동안 켜기 위한 비용은 해당 도로의 길이와 동일합니다. 예를 들어 2번 집과 3번 집 사이를 연결하는 길이가 7인 도로가 있다고 해봅시다. 하루 동안 이 가로등을 켜기 위한 비용은 7이 됩니다. 정부에서는 일부 가로등을 비활성화하되, 마을에 있는 임의의 두 집에 대하여 가로등이 켜진 도로만으로도 오갈 수 있도록 만들고자 합니다. 결과적으로 일부 가로등을 비활성화하여 최대한 많은 금액을 절약하고자 합니다. 마을의 집과 도로 정보가 주어졌을 때, 일부 가로등을 비활성화하여 절약할 수 있는 최대 금액을 출력하는 프로그램을 ..

문제 링크 https://www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net Test Case 문제 풀이 union-find문제 인데 완벽하게 이해를 하고 풀지는 못했다. 내가 확실히 이해한 부분은 g_i를 입력받았을 때 최대한 도킹을 많이 하기 위해서는 해당 번호의 게이트로 도킹하는 것이 제일 최선의 방법이라는 점이다. 처음에 문제만 봐서는 union-find 문제인지 알기어렵지만 문제 조건을 보면 G, P의 범위가 매우크기 ..

문제 링크 한울이가 사는 나라에는 N개의 여행지가 있으며, 각 여행지는 1 ~ N번 까지의 번호로 구분된다. 또한 임의의 두 여행지 사이에는 두 여행지를 연결하는 도로가 존재할 수 있다. 이때, 여행지가 도로로 연결되어 있다면 양방향으로 이동이 가능하다. 한울이는 하나의 옇애 계획을 세운 뒤에 이 여행 계획이 가능한지 여부를 판단하고자 한다. 예를들어 N=5이고, 다과 같이 도로의 정보가 주어진다 1번 - 2번 1번 - 4번 1번 - 5번 2번 - 3번 2번 - 4번 만약 한울이의 여행 계획이 2번 -> 3번 -> 4번 -> 3번 이라면, 2번 -> 3번 -> 2번 -> 4번 -> 2번 -> 3번의 순서로 여행지를 방문하면, 여행 계획을 따를 수 있다. 여행지의 개수와 여행지 간의 연결 정보가 주어졌을 ..

문제 링크 동빈이는 온라인으로 컴퓨터 공학강의를 듣고 있다. 이때 각 온라인 강의는 선수강의가 있을 수 있는데, 선수강의가 있는 강의는 선수 강의를 먼저 들어야만 해당 강의를 들을 수 있다. 동빈이는 총 N개의 강의를 듣고자 한다. 모든 강의는 1번부터 N번 까지의 번호를 가진다. 또한 동시에 여러 개의 강의를 들을 수 있다. 동빈이가 듣고자 하는 N개의 강의 정보가 주어졌을 때, N개의 강의에 대하여 수강하기까지 걸리는 최소 시간을 각각 출력하는 프로그램을 작성하시오 첫째줄에 듣고자하는 강의의 수 1

문제 링크 https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net Test Case 문제 풀이 그래프 문제 중 크루스칼 알고리즘. 전체 그래프에서 2개의 최소 신장 트리를 만들어야하는데, 제일 좋은 방법은 일단 주어진 그래프를 최소 신장 트리로 만들고, 그 중에서 제일 비용이 큰 마을 사이를 빼면 문제 조건을 만족할 수 있다. 서로소 집합 개념과 크루스칼 알고리즘을 알아야 풀 수 있고 find_parent, uni..

문제 링크 방문 판매원 A는 많은 회사가 모여 있는 공중 미래 도시에 있다. 공중 미래 도시에는 1번부터 N번 까지의 회사가 있는데 특정 회사끼리는 서로 도로를 통해 연결되어 있다. 방문 판매원 A는 현재 1번 회사에 위치해 있으며, X번 회사에 방문해 물건을 판매하고자 한다. 공중 미래 도시에서 특정 회사에 도착하기 위한 방법은 회사끼리 연결되어 있는 도로를 이용하는 방법이 유일하다. 또한 연결된 2개의 회사는 양방향으로 이동할 수 있다. 공중 미래 도시에서의 도로는 마하의 속도로 사람을 이동시켜주기 때문에 특정 회사와 다른 회사가 도로로 연결되어 있다면, 정확히 1만큼의 시간으로 이동할 수 있다. 또한 오늘 방문 판매원 A는 기대하던 소개팅에도 참석하고자 한다. 소개팅의 상대는 K번 회사에 존재한다...

문제 링크 어떤 나라에는 N개의 도시가 있다. 그리고 각 도시는 보내고자 하는 메시지가 있는 경우, 다른 도시로 전보를 보내서 다른 도시로 해당 메시지를 전송할 수 있다. 하지만 X라는 도시에서 Y라는 도시로 전보를 보내고자 한다면, 도시 X에서 Y로 향하는 통로가 설치되어 있어야 한다. 예를 들어 X에서 Y로 향하는 통로는 있지만 Y 에서 X로 향하는 통로가 없다면 Y는 X로 메시지를 보낼 수 없다. 또한 통로를 거쳐 메시지를 보낼 때는 일정 시간이 소요된다. 어느 날 C라는 도시에서 위급 상황이 발생했다. 그래서 최대한 많은 도시로 메시지를 보내고자 한다 메시지는 도시 C에서 출발하여 각 도시 사이에 설치된 통로를 거쳐, 최대한 많이 퍼져나갈 것이다. 각 도시의 번호와 통로가 설치되어 있는 정보가 주..

문제 링크 동빈이네 전자 매장에 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호. 어느날 손님이 M개 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 동빈이는 대를 놓치지 않고 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다. 이 때 가게 안에 부품이 모두 있는지를 확인하는 프로그램을 작성하시오. 부품 개수 : 1 ≤ N ≤ 1,000,000 문의한 부품 : 1 ≤ M ≤ 1,000,000 Test Case 입력 5 8 3 7 9 2 3 5 7 9 출력 no yes yes 문제 풀이 이진탐색 알고리즘으로도 풀 수 있고, 계수정렬로도 풀 수 있는데 set 자료구조로도 풀수 있는데 set 개념 기억해두려고 포스팅 Source Code import sys input..

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/60057 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문 programmers.co.kr Test Case 문제풀이 너무 많이 풀어서 풀이가 외워져버린 문제. 문자열 + 구현문제로 연습하기에 너무 좋은 문제라고 생각. 문자열을 1,2,3.. 개로 나눠가며 해당 개수 단위별로 같은 부분이 생기면 카운트 +1, 다르면 이것저것 처리해줘야함 구현문제 많이 풀어봐야할 듯 Source Code import sys input = sys.std..