우노

들어가기 앞서 투 포인터 알고리즘은 리스트에 순차적으로 접근해야 할 때, 2개의 점의 위치를 기록하면서 처리하는 알고리즘을 의미한다. ‘특정한 합을 가지는 부분 연속 수열 찾기’ 또는 ‘정렬되어 있는 두 리스트의 합집합’과 같은 문제에 사용된다. 특정한 합을 가지는 부분 연속 수열 찾기 투 포인터 알고리즘을 이용하여 ‘특정한 합을 가지는 부분 연속 수열 찾기’ 문제를 풀어보자. 해당 문제는, 양의 정수로만 구성된 리스트가 주어졌을 때, 그 부분 연속 수열 중에서 ‘특정한 합’을 갖는 수열의 개수를 출력하는 문제이다. 투 포인터 알고리즘의 특징은 2개의 변수를 이용해 리스트 상의 위치를 기록한다는 점이며, 해당 문제에서는 부분 연속 수열의 시작점(start)와 끝점(end)의 위치를 기록한다. 특정한 부분..

들어가기 앞서, 소수는 2보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어떨어지지 않는 자연수이다. 간혹 코딩 테스트에선, 어떠한 자연수가 소수인지 아닌지 판별하거나, 1부터 N까지의 모든 소수를 출력해야 하는 문제 등이 출제된다. 따라서, 해당 포스팅에선 두 가지 문제를 해결하는 효율적인 방법에 대해서 다뤄볼 것이다. 특정 자연수의 소수 판별 특정한 자연수 X가 소수인지 아닌지 효율적으로 확인하기 위해선, 자연수 X의 제곱근까지 나누어떨어지는 수가 있는지 없는지 확인하면 된다. 해당 알고리즘의 시간 복잡도는, 자연수 X의 제곱근까지만 확인하므로 O(X^1/2)이다. import math # 소수 판별 함수 def is_prime_number(x): # 2부터 x의 제곱근까지의 모든 수를..

문제 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했습니다. 팀은 1번부터 n번까지 번호가 매겨져 있습니다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일합니다. 올해 인터넷 예선 본부에서는 최종 순위를 발표하지 않기로 했습니다. 그 대신에 작년에 비해서 상대적으로 순위가 바뀐 팀의 목록만 발표하려고 합니다. (작년에는 순위를 발표했습니다.) 예를 들어, 작년에 팀13이 팀6보다 순위가 높았는데, 올해 팀6이 팀13보다 순위가 높다면, (6, 13)을 발표할 것입니다. 창영이는 이 정보만을 가지고 올해 최종 순위를 만들어보려고 합니다. 작년 순위와 상대적인 순위가 바뀐 모든 팀의 목록이 주어졌을 때, 올해 순위를 만드는 프로그램을 작성하세요. 하지만, 본부에서 발표한 정보를 가..

문제 때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었습니다. 왕국은 N개의 행성으로 이루어져 있습니다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 합니다. 행성은 3차원 좌표 위의 한 점으로 생각하면 됩니다. 두 행성 A(Xa, Ya, Za)와 B(Xb, Yb, Zb)를 터널로 연결할 때 드는 비용은 min(|Xa - Xb|, |Ya - Yb|, |Za - Zb|)입니다. 민혁이는 터널을 총 N - 1개 건설해서 모든 행성이 서로 연결되게 하려고 합니다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하세요. 입력 조건 첫째 줄에 행성의 개수 N이 주어집니다. (1

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

문제 공항에는 G개의 탑승구가 있으며, 각각의 탑승구는 1번부터 G번까지의 번호로 구분됩니다. 공항에는 P개의 비행기가 차례대로 도착할 예정이며, i번째 비행기를 1번부터 gi번째 (1

문제 한울이가 사는 나라에는 N개의 여행지가 있으며, 각 여행지는 1 ~ N번까지의 번호로 구분됩니다. 또한 임의의 두 여행지 사이에는 두 여행지를 연결하는 도로가 존재할 수 있습니다. 이때, 여행지가 도로로 연결되어 있다면 양방향으로 이동이 가능하다는 의미입니다. 한울이는 하나의 여행 계획을 세운 뒤에 이 여행 계획이 가능한지의 여부를 판단하고자 합니다. 예를 들어 N = 5이고, 다음과 같이 도로의 정보가 주어졌다고 가정합시다. 1번 여행지 - 2번 여행지 1번 여행지 - 4번 여행지 1번 여행지 - 5번 여행지 2번 여행지 - 3번 여행지 2번 여행지 - 4번 여행지 만약 한울이의 여행 계획이 2번 -> 3번 -> 4번 -> 3번이라고 해봅시다. 이 경우 2번 -> 3번 -> 2번 -> 4번 -> ..

문제 동빈이는 숨바꼭질을 하면서 술래로부터 잡히지 않도록 숨을 곳을 찾고 있습니다. 동빈이는 1 ~ N번까지의 헛간 중에서 하나를 골라 숨을 수 있으며, 술래는 항상 1번 헛간에서 출발합니다. 전체 맵에는 총 M개의 양방향 통로가 존재하며, 하나의 통로는 서로 다른 두 헛간을 연결합니다. 또한 전체 맵은 항상 어떤 헛간에서 다른 어떤 헛간으로 도달이 가능한 형태로 주어집니다. 동빈이는 1번 헛간으로부터 최단 거리가 가장 먼 헛간이 가장 안전하다고 판단하고 있습니다. 이때 최단 거리의 의미는 지나야 하는 길의 최소 개수를 의미합니다. 동빈이가 숨을 헛간의 번호를 출력하는 프로그램을 작성하세요. 입력 조건 첫째 줄에는 N과 M이 주어지며, 공백으로 구분합니다. (2

문제 당신은 화성 탐사 기계를 개발하는 프로그래머입니다. 그런데 화성은 에너지 공급원을 찾기가 힘듭니다. 그래서 에너지를 효율적으로 사용하고자 화성 탐사 기계가 출발 지점에서 목표 지점까지 이동할 때 항상 최적의 경로를 찾도록 개발해야 합니다. 화성 탐사 기계가 존재하는 공간은 N x N 크기의 2차원 공간이며, 각각의 칸을 지나기 위한 비용(에너지 소모량)이 존재합니다. 가장 왼쪽 위 칸인 [0][0] 위치에서 가장 오른쪽 아래 칸인 [N - 1][N - 1] 위치로 이동하는 최소 비용을 출력하는 프로그램을 작성하세요. 화성 탐사 기계는 특정한 위치에서 상하좌우 인접한 곳으로 1칸씩 이동할 수 있습니다. 입력 조건 첫째 줄에 테스트 케이스의 수(1

문제 선생님은 시험을 본 학생 N명의 성적을 분실하고, 성적을 비교한 결과의 일부만 가지고 있습니다. 학생 N명의 성적은 모두 다른데, 다음은 6명의 학생에 대하여 6번만 성적을 비교한 결과입니다. 1번 학생의 성적 < 5번 학생의 성적 3번 학생의 성적 < 4번 학생의 성적 4번 학생의 성적 < 2번 학생의 성적 4번 학생의 성적 < 6번 학생의 성적 5번 학생의 성적 < 2번 학생의 성적 5번 학생의 성적 < 4번 학생의 성적 A번 학생의 성적이 B번 학생보다 낮다면 화살표가 A에서 B를 가리키도록 할 때 위의 성적 결과를 다음 그림처럼 표현할 수 있습니다. 이 그림으로 유추해서 순위를 정확히 알 수 있는 학생도 있고, 알 수 없는 학생도 있습니다. 예를 들어 1번 학생은 5번 학생보다 성적이 낮고,..