해나의 컴공생존기

정의해준 재귀함수를 분석해보겠다. 인자로 a,b,c 가 들어오고 이 값에 따라 재귀호출을 하는 것 같다. a,b,c 중 하나라도 0이하가 되면 1을 리턴한다. a,b,c 중 하나라도 20이상이 되면 a,b,c에 20을 넣고 재귀호출한다. a> b >> c; if (a == -1&&b==-1&&c==-1) break; //종료조건 cout

알고리즘시간에 배운 동적프로그래밍 문제를 하나 가져와봤다. 의사코드를 한번 보면 재귀호출은 들어온 숫자(n)이 1이나 2가 아니라면 n-1과 n-2를 인자로 재귀호출하여 더해준다. 만약 6이 들어온다면 f(6) → f(5) + f(4) → ( f(4)+f(3) ) + ( f(3)+f(2) ) → ( ( f(3)+f(2) ) + ( f(2)+f(1) ) ) + ( ( f(2)+f(1) )+1 ) → ( ( ( f(2)+f(1) )+1 ) + ( 1+1 ) ) + ( (1+1 )+1 ) → ( ( ( 1+1 )+1 ) + 2 ) + 3 → 8 동적프로그래밍 의사코드를 보면 인자로 들어온 n만큼 배열을 만들어서 인덱스 1,2, 에는 1을 넣어주고 나머지 인덱스에는 앞에 두자리를 더한 값을 넣어준다. 하지만 '..

오랜만에 푸는 문제이기 때문에 별로 워밍업이 되지 않을까 하는 문제를 가져왔다 (풀어봐야알겠지만..) 처음에 들어오는 값은 학생 수(N) 이고 두번째 들어오는 값은 상을 받는 사람들(k)일 것이다. 그다음에는 점수들이 쭉 나열이 된다. 점수들을 오름차순으로 저장하고 k등 한 사람을 return 해주면 될 것이다. 점수가 중복이 되면 어떡하지..?라는 고민이 들지만.. 누가 상을 받냐? 가 아니라 점수의 커트라인이 몇이냐 이기 때문에 상관없을 것 같다. list를 이용하여 한번 코드를 짜봐야겠다. 분명 맞게 짠거같은데..게속 결과가 0만 나왔다... k번째까지 출력해봐도 0만 계혹 나왔다. iterator의 오류일까 싶어서 봤지만 아무리 봐도 맞았다. 원인은..! list score(N); 으로 초기화를 ..

1. STL이란? Standard Template Library 의 약자 반복자, 컨테이너, 알고리즘 함수객체 등의 라이브러리로 구성 2. 컨테이너 기본 자료형과 유저가 정의한 자료형을 담는 일종의 자료구조 2.1 시퀀스 컨테이너 일반적인 자료구조와 동일한 형태 (vector / list / string / deque ...) 자료를 입력한 순서대로 저장하기 때문에 저장, 검색, 알고리즘에 불리하다. 적은 양의 자료나 검색 속도가 중요하지 않은 경우에 사용한다. 2. 연관 컨테이너 일정한 규칙에 따라 자료를 조직화하여 저장 (set / map / multiset / multimap ...) 자료를 정렬하여 저장하기 때문에 검색에 유리하다. 많은 양의 자료나 검색 속도가 중요한 경우에 사용한다. 3. 어댑..

1. time_t time_t는 time 헤더에서 시간을 잘 다루기 위해서 만들어진 데이터 타입이다. 일반적으로 1970년 1월 1일 00:00 UTC (유닉스 타임)이후 경과된 초(정수값)를 나타낸다. time() 이라는 함수의 반환형이다. 2. tm 구조체 tm구조체는 시간을 우리가 알아볼 수 있게 세세하게 변수로 나누어서 만들어져 있는 구조체 이다. time_t는 사람이 알아보기 힘드므로 tm 구조체를 활요하면된다. struct tm { int tm_sec; // seconds after the minute - [0, 60] including leap second int tm_min; // minutes after the hour - [0, 59] int tm_hour; // hours since ..

1. Select Working Days 1.1 문제정의 N일의 각각 Pay가 지정되어있다. 가장 돈을 많이 벌 수 있도록 일하는 날짜를 골라야한다. 연속근무는 불가하다. 2. solution X는 그날 일을 안했을 때, 그날까지 벌 수 있는 최대의 돈이다. O는 그날 일을 했을 때, 그날까지 벌 수 있는 최대의 돈이다. 노란색으로 색칠한 것은, 결과가 나온 후 역추척한 것이다. 3. Code 이 코드는 내용을 모르면 알아보기 쉽지 않다. 열 인덱스 0: 그 날 일을 안하는 것중에 제일 좋은 것 열 인덱스 1: 그 날 일을 하는 것중에 제일 좋은 것 배열 생성하고 첫 날 일을 할 때&안할 때의 초기값을 넣어준다. day2부터 계산한다. 그 날 일을 안할 때 = MAX(그 전날 일 할때 , 그 전날 일 안..

1. Fibonacci Number 피보나치 수열은 f(0) = 0 이고 f(1) = 1 일 때, f(n) = f(n-1) + f(n-2) 를 따라가는 수열이다. 1.1 Recursion 재귀는 독립적으로 실행할 수 있어야 한다. 전체 문제가 있고 잘라서 자른 문제가 전체인 것처럼 동작한다. 머지소트는 왼쪽 배열이 오른쪽배열의 영향을 받지 않는다. 하지만 그래프와 같은 경우는 영향을 받을 수 밖에 없다 완전히 독립적으로 잘라서 재귀로 적용하기 힘들다. 독립적인 부분문제의 답으로 전체의 답을 만든다는 점에서 분할정복과 비슷하지만 재사용에서 다르다. 피보나치에서 F(n)의 값은 변하지 않는다. F(6) = F(5) + F(4) F(7) = F(6) + F(5) 여러 곳에서 쓰이지만 F(5)의 값은 같다. 이..

1. Matrix Multiplication N*N 배열 두개를 곱하는 과정은 O(N^3)이 소요된다. 한칸만드는데 O(N) * n^2개 칸 존재 여기서도 Divide and Conquer 를 사용할 수 있다. 이렇게 되면 식이 아래와같이 된다. T(N) = 8T(n/2) = 2^3 T(n/2) = 2^6T(n/2) = ... =(2^3)^logn 2. Strassen Alg 3. Karatsuba Alg n bit 곱하기 n bit 는O(n^2)에 할 수 있다. 하지만 Karatsuba Alg를 사용하면 n에 가깝게 수행할수있다.

Convex Hull 이란 평면 좌표에서 어떤 점들이 있을 때 모든 점들을 포함 하는 가장 작은 볼록 다각형을 의미한다. (점들의 바깥에서 고무줄을 놨을 때 만들어지는 도형) 점들을 정렬하는 과정이 필요하기 때문에 Convex Hull 을 만드는 알고리즘의 시간 복잡도는 O(nlog n)보다 빠를 수 없다. 1. Count - Clock - Wise (CCW) 이 알고리즘은 세 점이 관계를 표현할 때 유용하다. A(x1,y1), B(x2,y2), C(x3,y3)가 있다고 해보자. A와 B의 기울기 + B와 C의 기울기를 가지고 회전 방향을 알 수 있다. A와 B의 기울기 > B와 C의 기울기 → 우회전 A와 B의 기울기 < B와 C의 기울기 → 좌회전 A와 B의 기울기 = B와 C의 기울기 → 한 직선 ..

1. Closest pair Closest pair은 주어진 점들 중에서 가장 가까운 쌍을 찾는 문제이다. 이 문제는 직관과 심하게 충돌하는 경우가 많다 1차원일 때는 단순하게 sorting 하면 구할 수 있고 2차원일 경우 두 점사이의 거리공식으로 구할 수 있다. 하지만 이 경우에는 O(n^2) 이 필요하다. 이 방법은 어렵지 않다. 우리의 목표는 O(nlogn)이다. 2. Divide and Conquer 먼저 이들을 절반으로 나눈다. (나누는 것은 x 를 기준으로 sorting 한 뒤 나눠주면 된다) 나눠거 각각 가장 최소거리를 구해준다. 왼쪽의 최소걸이는 DL 오른쪽의 최소거리를 DR이라고 하자. D = min(DL , DR) 라고 D를 정의하자. 중심 선으로부터 D만큼의 거리에 선을 그으면 위 ..