투투

문제 두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다. 예를 들어, 과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다. 전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위치의 번호가 주어질 때, 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 구하는 프로..

문제 수열 A가 주어졌을 때 가장 긴 증가하는 부분 수열을 구하라. 입력 첫째 줄에 수열의 크기 N이 주어진다. 둘째 줄에는 N개의 수를 갖는 수열이 주어진다. 출력 첫째 줄에 가장 긴 증가하는 부분 수열의 길이를 출력하고 둘째 줄에 가장 긴 증가하는 부분 수열을 출력한다. 접근 가장 긴 증가하는 부분수열을 구하는 것을 LIS 알고리즘이라 하고 완전 탐색, 동적 계획법, 이진 탐색의 방법이 있다. 이 문제에서는 동적 계획법으로 접근을 했다. {10 20 10 30 20 50}이라는 수열이 있을 때 30까지의 증가하는 부분수열을 구해보자. 이전에 20의 증가하는 부분수열의 길이는 2이다. - 10과 30을 비교했을 때 30이 더 크다. - 이제 증가하는 부분수열은 10+30로 길이는 2이다. 원래 10만 ..

문제 NxN 크기의 땅이 있고 1X1개의 칸으로 나누어져있다. 각각의 땅에는 나라가 존재하고 몇 명이 사는지 알 수 있다. 인구이동이 시작할 때는 다음과 같이 진행되고 인구 이동을 할 수 없을 때까지 반복한다. 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루동안 연다. 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다. 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다. 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다. 연합을 해체하고, 모든 국경선을 닫는다. 각 나라의 인구수가 주어졌을 때..

문제 빨간색, 파란색, 노란색, 녹색의 네 가지 색이 있는 카드가 있고 각 색깔별로 1부터 9까지 숫자가 쓰여져있다. 총 36장의 카드에서 5장의 카다를 뽑고 아래와 같은 규칙으로 계산한다. 1. 카드 5장이 모두 같은 색이고 숫자가 연속될 때 가장 높은 숫자에 900을 더한다. 2. 카드 5장 중 4장의 숫자가 같을 때 점수는 같은 숫자에 800을 더한다. 3. 3장의 숫자가 같고 2장의 숫자도 같을 때 3장이 같은 숫자에 10을 곱하고 2장이 같은 숫자를 더한 다음 700을 더한다. 4. 5장의 숫자가 연속적일 때 점수는 가장 높은 숫자에 600을 더한다. 5. 카드 5장의 숫자가 연속적일 때 가장 높은 숫자에 500을 더한다. 6. 3장의 숫자가 같을 때 점수는 숫자에 400을 더한다. 7. 2장의..

문제 강을 가로지르는 하나의 차선으로 된 다리가 하나 있다. 이 다리를 n개의 트럭이 건너가려고 한다. 다리 위에는 w대의 트럭만 동시에 올라갈 수 있고 다리의 길이는 w 단위길이, 각 트럭들은 하나의 단위시간에 하나의 단위길이만큼 이동할 수 있다. 또한, 동시에 다리 위에 올라가 있는 트럭들의 무게의 합은 다리의 최대하중인 L이하여야한다. 다리의 길이와 다리의 최대하중, 다리를 건너려는 트럭들의 무게가 순서대로 주어졌을 때 모든 트럭이 다리를 건너는 최단시간을 구하라. 입력 첫째 줄에 트럭의 수 N, 다리의 길이 W, 다리의 최대하중 L이 주어진다. 두 번째 줄에는 트럭의 무게가 N개 주어진다. 출력 모든 트럭들이 다리를 건너는 최단시간을 출력한다. 접근 처음에는 주어진 예시를 통해 직접 그려보면서 시..

NxN의 맵이 있다. (0, 0)에서 출발해서 (N-1, N-1)까지 이동을 하려고하는데 중간중간에 도로들이 파손이 되어있다. 파손된 도로를 복구하는데 걸리는 시간은 각 칸에 적힌 수만큼 걸린다. 도로를 이동할 때 걸리는 시간을 제외하고 출발지부터 도착지까지 복구하면서 이동할 때 걸리는 시간이 최소인 시간을 구하라. 접근 - 기본적으로 다익스트라를 적용시켰다. - 2차원 맵이기 때문에 현재위치에서 상하좌우 칸에 대한 시간을 구하여 최솟값을 갱신해나간다. 구현 - 2차원 맵에 대한 정보를 입력받아 graph라는 2차원 리스트에 저장한다. - 이후 solve함수에서 해를 구하여 반환한다. - 다음은 solve함수에 대한 코드이다. - 먼저 각 칸을 INF로 초기화하여 나중에 최솟값으로 갱신될 수 있도록 한다..

어떤 도시에 E개의 일방통행 도로가 있고 각 구간이 만나는 연결지점에 0번부터 N번까지의 번호가 붙어있다. 이때 0번 지점에서 N번 지점까지 이동하는데 걸리는 최소한의 거리가 얼마인지 구하라. 다익스트라 알고리즘 - 다음 방문하는 노드에 대한 경로를 지금까지 기록한 정보를 통해 최솟값을 갱신한다. - 기록되어있는 정보에는 출발점부터 해당 번호까지 왔을 때의 최솟값이 저장되어있으며, 계속 갱신될 수 있다. 구현 - 2차원 리스트로 그래프를 표현한다. - 초기에 INF 값으로 초기화한 이유는 이후에 그래프를 탐색하면서 최솟값을 찾을 때 연결되어있지 않은 그래프는 최솟값의 후보에서 벗어나도록 하기위함이다. - E개의 일방통행 도로를 입력받아 그래프에 저장한다. V, E = map(int, input().spl..

0번부터 V번까지의 노드가 있고 E개의 간선이 주어지는 그래프가 있을 때 최소신장트리를 구성하는 가중치의 합을 출력한다. 프림 알고리즘 - 특정 정점을 시작으로 점진적으로 최소신장트리를 완성해나간다. - 지금까지 선택한 정점을 검색하여 아직 선택하지않은 정점 중에 가중치가 가장 적은 정점을 선택한다. 구현 - 정점의 개수(V)와 간선의 개수(E)를 입력받는다. - 간선의 개수만큼 노드a, 노드b, 가중치w를 입력받아 2차원 리스트로 그래프를 표현한다. V, E = map(int, input().split()) graph = [[0 for _ in range(V+1)] for _ in range(V+1)] for _ in range(E): a, b, w = map(int, input().split()) g..

문제 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 그로부터 일정 시간 뒤 a도 감염되고 만다. 이때 b가 a를 의존하지 않는다면, a가 감염되더라도 b는 안전하다. 최흉최악의 해커 yum3이 해킹한 컴퓨터 번호와 각 의존성이 주어질 때, 해킹당한 컴퓨터까지 포함하여 총 몇 대의 컴퓨터가 감염되며 그에 걸리는 시간이 얼마인지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 최대 100개이다. 각 테스트 케이스는 다음과 같이 이루어져 있다. 첫째 줄에 컴퓨터 개수 n, 의존성 개수 d, 해킹당한 컴퓨터의 번..

문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고있다. 이 N명의 학생이 X번 마을에 모여서 파티를 하려고한다. 마을 사이에는 총 M개의 단방향 도로들이 있고 이 도로들을 지나갈 때는 T만큼의 시간이 소비된다. 각각의 학생들이 각자의 마을에서 X번 마을로 파티하러왔다가 다시 돌아갈 때 걸리는 시간이 가장 오래걸리는 시간이 몇인지 구하라. 입력 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어온다. 시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개이다. 출력..