[백준 / BOJ] 14003 가장 긴 증가하는 부분 수열 5
문제 출처 : www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 수열 A가 주어졌을때, 가장 긴 증가하는 부분 수열의 길이와 해당 수열을 구하는 문제다. 풀이 dp를 이용해 풀어야하는문제다. 수열의 크기가 1,000,000까지 가서, 이전 idx에서 가장큰 수를 N^2으로 뽑는 풀이로는 풀수없다. (매 탐색마다 자신의 뒤에서 가장 큰수를 가져오는 풀이로는 풀수없음) 이분탐색(혹은 세그)을 활용한 NlogN LIS알고리즘을 쓰면 풀..
[백준 / BOJ] 17070 파이프 옮기기 1
문제 출처 : www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 새 집으로 이사한 유현이는, 파이프를 옮길려한다. 파이프는 대각선, 왼쪽, 아래로 움직일수있다. 이때, 새 집에 새로운 벽지를 발랐기 때문에, 파이프가 벽을 긁으면 안 된다. 파이프를 N,N 위치로 옮기는 모든 경우의수를 구하는 문제다. 풀이 다이나믹 프로그래밍으로 푼 문제다. 문제에서 이동하는 모양을 보면, 항상 최소경로로 이동하기때문에, 최소경로로 이동했는지 고려해주지..
[백준 / BOJ] 2096 내려가기
문제 출처 : www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 내려가기 게임을 하고있다. 이 게임은 첫번째 줄에서 마지막 줄까지 내려가는 게임인데, 내려갈때 일정한 규칙에 따라 내려가야한다. 바로 아래 칸으로 내려가거나 바로 아래칸에 연결된 칸으로만 내려갈수있다. 예를들어, 왼쪽에서 내려갈수있는경우는, 왼쪽아래와 가운데 아래이다. 마지막 줄까지 내려갔을때, 최댓값과 최솟값을 구하는 문제다. 풀이 N이 100000이라서 완전탐색으로 풀경우 시간초과가 난다. 그리디로 풀려고해..
[백준 / BOJ] 11053 가장 긴 증가하는 부분 수열
문제 출처 : www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 수열 A가 주어진다. 이때, 수열A에서 가장 긴 증가하는 부분 수열의 길이를 구하는 문제다. 예를들어, 수열 : {1 2 1 4 5} 가 주어지면, 1 -> 2 -> 4 -> 5 가 가장 긴 증가하는 부분수열이되어서 답은 4이다. 풀이 수열의 길이가 최대 1000이므로 모든경우를 보면 시간초과가 난다. 하나의 수를 지정..