분류 전체보기 (12) 썸네일형 리스트형 [프로그래머스] 가장 긴 팰린드롬 문제 풀이 (c++) https://school.programmers.co.kr/learn/courses/30/lessons/12904 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 요약) 팰린드롬은 앞뒤로 뒤집어도 똑같은 문자열을 의미한다. 주어진 문자열의 부분 문자열 중 가장 긴 팰린드롬의 길이를 구하는 문제이다. [풀이]완전 탐색으로 부분 문자열을 모두 비교하는 시간복잡도는 O(N^3) 이며, 주어진 입력 S.len() 재귀함수를 사용하면 팰린드롬을 최적화 할 수 있다. 본인은 O(N^2) 로 해결하였다.두가지의 조건을 통해 팰린드롬을 구한다.1. S[st] == S[ed + 1] 인 경우 두개의 문자열은 같기 .. [프로그래머스] 3 x n 타일링 문제 풀이 (c++) https://school.programmers.co.kr/learn/courses/30/lessons/12902 문제 요약) 3 x n 타일링 문제는 2 x 1, 1 x 2 의 타일을 가지고 만들 수 있는 높이가 3이고 너비가 n 인 직사각형의 경우의 수를 출력하는 문제 [풀이]완전 탐색으로 먼저 생각을 해보면, 러프하게 O(K^N) 이므로 N 특정한 조건을 가지고 점화식을 만들어 bottom-up 방식으로 memoization 을 통해 최적해를 구할 수 있다.너비가 짝수인 2 * 1 타일들로 홀수인 타일을 채우는 방법은 없으므로, N이 홀수인 경우는 0을 리턴한다. (2k != 2r + 1)점화식은 DP[i] = DP[i - 1] * 3 + lim_{j = 0 -> i - 2} DP[j] * 2 와 .. [프로그래머스] 뒤에 있는 큰 수 찾기 (c++) https://school.programmers.co.kr/learn/courses/30/lessons/154539 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 요약) 주어진 배열 numbers에서 numbers[i] [풀이]배열의 크기가 1 자료구조 문제로 stack 을 활용하여 각 값들을 비교할 수 있다.numbers[i] 더 큰 값이 없는 경우 -1 을 answer 에 담아야 하므로, answer 의 초기 값을 모두 -1 로 설정stack 으로 관리하면 current index 가 어디인지 알 수 없는데, 현재의 index 와, stack 에서 pop 된 개수를 기반으로 distance .. [프로그래머스] 인사고과 (c++) https://school.programmers.co.kr/learn/courses/30/lessons/152995 문제 요약) {근무 태도 : X, 동료 평가 : Y} 쌍이 배열로 주어진다.0번 index 의 X0, Y0 값이 k 번째 index 의(0 X0 + Y0 이 Xk + Yk 보다 작은 경우 순위에서 밀린다. [풀이]각 입력은 100,000 보다 작거나 같으므로, O(N) 혹은 O(NlogN) 알고리즘을 생각해야 함.등수 = 전체 사원수 - 인센티브를 받지 못하는 사원수 - 0번째 사원보다 점수가 크거나 같은 사원수가 된다.i 번째의 X 와 Y 둘 모두 j 번째의 X 와 Y 보다 작은 경우 순위에서 제외되기 때문에 기준을 X로 잡고,동일한 X 의 값에 포함되는 최대의 Y 로 최적화 시킨다. M.. [프로그래머스] 조이스틱 (c++) https://school.programmers.co.kr/learn/courses/30/lessons/42860 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr [문제 요약]입력으로 주어진 문자열과 길이가 같은 'A' 로 이루어진 문자열을 조이스틱 이동을 통해 주어진 문자열과 동일하게 만드는 최소 비용을 구하는 문제.커서는 항상 제일 처음 문자에서 시작하며, 양 끝의 커서에서 이동은 반대 끝으로의 이동을 의미한다. [풀이]완전 탐색 문제로, 그리디하게 O(n^2) 풀린다.풀이는 O(n)에 풀었다.조이스틱 이동은 크게 2개의 분류로 나뉜다.알파벳을 변경시키는 .. [프로그래머스] N으로 표현 (c++) https://school.programmers.co.kr/learn/courses/30/lessons/42895 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr [문제 요약]주어진 숫자 N 으로 사칙연산하여 number 를 만들 수 있는 N 의 최소 개수 구하기 [풀이]완전 탐색 문제로, number = 10^k 일 때 O(k^k) 에 풀린다. (풀이 코드는 러프하게 O(8^8) 로 해결)number 이 커지면 DP로 최적화 가능하다.cur = (w - 1)(N * 10) + N 의 값인 { N, NN, NNN, ..., NNNNNNNN} 의 값들을 재귀적으.. [프로그래머스] 광물 캐기 (c++) https://school.programmers.co.kr/learn/courses/30/lessons/172927 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [문제 요약] 광물 별 강도와 곡괭이 별 위력이 주어지고, 광물 배열과 곡괭이 별 개수 배열이 주어진다. 광물을 캐는데 필요한 피로도는 (강도 / 위력)일 때, 피로도의 최소값을 구하여라. (곡괭이는 5개의 광물을 캘 수 있으며, 중간에 쓰다 버릴 수 없다.) [풀이] 완전 탐색 문제로 O(2^N)에 풀린다. 곡괭이는 5개씩 묶어서 사용하므로, 5의 배수마다 새로운 곡괭이로 바꿀 수 있다. 따라.. [프로그래머스] 과제 진행하기 (c++) https://school.programmers.co.kr/learn/courses/30/lessons/176962 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [문제 요약] 과제 배열(name, start, playtime)에 대해 먼저 끝나는 과제 순서대로 스케쥴링 하는 문제이다. [풀이] 정렬, 자료구조, 시뮬레이션, 구현 문제 O(NlogN)에 해결된다. 과제배열의 시작 시간은 정렬되어 있지 않기 때문에 시작시간을 기준으로 정렬한다. 다음 과제의 시작 시간과 현재 과제가 끝나는 시간을 비교해야 한다. nextStart - (curStart + p.. 이전 1 2 다음
