목록전체 글 (222)
꺼내먹는지식 준
공유기 설치 문제 도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다. 도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다. C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오. 입력 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌..
Python Collections Libaray from collections import Counter Counter 는 원소의 개수를 세서 dictionary 로 return 해준다. 아주 유용한 기능은 str 의 경우에도 처리가 가능하다는것. if key in dict: 를 안해도 한줄로 str 의 모든 단어도 count 할 수 있다. from collections import defaultdict dictionary 에서 만약 접근한 key 값이 존재하지 않을 때 key error 를 내는 것이 아니라 사전 설정해놓은 값으로 설정 defaultdict(lambda: 0) 이런식으로 설정 가능 from collections import deque queue 를 호출 원소의 개수가 많아질 수록 lis..
연산자 끼워넣기 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 512 MB 68464 35831 22847 49.465% 문제 N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다. 예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식..
필자에게 자신을 돌아볼 충격적인 일이 있었다. ln(x - 1)을 미분하는데, 두가지 방법에 따라 결과값이 다르게 나온 것이다. 1) 합성 함수의 미분 $$\ln(x-1)' = g'(f(x))f'(x) $$ $$\ln(x-1)' = \ln'(x-1)(x-1)' $$ $$\ln(x-1)' = \frac{1}{x-1} (-1)$$ $$-\frac{1}{x-1}$$ 2) 미분 계수 정의 이용 $$\lim_{h \to 0} \frac{\ln(x-1+h) - \ln(x-1)}{h}$$ $$\lim_{h \to 0} \frac{1}{h} \ln{(\frac{(1-x)+h}{1-x})}$$ $$\lim_{h \to 0} \frac{1}{h} \ln{(1 + \frac{h}{1-x})}$$ $$\lim_{h \to 0..
특정 거리의 도시 찾기 어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다. 이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다. 예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자. 이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다. 2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다. 입력 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 ..
문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다. 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다. 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는..
문제 요약 자물쇠와 열쇠 특이한 형태의 자물쇠와 열쇠가 있다. 잠겨있는 자물쇠는 격자 한 칸의 크기가 1 x 1 인 N x N 크기의 정사각 격자 형태이고 특이한 모양의 열쇠는 M x M 크기인 정사각 격자 형태로 되어 있다. 자물쇠에는 홈이 파져있고 열쇠 또한 홈과 돌기 부분이 있다. 열쇠는 회전과 이동이 가능하며, 열쇠 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열린다. 자물쇠 영역을 벗어난 부분에 있는 열쇠와 홈의 돌기는 자물쇠를 여는데 영향을 주지 않지만, 자물쇠 영역 내에서는 열쇠의 돌기부분과 자물쇠의 홈 부분이 정확히 일치해야하며 열쇠의 돌기와 자물쇠의 돌기가 만나서는 안 된다. 자물쇠 모든 홈을 채워 비워있는 곳이 없어야 한다. 아이디어 회전 행렬 에대한 개념이 필요하다. 2D..
문자열 압축 한번 풀었던 문제라 간단하게 해결하고 싶었으나 엄청나게 해맸다. ababcdcdababcdcd 2ab2cd2ab2cd : 2개 단위 2ababcdcd : 8개 단위 문자열을 1개 이상 단위로 압축 할 때 가장 짧은 것의 길이를 return 문자열은 제일 앞부터 정해진 길이만큼 잘라야 한다. 따라서 주어진 문자열을 x/ ababcdcd / ababcdcd 로 자르는 것은 불가능 한번만 나타난 경우 1 은 생략 해당 문제의 해결 골자는 다음과 같다. 반복이 될 수 있는 경우는 글자 1개 ~ 총 글자 // 2 이다. 총 글자 // 2 를 넘어선 순간 반복하면 총 글자 수를 넘어가서 반복이 불가능하다. 문제에서 구하고자 하는 답은 "반복 하는 경우 중 가장 글자 수가 적은 경우" 이다. 즉 반복이 ..
회전판 위 N 개의 음식 각 음식은 1 ~ N 까지의 번호 각 음식 섭취에는 일정 시간 소요 다음의 방법으로 음식 섭취 1. 무지는 1번 음식부터 먹는다. 회전판 번호가 증가하는 순서대로 음식을 무지 앞으로 가져다 놓는다. 2. 마지막 번호의 음식 섭취 후 회전판에 의해 다시 1번 음식이 무지 앞으로 온다. 3. 무지는 음식 하나를 1초 동안 섭취한 후 남은 음식은 그대로 두고, 다음 음식을 섭취 (다음 음식이란 아직 남은 음식 중 가장 가까운 번호의 음식) 4. 회전판이 다음 음식을 무지 앞으로 가져오는데 걸리는 시간은 없다. import sys input = sys.stdin.readline food_times = list(map(int,input().split())) k = int(input()) ..
문제 A,B 두 사람이 볼링을 치고 있습니다. 두 사람은 서로 무게가 다른 볼링공을 고르려고 합니다. 볼링공은 총 N개가 있으며 각 볼링공마다 무게가 적혀 있고, 공의 번호는 1번부터 순서대로 부여됩니다. 또한 같은 무게의 공이 여러 개 있을 수 있지만, 서로 다른 공으로 간주합니다. 볼링공의 무게는 1부터 M까지의 자연수 형태로 존재합니다. 예를 들어 N이 5이고, M이 3이며 각각의 무게가 차례대로 1,3,2,3,2일 때 각 공의 번호가 차례대로 1번부터 5번까지 부여됩니다. 이때 두 사람이 고를 수 있는 볼링공 번호의 조합을 구하면 다음과 같습니다. (1번, 2번), (1번, 3번), (1번, 4번), (1번, 5번), (2번, 3번), (2번, 5번), (3번, 4번), (4번, 5번) 결과적으로..