본문 바로가기

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

 (260)
[백준 / BOJ] 15732 도토리 숨기기 문제 출처 : https://www.acmicpc.net/problem/15732 15732번: 도토리 숨기기 첫째 줄에 상자의 개수 N(1 ≤ N ≤ 1,000,000)과 규칙의 개수 K(1 ≤ K ≤ 10,000), 도토리의 개수 D(1 ≤ D ≤ 1,000,000,000)가 주어진다. 그 후 K개 줄에는 A, B, C(1 ≤ C ≤ A ≤ B ≤ N)가 주어지며 A번 상자부터 www.acmicpc.net 수형이는 N개의 상자에 도토리를 숨기려한다. 이때, 도토리를 숨긴위치를 기억하기 쉽게하기위해 규칙있게 숨긴다. 예를들어, A상자부터 B상자까지 C간격으로 도토리를 숨긴다면, A 상자에 하나를 숨기고, A+C상자에 하나를 숨기고, A+2C상자에 하나를 숨기고..B상자에 마지막하나를 숨긴다. 상자의 수..
[백준 / BOJ] 1305 광고 문제 출처 : https://www.acmicpc.net/problem/1305 1305번: 광고 세준이는 길 한가운데에서 전광판을 쳐다보고 있었다. 전광판에는 광고가 흘러나오고 있었다. 한참을 전광판을 쳐다본 세준이는 이 광고가 의미하는 것이 무엇인지 궁금해지기 시작했다. 전광 www.acmicpc.net 세준이는 길 한가운데에서 전광판을 보고있다. 전광판에는 광고가 나오고있다. 전광판의 크기는 전광판에서 한번에 보이는 문자열의 최대 길이를 나타낸다. 전광판의 크기 L과 세준이가 본 전광판의 글자가 주어졌을때, 가능한 광고길이중 최솟값을 출력하는 문제다. 풀이 모든경우를 보면, L^2이 되서 시간안에 통과하지못한다. KMP알고리즘을 이용해 푼문제다. 광고판에서 광고가 나올수있는 경우는 광고 A뒤에 똑같..
[백준 / BOJ] 17135 캐슬 디펜스 문제 출처 : https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net N*M배열에 적이있고 N-1번째 줄에 궁수가있다. 매 턴마다 궁수는 자기의 사정거리안에서 가장 가까운적(가까운적이 여러명이라면, 가장 왼쪽적)을 찾아 공격하고 궁수의 공격이 끝난후 적은 한칸 아래로 내려온다. 궁수는 일제히사격하므로, 한 적에게 여러궁수가 공격할수있다. 이때, 가장많은 적을 없애는 경우의 수를 구하는 문제다. 풀이 시뮬레이션 문제였다. 최악의경우 (N=15, M=15)일때 반복..
[백준 / BOJ] 14500 테트로미노 문제 출처 : https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net N*M크기의 종이에 숫자들이 쓰여있다. 이 종이에 테트로미노하나를 놓았을때, 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 찾는 문제다. 소스코드 완전탐색으로 푼 문제다. 종이의 세로,가로가 각각 최대 500이며, 한번 탐색마다 (모든 폴리오미노를 본다했을때,) 40번이라고 하면, 총 탐색횟수는 250000*40 = 10000000가 되어서 시간초과를 피할수있..
[백준 / BOJ] 14501 퇴사 문제 출처 : https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 백준이는 오늘부터 N+1일째 되는 날 퇴사를 하기위해 남은 N일동안 최대한 많은 상담을 하려고 한다. 상담은 상담을 완료하는데걸리는시간 Ti와 이때 얻을수있는 금액 Pi로 이루어져있다. 하나의 상담을 하는중 다른상담은 할수없다. 이때, 백준이가 N일동안 상담을했을때 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오. 소스코드 다이나믹 프로그래밍으로 풀은문제다. 일반적인 완전탐색으로 풀경우, 15!번 반복해서 시간초과가 난다. 현재 일을 Ni, dp[Ni] = Ni일 까지의 최댓값 이라고하자. 현재 날(N(i))부터..
[백준 / BOJ] 15591 MooTube (Silver) 문제 출처 : https://www.acmicpc.net/problem/15591 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 농부 존은 MooTube라는 동영상 공유 서비스를 만들었다. MooTube의 동영상들은 트리구조로 연결되어있고, 동영상 Vi를 볼때, Vi와 연결된 모든 동영상들중에 유사도가 Ki이상인 동영상들을 추천해준다. 이때, 동영상 Vi와 다른 동영상 Vj의 유사도는 Vi와 Vj 를 연결하는 경로의 최소 유사도이다. 소가 Vi동영상을 시청하..
[백준 / BOJ] 1039 교환 문제 출처 : https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 0으로 시작하지않는 정수 N이 주어진다. 정수 N의 자릿수 M에 대해 다음과 같은 연산을 K번 수행했을때, 나올수있는 최댓값을 계산하는 프로그램이다. 1 13 -> 31 과 같은 루트로 이동해 최댓값을 찾을수도 있기때문이다. 따라서, 체크배열을 map check; 와 같이 선언한다. (cnt번 이동해서 vector 형태가 되었을때, 이동횟수) 위 정보들을 갖고 구현하면된다. -1 출력은 1. N이 한자릿수 인경우 2. N이 두자릿수면서 일의자리가 0인경..
[백준 / BOJ] 1087 쥐 잡기 문제 출처 : https://www.acmicpc.net/problem/1087 1087번: 쥐 잡기 첫째 줄에 쥐의 수 N이 주어진다. N은 2보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 각 쥐의 시작 위치와 속도가 주어진다. 이 값은 모두 절댓값이 1,000보다 작거나 같은 정수이 www.acmicpc.net 김지민은 쥐를 잡는 게임을 만들었다. 쥐는 각자의 시작위치(x,y)부터 1초마다 (dy,dx)방향으로 움직이며, 이때 속력은 항상같다. 쥐는 한변의 길이가 L인 x축에 평행인 정사각형 모양의 울타리로 쥐를 가둔다음, 판 밖으로 밀어내면 잡힌다. (쥐가 울타리의 경계에 있다면 잡힌쥐가 아니다) 한번에 모든 쥐를 절대로 잡을 수 없는 가장 큰 L을 구하는 프로그램을 만드는 문제..

티스토리툴바