본문 바로가기

알고리즘

 (151)
[백준 / 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] 1035 조각 움직이기 문제 출처 : www.acmicpc.net/problem/1035 1035번: 조각 움직이기 최대 5개의 조각이 있는 5*5 크기의 보드가 있다. 김지민은 조각을 적절히 움직여서 모든 조각이 연결 요소를 이루게 하려고 한다. 즉 상하좌우로 인접한 조각을 모두 연결했을 때, 모든 쌍의 조 www.acmicpc.net 5*5크기의 보드에 최대 5개의 조각이있다. 이 조각을 적절히 움직여서 모든 조각이 연결되도록 할려고한다. 조각은 상하좌우 한칸으로 이동시킬수 있다고할때, 모든 조각을 연결하는 최소한의 이동 횟수를 구하는 문제다. 풀이 처음에는(1년전??) BFS로 풀려했는데, BFS는 항상 최단경로를 보장하므로 하나의 조각을 기준으로 잡고 나머지 조각을 해당 조각으로 이동하는 횟수를 BFS로 구해주는로직을짰..
[백준 / BOJ] 10830 행렬 제곱 문제 출처 : www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 크기가 N*N인 행렬A가 주어졌을때, 해당 행렬을 B제곱한 결과를 구하는 문제다. 수가 매우 커질수있으니 A^B의 각 원소를 1000으로 나눈 나머지를 출력한다. 풀이 B가 최대 100,000,000,000까지 가서 일반적인 곱셈(A*A*A*A*A)으로는 시간초과가 난다. 분할정복을 이용해 풀어야하는데, A*A = A^2 A*A*A*A = A^2*A^2 = A^4 A*A*A*A*A*A*A*A = A^2*A^2..
[백준 / BOJ] 17144 미세먼지 안녕! 문제 출처 : www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 구사과는 미세먼지를 제거하기위해 공기청정기를 설치하려고한다. 공기 청정기는 항상 1번 열에 설치되어있고, 크기는 두행을 차지한다. 공기청정기가 없는 칸에는 미세먼지가 있다. 미세먼지는 매초 마다 확산을 하는데, 확산되는 양은 다음과같다. 확산되는 양 : Ay,x / 5 y,x에 남는양 : Ay,x - (Ay,x/5 * 확산된 방향의 개수) 미세먼지가 확산을 한 이후에는 공기청정기가 작동하여 미세..
[백준 / BOJ] 17070 파이프 옮기기 1 문제 출처 : www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 새 집으로 이사한 유현이는, 파이프를 옮길려한다. 파이프는 대각선, 왼쪽, 아래로 움직일수있다. 이때, 새 집에 새로운 벽지를 발랐기 때문에, 파이프가 벽을 긁으면 안 된다. 파이프를 N,N 위치로 옮기는 모든 경우의수를 구하는 문제다. 풀이 다이나믹 프로그래밍으로 푼 문제다. 문제에서 이동하는 모양을 보면, 항상 최소경로로 이동하기때문에, 최소경로로 이동했는지 고려해주지..
[백준 / BOJ] 11054 가장 긴 바이토닉 부분 수열 문제 출처 : www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 수열S가 주어진다. 이때, 수열S의 어떤 수 A를 기준으로 A이전의 수가 증가하는 부분 수열 일때, A 이후가 감소하는 부분 수열 이라면, 그 수열을 바이토닉 수열 이라고 한다. 이때, 수열 S에서 가능한 모든 바이토닉 수열중 가장 긴 수열의 길이를 구하는 문제다. 풀이 N이 1000이므로 완전탐색으로 풀경우 시간초과가 난다. 다이나믹 프로그래밍으로 풀어야 하는 문제였다. 문제 이해가 좀 어려운 문제였다, 문제에서 ..
[백준 / BOJ] 2638 치즈 문제 출처 : www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net N*M크기의 모눈종이에 치즈가 있다. 모눈종이의 가장자리부터 공기가 들어오는데, 공기에 2면 접촉해있는 치즈는 1초후 녹기시작한다. 가장자리에는 치즈가없을때, 모든 치즈가 녹아 없어지는데 걸리는 정확한 시간을 구하는 문제다. 풀이 BFS,DFS를 이용한 시뮬레이션 문제다. N,M이 최대 100,100이라서 총 칸수가 10000칸 까지 갈수있다. 한번 치즈를 녹일때마다 모든 칸을 다 봐준다..
[백준 / 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이라서 완전탐색으로 풀경우 시간초과가 난다. 그리디로 풀려고해..

티스토리툴바