컴공생 일상 블로그 컴공생 일상 블로그

> : 추출연산자 입력을 받기위해 cin객체를 사용하고, c와 다르게 주소연산자는 사용하지 않는다. 이때, cin객체는 사용자가 입력한 데이터를 오른쪽에 위치한 변수의 타입과 동일하게 변환시켜 준다. endl : C언어에서 \n과 동일 의미, 개행 #include using namespace std; int main() { int age; cout > age; cout

Subset Sum(부분 합 문제) : 양의 정수들의 배열이 들어 올때, 배열의 부분합으로 일정 수를 만들 수 있으면 TRUE를, 만들 수 없으면 FALSE를 돌려준다. Ex) X = {8, 6, 7, 5, 3, 10, 9} T = 15이면, {8,7}, {5,10}, {6,9}, {7,5,3} > TRUE - Base Cases T = 0 이면, 선택하지않으면 항상 TRUE 이다. T < 0 이면, 항상 FALSE이다. - General Case(점화식) 총합이 T인 부분집합에 대해, 해당 부분집합은 X의 원소 x에 대해 x를 포함하거나, 포함하지않거나의 두가지로 나뉜다. 1. x를 포함할 경우, T-x 인 X-{x}의 부분집합이 존재한다. 2. x를 포함하지 않을 경우, T 인 X-{x}의 부분집합이..

이진 탐색 정렬된 A[0...n-1]의 배열에 대해 k값을 찾을 때, a의 중간값(median)을 k 와 비교하여 같으면 종료. 이진탐색은 실은 분할정복기법이다. 중간값을 k와 비교한 뒤에 배열의 절반에 대해서만 탐색을 계속한다. 즉 문제의 크기가 n/2인 동일한 작은 문제를 해결하다보면, 문제를 해결 할 수 있다. 이진탐색 # A가 정렬된 배열일때 A[a...b]에서 k값을 탐색 int binary_search(A[a...b], k, a, b): if a>b: return -1 mid = (a+b)/2 if A[mid] > k: return binary_search(A, k, a, mid-1) elif A[mid] < k: return binary_search(A, k, mid+1, b) else re..

https://programmers.co.kr/learn/courses/30/lessons/92335 코딩테스트 연습 - k진수에서 소수 개수 구하기 문제 설명 양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다. 0P0처럼 소수 양쪽에 0이 있는 경우 P0처럼 소 programmers.co.kr 문제자체는 간단하다. 1. 진수변환 2. 조건에 맞는 소수 판별 # 어찌저찌 길이 줄여봄... import math def solution(n, k): num = '' while n > 0: n, mod = divmod(n, k) #몫과 나머지를 돌려줌 num += str(mod) numbers = [int(i..

https://programmers.co.kr/learn/courses/30/lessons/92334 코딩테스트 연습 - 신고 결과 받기 문제 설명 신입사원 무지는 게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려 합니다. 무지가 개발하려는 시스템은 다음과 같습니다. 각 유저는 한 번에 한 명의 programmers.co.kr 풀긴 풀었는데, 효율성이 좋을지는 모르겠다. 유저 : (신고한 유저목록) 과 같은 자료구조를 만들고 , 게시판 이용이 정지되는 유저목록을 구해서 교집합 연산 후에 개수를 세서 발송해야하는 메일 개수를 구하면된다. from collections import defaultdict def solution(id_list, report, k): result, ba..

https://programmers.co.kr/learn/courses/30/lessons/43105?language=python3 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 예전에는 dp문제가 어려웠는데, 그렇게 어렵지도 않은 것 같다. 효율성 테스트도 한번에 통과했다. 위와 같이 삼각형의 일부분에 대해, 1을 지나가는 경우는, 3을 지나고 1을 지나는 경우와 8을 지나고 1을 지나는 경우 두가지밖에 없다. 즉 삼각형이 양 끝의 경우에 대해 if문으로 처리해주고, 그 가운데들에 대해서는 두 가지경우중 더 큰 경우를 선택하면서 삼각형테이블을 채우다보면, 맨 마지막 행중 최대값이 ..

1. 일반적인 마스터 정리 T(n) = rT(n/c) + O(f(n))을 만족 하는 경우 3가지의 경우로 복잡도를 구할 수 있다. 2. 등차수열의 경우, T(n-2) + T(2) + O(n)과 같은 경우 3. 마스터정리를 만족하지 않는 경우, recursion tree를 그려서 복잡도를 구하는 경우 3_1. 만약 트리의 각 층의 너비가 같은 경우 : 트리의 높이 * 너비 3_2. 만약 트리의 너비가 작아질 경우 : 등비가 1보다 작은 등비수열의 합으로 표현가능, 즉 특정 상수에 수렴한다. 3_3. 만약 트리의 너비가 커질 경우 : 트리의 잎의 개수, (나누어지는 자식노드의 개수)^트리의 높이 3_2와 3_3의 예제. (algorithms-Jeff 49p 7번 의 (k), (l)) K(n). 공비가 1보다..

분할 정복 : 말그대로 문제를 분할하여 정복하여 풀이 - 분할 정복의 대표적인 예시 : Merge Sort 병합정렬 1. 주어진 배열을 두 부분으로 나눈다. 2. 두 부분배열을 각각 Mergesort한다. 3. 정렬된 부분배열을 합쳐서(merge) 하나의 정렬된 배열로 만든다. MergeSort(A[1...n]): if n > 1: m = [n/2] MergeSort(A[1...m]) MergeSort(A[m+1...n]) Merge(A[1...n], m) - Divide and Conqur의 설계 1. 문제를 동일한 작은 문제들로 나누어라 2. 각각의 작은 문제들을 재귀요정에게 맡겨라(일단 같은 작은 문제들을 던져주면 알아서 해결해준다.) 3. 최종 해결법은 작은 문제들에 대한 답을 결합해라. * 어떤..