컴공에서 살아남기

가장 긴 증가하는 부분 수열 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000) 출력 첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다. 예제 입력 1 6 10 20 10 30 20 50 예제 출력 1 4 📌 LIS 해당 문제는 LIS 수열을 구하는 문제이다. LIS는 Longest Increasing Su..

경쟁적 전염 문제 NxN 크기의 시험관이 있다. 시험관은 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 바이러스가 존재할 수 있다. 모든 바이러스는 1번부터 K번까지의 바이러스 종류 중 하나에 속한다. 시험관에 존재하는 모든 바이러스는 1초마다 상, 하, 좌, 우의 방향으로 증식해 나간다. 단, 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다. 또한 증식 과정에서 특정한 칸에 이미 어떠한 바이러스가 존재한다면, 그 곳에는 다른 바이러스가 들어갈 수 없다. 시험관의 크기와 바이러스의 위치 정보가 주어졌을 때, S초가 지난 후에 (X,Y)에 존재하는 바이러스의 종류를 출력하는 프로그램을 작성하시오. 만약 S초가 지난 후에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다. 이 때 X와 Y..

다리 놓기 문제 재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M) 재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때..

이항 계수 1 문제 자연수 N과 정수 K가 주어졌을 때 이항 계수(N/K)를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 0 ≤ K ≤ N) 출력 이항계수(N/K)를 출력한다. 예제 입력 1 5 2 예제 출력 1 10 📌이항계수 (Binomial Coefficient) 이항계수란 조합론에서 등장하는 개념으로, 주어진 크기 집합에서 원하는 개수만큼 순서없이 뽑을 수 있는 조합의 가짓수를 말한다. 평소 알고있던 nCk 를 말하는 것이다! 2를 상징하는 '이항'이라는 단어가 붙은 이유는 '뽑거나, 안뽑거나'의 두 가지 선택지가 존재하기 때문이다. 전체 집합에서 원소의 개수 n에 대해 k개의 아이템을 뽑는 이항계수(조합의 수)는 아래와 같은 공식을 갖는다. 해당 공..

Enemy AI의 공격(Action) 기능을 구현해보았다. 가장 먼저, 공격하기 위해선 무기를 장착해야 하기 때문에 Task_Equip 클래스를 작성하였다. 💻 CBTTaskNode_Equip Equip ExecuteTask 에서는 EnemyAI가 가지고 있는 Weapon Component를 참조하여, SetSwordMode를 적용시켜 주었다. Tick 함수에서는 Enemy_AI의 State Component가 Idle 모드인 경우 Equip Task를 성공으로 종료시키도록 하였다. Sword 모드의 장착이 끝나면 자연스럽게 Idle 모드로 전환되기 때문이다. ❌ Equip 발동 시 문제점 : Weapon Asset 공유 문제 Equip 발동 시 나타나는 문제점이 있는데, 바로 두명의 Enemy와 Pla..

이전 시간에 구현해두었던 Enemy AI의 추적(Patrol) 기능에 한 가지 문제점이 발생하였다. 한 명의 Enemy만 추적을 수행하면 아무런 문제가 없는 듯 보이지만, 두 명의 Enemy를 각각 배치하고, 서로 다른 Patrol Path 액터(Spline Component가 포함된 경로 액터)를 지정해주면 바로 문제점이 나타났다. 원하던 기능은 각각의 Enemy가 할당된 Spline Component를 따라 순찰하는것이었지만, 실제로는 두 Enemy가 똑같은 SplineComponent를 순찰하며 서로에게 할당된 Spline을 번갈아가며 랜덤하고 이상하게 순찰이 진행되었다. 문제점은, 작성한 Patrol Task 클래스에서 이동할 위치 변수인 FVector Location 값이 두 Enemy에게 공유..

골드바흐 파티션 문제 골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다. 짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 두 소수의 순서만 다른 것은 같은 파티션이다. 입력 첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다. 출력 각각의 테스트 케이스마다 골드바흐 파티션의 수를 출력한다. 예제 입력 1 5 6 8 10 12 100 예제 출력 1 1 1 2 1 6 #include #include #include using namespace std; const int Max..

소수 구하기 문제 M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. 출력 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다. 예제 입력 1 3 16 예제 출력 1 3 5 7 11 13 특정 범위 안에 소수를 구하는 문제로, sqrt를 이용해 문제를 해결하는 방법과 에라토스테네스의 채를 이용해 해결하는 두 가지 방법으로 풀이해보았다. ✔️ sqrt 이용 #include #include #include using namespace std; bool IsPrime(int n) { if (n M >> N; for(int i = M; i..

정수 삼각형 문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다. 입력 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. 출력 첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다..

🚶🏻Animation 실행 이전에는 애니메이션의 한 프레임, 한 프레임을 출력했다면 이젠 존재하는 프레임을 자동으로 전부 출력하여 애니메이션을 실행시키도록 구현하였다. 애니메이션의 시간 비율을 만들어서 비율이 1을 넘어가는 순간 다음 Frame을 출력하도록 만들었다. 그러나 이렇게 현재 프레임만을 출력하면 언뜻볼 때 괜찮아보이지만, 속도를 0.1로 늦춰 재생하면 한가지 문제점이 발생한다. 직접 확인을 위해 현재 프레임인 CurrFrame의 애니메이션을 출력한 결과는 아래와 같다. 느리게 재생되는 애니메이션을 보면, 현재 프레임 프레임이 뚝뚝 끊겨서 출력되는 것을 볼 수 있었다. 그러나, 애니메이션은 동작 사이사이가 부드럽게 연결되어야 퀄리티 좋은 게임을 만들어낼 수 있다. 🏃🏻Lerp Animation ..

🚩 SRV 생성하기 이전에 작성해왔던 Create Texture 함수에 SRV를 생성하는 코드를 추가해주었다. 만들어놨던 Texture2D를 이용해 ResourceView를 생성하고, Model Mesh의 TransformSRV로 지정해주었다. Model Mesh에는 이러한 애니메이션 TransformSRV를 저장하기 위한 변수를 각각 선언해주었고, Shader에 생성해둔 Texture2DArray인 TransformsMap에 연결해준 뒤 Render해주었다. 📄 45_Animation.fx #include "00_Global.fx" float3 Direction = float3(-1, -1, +1); struct VertexModel { float4 Position : Position; float2 U..

스도쿠 문제 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다. 나머지 빈 칸을 채우는 방식은 다음과 같다. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다. 또한 위쪽 가운데 위치한 3x3 정사..