Study/Algorithm (36) 썸네일형 리스트형 [동적계획법] 6. 원주율 외우기 8.7 문제: 원주율 외우기 (문제 ID: PI, 난이도 : 하) https://algospot.com/judge/problem/read/PI algospot.com :: PI 원주율 외우기 문제 정보 문제 (주의: 이 문제는 TopCoder 의 번역 문제입니다.) 가끔 TV 에 보면 원주율을 몇만 자리까지 줄줄 외우는 신동들이 등장하곤 합니다. 이들이 이 수를 외우기 위해 사용하는 방법 중 하나로, 숫자를 몇 자리 이상 끊어 외우는 것이 있습니다. 이들은 숫자를 세 자리에서 다섯 자리까지로 끊어서 외우는데, 가능하면 55555 나 123 같이 외우기 쉬운 조각들이 많이 등장하는 방법을 택하곤 합니다. 이 때, 각 조각들의 난이 algospot.com 컨셉 3~5자리씩 끊어 읽는 점화식을 세워봤다. in.. [동적계획법] 5. 합친 LIS 어려워잉 https://algospot.com/judge/problem/read/JLIS algospot.com :: JLIS 합친 LIS 문제 정보 문제 어떤 수열에서 0개 이상의 숫자를 지운 결과를 원 수열의 부분 수열이라고 부릅니다. 예를 들어 '4 7 6'은 '4 3 7 6 9'의 부분 수열입니다. 중복된 숫자가 없고 오름 차순으로 정렬되어 있는 부분 수열들을 가리켜 증가 부분 수열이라고 부르지요. 예를 들어 '3 6 9'는 앞의 수열의 증가 부분 수열입니다. 두 개의 정수 수열 A 와 B 에서 각각 증가 부분 수열을 얻은 뒤 이들을 크기 순서대로 합친 것을 합친 증가 부 algospot.com [동적계획법] 4. LIS (미완) 어려웡 https://algospot.com/judge/problem/read/LIS algospot.com :: LIS Longest Increasing Sequence 문제 정보 문제 어떤 정수 수열에서 0개 이상의 숫자를 지우면 이 수열의 부분 수열 (subsequence) 를 얻을 수 있다. 예를 들어 10 7 4 9 의 부분 수열에는 7 4 9, 10 4, 10 9 등이 있다. 단, 10 4 7 은 원래 수열의 순서와 다르므로 10 7 4 9 의 부분 수열이 아니다. 어떤 부분 수열이 순증가할 때 이 부분 수열을 증가 부분 수열 (increasing subseque algospot.com [동적계획법] 3. 삼각형 위의 최대 경로 https://algospot.com/judge/problem/read/TRIANGLEPATH algospot.com :: TRIANGLEPATH 삼각형 위의 최대 경로 문제 정보 문제 6 1 2 3 7 4 9 4 1 7 2 7 5 9 4 위 형태와 같이 삼각형 모양으로 배치된 자연수들이 있습니다. 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려가 맨 아래 줄로 내려가는 경로를 만들려고 합니다. 경로는 아래 줄로 내려갈 때마다 바로 아래 숫자, 혹은 오른쪽 아래 숫자로 내려갈 수 있습니다. 이 때 모든 경로 중 포함된 숫자의 최대 합을 찾는 프로그램을 작성하세요. 입력 입력의 첫 줄에는 테 algospot.com 컨셉 점화식을 만들었다. path(y,x) //(y,x)에서 시작하여 맨 아래줄까지.. [동적계획법]2.와일드카드 종만북 8장 동적계획법. 8.2. WILDCARD https://algospot.com/judge/problem/read/WILDCARD algospot.com :: WILDCARD Wildcard 문제 정보 문제 와일드카드는 다양한 운영체제에서 파일 이름의 일부만으로 파일 이름을 지정하는 방법이다. 와일드카드 문자열은 일반적인 파일명과 같지만, * 나 ? 와 같은 특수 문자를 포함한다. 와일드카드 문자열을 앞에서 한 글자씩 파일명과 비교해서, 모든 글자가 일치했을 때 해당 와일드카드 문자열이 파일명과 매치된다고 하자. 단, 와일드카드 문자열에 포함된 ? 는 어떤 글자와 비교해도 일치한다고 가정하며, * 는 0 글자 이상의 어떤 문자 algospot.com 컨셉 처음엔 그냥 *만나면 다음글자 검색하면 되.. [동적계획법] 1.외발뛰기 종만북 8장 동적계획법. 8.1. JUMPGAME https://algospot.com/judge/problem/read/JUMPGAME 동적 계획법으로 풀었다. 그래프 문제로도 접근할 수 있다고 한다. 8.1. 외발뛰기(JUMPGAME) 코드 (정답, 20ms) ...더보기 /** * @name 8.1.외발뛰기 * @ID JUMPGAME * @date 2019-08-04 * @author Sunmon */ #include #include int n, board[100][100], cache[100][100]; using namespace std; //(y,x)부터 (n-1, n-1)까지 도달할 수 있으면 1, 아니면 -0 리턴 int jump(int y, int x) { if(y >= n || x >=.. [동적계획법] 0. 동적 계획법 종만북 8장 동적계획법. Dynamic programming 동적계획법vs분할정복법 문제를 나누는 방식의 차이 동적계획법 - 점화식으로 표현 가능 → 두 번 이상 계산되는 `중복문제`를 알아낸다. - `중복문제`를 해결하는 데 동적계획법 사용. 같은 문제를 또 계산할 필요 없잖아? - 중복문제 계산값을 어디다 담아두느냐? `캐시(cache)`에. 캐시에 저장해뒀다가 문제가 같으면 계산하지 않고 값만 꺼내 쓴다. - 이렇게 결과를 저장해두었다가 재사용 하는 방법을 `메모이제이션(memoization)`이라고 부른다. - 메모이제이션을 적용하려면 `참조적 투명성(referential transparency)`가 보장되어야 함 - 참조적 투명성이란? input이 같으면 같은 output이 나오는 것! 메모이제.. 스택(Stack) 스택(stack)스택: 차곡차곡 쌓아올린 형태의 구조같은 구조, 같은 크기의 자료를 정해진 방향으로만 쌓는다. top(맨윗층)에서만 접근할 수 있다.크레페처럼 생각하면 된다. 한 층 한 층 쌓아올려서 맨 윗층부터 하나씩 벗겨먹는것.LIFO: Last-In-First-Out 구조: 먼저 들어간 게 바닥에 깔림(오래됨) , 최근에 들어간 게 맨 위층에 얹혀짐. 꺼낼때는 윗층(최근꺼)부터.push: 삽입(넣기)pop: 삭제(꺼내기) 스택에 pushtop 포인터가 +1을 하면 stack의 크기를 넘지 않는가 확인하고 (overflow)top+1한 포인터에 push 스택에 poptop포인터가 -1을 하면 땅바닥을 뚫지 않는가 확인하고(underflow1)top에 있는 포인터에 pop stack뿐만 아니라 모든 코.. 이전 1 2 3 4 5 다음