Algorithms/백준(BOJ)

퇴사링크: https://www.acmicpc.net/problem/15486문제상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.N = 7인 경우에 다음과 같은 상담 일정표를 보자. 1일2일3일 4일5일6일7일T[i]3511242P[i]1020102015402001일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이..

가장 긴 증가하는 부분 수열링크: https://www.acmicpc.net/problem/11053문제수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.문제 접근처음에는 문제 자체를 이해하지 못했다. 이유는 부분수열의 정의를 모르고 있었기 때문이다.부분 수열의 정의: 주어진 항을 원래 순서대로 나열하여 얻을 수 있는 수열DP로 풀 수 있는 알고리즘 중 LIS(Longgist Increasing Subsequence)을 사용하는 문제이다.자, LIS를 먼저 간단히 알아보도록 하자.LIS(..

이친수링크: https://www.acmicpc.net/problem/2193문제 접근DP 문제집을 통해 접근한 것이 아니었다면 백트래킹인가? 했을 것이다.적절한 알고리즘을 선택할 수 있는 안목을 길러야겠다.1로 시작해야 한다는 조건과 연속된 1이 나올 수 없다는 조건을 만족하는 방법의 개수를 세는 문제이다.풀이 힌트table 정의와 점화식, 초기값을 발견하기 위해 값을 직접 대입해보았다.첫째 자리가 1로 시작하면 앞에 두 자리는 1과 0으로 고정이 된다는 사실을 발견했다.아래 그림을 보자.규칙성을 발견했는가?피보나치 수열이었다.앞의 2자리 수는 1 0 으로 고정되어있기 때문에 앞의 2자리를 제외한 자리의 경우의 수가 중요하다.7개까지 끄적이며 찾아보다가 피보나치 수열이 확실하다고 생각하여 바로 제출하고..

오아시스 재결합링크: http://www.acmicpc.net/problem/3015 문제오아시스의 재결합 공연에 N명이 한 줄로 서서 기다리고 있다.이 역사적인 순간을 맞이하기 위해 줄에서 기다리고 있던 백준이는 갑자기 자기가 볼 수 있는 사람의 수가 궁금해졌다.두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다.줄에 서 있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램을 작성하시오.문제 접근A와 B 사이에는 같거나 작은 값들만 존재해야 한다.2 4 1 2 2 5 1의 경우 총 10개의 쌍이 존재한다.(2,4), (4,1), (4,2), (4,2), (4,5), (1,2), (2,2), (2,5), (2,5), (5,1)풀이..

옥상 정원 꾸미기https://www.acmicpc.net/problem/6198 문제도시에는 N개의 빌딩이 있다.빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다.i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으로만 볼 수 있다.i번째 빌딩 관리인이 볼 수 있는 다른 빌딩의 옥상 정원은 i+1, i+2, .... , N이다.그런데 자신이 위치한 빌딩보다 높거나 같은 빌딩이 있으면 그 다음에 있는 모든 빌딩의 옥상은 보지 못한다.예) N=6, H = {10, 3, 7, 4, 12, 2}인 경우 = = = = - = = = = -> 관리인이 보는 방향 = - =..