백준

[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 ..