인프라 엔지니어가 꾸는 꿈

문제 링크 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에서 출발하여 각 도시 사이에 설치된 통로를 거쳐, 최대한 많이 퍼져나갈 것이다. 각 도시의 번호와 통로가 설치되어 있는 정보가 주..

문제 링크 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..

문제 링크 https://codeup.kr/problem.php?id=4572 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y 좌표값과 오 codeup.kr Test Case 문제 풀이 평범한 bfs, dfs 문제인줄 알았는데 초반에 입력받은 사각형 그래프 좌표가 주어지고 그래서 어쩌라고? 라는 생각이 들었다. 찬찬히 생각 해보니 좌표가 주어진 곳을 1로, 아닌곳을 0으로 처리해서 0인 부분을 탐색하면 되는 문제. 예전에 풀때는 다른사람 코드 보고 이해도 못하고 그냥 카피 코딩만 했었는데 이번에 다시 푸니까 풀리네 생각을 하도 안하고 살다보니..