백준 문제풀이

문제는 어떠한 S(k)를 기점으로 왼쪽은 부분증가수열 오른쪽은 부분감소수열의 최대길이를 출력하는것인데먼저 lis 알고리즘을 응용하는 문제라고는 누구나 일단 생각할 수 있을것이다.(lis알고리즘 링크 -> lis알고리즘이란?)나의 해결방법은 이렇다.dp1과 dp2 1차원

이 문제는 lis 알고리즘으로 해결가능하고lis 관련링크는 ----> lis 알고리즘 설명!!!lis알고리즘으로 구현 해보자면

백준 2573문제 이문제의 해결과정은 이렇다 matrix 전체를 순회하며 빙산이 있는곳을 찾는다 빙산이 있는곳을 찾았을때 처음 지점부터 DFS를 수행해주면서 주변 바다의 개수만큼 matrix값을 빼준다 DFS가 2번이상 수행된다면 그 때가 빙산이 분리되는 시점 다음

이문제도 정말 삽질 많이했다.결론만 하자면 정말 간단하다.결국 이 주어진 규칙에서dpi는 i번째를 마셨을 때 A와 안마셨을때 B로나누고A일때는1\. i-1을 마셨을때와2\. i-1을 안마셨을 때로 나눌수있다.또한 테이블 dpi가 나타내는 것은 i까지의 포도주중 마실 수

먼저 이문제는 상당히 삽질하며 풀었던 문제이다. 1차원 리스트로 dp테이블을 만들어서 해결하려다가 정말 시간낭비를 많이했다.먼저 이문제를 해결할때 생각순서는 이렇다.모든 경우의 수에서 이 수가 계단수인지 검사하는 직관적으로 떠오르는 방법이 있는데이방법을 할경우 연산횟수

먼저 이문제는2번째 조건인 연속된 세 개의 계단을 모두 밟아서는 안된다고 한다.i번째 계단까지의 합의 최댓값을 dpi라 했을 때dpi는 무조건 2가지로 경우가 나뉘는데 i계단에 도착하기전에 i-1계단에서 1단점프를 하든가아니면, i-2계단에서 2단점프를 하는 방법밖에없

문제에 앞서 이문제를 top-down방식으로 해결하려 했지만 아무리 고민해도 해결이 안되었다.이부분은 언젠가 해결해야 한다.바텀업 방식으로 해결가능한데 먼저 점화식을 보여주자면dpi = min(dpi / 3, dpi / 2, dpi+1)이고이에따라 바텀업으로 채워가면