허비의 기술블로그

1 ~ N 번의 번호가 붙은 학생이 있다. 두 학생끼리 키를 비교한 결과가 주어지는데, 이 결과를 통해서 본인의 키 순서를 알 수 있는 학생이 몇 명인지 구하는 문제이다. (단, 모든 학생의 키는 다르다.) 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 풀이 과정 학생의 키가 몇 번째인 지 알려면 그 학생은 대소 관계에 있어서 모든 학생과 연결돼 있어야 한다. 즉 모든 학생을 노드로 하고, (키가 작은 학생 -> 키가 큰 학생)으로 노드를 연결한다고 했을 때, 모든 학생과 연결돼 있다면, 그 학생의 키 순서를..

R X C의 2차원 보드의 각 위치에 영문 대문자가 들어있다. (0, 0)의 좌표에서 상하좌우 중 한 방향으로 이동하려고 하는데, 가려고 하는 좌표의 값이 이미 지나온 경로에 있는 값이라면 갈 수 없다. 이때 이동할 수 있는 최대 거리를 구하는 문제이다. 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 풀이 과정 (0, 0)의 좌표에서 이동하면서 현재까지 지나온 값을 저장해야 한다. 보드의 값이 대문자 알파벳(A ~ Z) 26개로 한정돼 있으므로 26개 길이의 배열을 선언해 각 알파벳의 사용 여부 (T..

숫자의 길이 N이 주어질 때 N의 길이로 만들 수 있는 오르막 수의 개수를 구하는 문제다. 오르막 수란 수에서 모든 인접한 숫자가 오름차순으로 연결되는 수를 말한다. 인접한 숫자는 같아도 된다. N은 최대 1000이다. ex) 1, 2, 11, 12, 123, 112는 오르막 수다. 21, 12343, 154는 오르막 수가 아니다. 시간 복잡도: O(N * 10) 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 풀이 과정 모든 경우를 탐색하는 완전 탐색으로 문제를 해결하려면 ..

치킨집과 집의 정보가 담긴 N * N 크기의 2차원 배열이 주어질 때, M개의 치킨집만 남겼을 때 치킨집 집 거리 합의 최솟값을 구하는 문제다. N은 최대 50, M은 최대 13이다. 치킨 집의 개수도 13 이하이다. 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 풀이과정 우선 치킨 집 중에서 M개의 치킨집을 골라야 한다. 치킨집과 M의 크기가 최대 13이므로 치킨집을 고르는 경우의 수는 최대 13C6 = 1716가지다. 이렇게 M개의 치킨집을 고른 뒤 각 집의 좌표에서 가장 가까운 치킨..

수열의 길이 N, 정수 S와 길이와 수열이 입력으로 들어올 때 부분 수열의 합이 S가 나오는 경우의 수를 구하는 문제다. (단, 1

1 e: return s mid = (s + e) // 2 if arr[ mid]

카드를 총 N장 구매하려고 한다. 이때 카드의 수가 각각 1장부터 N장까지 있는 묶음의 가격이 차례대로 주어질 때, 딱 N장을 구매하기 위해 드는 비용을 최대로 하는 정답을 찾는 문제다. ex) N = 4, 카드 묶음 = [1, 5, 6, 7] 일 때 이는 1장 묶음을 사는데 드는 비용이 1, 2장 묶음을 사는데 드는 비용이 5, 3장 묶음을 사는데 드는 비용이 6, 4장 묶음을 사는데 드는 비용이 7 이 든다는 것을 의미한다. 4장을 사는데 드는 최대 비용은 2장 묶음을 2번 사서 드는 10이다. 시간 복잡도: O(N^2) 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1..

1~100,000 사이의 자연수 N을 제곱수들의 합으로 나타낼 때, 가능한 경우의 수에서 항의 최소 개수를 구하는 문제다. 시간 복잡도: O(N) 풀이 과정 어떤 규칙으로 나타낼 수 있을지 생각이 안 나서 1부터 숫자들을 제곱수로 나타내 봤다. 제곱수 하나로 만들어질 수 있는 1, 4, 9에서 수가 커질수록 1의 제곱이 1씩 붙는 경우가 많다. 하지만 8, 12처럼 뒤에 1의 제곱이 아니라 다른 수가 붙는 경우도 있어 규칙이 존재하지는 않는다. 그런데 여기서 N에 대해 제곱수의 합으로 나타내려고 할 때, 그 항의 개수는 N에서 어떤 제곱수를 뺀 값에서의 항 개수 + 1과 같다. 12의 경우를 다시 살펴보자. N = 12일 때 정답 값은 N = 8일 때 정답 값 + 1이다. 하지만 나올 수 있는 경우는 N..

암호의 길이 L과 암호에 들어갈 후보 C개의 문자가 입력이 들어오면, 암호가 될 수 있는 모든 문자열들을 출력하는 문제다. 단 암호는 문자가 중복되지 않으며, 모음이 1개 이상이고 자음이 2개 이상이다. 또한 암호는 오름차순으로 정렬돼있다. 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 풀이 과정 후보 문자열에서, 암호로 뽑을 L개의 문자를 선별한다. 이때 파이썬에선 Collections 모듈의 Combinations 함수를 사용하면 조합을 쉽게 구할 수 있다. 또 암호는 정렬돼있으므로 후보 문자열을 입력받은 다..

가로, 세로의 크기가 각각 N, M인 직사각형에서 (3