본문 바로가기

종만북10

비트마스크 1은 부호있는 32비트 상수취급이므로 (1 2020. 2. 5.
QUANTIZE - Quantization (dp, 전처리, 수학) https://algospot.com/judge/problem/read/QUANTIZE 최대 100개의 숫자 배열이 주어진다. 최대 10개의 대표 정수를 정해서(배열에 없는 값 허용) 오차 제곱의 합의 최소치를 구하는 문제. 오차 제곱의 합이 최소가 되도록 하려면 대표값을 각 집합의 평균으로 정해야 한다. (식을 미분하면 알 수 있다) 입력받은 배열을 오름차순 정렬하면, 인접한 두 숫자는 같은 대표값을 갖거나 다른 대표값을 갖는 집합의 경계이다. f(k,e,t) : k이후, 이번 집합의 처음 인덱스 e, 여태까지 분류한 집합의 수 t에 대해 오차 제곱의 합의 최소를 반환 배열의 각 숫자마다 두개의 선택지가 있다. 새로 집합만들어 그 집합의 첫번째 원소가 되거나 기존 집합에 포함되거나. cost(l,r) .. 2020. 2. 3.
07 - 쿼드 트리 QUADTREE 1. 흑백 그림의 string 형태 표현에 대한 규칙설명, string 형태 표현 입력으로 주어졌을 때 그림을 상하반전했을 때의 결과에 대한 string 형태 표현을 출력으로 하는 문제. 2,3. 문제에서 트리를 그림으로 굳이 보여준 것에 의문을 갖고 생각해보니 주어진 입력을 트리로 구성만 한다면 x의 자식은 항상 4개고 w,b의 자식은 항상 없으니 루트트리부터 3,4,1,2번째 자식 순회하면 ㅆ가능하다고 생각함. 4. 처음엔 재귀로 트리를 구성하려 했지만 내 수준이 너무 떨어져서인지 구현할 수 없었음. string의 최대 길이가 1000이므로 for문으로 돌려도 가능하겠다 싶어서 구현해봄. 1) 첫 인덱스부터 for문을 돌린다면 자식노드로 사용된 노드는 다음에 부모 노드로 사용될 수 있지만, 부모 노드.. 2019. 6. 30.
06 - 시계 맞추기 CLOCKSYNC 1. 시계 16개를 모두 12시가 되도록 스위치를 누르는 문제. 2,3. 스위치와 시계의 연결은 const vector linked[10] = { //[switch][clock]형태 {0,1,2}, {3,7,9,11}, {4,10,14,15}, {0,4,5,6,7}, {6,7,8,10,12}, {0,2,14,15}, {3,14,15}, {4,5,7,14,15}, {1,2,3,4,5}, {3,4,5,9,13} }; 이렇게 함. 스위치를 4번 이상 누르는 경우가 없다. 스위치를 누르는 순서는 상관이 없다 (이걸 생각을 못해서 처음에 재귀를 못짬.) -> 스위치 누르는 순서를 0번-9번으로 강제함. 기저: 누를 스위치가 10번(존재하지않음)일 때 시계들이 정렬돼 있다면 0, 아니면 큰 수 반환 5. #incl.. 2019. 6. 27.

티스토리툴바