Total

[4948] 베르트랑 공준 (소수의 개수)

4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 분석 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다 자기자신 포함하지 않음 [1929] 소수 구하기 (에라토스테네스 방식, 2부터 배수 제거) 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 분석 1 ≤ M ≤ N ≤ 1,000,000 karla.tis..

[9613] GCD 합 (조합)

9613번: GCD 합 첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진 www.acmicpc.net 풀이 """ 양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오. 첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진다. 입력으로 주어지는 수는 1,000,000을 넘지 않는다. """ import sys input=sys.stdin...

[1011] Fly me to the Alpha Centauri

1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net 분석 이동해야 하는 거리 n의 제곱보다 작거나 같을 때 공간이동 작동 횟수 = n * 2 - 1 n의 제곱보다 클 때공간이동 작동 횟수 = n * 2 거리 경로 N N² 공간이동 작동횟수 반복횟수 1 1 1 1 1 1 2 11 1 1 2 1 3 111 2 4 3 2 4 121 2 4 3 5 1211 2 4 4 2 6 1221 2 4 4 7 12211 3 9 5 3 8 12221 3 9 5 9 12321 3 9 5 10..

[16930] 달리기 (BFS)

16930번: 달리기 진영이는 다이어트를 위해 N×M 크기의 체육관을 달리려고 한다. 체육관은 1×1 크기의 칸으로 나누어져 있고, 칸은 빈 칸 또는 벽이다. x행 y열에 있는 칸은 (x, y)로 나타낸다. 매 초마다 진영이는 www.acmicpc.net 분석 6087 레이저 통신 문제와 유사 시간 초과 시 조건 추가 새 경로의 값이 -1이 아닌 현재 경로보다 작은 경우 break 풀이 """" 매 초마다 진영이는 위, 아래, 오른쪽, 왼쪽 중에서 이동할 방향을 하나 고르고, 그 방향으로 최소 1개, 최대 K개의 빈 칸을 이동한다. 시작점 (x1, y1)과 도착점 (x2, y2)가 주어졌을 때, 시작점에서 도착점으로 이동하는 최소 시간 체육관의 크기 N과 M, 1초에 이동할 수 있는 칸의 최대 개수 K ..

[6087] 레이저 통신 (BFS)

6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 분석 어떤 칸에서 이동할 수 있는 정점은 인접한 네 칸이 아닌 같은 방향 일직선 한번에 이동할 수 있는 방향을 한번에 큐에 넣음 이동 경로가 바뀌면 거울이 필요 거울의 개수 = 직선의 개수 구한 뒤 -1 한 값 (sx,sy) 에서 (ex,ey)로 가는 최단거리를 구하는 문제 풀이 """ W×H 크기의 지도 레이저는 C에서만 발사할 수 있고, 빈 칸에 거울('/', '\')을 설치해서 방향을 90도 회전시킬 수 있다. 빈 칸은 '.', 벽은 '*'로 나타..

[1477] 휴게소 세우기 (이분 탐색)

1477번: 휴게소 세우기 첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. 둘째 줄에 현재 휴게소의 위치가 공백을 사이에 두고 주어진다. N = 0인 경우 둘째 줄은 빈 줄 www.acmicpc.net 분석 풀이 """ 현재 고속도로에 휴게소를 N개 가지고 있는데, 휴게소의 위치는 고속도로의 시작으로부터 얼만큼 떨어져 있는지로 주어진다. 다솜이는 지금 휴게소를 M개 더 세우려고 한다. 다솜이는 이 고속도로를 이용할 때, 모든 휴게소를 방문한다. 다솜이는 휴게소를 M개 더 지어서 휴게소가 없는 구간의 길이의 최댓값을 최소로 하려고 한다. (반드시 M개를 모두 지어야 한다.) 고속도로의 길이가 1000이고, 현재 휴게소가 {200, 701, 800}에..

최장 증가 수열(LIS) 정리

최장 증가 수열 (LIS) Longest Increasing Subsequence, 원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열이라고 합니다. {6, 2, 5, 1, 7, 4, 8, 3}이라는 배열이 있을 경우, LIS는 {2, 5, 7, 8}이 됩니다. {2, 5}, {2, 7} 등 증가하는 부분 수열은 많지만 그 중에서 가장 긴 것이 {2, 5, 7, 8} 입니다. 1. 가장 긴 증가하는 부분 수열 (1 ≤ N ≤ 1,000) 가장 긴 증가하는 부분수열 길이 구하기, 2중 for 문 DP [11053] 가장 긴 증가하는 부분수열 (LIS) 11053번: 가장 긴 증가하는 부분 수열..

[7570] 줄세우기 (연속 최장 증가 수열, LIS)

7570번: 줄 세우기 입력은 2 개의 줄로 이루어져 있다. 첫 줄에는 어린이 수를 나타내는 정수가 주어진다. 둘째 줄에는 처음에 줄서있는 어린이들의 번호가 차례대로 주어진다. 주어진 번호들 사이에는 공백이 하 www.acmicpc.net 분석 유사문제 : 2631 [2631] 줄 세우기 (2중 for문) 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과 karla.tistory.com 추가 조건 : 이동하는 어린이를 제일 앞이나 제일 뒤로만 보낼 수 있음 ➔ 바로 옆에 있는 최장 증가 수열을 구해야함 4 2 3 1 5 1. 한 명의 어린이를 뽑아서 원하는 곳..

[2631] 줄 세우기 (최장증가수열, LIS, 이분 탐색)

2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 분석 정렬되어 있는 어린이 빼고 나머지를 이동하므로 LIS의 길이를 구한 뒤 N에서 뺌 풀이 import sys from bisect import bisect_left input=sys.stdin.readline n = int(input()) arr=[] for _ in range(n): arr.append(int(input())) d=[] for i in arr: k = bisect_left(d, i) if len(d) == k: d+=[i] else: d[k]=i ..

[2631] 줄 세우기 (최장증가수열, LIS, 2중 for문)

2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 분석 정렬되어 있는 어린이 빼고 나머지를 이동하므로 LIS의 길이를 구한 뒤 N에서 뺌 풀이 import sys input=sys.stdin.readline n = int(input()) arr=[] for _ in range(n): arr.append(int(input())) dp = [0 for _ in range(n)] for i in range(n): dp[i] = 1 for j in range(i): if arr[j] < arr[i]: dp[i] = max(d..