본문 바로가기

분류 전체보기

 (341)
[백준 / 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동영상을 시청하..
[디자인 패턴] 옵저버 패턴 문제 - 건물 (옵저버, 스트래티지) 책을 공부하며 새로운 문제를 만들고 구현한것을 기록한 게시글입니다. (이해한 내용을 바탕으로 작성했기 때문에, 내용이 정확하지않고 틀린부분이 있을수있으며, 예시가 패턴을 사용하기에 알맞지 않을수도있습니다) 옵저버 패턴 - 하나의 주제가 여러개의 옵저버에 바뀌는 내용을 전달함. (한 객체가 바뀌면 객체에 의존하는 다른객체들의 내용이 갱신되는 1대다 패턴) - 주제와 옵저버는 느슨한 결합으로 연결되어있어야함. (옵저버가 추가되거나 옵저버의 내용이 바뀌어도 주제의 내용은 바뀌면 안됨) - 옵저버들에게 연락을 돌리는 순서에 의존하면안됨. (순서가바뀌면 옵저버가 잘못된 데이터를 받을수있음 이는 느슨한 결합이 아님) 문제 재석이의 건물 건물주가 된 재석이는 자신의 건물을 효과적으로 관리하고싶어한다. 지금까지 재석이..
[백준 / 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을 구하는 프로그램을 만드는 문제..
[디자인 패턴] 스트래티지 패턴 문제 - 커피 책을 공부하며 새로운 문제를 만들고 구현한것을 기록한 게시글입니다. (이해한 내용을 바탕으로 작성했기 때문에, 내용이 정확하지않고 틀린부분이 있을수있으며, 예시가 패턴을 사용하기에 알맞지 않을수도있습니다) 스트래티지 패턴 - 실행중 알고리즘을 변경할수있도록 하는 디자인 패턴. - 알고리즘군 각각을 캡슐화하고 상호교환가능하게만듬 문제 카페24에는 자동 커피 제조기가 있다. 커피 제조기는 설정된 커피를 무한대로 만드는데, 만들수있는 커피목록은 다음과 같다. americano cafe latte coldbrew 손님의 요구에 따라 만들고있는 커피종류를 바꿔야하며, 카페24의 알바생은 현재 만들고있는 커피의 종류를 알고싶다. 알바생은 만들고있는 커피를 바꿀때마다 프로그램에 다음과 같이 기록을한다. America..
[백준 / BOJ] 1135 뉴스 전하기 문제 출처 : https://www.acmicpc.net/problem/1135 1135번: 뉴스 전하기 민식이는 회사의 매니저이다. 그리고, 민식이는 회사의 중요한 뉴스를 모든 직원에게 빠르게 전달하려고 한다. 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다 www.acmicpc.net 민식이는 회사의 매니저이다. 민식이는 회사의 뉴스를 모든 직원들에게 전하려고한다. 회사의 모든 직원들은 정확히 한명의 선임이 있으며, 자신은 자신의 선임이 아니다. 모든 직원들은 모두 민식이의 간접,직접적인 부하이다. 모든 사람은 자신의 직속부하에게만 뉴스를 전달할수있고, 이때, 1분의 시간이 걸린다. 모든 직원이 뉴스를 전달받는 최소시간을 구하는 문제다. 풀이 그리디로 풀은 문제다. 직..

티스토리툴바