Algorithm (9) 썸네일형 리스트형 [프로그래머스] 인사고과 (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.. [프로그래머스] 연속된 부분 수열의 합 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/178870 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [문제 요약] 오름차순으로 정렬된 배열에서 연속된 수들의 합이 k 와 같은 집합에서 원소의 개수가 가장 적으면서 시작 index가 가장 낮은 수열의 시작과 끝 index를 구하는 문제. [풀이] 투포인터 문제 O(N)에 풀린다. 세가지의 조건이 필요하다 k > sum[s,e] : e(end) pointer를 증가시켜 sum의 값을 증가시킨다. k < sum[s,e] : s(start) point.. [프로그래머스] 아방가르드 타일링 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/181186 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [문제 요약] 90도씩 회전이 가능한 두개의 도형으로 만들 수 있는 3 * n 의 타일의 개수를 구하는 문제. [풀이] O(N)에 풀리는 DP문제 두 도형을 90도씩 회전해 가면서 만들 수 있는 도형의 규칙성을 찾는다. 3 * 1인 경우는 1개 3 * 2인 경우는 3 * 1 + 3 * 1을 제외한 2개를 만들 수 있다. 3 * 3인 경우는 2 + 1, 1 + 2를 제외한 5개를 만들 수 있다. .. [프로그래머스] 요격 시스템 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/181188 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [문제 요약] (s, e)구간의 x축에 평행하는 직선들의 집합에서 모든 선을 관통하기 위한 y축에 평행하는 직선의 최소 개수를 찾는 문제. [풀이] Greedy하게 풀리는 문제 O(NlogN)에 풀린다. e 값을 기준으로 오름차순으로 정렬한 이후, e 보다 크거나 같은 s 값이 나올 때 마다 새로운 선이 필요하다. (e 값을 기준으로 정렬했기 때문에 n번째의 s 값이 n - k번째의 e 값보다 .. 이전 1 2 다음
