Algorithm (12) 썸네일형 리스트형 [프로그래머스] 연속된 부분 수열의 합 (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 k == sum[s,e] : 현재까지의 candidates .. [프로그래머스] 아방가르드 타일링 (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 값보다 .. [프로그래머스] 두 원 사이의 정수 쌍 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/181187 문제 요약) 두 원의 사이의 정수인 좌표 개수를 출력하는 문제이다. [풀이 1] 입력이 1,000,000 까지이기 때문에 완전 탐색으로 풀 수 없다. O(nlong(n))으로 풀릴 수 있기 때문에 하나의 x좌표에 대한 y의 최대 최소를 이분탐색으로 구하면 O(nlog(n))으로 문제가 해결된다. 하나의 사분면의 좌표만 구하면 나머지 3개도 같기 때문에 하나의 사분면의 좌표 개수를 구해준다. minY는 작은 원의 y좌표들보다 크거나 같은 최소 y 좌표이며, maxY는 큰 원의 y좌표들보다 작거나 같은 최대 y 좌표이다. [풀이 2] 풀이 1을 고민하다 보니 굳이 복잡하게 풀 필요가 없었다. .. 이전 1 2 다음
