본문 바로가기

알고리즘 (2020 : 08 : 10 ~ )

 (260)
[백준 / BOJ] 10875 뱀 문제 출처 : www.acmicpc.net/problem/10875 10875번: 뱀 가로 길이와 세로 길이가 모두 2L + 1인 2차원 격자판이 있다. 이 격자판의 각 칸을 그 좌표에 따라 (x, y)로 표현하기로 한다. 격자판의 가운데 칸의 좌표는 (0, 0)이고, 맨 왼쪽 맨 아래 칸의 좌표는 www.acmicpc.net 2차원 그리드에서 뱀이 움직인다. 뱀은 1초가 지날때마다, 바라보는 방향으로 한 칸씩 몸의 길이를 늘려가며 움직인다. 뱀은 자신의 몸과 닿거나 2차원 그리드 범위 밖으로 나가면 몸을 늘리며 숨을 거둔다. 뱀이 머리를 회전하는 시간과 방향이 주어질때, 뱀이 언제 숨을 거두는지 출력하는 문제다. 풀이 시뮬레이션 문제다. 문제의 조건을 읽어보면, 그리드의 길이가 가로 세로 각각 최대 4..
[백준 / BOJ] 2098 외판원 순회 문제 출처 : www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고한다. 이때, 이미 방문한 도시는 재방문할수없다. 도시를 이동할때 일정한 비용이 필요할때, 외판원이 모든 도시를 거쳐 출발도시로 돌아오는 최소 비용을 구하는 문제다. 풀이 완전탐색으로 풀려고할경우, N이 최대 16이므로, 16 * 15 * 14 ..
[백준 / BOJ] 1052 물병 문제 출처 : www.acmicpc.net/problem/1052 1052번: 물병 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번 www.acmicpc.net 지민이는 N개의 물병을 갖고있다. 각 물병에는 물을 무한대로 부을 수 있는데, 처음에 모든 물병에는 물이 1리터씩있다. 지민이는 N개의 물병을 적절히 합쳐 K개이하의 물병으로 만들려하는데, 물병을 합칠때 는 다음 규칙에 따라 합칠수있다. - 같은 물이 들어있는 물병만 합칠수있다. 이때, 물병을 더 이상 합칠수없다면, 1리터의 물이 들어있는 물병을 추가할수있다. K개 이하의 물병을 만들기위해 추가해야할 ..
[백준 / BOJ] 1029 그림 교환 문제 출처 : www.acmicpc.net/problem/1029 1029번: 그림 교환 첫째 줄에 예술가의 수 N이 주어진다. N은 2보다 크거나 같고, 15보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 N개의 수가 주어진다. i번째 줄의 j번째 수는 j번 예술가가 i번 예술가에 www.acmicpc.net 사람들이 그림을 사고팔려고한다. 모든 그림 거래는 다음 조건을 만족해야한다. 1. 그림을 팔때, 그림을 산 가격보다 크거나 같은 가격으로 팔아야한다. 2. 같은 그림을 두 번 이상 사는 것은 불가능하다. 항상, 1번 사람이 그림을 0원에 샀다고했을때, 그림을 소유했던 사람의 수의 최댓값을 출력하는 문제다. 풀이 완전탐색으로 풀면, 최악의경우 첫 선택 = 15명 두번째 선택 = 14명 세번..
[백준 / 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 * 확산된 방향의 개수) 미세먼지가 확산을 한 이후에는 공기청정기가 작동하여 미세..

티스토리툴바