본문 바로가기

프로그래머스69

[코딩테스트 연습] 올바른 괄호의 갯수 문제: 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.
[코딩테스트 연습] 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.
[코딩테스트 연습] 정수 삼각형 문제: https://programmers.co.kr/learn/courses/30/lessons/43105 DP 문제입니다. 점화식은 아래와 같습니다. dp[h][w] 정의: 꼭대기부터 triangle[h][w] 칸까지 이어지는 경로의 합 중 최댓값. //점화식 dp[h][w] = triangle[h][w] + max(dp[h-1][w-1], dp[h-1][w]) N제한이 크지않으므로 위와 같이 점화식을 세운 후 TOP-DOWN이나 BOTTOM-UP 방식 중 편한 걸로 풀면됩니다. 코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/PG43105.cc 2020. 7. 21.
[코딩테스트 연습] 베스트 앨범 문제: https://programmers.co.kr/learn/courses/30/lessons/42579 주어진 자료를 어떻게 (장르, 재생횟수, 고유번호)로 파싱해서 정렬하냐의 문제입니다. 문제를 해결한 순서는 아래와 같습니다. 1. 장르별 총 재생횟수 카운팅 후 장르를 내림차순 정렬 2. 1번 과정을 통해 장르의 우선순위를 알았으니 vector plays의 players[idx]값과 idx를 활용하여 (장르, 재생횟수, 고유번호)로 소팅 3. 장르마다 최대 2회까지만 재생해야하므로 streamingCnt라는 배열을 선언해 장르별 재생횟수 관리 코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/PG42579.cc 2020. 7. 14.

티스토리툴바