문제 링크 1238번: 파티 풀이 인접 리스트들에 대해 각 정점에서 목표 정점까지의 최단 거리를 구하는 다익스트라 문제 우선 순위 큐로 풀어야하나 싶은데 큐로 해도 풀리긴 함 값을 입력 받으며 인접 리스트를 만들어줌 func에서 현재 정점인 cur에서 각 노드까지의 최단 거리를 구해준다. 거리를 갱신해줄 dist를 무한대로 만들어주고 시작 노드는 0 큐가 빌 때까지 반복하는데, 현재 노드인 curN에서 연결된 정점을 보며 각 노드까지 거리가 최소로 갱신될 때만 dist 갱신과 q에 추가해준다. 그렇게 현재 정점에서 각 노드까지의 최소 거리가 구해진다. xdist는 집으로 각자 돌아갈 때인데, 한 번만 구해주면 각 노드까지의 최소 거리가 만들어진다. xdist[i]와 cdist[i]를 더한 값이 가장 큰 ..
문제 링크 1138번: 한 줄로 서기 풀이 answer 벡터를 0으로 초기화한다. 작은 키부터 자리를 찾아가는데, 이렇게 하게 되면 answer의 0은 자기보다 큰 키가 될 것이다.(자기 이후에 찾게 될테니) answer를 돌면서 자기보다 큰 키면(answer[j] == 0) zeroCnt를 하나 더해준다. 그렇게 zeroCnt가 arr[i]와 같아지게 되면 해당 자리의 다음 자리에 넣어주면 된다. 그 자리가 비어있지 않다면(0이 아니라면) 빈 자리를 찾아 넣어준다. answer를 출력한다. 코드 #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector..
'이득우의 게임 수학' 책을 보고 정리한 글입니다. [7장] 벡터의 내적 (Dot product) 같은 차원의 벡터 두개를 스칼라로 만들어내는 연산
문제 링크 16507번: 어두운 건 무서워 풀이 누적합 문제 사진의 밝기를 입력받으며, 각 행마다 누적합을 구한다. func를 통해 영역의 사진 밝기 평균을 구하는데, 각 행열은 1부터 시작하므로 -1 해준다. r1부터 r2까지 행마다 c2에서 c1-1의 값을 빼주면 해당 행의 영역 값을 구할 수 있다. c1이 0이라면 c1-1에서 에러가 나니까 예외 처리를 해준다. 사각형의 영역값으로 sum을 나눠주면 된다. 코드 #include #include using namespace std; int func(vector &arr, int r1, int c1, int r2, int c2) { int sum = 0; for (int i = r1; i > r >> c >> q; vector arr(r, vector(..
'이득우의 게임 수학' 책을 보고 정리한 포스팅입니다. [6장] 이동 변환을 위한 아핀 공간 2 × 2 정방 행렬의 곱셈으로 2차원 평면에서의 이동 구현 X 임의의 벡터 (x,y)를 (a,b)만큼 이동시키는 기능 → 행렬의 덧셈으로 하지만 행렬 곱을 만족하는 정방행렬 A는 존재 X 표준기저벡터의 원점 이동 변환이 행렬이 되기 위해서는 선형성을 만족해야하는데, 선형성이 되기 위해서 기저벡터는 원점에서부터 출발해야 함 차원을 늘리면 구현이 가능 → 두 개의 차원은 물체 표현, 한 개의 차원은 선형 변환을 위한 원점과의 연결고리 전단 변환의 성질을 통해 y값을 1로 적용하면 선형 변환시 다음과 같은 수식이 성립 → 이를 통해 1차원의 이동 변환을 할 수 있음 → 마찬가지로 2차원의 이동 변환을 위해서는? 3차..
문제 링크 6588번: 골드바흐의 추측 풀이 소수 문제인데 시간 초과로 꽤나 머리 아팠던 문제 먼저 최대 숫자인 1000000까지 소수를 체크하기 위한 배열을 정의한다. 소수가 아닐 경우 true이다. 에라토스테네스의 체를 통해 소수인지 체크한다. 첫번째 반목문에서 1000000의 제곱근까지만 구해도 내부 반목문에서 해당 숫자의 제곱부터 배수를 체크할 것이다. sosu[i]가 true라면 소수가 아닌 것으로 이미 체크가 된 것이므로 continue 2번이 해당되지 않으면 해당 숫자는 소수이고, 그 소수의 제곱부터 배수들을 소수가 아닌 것으로 체크한다. 왜 배수를 체크하는데 제곱부터 구하냐면, 해당 수보다 작은 숫자의 배수는 그 전 숫자들에서 구했을 것이므로 중복된다. 예를 들어 j가 5라면 배수인 2부터..
[KUOCW] 한정현 컴퓨터그래픽스를 듣고 정리한 포스팅입니다. 행렬과 벡터 (Matrices and Vector) 행렬의 곱 m×n 행렬이 있을 때, m=n이라면 정사각 행렬 A 행렬 l×m과 B 행렬 m×n은 A의 열 개수와 B의 행 개수가 같아 곱할 수 있음 => l×n 행렬 2D 벡터 (x,y), 3D 벡터 (x,y,z) => row vector (행 벡터) column vector (열 벡터)로도 표현 가능 열벡터 (Column Vector)와 행벡터 (Row Vector), 전치 행렬 (Transpose) 벡터를 행렬로 바꾸어 연산을 한다면 다음과 같음 전치 행렬(Transpose)은 다음과 같음 그래서 벡터의 전치 행렬과, 행렬의 전치 행렬을 곱한 값은 다음과 같다. 열벡터 = 행벡터 열벡터..
[KUOCW] 한정현 컴퓨터그래픽스 강의를 듣고 정리한 포스팅입니다. 컴퓨터 그래픽스(Computer Graphics)란? 3차원으로 표현된 물체를 입력해 2차원 영상(프레임)으로 출력하는 작업 실시간 그래픽스 : 게임, VR/AR에서 사용, 30fps 이상 만들어냄 비실시간 그래픽스 : 영화 특수효과, 사실적, 많은 연산 컴퓨터 그래픽스 5단계 Modeling → Rigging→ Animation→ Rendering → Post Processing 런타임에 프로그램이 자동 실행 모델링 (Modeling) 모델(폴리곤 메시, 텍스쳐)을 만드는 과정 모델 : 컴퓨터가 이해,처리하도록 물체를 표현 모델링 기법 : 폴리곤 메시, 대부분 삼각형 메시 사용 폴리곤 메시에 입힐 이미지인 텍스쳐를 만듦 리깅 (Rig..
