일지 & 개발

문제 요약알고리즘 분류: dp, LIS난이도:  Silver2문제내용:수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.사이트: https://www.acmicpc.net/problem/11055문제풀이 이번 문제에는 모든 경우의 수를 구해서 풀기가 힘들다. 모든 경우의 수를 구하 O(N^N)개 이상으로 나올수 있다. 그래서 이번 문제는 LIS 개념을 적용해서 풀어야 한다. LIS에 대한 개념은 아래 글에서 확인 해보면된..

문제 요약알고리즘 분류:동적계획법(DP)난이도: Medium문제내용:나이트는 체스의 이동처럼 같다나이트는 체스판이 아닌 계산기에서 이동한다.(단 *, # 이동 불가능이다.)0~9에서 아무대나 시작한다고 했을때 이동횟수가 n을 주어 졌을때 나올수 있는 경우의 수를 반환 하여라.사이트 주소: https://leetcode.com/problems/knight-dialer/description/문제풀이 이번 문제는 나이트 이동때문에 백트레킹이라고 볼수 있지만 n이 5000인점을 보면 백트레킹으로 풀면 시간 초과로인하여 완전 탐색같은 알고리즘으로는 하기는 그렇다. 그래서 최적화 할 수  있는 동적 계획법을 해야 한다. 동적계획법에 대한 설명은 아래글에서 확인해보면 된다.https://jih3508.tistory...

문제 요약 알고리즘 분류: dp 난이도: Gold5 문제내용: 두 문자열에서 가장 긴 수열 길이를 구하여라 사이트: https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제풀이 이번 문제에는 동적계획법 알고리즘 대표적인 문제인 LCS이다. LCS에 대한 개념은 아래 사이트에서 확인해보면 된다. https://jih3508.tistory.com/191 [알고리즘 이론] LCS(Longest Increasi..

이론 1. LCS이란? LCS 개념을 이해하기 전에 기본적으로 DP(동적 계획법)또는 이분탐색을 알아야 된다. DP 에 관련 내용은 아래 사이트에 참조하면된다. https://jih3508.tistory.com/89 [알고리즘 이론] 동적계획법(Dynamic Programming, DP) 이론 이번에 볼 알고리즘은 동적계획법(Dynamic Programming)이다. 이 알고리즘은 줄어서 dp라고 많이 불리고 코딩테스트에도 자주 나오는 유형이라서 무조건 알아야 되는 알고즘이다. 동적계획법 알 jih3508.tistory.com LCS는 2개의 문자열에서 비교해서 공통으로 길이가 가장 큰 열을 말한다. 예시로 ABCDEFG와 BDFGEH에서 가장 길이가 긴 수열은 BDFG가 될 수가 있다. 두 개의 문자열..

문제 요약 알고리즘 분류: dp 난이도: Silver5 문제내용: 피자 높이가 A일 때 B, C로 분리하면 B*C 만큼 즐거움이 있다. B, C에서 분리해서 추가로 즐거움을 더 할 수 있다. 피자 높이 N으로 주어 질때 최대 총합 즐거움을 구하여라\ 사이트: https://www.acmicpc.net/problem/14606 14606번: 피자 (Small) 예제1의 입력이 1이므로, 게임 시작부터 갑이 분리할 수 있는 피자탑이 없습니다. 따라서 갑이 얻는 즐거움은 0입니다. 예제2의 정답 3은 다음과 같은 과정을 통해 얻어집니다. 먼저 놀이를 시작 www.acmicpc.net 문제풀이 이번 문제에는 모든 경우의 수를 구해서 풀기가 힘들다. 모든 경우의 수를 구하 O(N^N)개 이상으로 나올수 있다. 그..

문제 요약 알고리즘 분류: 동적계획법, dp 난이도: Silver1 문제내용: N개가 주어지고 1 부터 N까지의 팩의 개수와 가격이 있다. i번째는 팩개수를 나타내고 팩 개수마다 가격이 붙어 있다. N개 카드를 구입할때 가장 싸게 구입할수있는 가격을 출력해라. 사이트: https://www.acmicpc.net/problem/16194 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 문제풀이 이번 문제에는 모든 경우의 수를 구해서 풀기가 힘들다. 모든 경우의 수로 풀라면 재귀호출방식으로 해야 하는데 재귀호출시 시간..

문제 요약 알고리즘 분류: 동적계획법, dp 난이도: Silver1 문제내용: 가로가 N, 세로가 2인 사자 우리가 있다. 각 사자들이 가로 세로 겹치지 않게 배치 할수 있는 경우의 수를 구해라. 사이트: https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 문제풀이 이번 문제는 데이터 길이가 10만이라서 O(N)시간에 풀어야 한다. 그래서 이번 문제 유형은 동적 계획법이다. 동적계획법의 자세한 설명은 여기에 확인 해보면 된다. dp문제는 구현하는 능력보다 아이디어를 요구하기 때문에 점화식을 짜는 방법만 알면 쉽게 풀수 있다. 문제 접근 방법 1일때의 경우의 수는 왼쪽, 오른쪽, 아..

문제 요약 알고리즘 분류: 동적계획법, dp 난이도: Silver1 문제내용: N개가 주어지고 1 부터 N까지의 팩의 개수와 가격이 있다. i번째는 팩개수를 나타내고 팩 개수마다 가격이 붙어 있다. N개 카드를 구입할때 가장 비싸게 구입할수있는 가격을 출력해라. 사이트: https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 문제풀이 이번 문제에는 모든 경우의 수를 구해서 풀기가 힘들다. 모든 경우의 수로 풀라면 재귀호출방식으로 해야 하는데 재귀호출시 시간초..