본문 바로가기

분류 전체보기361

[코딩테스트 연습] 징검다리 문제: https://programmers.co.kr/learn/courses/30/lessons/43236 이분 탐색 문제입니다. 10억에 해당하는 distance를 선형 탐색하면 O(10억)으로 시간초과가 납니다. 그러므로 5만에 해당하는 바위 갯수를 이용해서 문제를 해결해야 합니다. 아이디어는 다음과 같습니다. 1. 임의의 바위 간의 거리를 정합니다. (mid) 2. 이 바위 거리를 정답으로 할 때 n개 이하의 돌을 제거할 수 있는 지 세봅니다. 3-1. 2번이 가능하다면 바위 거리를 정답후보로 저장하고, 바위 간의 거리를 증가 시켜봅니다. 3-2. 2번이 불가능하다면 바위 간의 거리를 줄여봅니다. 이런 식으로 이분 탐색을 하면 됩니다. 단, 2번에서 n개 '이하'의 돌에 적용할 수 있는 것은 예를.. 2020. 7. 24.
[코딩테스트 연습] 올바른 괄호의 갯수 문제: https://programmers.co.kr/learn/courses/30/lessons/12929?language=cpp 재귀문제입니다. 올바른 괄호의 조건은 크게 두 가지 입니다. 1. ( ) 쌍의 갯수가 맞아야 한다. 2. '(' 괄호가 ')' 보다 먼저 나와야 합니다. 즉, 사용할 '(' 괄호가 없을 때 ')' 괄호가 나오면 안된다는 뜻입니다. 괄호를 만드는 재귀함수는 2가지 케이스로 뻗어나갑니다. case1. 현재 깊이에서 + '(' 괄호 더하기 case2. 현재 깊이에서 + ')' 괄호 더하기 재귀함수이므로 기저 사례를 잘 적용해주고, 조건에 맞을 때만 호출할 수 있도록 함수를 작성하면 됩니다. 코드: https://github.com/cottory/algorithm/blob/mast.. 2020. 7. 24.
[BOJ]2096번: 내려가기 문제: https://www.acmicpc.net/problem/2096 슬라이딩 윈도우 문제입니다. 메모리 제한이 심상치 않습니다. 발판은 board[N][3]의 형태를 가지고 있지만, i번째 칸을 계산함에 있어서 필요한 발판정보는 i-1번째 칸의 정보만 필요합니다. 그러므로 메모이제이션을 위한 dp[][] 배열이나 input값을 저장하는 board[][] 배열 모두 [2][3] 크기면 됩니다. dp배열을 다음과 같이 정의내리겠습니다. max_dp[N][M]: 맨 윗칸에서부터 board[N][M] 칸까지 내려왔을 때 얻을 수 있는 최댓값 min_dp[N][M]: 맨 윗칸에서부터 board[N][M] 칸까지 내려왔을 때 얻을 수 있는 최솟값 끝으로 dp[i][], dp[i+1][] 이렇게 두 칸만 사용하.. 2020. 7. 22.
[코딩테스트 연습] 2 x n 타일링 문제: https://programmers.co.kr/learn/courses/30/lessons/12900 DP 문제입니다. DP[N]: 2 x N개의 타일칸에 놓을 수 있는 방법으로 가정하겠습니다. 기저 사례부터 생각해보면, DP[1] = 1, 세로로만 놓을 수 있으므로 1 입니다. DP[2] = 2, 세로로 두 개, 가로로 두 개 놓을 수 있으므로 2입니다. 위 두 개가 기저 사례이고, N > 2 부터는 DP[N]에 대해 다음과 같은 성질이 성립합니다. 1. DP[N-1] 방법의 갯수 + 세로로 한 개 놓으면 DP[N]이 됩니다. 2. DP[N-2] 방법의 갯수 + 가로로 두 개 놓으면 DP[N]이 됩니다. 위 1, 2번 방법을 모두 더한 게 DP[N]의 가짓 수가 됩니다. 그러므로 DP[N] = .. 2020. 7. 22.

티스토리툴바