전체 글

문제 2295번: 세 수의 합 우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x, y, z, k가 차례로 1, 2, 3, 4가 되며, 최적해의 경우는 2, 3, 4, 5가 된다. k번째 수가 최 www.acmicpc.net 풀이 이분 탐색 문제이다. 세 수의 합을 4중 for문을 이용하면 시간복잡도가 O(N * N * N * N)으로 당연히 시간초과다. x + y + z = k x + y = k - z x + y + z = k는 x + y = k - z와 같다. 여기서 x + y를 2중 for문으로 미리 구해둔다. 미리 구한 합에서 k - z를 만족하는 값을 이분탐색으로 찾으면 시간복잡도가 O(N * N * log(N))이 므로..

문제 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 풀이 구현, 시뮬레이션 문제이다. 로봇 청소기가 후진하지 못할 때까지 while로 무한 루프를 돈다. 현재 위치의 상하좌우에 청소 가능한 칸이 있는지 확인한다. 북, 동, 남, 서 방향으로 이동할 때의 x, y의 위치 변화는 다음과 같다. // 북, 동, 남, 서 int move_x[4] = { -1, 0, 1, 0 }; int move_y[4] = { 0, 1, 0, -1 }; 청소 가능한 칸이 있다면 반시..

문제 13144번: List of Unique Numbers 길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라. www.acmicpc.net 풀이 두 포인터 문제이다. 두 포인터를 이용하여 start를 포함하며 반복되는 수가 없는 수열의 경우의 수를 계산하는 방식으로 해결한다. start부터 중복되는 수가 없을 때까지 end를 늘린다. 혹은 end가 N까지 도달하여 더 이상 수열을 늘릴 수 없을 때까지 늘린다. start에서 end까지 start를 포함하여 만들 수 있는 수열의 개수는 end - start개이다. 이 개수를 answer에 추가한다. 그 다음, start를 앞으로 늘려서 1번부터 반복한다...

혼합 현재 래스터화하는 픽셀(소위 원본 픽셀)을 후면 버퍼에 이미 래스터화되어 있는 픽셀(소위 대상 픽셀)과 섞는 혼합(blending) 기법이다. 물이나 유리 같은 반투명 물체를 렌더링할 수 있게 된다. 혼합 공식 현재 래스터화 중인 ij번째 픽셀, 즉 원본 픽셀(source pixel)에 대해 픽셀 셰이더가 출력한 색상이 Csrc라고 하자. 그리고 현재 후면 버퍼에 있는 ij번째 픽셀, 즉 대상 픽셀(destination pixel)의 색상이 Cdst라고 하자. 혼합을 적용하지 않는다면 Csrc가 Cdst를 덮어써서 후면 버퍼의 ij번째 픽셀의 새로운 색상이 된다. 그러나 혼합을 적용하면 Csrc와 Cdst를 일정한 공식에 따라 혼합해서 얻은 새로운 색상 C가 Cdst를 덮어쓰게 된다. 혼합 공식은 ..

문제 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 풀이 정렬, 두 포인터 문제이다. 먼저 용액을 두 포인터를 위해 정렬한다. 배열에서 세 용액 중 하나를 0에서부터 N - 1까지 선택한다. 선택한 용액 뒤의 배열에서 두 포인터를 실시하여, 선택한 용액과 start, end에서의 용액의 합의 절대값이 0과 가장 가까운 용액을 답으로 한다. 시간 복잡도는 O(N * N)으로 N은 5000이하이므로 시간초과는 발생하지 않는다. 코드 #include #include #include #incl..

문제 15565번: 귀여운 라이언 꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 www.acmicpc.net 풀이 두 포인터, 슬라이딩 윈도우 문제이다. 라이언의 인덱스를 따로 벡터에 저장한다. 벡터의 길이가 K보다 작은 경우 집합을 만들 수 없다. 크기가 K로 고정된 슬라이딩 윈도우 방식으로 벡터를 순회하면서 집합의 최소 크기를 탐색한다. i에서 부터 i + K - 1까지의 원소의 수는 K개이다. lion[i + K - 1] - lion[i] + 1이 lion[i]를 첫 요소로하며 크기가 K인 집합의 크기이다. 코드 #include #include #incl..

ThisClass Typedef for [UObject](API\Runtime\CoreUObject\UObject\UObject). docs.unrealengine.com 델리게이트를 Bind시, 콜백 함수를 설정한다. 이때, 클래스 이름 대신에 ThisClass를 사용하면 편리하다. GENERATED_BODY() 메크로에서 생성된다. // 위 아래 같은 의미 PlayerInputComponent->BindAxis(TEXT("MoveX"), this, &CurrentClassName::MoveX); PlayerInputComponent->BindAxis(TEXT("MoveY"), this, &ThisClass::MoveY);

문제 1484번: 다이어트 성원이는 다이어트를 시도중이다. 성원이는 정말 정말 무겁기 때문에, 저울이 부셔졌다. 성원이의 힘겨운 다이어트 시도를 보고만 있던 엔토피아는 성원이에게 새로운 저울을 선물해 주었다. www.acmicpc.net 풀이 수학, 두 포인터 문제이다. 몸무게는 0에서 시작할 수 없고, 현재 몸무게는 기억한 몸무게보다 커야 한다. 기억한 몸무게와 현재 몸무게를 두 포인터, start = 1, end = 2로 설정한다. 현재 start와 end일 때의 G를 current라고 할 때, current가 G 이하일 경우 end를 증가시켜 현재 몸무게를 더 늘려야 한다. 코드 #include #include using namespace std; int main() { ios_base::sync_..

텍스처 좌표 Direct3D는 u축이 이미지의 가로 방향이고 v축이 이미지의 세로 방향인 텍스처 좌표계를 사용한다. 텍스처를 구성하는 요소들을 텍셀(texel)이라고 부른다. 텍스처 좌표는 [0, 1]의 구간으로 정규화된 좌표성분들을 사용하는데 텍스처 이미지의 크기와는 독립적인 구간의 좌표들을 다룰 수 있게 하기 위한 것이다. 물체에 텍스처를 입히려면, 물체의 각 3차원 삼각형마다 그 삼각형에 입힐 텍스처 이미지상의 삼각형을 지정해야 한다. 정점에 지정된 텍스처 좌표들을 3차원 삼각형 면을 따라 삼각형 정점들과 동일한 s, t매개변수로 보간해서 텍스처 좌표 (u, v)를 구한다. 실제 응용에서는 여러 종류의 서로 무관한 이미지들을 하나의 커다란 텍스처 맵 (이를 텍스처 대지도(texture altas)라..

문제 17425번: 약수의 합 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net 풀이 수학, 정수론, 누적 합 문제이다. for (int i = 1; i T; // 먼저 약수들의 합을 구해야 한다. // 약수들의 합을 O(N * log(N))의 시간복잡도로 구한다. for (int i = 1; i