되면한다

https://www.acmicpc.net/problem/1106 1106번: 호텔 첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 www.acmicpc.net 전형적인 dp 문제이다. 1. 특징 이 문제의 점화식이 백준 14501.퇴사 문제와 비슷하다. https://todaywithhaeul.tistory.com/159 나는 우선 dp 테이블을 정의했다. 1) d[i]: i원을 쓸 때 늘릴 수 있는 인원의 최댓값 or 2) d[i]: 고객수를 i명으로 늘릴때 비용의 최솟값. 나는 2번으로 정의했다. (1번 풀이로 하고 싶다면, https://ong..

https://www.acmicpc.net/problem/2240 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 2시간동안 풀었는데, 못풀었다ㅎ 아래 코드를 참고했다. https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x10/solutions/2240.cpp 1. 특징 1) dp 2. 삽질 포인트 1) 나는 dp 테이블을 i번 이동해서 얻을 수 있는 최대 자두수라고 설정했다. 그래서 점화식을 세우기 쉽지 않았다. 3. 구현 포인트 dp 테이블을 d[..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 이문제 못풀어서 다음 블로그에서 풀이법을 가져왔다. https://velog.io/@sj-lee33/%EB%B0%B1%EC%A4%80-14501%EB%B2%88-%ED%87%B4%EC%82%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-c-%ED%92%80%EC%9D%B4 백준 14501번 : 퇴사 (알고리즘 c++ 풀이) 백준 14501 velog.io 동적 프로그래밍을 이용하는 문제이다. 문제를 역순으로 생각하면 쉽게 풀 수 있다. 7일: 2일 걸림, 0일 남음, 진행 x 6일: 4일 걸림, 1일 남음, ..

https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가하는 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 www.acmicpc.net n> n; for(int i = 0; i > arr[i]; d[i] = arr[i]; } for(int i = 0; i arr[j]) d[i] = max(d[j]+arr[i], d[i]); } } cout

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net n이 1 n; for(int i = 1; i > arr[i]; } d[1] = arr[1]; for(int i = 2; i

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 풀이는 바킹독의 실전 알고리즘 0x10강 - 다이나믹 프로그래밍을 참고했다. 1. 특징 1) DP 2. 구현 포인트(DP문제) 1) 테이블 정의하기 D[i][j] = 현재까지 j개의 계단을 연속해서 밟고 i번째 계단까지 올라섰을 때 점수 합의 최댓값, 단 i번째 계단은 반드시 밟아야 함 2) 점화식 찾기 D[k][1] = max(D[k-2][1] + D[k-2][2]) + S[k] D[k][2] = ..

https://school.programmers.co.kr/learn/courses/30/lessons/12904 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 인덱스를 이용한 구현 문제이다. 나는 문제를 못풀어서 아래 링크를 참고했다. 처음 풀 때도 정답과 비슷한 알고리즘으로 풀었던 거 같은데, 꼬인 것같다. 이전 코드를 저장을 안해둬서 어디서 실수했는지 모르겠다. 이 문제 풀때 시간 복잡도와 관련해서도 고민을 했었어서, 정답 코드로 시간 복잡도도 계산해봤다. 1. 특징 1) 인덱스 관련 구현 2. 삽질 포인트 1) 회전 과정에서 이미 값을 덮어버린 ..

https://www.acmicpc.net/problem/16987 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 계란을 들고 깨지지 않은 계란을 깬다. 이때 계란을 깨는 순서에 대한 모든 경우를 확인해봐야 하기 때문에 백트래킹으로 문제를 푼다. 1. 특징 1) 백트래킹을 잘 구현 2. 삽질 포인트 1) 조건 구현- "들고 있는 계란이 깨졌으면, 다음 계란을 든다." if(_vec[cur].first