분류 전체보기657 [codeground] 31. 프리랜서 codeground - Practice - SCPC 2회 예선 - 31. 프리랜서 문제 : https://www.codeground.org/practice/practiceProblemList DP를 Top-down(탑다운) 방식으로 채워나가면서 문제를 해결합니다. D[0][ind] = ind주에 P사 작업했을 때 얻을 수 있는 최대 이익 D[1][ind] = ind주에 Q사 작업했을 때 얻을 수 있는 최대 이익 go(int ind) = ind주까지 작업했을 때 얻을 수 있는 최대 이익 반환 만약 ind주에 P사를 작업했을 때 얻을 수 있는 최대 이익은 D[0][ind] = go(ind-1) + P[ind] 입니다. ind주에 Q사를 작업했다면 그 전주에도 Q사 작업을 해야 하므로 D[1][ind] = g.. 2019. 9. 13. [codeground] 52. 최대 직사각형 codeground - Practice - 연습문제 - 52. 최대 직사각형 문제 : https://www.codeground.org/practice/practiceProblemList 2차원 배열에서 만들 수 있는 모든 직사각형들의 배열 합 중 최대값을 구하는 문제다. 직사각형을 [그림 1] 순서로 탐색하였다. 그런데 실제로는 1,2를 합친 것, 3,4를 합친 것, 5,6을 합친 것 또한 직사각형도 탐색을 해야 하므로 추가적인 알고리즘이 더 필요하다. 이를 위해 변수 2개를 사용한다. tmp는 현재 탐색 중인 직사각형(빨간색)의 배열 합을 의미한다. row는 현재까지 탐색한 열 범위([그림 2]에서 열 범위는 1~2)로 만들 수 있는 직사각형들 중 가장 큰 배열의 합을 의미한다. 즉, [그림 3] 처럼.. 2019. 9. 12. [leetcode] 1048. Longest String Chain 문제 : https://leetcode.com/problems/longest-string-chain/ 먼저 words 배열을 문자열 길이 오름차순으로 정렬한다. 이제 반드시 [words[i], words[j]] (i < j) 식으로 string chain이 만들어진다. longest length를 저장하는 map을 하나 만든다. map dp; 위 map에는 key : words[i], value : longest length of a word chain 이 들어간다. 이제 words를 앞에서부터 탐색한다. 탐색 중인 words 문자열을 word2라고 했을 때 word2에서 문자를 하나씩 빼면서 string chain을 만드는 word1인지 확인한다. 만약 string chain을 만들 수 있는 word1.. 2019. 9. 11. [디자인패턴] 데코레이터 패턴(Decorator pattern) 데코레이터 패턴이란 기본(공통) 기능에 여러가지 기능을 조합해서 제공하고자 할 때 유용하게 사용된다. 만약 기능의 조합들을 상속으로만 표현하자면 조합별로 클래스를 만들어야 한다. 즉, 기본 기능에 A, B, C 기능을 추가하고자 한다면 1. 기본 기능 2. 기본 기능 + A 3. 기본 기능 + B 4. 기본 기능 + C 5. 기본 기능 + A + B 6. 기본 기능 + B + C 7. 기본 기능 + C + A 8. 기본 기능 + A + B + C 와 같이 총 8가지 클래스를 만들어야 한다. 기능이 하나씩 추가될수록 만들어야 하는 클래스의 수는 엄청나게 증가한다. 이를 해결하기 위해 데코레이터 패턴을 사용할 수 있다. 버스 정류장 전광판으로 예를 들어보자. 기본기능(공통 기능) : 곧 도착할 버스들의 번호.. 2019. 9. 11. [테트리스] 11. 블럭 저장, 불러오기 오늘할 이슈. 테트리스 시 블럭을 keep해두고 keep해둔 블럭을 load해서 사용하는 것까지 구현했다. #1. 이미 불러온 블럭인 경우 -> 아무 행동하지 않고 종료 #2. keep해놓은 블럭이 있는 경우 -> 현재 블록 타입을 keep, keep해뒀던 타입으로 새로운 블럭 생성 후 위에서 부터 다시 떨굼. #3. keep해놓은 블럭이 없는 경우 -> 현재 블록 타입을 keep, 다음에 나올 예정이었던 타입의 블럭을 생성. 수도코드를 간단히 적어보자면 위와 같다. const keepOrLoadBlock = function() { // #1 if(nowBlock.isLoaded) return false; nowBlock.eraseBeforeBlock(); const willKeepType = nowBl.. 2019. 9. 10. [leetcode] 1155. Number of Dice Rolls With Target Sum 문제 : https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/ DP 문제. int dp[d+1][target+1]; // dp[d][sum] = d개의 dice로 sum을 만들 수 있는 경우의 수 점화식은 위와 같다. 먼저 dp[1][1~target]을 1로 초기화 시킨다. (다이스 1개로 만들 수 있는 경우의 수 세팅) dp 배열을 행우선탐색으로 탐색하면서 배열을 채운다. (dice, sum) dp 요소를 채운다고 할 때, for(int face=1; face 2019. 9. 8. 이전 1 ··· 74 75 76 77 78 79 80 ··· 110 다음
