문제 https://school.programmers.co.kr/learn/courses/30/lessons/17683 풀이 주어진 곡과 시간 정보 string을 분리하여 조건대로 나누었다. 재생 시간을 분으로 치환하여 비교할 문자를 찾고, find를 통해 일치 여부를 판단한다. #include <string> #include &...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/154540 풀이 X와 숫자로 이루어진 2차원 배열을 그리드 형태로 변환, 지도를 순회한다. 방문 여부를 체크하면서 숫자로 이루어진 연결 요소(Connected Component) 별 크기를 측정 return한다. #include &...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/67258 풀이 진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾기 위해 주어진 배열을 순서대로 map에 넣고, 모든 보석의 개수가 1개 이상인 경우 해당 구간의 길이를 저장한다. 추가적으로 모든 보석의 개수가...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/86971 풀이 전력망 네트워크를 2개로 분할하고, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추기 위해 각각의 배열 원소를 제외하고 BFS를 통해 나뉘어진 송전탑 개수를 카운트한다. 그리고 이중 절댓값이 가장 낮은 값을...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12899 풀이 주어진 자연수를 1, 2, 4로 이루어진 3진법으로 변환하는 문제이다. 다만 기존 3진법과 달리 3대신 4가 포함되어 있으므로, 변환 시 3으로 나누되, 나머지가 없는 숫자는 ‘4’를 사용한다. #include &lt...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12971 풀이 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대인, 최적해를 구하는 문제이므로 DP를 활용하여 풀이한다. 다만, 스티커 한 장을 뜯어내면 양쪽으로 인접해있는 스티커는 찢어져서 사용할 수 없게...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/178870 풀이 비 내림차순으로 정렬된 수열에서 주어진 조건을 충족하는 부분 수열을 찾는 문제로, 투 포인터를 사용하여 풀이하였다. 부분 수열의 합이 k이면서 제일 짧고, 제일 앞에 있는 수열을 찾기 위해 두 포인터를 사용, 두 포인...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42883 풀이 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하기 위해 탐욕법을 사용하여 풀이한다. 숫자 제거 후 남은 숫자들의 순서대로 가장 큰 숫자가 정해지므로, 앞자리를 큰 수로 유지하기 위해 k-1 개...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/60057 풀이 문자열을 나눠 공통된 문자열을 찾는 문제로, 문자열을 추출하고 남은 문자열과 비교하여 최소 길이를 탐색한다. 다만, 나누는 문자열의 길이가 1/2 보다 크면 압축하는 의미가 없어, 탐색에 제한을 두고, 비교 문자열이 연...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/62048 풀이 격자 맵에 선을 그었을 때, 선에 해당하는 사각형의 개수를 제외한 격자의 개수를 구하는 문제로, 선은 그림에서 선이 정확하게 꼭지점에 들어갔을 때 1개의 사각형을, 이외에는 2개의 사각형을 못쓰게 한다. 따라서 정확히 ...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/43164 풀이 #pragma once #include <iostream> #include <string> #include <vector> #include <string> #include &...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42861 풀이 노드 간 연결 비용을 최소로 하여 모든 노드와 연결해야하는 문제로, 크루스칼 알고리즘을 통해 해결하였다. 크루스칼 알고리즘은 최소 신장 트리를 구하는 알고리즘으로, 가중치의 오름차순으로 정렬해 놓은 뒤, 사이클을 형성하...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/49189 풀이 1번 노드와 가장 먼 거리의 노드를 찾는 문제로, bfs를 통해 거리를 측정하고, 가장 큰 값을 가지는 원소의 개수를 리턴한다. #include <string> #include <vector> #...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12936 풀이 제시된 배열 원소들을 순열로 나열할 때, k번째 순열을 구하는 문제이다. 단순하게 모든 순열을 구하면 제한 조건이 20까지 이므로, 시간 초과가 발생한다. 따라서 순열의 규칙을 활용, 원소가 등장할 순서를 계산하여 k번...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/77485 풀이 주어진 2차원 배열을 그리드 형태로 구현하고, 주어진 값 주변 원소를 이동하는 문제으로, 단순하게 주어진 방식을 구현하여 정답을 구하면 된다. #include <string> #include <vect...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/60058 풀이 주어진 방식을 구현하여 정답을 구하는 문제로, stack을 활용하여 비교한다. #include <string> #include <vector> #include <map> #include...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/64062 풀이 주어진 징검다리 배열에서 각 원소 값을 1 빼는 것을 반복할 때, 0이 k개 이상 연속되지 않는 최대 횟수를 구하는 문제이다. 단순하게 각 원소 값들을 빼주는 것은 최대 원소 값 200,000,000 이하, 배열의 크기...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12978 풀이 마을 간 연결 정보와 거리를 입력 받아 1번 마을과 k이하의 거리를 가진 마을들을 찾는 문제이다. 다익스트라 알고리즘을 토대로 마을 별 최소 거리를 측정, k이하의 거리를 가진 마을의 개수를 return한다. #inc...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/135807 풀이 #include <iostream> #include <string> #include <vector> #include <string> #include <stack>...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/148653 풀이 #include <iostream> #include <string> #include <vector> #include <string> #include <stack>...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/152996 풀이 #include <iostream> #include <string> #include <vector> #include <string> #include <stack>...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/155651 풀이 대실 시간이 겹치는 시간을 탐색하기 위해 손님 별 시간을 정리하고, 이를 정렬하여 필요한 방의 개수를 구하였다. #include <string> #include <vector> #include ...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/72411 풀이 #include <iostream> #include <string> #include <vector> #include <map> #include <algorithm> ...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/64064 풀이 #include <string> #include <vector> #include <iostream> #include <set> #include <algorithm> ...

분석 특수 블록이 배치되지 않은 서로 다른 크기의 맵에서 목표달성에 필요한 스왑 횟수 측정 후, 자동플레이를 통한 특수 블록 미배치 맵의 스왑매치 경우의 수에 따른 평균 스왑 횟수 측정 특수 블록의 배치에 따른 스왑 횟수 증가량을 측정하였다. 특수 블록의 종류별 맵 크기와 스왑매치 경우의 수 감소에 따른 평균 스왑 횟수 측정 ...

분석 그러나 이러한 유전 알고리즘을 통한 자동 플레이를 진행 시, 하나의 맵을 생성하는데 많은 시간을 투자하게 되어, 실시간으로 맵을 생성하기 어렵다. 따라서 이러한 난이도 측정 과정을 블록 배치를 통해 측정한다. 스왑을 통해 매치를 발생시키기 위해서는 매치 발생 조건, 수직 혹은 수평으로 같은 종류 일반 블록 3개 연속 배치를 충족해야 한다. ...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/68645 풀이 밑변의 길이와 높이가 n인 삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후, 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 return하는 문제로, 단순하게 각 배열의 맨 앞자리, 마...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42579 풀이 장르와 고유 번호로 구분된 노래를 재생 순으로 정렬하여 장르 별 가장 많이 재생된 노래 2개를 선택하는 문제로, 주어진 배열을 정렬하여 원하는 값을 retrun한다. 정렬은 장르 별 재생순, 같은 장르의 노래 별 재생 ...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/118667 풀이 큐의 특성을 활용하여 주어진 각 큐의 원소 합이 같게 만드는 문제이다. 원소 합이 같게하기 위해 더 높은 원소 합을 가진 큐가 다른 큐에게 원소를 전달하는 것을 반복하여 문제를 푼다. 다만 가장 큰 원소와 다른 모든 ...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/68936 풀이 주어진 2차원 정수 배열을 쿼드 트리와 같은 방식으로 압축하는 문제로, 주어진 배열을 균일하게 압축하기 위해, 같은 숫자로 이루어져 있지 않은 2차원 정수 배열의 행과 열을 2로 나눠 4개의 2차원 정수 배열을 만든다....

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42583 풀이 모든 트럭이 일차선 다리를 건너려면 최소 몇 초가 걸리는지 알아내는 문제로, 한 번에 다리를 건널 수 있는 무게가 제한되어있다. 따라서 queue에 트럭의 무게와 시간을 넣고 시간을 측정하여 다음 트럭의 무게와 현재 다...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42839 풀이 종이 조각을 통해 만들 수 있는 소수의 개수를 구하는 문제로, 만들 수 있는 모든 숫자를 DFS를 통해 만들고, 찾은 소수의 배수를 지워나가는 방식인 에라토스테네스의 체를 통해 일정 범위 내의 모든 소수를 구해, DFS...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42746 풀이 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 찾는 문제로, 두 수를 이어 붙였을 때 더 큰 수 나오도록 sort하여 최댓값을 return한다. #include <string&...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12979 풀이 현재 기지국이 설치된 아파트의 번호가 담긴 1차원 배열 stations, 전파의 도달 거리 W가 매개변수로 주어질 때, 모든 아파트에 전파를 전달하기 위해 증설해야 할 기지국 개수의 최솟값을 구하는 문제로, 단순하게 완...

분석 클리어에 필요한 스왑 횟수에 따른 난이도 설정하였으나, 일반 블록의 랜덤성으로 인해 같은 레벨을 반복하더라도 각각의 클리어에 필요한 스왑 횟수가 다르다. 따라서 이를 반복하여 모평균을 추정하고자 한다. 이러한 추정을 위해 적절한 반복 횟수가 필요하다. 해당 맵에서 반복 플레이 했을 때 아래와 같은 결과를 확인할 수 있다. 반...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/77885 풀이 양의 정수 x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수를 구하는 문제로, 짝수는 항상 오른쪽 비트가 0이므로 1을 더해주면 된다. 그러나 홀수의 경우 올림을 해야 하므로 1을 더하면 전혀 다른 수가...

분석 ※ 그리드 크기 별 예측 그래프 ※ 타겟 개수 별 예측 그래프 ※ 특수 블록 배치 별 예측 그래프

문제 Match-3 게임에서 유전 알고리즘을 통한 자동 맵 생성 구현을 위해 유전자로 맵의 크기와 같은 배열을 사용, 배열 값에 따라 각 맵에 위치한 블록의 종류를 정한다. 이를 통해 맵 생성 시 초기 블록이 배치되고, 게임이 진행됨에 따라 파괴, 생성 과정이 진행된다. internal GridObject SetObject(GridObject ...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42884 풀이 고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는 지를 구하는 문제로, 탐욕법을 활용, 진출 위치를 기준으로...

개요 Fitness를 사용하는 대신, 선택 기준을 사용. 대칭적이고 좋은 디자인을 가진 레벨이 이미 다수 존재할 때, 이를 선택 기준으로 삼아 기존 맵들과는 다른 새로운 맵을 생성한다. 그리드의 대칭을 유지하기 위해 5 종류의 크로스오버 연산을 사용하여 그리드를 분할하고 해당 부분에서 연산을 수행. 그리드의 중간을 세로 혹은 가로...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12900 풀이 가로 길이가 2이고 세로의 길이가 1인 직사각형 모양의 타일을 N X 2 사각형에 배치할 때, 배치할 수 있는 경우의 수를 구하는 문제로, 다음 사이즈의 경우의 수가 이전 사이즈의 경우의 수에 영향을 받으므로 DP를 활...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12987 풀이 배열 A의 원소보다 높은 값을 배열 B에서 제시하기 위해 sort하여 비교하면 되고, 본인은 우선 순위 큐를 활용하여 풀이했다. #include <string> #include <vector> #...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/154538 풀이 자연수 x를 y로 변환하기 위한 연산을 진행할 때, 최소 연산 횟수를 구하는 문제로, DP를 활용하여 연산에 따라 나올 수 있는 경우의 수를 계산한다. 먼저, fill로 dp 배열 값을 최대 값으로 정하고 주어진 연산...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/17679 풀이 match-3 게임과 같은 방식으로 일정 이상의 같은 블록이 일정 배치를 가질 때, 이를 파괴하고 빈 칸을 파괴된 블록 위에 위치한 블록으로 채우는 방식이다. 따라서 파괴 가능 배치 조건 2×2를 이루는 같은 블록 배치...

분석 Match-3 게임에서의 난이도는 레벨 성공 확률이라 할 수 있다. 레벨 제한 조건이 스왑 횟수인 경우, 목표 달성에 사용한 스왑 횟수가 제한 조건에 가까울수록 낮은 성공 확률을 보인다. 따라서 성공 확률이 낮을수록 더 어려운 난이도의 레벨로 판단할 수 있다. 그러나 게임 플레이 시, 같은 레벨을 반복하더라도 각각 목표달성에 사용한 스왑 횟...

분석 자동 플레이 시 게임이 종료되면, 사용자가 클리어에 필요했던 스왑 횟수가 나온다. 난이도 측정에 필요한 스왑 횟수를 저장하고, 반복 횟수에 따른 스왑 횟수의 평균을 구하기 위해, 이를 엑셀 파일로 저장하는 코드를 구현했다. List<int> swapCntContainer = new List<int>(); privat...

문제 타겟 우선 알고리즘을 통한 자동 플레이를 구현 시, 이러한 문제가 적용되지 않는 문제가 발생하였다. 해결 이러한 문제는 기존 asset의 자동 플레이 형태가 게임이 끝난 후 발생하는 것으로 이루어져 생기는 문제로, Asset의 AutoPlay는 설정된 target의 개수를 사용자가 제거했을 때 score bonus의 개념으로 남은 이동 ...

분석 보통 Match-3 게임은 클리어 조건 만족 시, 남은 스왑 횟수만큼 점수를 추가로 부여하는 경우가 많다. 이러한 경우 중 남은 스왑 횟수만큼 임의적으로 더 스왑시켜 추가 점수를 주는 경우가 있는데, 현재 에셋에서 이러한 방식을 통해 추가점수를 부여하므로, 이를 통해 자동 플레이를 구현하고자 한다. 게임의 상태를 판단하는 update()에서...

분석 Match-3 게임 맵을 자동 생성하기 위해, 유전 알고리즘을 사용한다. 유전자를 통한 맵 구성을 사용, 유전자와 같은 크기의 그리드 형태의 맵 생성한다. int genes$[col*row]$ : 0과 1로 구성된 1차원 정수 배열. 유전자 배열의 각 index는 맵의 index와 일치, 각 index의 배열 값은 맵의 i...

분석 특수 블록을 배치하여 게임 진행 시, 일부 셀 값에서 null이 발생, 게임이 진행되지 않는 경우가 발생했다. 이를 확인해본 결과, 아래 그림과 같은 형태로 특수 블록이 배치되었을 때, 빈 셀을 채우지 못해 해당 셀들이 블록이 없어 발생한 것으로 확인됬다. 해결 따라서 이를 해결하기 위해 각 셀 간의 연결 여부를 판단한...

분석 Match-3 게임은 퍼즐 게임의 한 유형으로, 사용자가 여러 블록으로 구성된 맵에서 부여된 목표를 제한조건 내에 달성해야 하는 게임이다. 사용자는 블록 이동, 스왑(swap)을 통해 3개 이상의 동일 종류의 블록이 수직 혹은 수평 방향으로 연속 배치된 형태, 매치(match)를 이루고 매치를 이룬 블록들이 파괴되는 특성을 활용, 게임을 진행...

개요 gym match3는 강화 학습을 위한 환경으로, Match-3 보드 복제를 통해 새로운 레벨 생성 1. Console command Import Match3Env 및 선언 활성화 함수 호출 observation, reward, done, info = env.step(env.action_space.sample()...

필기

문제 https://school.programmers.co.kr/learn/courses/30/lessons/131704 풀이 원하는 순서로 배열의 배치를 바꾸는 문제로, 배치를 바꾸기 위해 앞 뒤로 이동이 가능하지만 입구 외에 다른 면이 막혀 있어서 맨 앞의 상자만 뺄 수 있는 보조 컨테이너 벨트, 즉 stack을 활용한 문제이다. #in...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/17686 풀이 주어진 문자열을 조건에 맞게 정렬하는 문제로, 문자열을 HEAD, NUMBER, TAIL로 나눠 정렬 기준에 맞게 정렬을 구현했다. #include <string> #include <vector>...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42898 풀이 최단 경로를 탐색하는 DP 문제로, (1, 1)에서 (m, n)로 이어지는 최소 거리를 구하면서 제시된 위치를 피해야 한다. 따라서 주어진 회피 위치에 음수 값을 지정, 해당 위치를 지나지 않게 한다. 그리고 오른쪽과 ...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42888 풀이 주어진 문자열을 문자를 출력하는 문제로, 유저 아이디와 닉네임을 저장하고, 중복 닉네임과 닉네임 변경을 유저 아이디와 매치하기 위해 map을 활용하여 채팅방을 구현하였다. #include <string> #...

구현 원래 샘플링은 픽셀 셰이더에서 픽셀 당 한 번 시도한다. 그러나 멀티 샘플링의 경우, 지정 횟수 만큼의 샘플링을 시도하는 방식이다. 따라서 멀티 샘플링을 사용하는 경우 MSAA buffer가 생성되는데, 이를 활용하여 서로 다른 여러 이미지를 출력할 수 있다. 그리고 이러한 방법은 기존 a buffer를 사용하는 것보다 높은 성능을 보여주기...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12938 풀이 집합의 원소의 개수 n과 모든 원소들의 합 s가 매개변수로 주어졌을 때, 각 원소의 합이 S가 되며 원소의 곱이 최대가 되는 집합을 구하는 문제로, 원소 곱을 최대로 하기 위해서는 원소들 간 비슷한 크기를 지녀야 하므로...

정리 언어모델 : 단어 나열에 확률을 부여하여, 얼마나 자연스러운지 확률로 평가 CBOW 모델을 언어모델로 사용시, 단어의 순서는 지키나, 맥락의 크기에 비례해 매개변수의 개수가 증가 RNN :  순환신경망으로, 데이터가 순환하면서 정보가 끊임없이 갱신되고, 과거 정보를 기억한다.(확장성)  출력이 2개로 분기하여 하나는 다시 입력으로(둘은 ...

문제 Stencil Routed Rendering을 통한 Depth Peeling을 진행 시, 아래와 같이 일부 폴리곤이 렌더링되지 않는 현상이 발생한다. 해결 이는 색상 샘플 방식 차이로 발생하는 것으로, DirectX3D의 버전에 따라 샘플 방식이 달라, 발생한다. Polygon이 픽셀의 중앙을 cover하는 ...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/49993 풀이 주어진 문자열을 충족하는 주어진 배열 원소를 찾는 문제로, 문자열이 배열 원소에 포함되어 있는 지를 확인해야 한다. 단, 문자열의 부분 집합 중 처음 문자부터 순서대로 문자들을 가지는 경우의 수 (ex) ABC -&gt...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12913 풀이 경로에 따른 최댓값을 찾는 문제로, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 존재한다. 따라서 메모이제이션을 통해 지난 행과 같은 행의 땅을 밟지 않으면서 가질 수 있는 최댓값을 저장하여 경로에 따른 최댓값을 찾는...

문제 모션 벡터 탐색에 실패한 픽셀을 Edge-Avoiding À-Trous Filter에서 edge로 판단, 디노이징 효과가 제대로 되지 않는 문제가 발생했다. static const float Gaussiankernel[25] = { 0.00390625f, 0.015625f, 0.0234375f, 0.015625f, ...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/132265 풀이 같은 토핑(원소 값)의 개수에 상관없이 동일한 가짓수로 롤케이크을 자르는 경우의 수를 찾는 문제로, map을 활용해 토핑의 종류의 개수가 같은 경우의 수를 탐색한다. 롤케이크는 한 번만 자르므로 map 2개를 활용, ...

정리 퍼셉트론(Perceptron) 다수의 신호를 입력받아, 하나의 신호를 출력(뉴런과 비슷한 구조) ※ AND, OR, NAND는 단층 퍼셉트론으로 표현할 수 있으나 XOR 같은 경우는 불가능, 단층 퍼셉트론은 직선형 영역만 표현할 수 있고, 다층 퍼셉트론은 비선형 영역도 표현 ※ 신경망은 크게 입력층, 은닉층, 출력층 이렇게 3개...

풀이 연습

문제 https://school.programmers.co.kr/learn/courses/30/lessons/92341 풀이 차량이 들어오고(입차) 나간(출차) 기록에 따라 차량 별 주차 요금을 측정하는 문제로, 시간 측정을 위해 모든 시를 분으로 환산, 요금을 측정하였다. 그리고 조건으로, 차량 번호 순으로 정렬하여 return해야 하기 때...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42584 풀이 배열 prices의 원소 값이 이전 값보다 낮아질 때의 시간을 측정하는 문제로, 배열의 원소 별 시간은 각 index + 1이라고 할 수 있으며, 원소 별로 다음 원소가 비교 값보다 낮아지는 index의 위치를 찾아 거...

개요 1. Stencil Routed K-Buffer 스텐실 라우팅을 사용, 지오메트리 패스당 픽셀당 8개의 조각 레이어를 캡처 픽셀당 최대 16개의 조각이 2개의 지오메트리 패스에서 래스터화 순서로 캡처 fullscreen shader pass는 bitonic 정렬을 사용하여 픽셀당 16개의 조각을 정렬 ...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/49994 풀이 주어진 경로에 따라 이동하면서 중복된 길의 개수를 제외한 방문한 길의 개수를 구하는 문제로, 방문할 위치 뿐만 아니라 현재 위치 또한 고려해야 한다. 따라서 이전 위치와 방문할 위치 좌표를 map을 통해 저장, 주어진 ...

개요 1. 개요 멀티샘플 텍스처를 사용하여 픽셀당 조각 벡터를 저장함으로써 GPU 가속 A-버퍼를 구현하기 위한 스텐실 라우팅 알고리즘 모든 조각들은 래스터화 순서에 따라 픽셀별로 캡처 전체 화면 셰이더 패스는 bitonic sort을 사용하여 조각을 정렬(이때 정렬된 프래그먼트를 임의로 블렌딩하여 차수 독립 투명도 또는 계층화된 깊이...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/43163 풀이 두 개의 단어 begin, target을 한 번에 한 개의 알파벳만 바꿔 주어진 문자열 집합 words의 원소 중 하나로 바꾸는 것을 반복하여 같은 문자로 변환하는 과정 중 가장 짧은 변환 과정을 찾는 문제이다. 따라서...

문제 레퍼런스와 depthpeeling 간 비교를 위해 많은 삼각형의 모델들과 조명 효과 등을 통해 높은 성능이 요구되는 환경에서 이를 비교하고자 한다. 그러나 조명이 적절하지 않게 적용되는 경우가 발생한다. 해결 이는 다른 부분에서는 적절한 조명 효과가 적용되었으나, 일부분에서 발생하였는데, 특히 일부 텍스처에서 발생하였...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42626 풀이 주어진 배열의 모든 원소가 K 이상이 될 때까지 반복하여 연산을 진행 시, 이를 위해 필요한 최소 횟수를 구하는 문제이다. 따라서 배열을 priority_queue를 통해 오름차순으로 정렬하고 K 이하의 원소 두 개를 ...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/154539 풀이 배열 의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 찾는 문제로, 순서대로 값을 비교하여 뒷 큰수를 찾는다. #include <string> #include ...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/1844 풀이 게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return하는 문제이다. 캐릭터의 이동을 구현하고 bfs를 통해 최소 이동 횟수를 구한다. ...

목표 아래 과정을 통해 모션 블러 이미지를 생성한다. 구현 기존 Efficient motion blur through motion vector sharing의 모션 블러 생성 방법에서 여러 깊이 별 레이어를 추가하여 모션블러 이미지를 생성한다. void DepthPeeling(ID3D11Device* pd3dDevice, ID3D...

문제 레퍼런스인 accumulation과 depthpeeling의 속도 차이를 비교했을 때, 아래와 같은 결과가 나왔다. 이는 그냥 단순히 여러 번 이미지를 그리는 것보다 느리므로, depthpeeling 알고리즘에 문제가 있다는 결론이므로, 이를 해결하기 위해 알고리즘을 수정했다. 해결 기존 알고리즘에서 아래와 같이 depth...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12927 풀이 우선순위 큐를 사용하는 문제로, 숫자가 클 수록 제곱 값이 커지므로, 가장 큰 수를 1 빼주는 것을 n번 반복한다. #include <string> #include <vector> #include...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/84512 풀이 DFS 횟수를 측정하는 문제로, 원하는 단어를 찾을 때까지 재귀를 통해 횟수를 측정하고, 찾았을 때 이를 return한다. #include <string> #include <vector> usi...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/17687 풀이 진법 n, 미리 구할 숫자의 갯수 t, 게임에 참가하는 인원 m, 튜브의 순서 p를 입력받아, 최대 나올 수 있는 숫자 t x m 만큼의 n진법 숫자를 구하고, p에 해당하는 문자를 return한다. #include ...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/17684 풀이 LZW 압축 과정을 그대로 구현하는 문제로, 길이가 1인 모든 단어를 포함하도록 사전 초기화. 사전에서 현재 입력과 일치하는 가장 긴 문자열 w를 찾는다. w에 대한 색인 번호를 answer에 담는다. ...

문제 앞서, 자신에게 오는 모션 벡터를 잘못 찾아 물체 간 색상이 침범하는 현상을 해결하였으나, 또 다른 문제가 발생했다. 이러한 형태로 앞에 위치한 물체의 모양으로 뒤에 있는 물체에 일부 픽셀이 소실되는 현상이 발생했다. 모션벡터 반대방향 공의 일부 픽셀이 소실되는 현상 자신을 지나는 모션벡터맵의 첫번째 layer 이...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/43162 풀이 DFS로 주어진 연결 정보를 통해 네트워크의 개수를 구하는 문제로, 네트워크는 컴퓨터간 연결요소가 존재 시, 1개의 네트워크로 친다. 따라서 아무하고도 연결되어있지 않거나, 각각 다른 컴퓨터끼리 연결되어 있는 경우를 탐...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42628 풀이 이중 우선순위 큐를 구하기 위해, 각 배열의 문자를 나눠 명령어와 숫자 배열을 생성했다. 생성된 배열의 값에 따라 answer에 적용하여 모든 연산을 처리한 후 큐가 비어있으면 (0,0) 비어있지 않으면 (최댓값, 최...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/43105 풀이 일정 패턴의 숫자 배열이 주어졌을 때, 맨 위에서 맨 아래까지 경로의 최대 합을 구하는 문제로, DP로 풀 수 있는 문제이다. 최대 합을 구하는 문제이므로, 순서대로 경로의 합을 더하고,위의 값 중 최대 값을 남겨 맨 ...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/92335 풀이 10진수를 n진수로 변환하고, 소수인지 판별하고, 숫자 앞 뒤에 0이 있는지 확인하여 이를 모두 충족하는 경우를 찾는 문제이다. 소수 판별에는 시간이 많이 걸리므로, 숫자 앞 뒤 0이 존재하는 지를 먼저 판단하여, 시간...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/43165 풀이 원하는 숫자를 만들 수 있는 경우의 수를 구하는 문제로, DFS를 통해 조건을 충족하는 경우의 수를 모두 더해 return한다. #include <string> #include <vector> ...

문제 아래 그림과 같이 여러 물체가 이동하는 씬에 모션 블러 적용 시, 모션 블러 효과가 이상하게 나오는 경우가 발생한다. 해결 모션 블러 효과는 자기 자신에게 오는 모션 벡터를 통해 시간 별 픽셀 이미지를 가져 온다. 이를 확인하기 위해 코드를 수정해서 이미지를 출력했다. 물체 간 서로 거리가 있을 경우, 아무런 ...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42577 풀이 단순하게 sort로 정렬 후, loop문을 돌며 접두어인지 확인하여 해결할 수 있다. #include <string> #include <vector> #include <algorithm&gt...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/17677 풀이 집합의 유사도를 검사하는 자카드 유사도를 구현하는 문제로, 두 문자열의 대소문자를 일치시키고, 각각 비교한다. #include <string> #include <unordered_map> usi...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42587 풀이 #include <string> #include <vector> #include <algorithm> using namespace std; int solution(vector<i...

필기

문제 https://school.programmers.co.kr/learn/courses/30/lessons/87946 풀이 이는 DFS 문제로, 탐험 횟수마다 필요한 피로도가 다른데, 최대 탐험 횟수를 이루는 경우를 찾는 것이다, 이를 찾기 위해 다음 탐험에 필요한 피로도가 현재 피로도보다 낮을 때를 구하고, 이중 가장 많은 탐험 횟수를 저...

문제 현재 framework는 하나의 모델에 하나의 texture를 적용, 렌더링한다. 그러나 대부분의 3D 모델은 여러 texture로 이루어져 있어, 여러 texture 모델을 불러오기 위해 코드를 변경하였다. void LoadModels(ID3D11Device* pd3dDevice) { g_pModel_1 = new Animatio...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/64065 풀이 각 원소 중 가장 많이 쓰인 것을 확인하여 이를 순서대로 배열에 넣어 return하는 문제이다. 따라서 문자열을 나누고 사용 횟수를 저장하여 가장 많이 사용한 순으로 배열에 넣어 return한다. #include &...

문제 Depthpeeling을 통한 모션 블러 구현 시, 아래 그림과 같이 앞의 공의 모션 블러 효과는 존재하는데 뒤의 모션 블러가 사라지는 현상이 발생했고, 이를 해결하고자 했다. 앞의 공의 모션 블러 효과는 존재하는데 뒤의 모션 블러가 사라지는 현상 해결 먼저 해당 위치에서 발생한 문제를 확인했는데 레이어 별로 모션 벡터 맵을 출력했...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42586 풀이 배열로 주어진 작업은 각각의 진도와 속도가 부여된다. 처음 작업의 진도가 100이 되었을 때 다음 작업의 진도도 100이라면 같이 배포된다. 이를 배포될 때마다 몇 개의 기능이 배포되는 지를 return하는 문제로, 순...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/17680 풀이 LRU(Least Recently Used) 알고리즘은 가장 오래 쓰이지 않은 것을 뽑아 교체하는 알고리즘으로, 이를 구현하는 문제이다. 캐시에 원하는 데이터가 있는 경우를 hit라고 하며, 이를 뽑아 맨 뒤에 넣고(가...

문제 Efficient motion blur through motion vector sharing에서 아래와 같은 문제가 발생한다. 여러 물체의 모션 블러 생성 시, 각 물체의 모션 벡터를 따라 샘플을 진행한다. 그런데 물체 간 이동 방향이 서로 다를 경우, 샘플 위치에 다른 물체가 존재할 수 있다. 이러한 경우, 배경을 샘플 해야 하나,...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42578 풀이 서로 다른 옷 조합 갯수를 구하기 위해 종류 별로 의상을 저장, 각 원소곱을 통해 조합의 개수를 구한다. 다만, 아무것도 입지 않은 경우를 제외하기 위해 마지막에 -1을 빼준다. #include <string&g...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12949 풀이 단순한 행렬곱 문제로, arr1의 행과, arr2의 열 크기의 2차원 벡터 안에 arr1의 행과 arr2의 열 간의 곱을 각각 곱한 후, 더해줘 값을 입력한다. #include <string> #includ...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42747 풀이 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index 일 때, h값을 구하는 문제로, 인용 횟수와 논문 개수가 일치한 것을 찾는다. 따라서...

k(+)-buffer 1. 개요 1) 제안 Fragment 깊이 정렬은 복잡한 렌더링 효과를 시뮬레이션 하는 다수의 이미지 기반 기술의 기본이나, 깊이 복잡도가 높은 장면을 래스터화 할 때는 시간과 공간의 관점에서 어려운 작업이다. 낮은 그래픽 메모리 요구 사항이 가장 중요할 때, k-버퍼는 생성된 모든 조각의 하위 집합에 대해 올바른 깊이 순...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/87390 풀이 n x n 배열에서 일정 행, 열마다 숫자를 지정하고, 이를 1차원 배열로 변환 시, left부터 right 구간의 원소들을 return하는 문제로, 일반적인 2차원 배열을 변환하여 사용하면 10 ^7 까지라는 제한 조...

목표 모션 블러를 accumulation으로 구현하는 방법은 실제와 거의 비슷한 모션 블러 효과를 주지만, 많은 렌더링 횟수를 필요로 한다. Motion blur 이를 해결하기 위해 모션 벡터를 활용, 렌더링 횟수를 줄인다. 1st pass – Make Texture 2nd  Pass – Draw Motion Blur in ...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/131127 풀이 원하는 물건의 종류와 개수가 할인하는 물건의 종류와 개수와 같을 때를 찾기 위해 먼저 원하는 물건들을 map에 넣고, 일치하는 순간을 탐색하였습니다. 그리고 탐색 기간이 10일이기 때문에, index가 10 이상이 되...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/76502 풀이 일반적으로 loop문을 통해 올바르지 못한 괄호를 찾고, erase로 해당 부분을 제거하는 방법을 쓸 수 있으나, 이는 시간 초과가 발생한다. 따라서 괄호를 회전하고 stack을 통해 서로 짝을 이룰 때 제거하는 것을 ...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/131701 풀이 원형으로 배치된 수열의 부분 수열 개수를 구하는 문제로, 인접한 숫자들을 일정 길이로 묶어 더해주면 된다. 다만 원형으로 배치되어 있기 때문에 일정 길이에 도달하지 못했는데 배열 끝에 도달한다면 다시 첫 번째 순서로 ...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/138476 풀이 서로 다른 크기의 귤을 최소 가짓수로 도출하는 문제로, 가장 적은 개수를 가진 크기부터 순서대로 더하면 되는 문제이다. map을 사용하여 같은 크기의 귤의 개수를 구하고 이를 오름차순으로 정렬한다. 각 크기 별 개수를...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12914 풀이 피보나치 수열 형태의 문제로, 이전 값들의 합으로 현재 값을 구할 수 있다. 다만 재귀로 풀면 시간 초과가 날 가능성이 높으므로, DP(동적계획법)을 사용해 풀었다. #include <string> #inc...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12985 풀이  A번 참가자와 B번 참가자는 서로 붙게 되기 전까지 항상 이긴다고 가정했을 때, 두 참가자가 붙으려면 바로 옆의 참가자를 이겨야 한다. 따라서 A와 B가 서로 같은 조가 될 때까지 계속 나눠줘야 한다. 다만 값이 홀수...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12953 풀이 최소 공배수를 구하기 위해 ‘유클리드 호제법’을 사용했다. 이는 두 수를 나눈 나머지를 반복하였을 때, 나머지가 0이되면 이 때 마지막으로 나눈 수가 최대 공약수인 것을 활용한 것으로, 이를 배열에 모두 적용, 최대 공...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42885 풀이 보트에 2명이 탈 수 있는지 검사하기 위해, sort를 통해 오름차순으로 정렬한 배열의 최솟값과 최댓값을 비교해가며 배열이 빌 때까지 제거를 지속한다. #include <string> #include &lt...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12980 풀이 #include <iostream> using namespace std; int solution(int n) { int answer = 0; while (n != 0) { ...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12981 풀이 이전에 나온 단어가 나오면 안되므로 map을 사용하여 중복된 값이 나왔을 때 해당 번호와 사이클을 리턴하고, 중복된 값이 없을 경우 (0,0)을 리턴해준다. #include <string> #include ...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42842 풀이 노란색 격자가 가운데에 존재하고, 갈색 격자가 그 주위를 감싸고 있을 때, 해당 격자의 합은 카펫의 크기이다. 먼저 노란색 격자가 이룰 수 있는 사각형의 최소 인자를 구하고, 이를 통해 사각형을 이루었을 때, 주위에 배...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12973 풀이 주어진 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾고, 제거하는 것을 반복하여 모든 문자가 사라질 수 있는지를 판단하는 함수를 구하는 문제로, 일반적으로 반복문을 통해 붙어있는 문자를 찾고 이를 제거하는 것을 반복...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12945 풀이 n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수를 작성하기 위해 먼저, 피보나치를 구현했다. 그런데 조건으로 n은 2 이상 100,000 이하인 자연수라는 조건이 붙어 있으므로, 일반적인 재귀로 풀게...

구현 Motion blur 모션 블러는 움직임이 흐릿함 을 뜻하는 말로,사진이나 애니메이션에서 동작의 빠름을 효과적으로 나타내기 위해 사용하는 기법. Motion blur Motion blur 카메라 셔터가 닫힐 때까지 들어오는 빛을 저장하는 과정에서 피사체의 움직임이 셔터 스피드보다 빠르게 움직일 경우 발생한다. ...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12911 풀이 n보다 큰 자연수 이면서, 2진수로 변환 시 1의 개수가 같은 가장 작은 수를 찾기 위해 n을 2진수로 변환하여 1의 개수를 세고, 같은 개수의 1을 가진 자연수를 찾기 위해 bitset을 활용, n+1부터 2진수로 ...

문제 기존 코드는 pd3dDevice에 만들 물체의 개수만큼 buffer를 생성하여 순차적으로 그린다. 이는 모델이 추가될 때마다 코드 수정이 많이 필요하다. ID3D11Buffer* g_pcbVSPerObject_1 = NULL; ID3D11Buffer* g_pcbVSPerObject_2 = NULL; ID3D11Buffer* g_pcbVSP...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12924 풀이 연속된 자연수로 숫자를 표현할 때, 연속된 숫자를 작은 값부터 하나하나 더해보면 정답이 나온다. #include <string> #include <vector> using namespace st...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/70129 풀이 주어진 string이 “1”이 될 때까지 이진 변환을 계속하고 이진 변환의 횟수와 제거된 0의 개수를 리턴해야한다. 따라서 0을 제거, 카운트하고 이를 이진 변환하는 것을 string이 “1”이 될 때까지 반복한다. ...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12909 풀이 괄호가 올바르게 짝지어져 있는지 확인하는 문제로, 스택을 활용하여 풀 수 있다. 괄호가 올바르게 짝지어져 있다면 ‘(‘과 ‘)’는 같은 개수가 존재할 것이고, 배열의 원소를 순서대로 접근하여 ‘(‘를 스택에 넣고 매칭...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12941 풀이 각각의 배열의 원소를 매칭, 곱해서 나오는 값을 최소로 하기 위해서 큰 숫자와 작은 숫자 간의 곱이 필요하다. 따라서 두 배열을 sort()하여 하나는 오름차순, 하나는 내림차순으로 곱해준다. #include <...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12939 풀이 stringstream을 통해 string을 파싱한다. 그리고 이를 정렬하여 최대, 최솟값으로 이루어진 string을 리턴한다. #include <string> #include <vector> ...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12951 풀이 단순하게 아스키 코드로 풀어 공백에 따라 대문자와 소문자를 변환하여 string으로 리턴 #include <string> #include <vector> using namespace std; ...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12935 풀이 배열에서 가장 작은 수를 제거한 배열을 리턴, 빈 배열일 경우 -1을 리턴 반복문을 통해 모든 원소를 탐색, 비교하여 가장 작은 숫자와 해당 인덱스 값을 저장 그리고 erase()를 통해 저장된 인덱스에 해당하는 원...

문제 모션블러 효과를 생성하기 위해 여러 개의 이미지들을 생성, 이러한 작업을 프레임마다 진행해야 한다. 이로 인해 프래그먼트 셰이더의 호출이 매우 빈번해져 성능에 영향을 줄 수 있으므로 fullscreen quad를 사용, 프래그먼트 셰이더 호출 횟수를 줄인다. 1st pass – Make Texture 2nd  Pass – Dr...

구현 앞서 구현한 render texutre를 사용하여 environment mapping을 구현한다. shadow.vs cbuffer MatrixBuffer { matrix worldMatrix; matrix viewMatrix; matrix projectionMatrix; matrix lightViewMatrix...

구현 백버퍼에 렌더링되는 장면을 텍스처에 그린다. ##ShadowMap pseudo Code #1PASS 카메라의 eye 값을 광원의 position과 일치시킨다. 광원의 위치에서의 NDC 행렬을 생성한다. Render() { RenderToTexture //전체 장면을 먼저 텍스처로 렌더링합니다. { setRenderTarget...

구현 백버퍼에 렌더링되는 장면을 텍스처에 그린다. RenderTextureClass를 정의한다. RenderTextureClass.h class RenderTextureClass { public: RenderTextureClass(); RenderTextureClass(const RenderTextureClass&); ~Ren...

문제 Render-to-texture 작업 시, 오류 발생 해결 2D 화면을 그리기 위해서는 Z버퍼를 사용하지 않아야 한다. 그래야 해당 픽셀에 올바로 새로운 색상을 덮어쓰는 것이 가능해진다. 그리고 작업이 끝난 후 다시 z버퍼를 켜야 올바른 3D 모델링이 가능하다. Initialize 함수에서 DepthEnable 변수가 fals...

구현 dds 텍스처 파일을 통해 텍스처 매핑을 진행할 수 있으나 dds 파일은 변환이 필요하다. 따라서 여러 파일 포멧 중 targa 파일 포멧의 텍스처 파일을 사용하여 텍스처 매핑을 하는 코드를 추가했다. bool ModelClass::Initialize(ID3D11Device* device, ID3D11DeviceContext* device...

구현 라이팅 이미지 출력을 위한 클래스를 추가한다. 프레임 워크 구성 shader 코드 작성한다. 기존 texure shader와 비슷한 구조로, 픽셀에 들어오는 빛을 계산하고, 빛의 양에 따라 색상을 계산한다. light.vs cbuffer MatrixBuffer { matrix worldMatrix; matrix viewMat...

구현 텍스처 매핑 이미지 출력을 위한 클래스를 추가한다. 프레임 워크 구성 shader 코드 작성한다. 기존 color shader와 비슷한 구조로, 텍스처 좌표를 받아, 해당 좌표의 텍스처 색상을 샘플(sample)하는 코드가 추가된다. texture.vs cbuffer PerFrameBuffer { matrix worldMatr...

구현 DX11에서 버퍼에 입력된 정점 데이터는 shader를 통해 그래픽 카드(GPU)에서 처리된다. DX11 렌더링 파이프라인 이를 구현하기 위해 프레임워크를 업데이트한다. 프레임 워크 구성 shader 코드 작성 color.vs cbuffer MatrixBuffer { matrix worldMatrix; ...

구현 렌더링에 사용할 GraphicsClass 정의 GraphicsClass.h #pragma once const bool FULL_SCREEN = false; const bool VSYNC_ENABLED = true; const float SCREEN_DEPTH = 1000.0f; const float SCREEN_NEAR = 0.1f; ...

구현 그래픽스 API 중 하나인 DirectX11로 렌더링을 구현한다. DirectX11를 사용하기 위해 프레임 워크 작업이 필요하다. 프레임 워크 구성 전체 어플리케이션을 캡슐화하는 SystemClass를 정의 main.cpp //main 함수 int APIENTRY wWinMain(_In_ HINSTANCE hInstance, ...

문제 기존 msh 파일만 읽어 오는 임포트 코드를 OBJ 파일을 읽어올 수 있게 코드 수정 시도 # cube.obj mtllib cube.mtl o cube v -0.500000 -0.500000 0.500000 v 0.500000 -0.500000 0.500000 v -0.500000 0.500000 0.500000 v 0.500000 0....

Environment mapping 환경맵을 활용, Sphere environment mapping을 진행하였다. 일반적으로 많이 사용하는 큐브 맵의 반사 색상 결정 공식이다. 큐브 맵 대신 Sphere map을 사용하여 환경맵을 만들기위해 다른 공식을 사용 해당 Sphere map을 임포트하고, Sphere...

1. 조명 모델 1. 지역 조명(local illumination) 조명 대상인 물체의 표면 재질과 광원의 속성만 이용해 해당 표면의 색상을 결정할 뿐, 같은 공간에 있는 다른 물체는 고려하지 않는다.(퐁 모델) 퐁 모델로 $S_1$, $S_2$, $S_3$ 라이팅 시 $S_2$의 앞에 $S_1$이 존재 하나, 이를 무시하고 빛을 받는다...

노멀 매핑 (d)에서 노멀 $n$과 빛 벡터 $l$ 계산을 통해 a, b, c의 반사 정도를 결정한다. b의 경우 $n$과 $l$ 사이 각도가 작아 빛을 많이 받아 밝게 보인다. a와 c는 $n$과 $l$ 사이 각도가 커 빛을 적게 받고 어두워 보인다. 이를 통해 울퉁불퉁한 표면을 표현할 수 있으나, 폴리곤 메시가 많을수...

Shadow mapping 쉐도우 매핑 구현을 위해 쉐도우 매핑 2패스를 구현한다. 먼저, 기존 코드는 하나의 모델만을 렌더링하는 코드로, 쉐도우 매핑을 위해 코드를 수정 Object.h #include"Matrix4.h" #include"Vector4.h" #ifdef _DEBUG #include <assert.h> #defin...

쉐도우 매핑 1. 쉐도우 매핑 두 번의 렌더링 패스(rendering pass)를 통해 수행, 쉐도우맵(shadow map) 텍스처를 생성 1) 1 Pass 광원에서 나온 빛이 미치는 표면을 샘플, 각 샘플 점 $p$마다 광원까지의 거리, $z$를 쉐도우 맵에 저장 1 Pass, 깊이맵 생성 $z$ : 광원에서 본 3차...

Lighting 라이팅을 위해 suface normal, vertex normal을 계산한다. P1,P2,P3 삼각형의 suface normal surface normal의 평균을 통해 vertex normal 계산 void Renderer ::makefaceNormals() //외적 { for (int i = 0; i &l...

라이팅 라이팅(lighting or illumination) : 빛과 물체 간 상호작용 처리 1. 퐁 모델 점 광원(point light source) : 3차원의 한 점으로부터 전방위로 빛이 발산 방향성 광원(directional light source) 물체 표면의 여러 점에 입사하는 빛의 빛의 방향이 서...

Texture mapping speckled213.raw 텍스처 텍스처를 임포트하고 텍스처 좌표를 생성한다. g_renderer.readTextureFile("speckled213.raw"); g_renderer.makeUVVertex(); void Renderer::readTextureFile(char* pFileName) { ...

이미지 텍스처링 1. 텍스처링 텍스처(texture) : 텍셀(texel)로 이루어진 2D 배열 텍셀(texel) : texture pixel로, 텍스처 이미지의 픽셀 텍스처와 텍셀 텍스처링 시, 텍스처 좌표(texture coordinate)에 따라 텍셀 위치가 할당된다. 텍스처링 ...

탐욕 알고리즘 1. 탐욕 알고리즘(greedy algorithm) 답을 하나씩 고르는데, 미리 정한 기준에 따라서 매번 ‘가장 좋아 보이는 답을 선택’ 동적 계획과 마찬가지로 최적화 문제를 푸는데 주로 사용(상대적으로 설계하기 더 쉬움)한다.동적 계획은 재귀관계식을 세워 입력 사례를 더 작은 입력 사례로 분할하는 반면, 탐욕 알고리즘은 입력 사...

Projection transform 면밀한 변환 과정 관찰을 위해 임포트 모델을 2D 모델에서 3D 모델로 변경. #$Vertex 2904 #$Face 5804 Vertex 1 0.151632 -0.043319 -0.08824 Vertex 2 0.163424 -0.0...

Culling & z-buffering 1. Culling bool Renderer::isBackFace(int nFace) { float normalZ = 0; Vector4 v1, v2, v3; v1.x = m_tramsformedVertex[m_face[nFace].m_vertex[0] - 1][0]; v1.y =...

프레임 버퍼 프레임 버퍼(frame buffer)는 컬러 버퍼(color buffer), 깊이 버퍼(depth buffer), 스텐실 버퍼(stencil buffer)로 구성된다. 컬러 버퍼: 스크린의 2차원 뷰포트에 나타날 픽셀 전체를 저장하는 메모리 공간으로, 화면과 같은 해상도 깊이 버퍼(z-buffer):...

레스터라이저 렌더링 파이프 라인 정점 쉐이더에서 출력한 정점들은 프리미티브로 조립된다. 이를 래스터화(rasterization)라고 한다. 그리고 이 과정에서 클리핑(clipping), 원근 나눗셈(perspective division), 뒷면 제거(back-face culling), 뷰포트 변환(viewport transform), 스캔 ...

View transform 변환을 사용하여 물체의 위치를 변환한다. 카메라 공간 1. 가상 카메라 //카메라(눈)의 위치 Vector4 eye(5.0f, 0.0f, 5.0f); //카메라의 초점(참조 위치) Vector4 at(0.0f, 0.0f, 0.0f); // 카메라의 위쪽 방향 지정(x=1이면 x축으로 누워있고, y=...

동적 계획 1) 프로이드의 최단경로 알고리즘 모든 점에서 모든 다른 점까지의 거리를 알아내는 알고리즘 $D^k$$[i][j]$= 집합 {v_1,v_2, v_3, … v_k}에 속하는 마디 만을 거쳐서 v_i 에서 v_j로 가는 최단 경로의 길이를 구한다. $D^0$$[i][j]$는 다른 어떤 마디도 거쳐 가지 못...

문제 뷰 공간 구현 후, translate를 진행하려 했으나, 적절한 이동, 회전 등이 발생하지 않음 변환 적용 실패 행렬 값이 원하는 대로 적용X 해결 Rotate translate $VRP(Y축 rotate) = rotateX(seta2) * rotateZ(seta1) * scale (l) * (1,0,0,1) ...

World transform 행렬과 벡터를 통한 transform 구현 월드 변환 1. 행렬, 벡터 행렬, 벡터 구현 class Matrix4 { public: float arr[4][4]; }; class Vector4 { public: float x, y, z, w; Vector4(float v[4]) ...

Rendering pipeline 렌더링 파이프 라인을 openGL 환경에서 엣지 테이블(edge table)을 통한 스캔라인(scanline)기법을 통해 구현하였다. 1. Import # model.msh # 점의 개수 $Vertex 6 # 면의 개수 $Faces 2 # 점번호 x y z ...

변환 렌더링 파이프 라인 GPU에서 렌더링 진행을 위해 렌더링 파이프 라인에 따라 정점 처리가 진행된다. 정점 쉐이더(vertex shader): 정점 배열의 모든 정점에 대한 연산 수행 레스터라이저(rasterizer): 연산된 정점들로 삼각형을 조립, 삼각형을 구성하는 픽셀, 프래그먼트(fragment)...

동적 계획 1) 함수 단일 변수 함수(function) : f는 변수 x를 유일한 값 f(x)와 연관 짓는 규칙 또는 법칙 주어진 실수 x와 그 실수의 제곱과 연관 짓는 함수 f는 순서쌍(ordered pair)집합으로 나타낼 수 있다.(ex) f(x) = x^2  는 모든 순서쌍 (x,x^2)) ...

모델링 1. 모델 구성 요소 1) vertex array 폴리곤 매쉬는 그림과 같이 정점 배열(vertex array)로 표현 가능하며, 삼각형을 이루는 3개의 정점이 순서대로 나열되어야 한다. 정점 배열을 통한 삼각형 폴리곤 매쉬 표현 2) index array 정점 배열만으로 폴리곤 매쉬 표현 시, 정점 정보가 중복되어 저장된다. ...

동적 계획 1. 동적 계획 1) 하향식 분석 : top - down으로, 출력 형태를 만들어 놓고 회수하는 형태이며 결과가 이전의 결과에 영향을 받는다. ※ 재귀 복습을 단계적으로 풀이 해 놓은 것을 하향식 분석이라고 할 수 있다. 하향식 분석이란, 가장 위쪽에 위치한 상자의 메소드 호출부터 시작해 계단식으로 자세히 조사하는 분석 기법을 말...

개요 컴퓨터 그래픽스(computer graphics): 컴퓨터를 통한 이미지(image) 생성 컴퓨터 그래픽스 제작 과정 모델링(modeling): 물체(object)를 컴퓨터가 처리할 수 있는 모델(model)로 정의 대부분 평면 다각형(polygon)의 집합, 폴리곤 매쉬(polygon mes...

분할 정복(Divide-and-Conquer) 문제의 입력 사례를 두 개 이상의 작은 입력 사례로 분할, 분할한 입력 사례의 답을 바로 얻을 수 있으면, 원래 문제의 답은 얻은 답들을 통하여 구할 수 있고 분할한 입력 사례가 여전히 커서 바로 답을 구하지 못하면 그보다 더 작은 입력 사례로 다시 분할한다. 바로 답을 구할 수 있을 만큼 충분히 작아...

알고리즘 4. 차수 첫째 알고리즘의 일정 시간 복잡도는 $100n$, 둘째 알고리즘의 일정 시간 복잡도 $0.01n^2$  이라고 가정했을 때 첫째 알고리즘이 둘째보다 궁극적으로 빠르다. 두 알고리즘에서 설정한 단위 연산 1회 실행 시간이 같고, 주변 명령문 실행 시간도 거의 같은 경우 n값에 대해서만 첫째 알고리즘이 빠르다고 할 수 있다....

알고리즘 컴퓨터 프로그램은 정렬하기(sorting)와 같은 특정 작업을 수행하는 개별 모듈(module)을 모아서 구성하고 프로그램 전체 설계보다 특정 과제를 수행하는 개별 모듈 설계에 중점을 주는 특정 과제를 문제(problem)라고 한다. 1. 알고리즘 문제를 푸는 단계 별 절차, 문제를 푸는 기법은 다양하지만, 기법에 따라서 알고리...

문제 풀이 입력 값은 Nkg으로, 설탕 5kg과 3kg을 통해 Nkg을 맞춰 최대한 적은 숫자의 봉지를 들고 가기 위한 최소 봉지의 개수를 출력으로 하는 문제입니다. 이를 구하기 위해 먼저 5kg을 먼저 하나씩 빼면서 이를 3kg로 나누어서 5kg의 개수와 3kg의 개수를 구하고자 하였습니다. 그러나 5와 3으로 정확히 나누어지지 않는...

문제 풀이 입력 값은 호텔의 층수인(H), 각 층의 방수(W), 손님의 순서(N)으로 이루어지며, 출력 값은 손님의 호수를 구하는 문제입니다. 호텔의 방은 왼쪽부터 가로가 아닌 세로로 101, 201호 순서로 이동 동선을 최소한 값이라고 하며 꼭대기 층이 꽉찬 경우 다시 내려와 201호 순서대로 다시 시작하며 이것이 반복됩니다. 이를...

문제 풀이 입력 값은 층수(K)와 호수(N)으로 출력 값인 사람 수를 구하는 문제입니다. 이 아파트는 a층 b호에 살려면 자신의 아래 (a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 살아야 합니다. 이는,A층 b호의 사람 수= (a-1)층 1호 + (a-1)층 2호 + ··· (a-1)층 b호 입니다. 이 문제는 일정한 수열의...

문제 풀이 달팽이는  V미터인 막대를 올라가는데 낮에 A미터를 올라가고, 밤에 B미터 미끄러진다고 하며, 정상에 올라간 후에는 미끄러지지 않는다는 조건 안에 막대를 올라가는 시간을 구하고자 한다. 이 문제에서는 높이V와 낮에 올라가는 높이 A, 밤에 미끄러지는 높이 B가 입력 값으로 주어져 얼마간의 시간이 걸리는지 출력 값을 ...

문제 풀이 이 문제는 표에 나열된 분수들이 1/1 -> ½ -> 2/1 -> 3/1 -> 2/2 -> … 과 같은 지그재그 순서로 차례대로 일정한 주기로 분수들이 반복되는 배열로 이루어져 있으며, 표와 같이 일정한 방향과 순서를 통해 이 것이 반복되고 있다. 반복되는 현상을 이용하여, 문제를 풀...

문제 https://www.acmicpc.net/problem/1011 풀이 #include <iostream> using namespace std; int main() { int T; cin >> T; for (int test_case = 0; test_case < T; test_case++) { ...

문제 https://www.acmicpc.net/problem/4948 풀이 #include <iostream> #include <cmath> using namespace std; bool decimal(int n, int m) { if (n < 2) // 1은 소수 X { re...

운영체제 1. 역할 컴퓨터의 하드웨어 제어 컴퓨터 프로그램 제어 사용자와 컴퓨터 간 커뮤니케이션 지원 2. 인터페이스 사용자 인터페이스 Shell(애플리케이션) -> 터미널, GUI 제공 Shell 응용프로그램 인터페이스...

문제 https://www.acmicpc.net/problem/1929 풀이 #include <iostream> #include <cmath> using namespace std; bool decimal(int m) { if (m < 2) // 1은 소수 X { return f...

문제 https://www.acmicpc.net/problem/2941 풀이 #include <iostream> #include<vector> #include<string> using namespace std; int main() { vector<string> Alpabet = {...

양방향 연결 리스트 머리(Head) 와 꼬리(Tail)로 모두 가진다는 특징 각 노드는 앞 노드와 뒤 노드의 정보를 모두 저장 연결리스트 삽입 과정 데이터를 ‘오름차순’으로 저장하는 양방향 연결 리스트 #define _CRT_SECIRE_NO_WARNINGS #include &l...

C와 C++의 비교 1. C 키워드(절차지향) 데이터형 : char, int, short, long, unsigned, float, double, struct, union, typedef 반복문 : form while, do while 분기문 : if, else, switch, case, def...

연결 리스트 1. 리스트 배열 기반 리스트 장점 배열로 만들었으므로 특정한 위치의 원소에 즉시 접근 가능 단점 데이터가 들어갈 공간을 미리 메모리에 할당해야 함 원하는 위치로의 삽입이나...

자료구조 1. 자료구조의 필요성 데이터를 효과적으로 저장하고, 처리하는 방법에 대해서 바르게 이해할 필요, 제대로 이해하지 못하면 불필요하게 메모리와 성능을 낭비할 여지 발생 가능성 2. 기본적인 자료구조 선형 구조 배열 연결 리스트 스택 큐 비선형 구조 ...

구조체 여러 개의 변수를 묶어 하나의 객체를 표현하고자 할 때, 구조체 사용 가능 캐릭터, 학생, 좌표 등 다양한 객체를 모두 프로그래밍 언어를 이용해 표현 가능 struct Student { char studentId[10]; char name[10]; int grade; char major[...

함수 포인터 특정 함수의 반환 자료형을 지정하는 방식으로 선언 가능 함수 포인터를 이용하면 형태가 같은 서로 다른 기능의 함수를 선택적 사용 가능 int add(int a, int b) { return a + b; } int sub(int a, int b) { return a - b; } i...

다차원 배열과 포인터 배열 1. 다차원 배열 1) 2차원 배열 2차원 배열 2) 3차원 배열 int a[2][3][3] = {{{1,2,3},{4,5,6},{7,8,9}},{{1,2,3},{4,5,6},{7,8,9}}}; int main(void) { int i, j, k; for (i = 0; i < 2; i++...

동적 메모리 할당 1. 동적 메모리 할당 함수 C언어에서 malloc()함수를 이용해 원하는 크기의 메모리 공간을 확보 가능 Malloc() 함수는 메모리 할당에 성공하면 주소를 반환, 그렇지 않으면 NULL 반환 Malloc() 함수는 라이브러리에 정의 #include <s...

포인터 1. 포인터 특정한 변수 자체가 존재하는 메모리 주소의 값 포인터 int main(void) { int a = 5; //b가 a의 주소를 가지고 있다. int *b = &a; //b가 a의 주소를 가지고 있으니 a의 주소에 간접 참조하여 a값 5를 반환한다. printf("%d", *b); system("pause...

렌더링 sketch up rendering using V-ray