목록분류 전체보기 (500)

기록공간

DNA (백준 - 1969번)

우선 Hamming Distance의 합이 가장 작은 DNA부터 구해야 한다. 입력받은 DNA들에서 각 번째마다 가장 많이 존재하는 뉴클레오티드를 종합하여 조합하면 Hamming Distance의 합이 가장 작은 DNA를 찾을 수 있다. TATGATAC TAAGCTAC AAAGATCC TGAGATAC TAAGATGT 이 DNA를 예로 들어보자. 첫번째에 가장 많이 존재하는 뉴클레이오티드는 T이다. 두번째는 A, 세번째는 A, 네번째는 G, 다섯번째는 A, .... 이렇게 해서 우리가 찾는 DNA의 값은 TAAGATAC가 된다. 하지만 이 DNA가 여러개 존재 할 수 있다는 것에 주목하자. 각 번째에서 즉 존재하는 뉴클레오티드 횟수가 서로 동일할 수 있다는 것이다. 이 경우에는 사전 순으로 했을때 가장 처..
Algorithm/문제 2020. 3. 29. 01:00
멀티탭 스케줄링 (백준 - 1700번)

그리디 알고리즘으로 푸는 문제이다. 플러그가 꽂혀있지 않을 경우 사용하는 전기용품 순으로 꽂는다. 이미 플러그에 꽂혀있는 전기용품은 꽂는 작업을 할 필요가 없다. 만약 플러그를 빼야 하는 경우(즉, 멀티탭에 플러그가 모두 사용중인 경우) 가장 나중에 쓰이거나 쓰이지 않을 전기용품의 플러그를 빼야 빼는 횟수를 최소화 할 수 있다. 정리해보면 다음과 같다. 전기용품 사용 순서대로 빈 플러그에 꽂는다. 플러그가 모두 사용 중이며 현재 사용할 전기용품이 플러그에 꽂혀있지 않는 경우 꽂혀있는 플러그 중 가장 나중에 쓰이거나 더이상 쓰이지 않을 전기용품 플러그를 뺀다. 멀티탭에 모든 플러그가 꽂혀있는 경우 N개의 사용순서에서 i번째에 있는 다른 전기용품을 사용해야 한다고 가정하자. 꽂혀있는 전기용품들을 순회돌며 i..
Algorithm/문제 2020. 3. 29. 00:59
수리공 항승 (백준 - 1449번)

그리디 알고리즘을 사용하는 문제였다. 우선 물이 새는 곳의 위치를 입력받으면 그 정보를 정렬한다. 그 다음 처음 물이 새는 곳의 위치를 기록한다.(start값) 물이 새는 곳이 하나라도 있으면 테이프를 한 개는 써야 하므로 테이프의 갯수를 기록할때는 1부터 시작한다. 테이프를 최소로 쓰기 위해서 어떻게 해야 하는지 살펴보자. 물이 새는 위치를 순회하며 start에서 물이 새는 위치까지의 길이가 테이프의 길이 - 1(좌우 0.5만큼 간격을 줘야 하므로) 보다 큰 경우 이미 테이프의 길이를 넘어 갔으므로 start부분만 막고 새로운 테이프로 현재 위치를 막아야 한다. 그리고 start값을 현재 위치의 값으로 갱신한다. 모든 위치를 방문했을때 테이프의 갯수가 우리가 원하는 값이 된다. 코드는 다음과 같다. #..
Algorithm/문제 2020. 3. 29. 00:58
저울 (백준 - 2437번)

우선 입력받은 추의 무게를 오름차순으로 정렬해야 한다. 정렬된 상태에서 맨 처음 추의 무게가 1이 아닌 경우에 측정할 수 없는 최소 무게는 1이다. 만약 맨 처음 추의 무게가 1인 경우 1을 시작으로 두번째 추부터 마지막 추까지 무게를 차례대로 더해주도록 한다. 무게가 적은 추부터 차례대로 더하는 sum이라는 값이 있다고 하자. 차례대로 sum에 추의 무게를 더해주는 도중에 sum + 1이면서 sum + 1값이 입력받은 어떤 추에도 존재하지 않는 값이라면 그것은 측정할 수 없는 최소 무게가 될것이다. 코드는 다음과 같다. #include #include #include using namespace std; int main() { int N; cin >> N; vector sinkers; for (int ..
Algorithm/문제 2020. 3. 29. 00:58
병든 나이트 (백준 - 1783번)

그리디 알고리즘을 사용하는 문제였다. 우선 나이트의 모든 이동방법이 위, 아래 오른쪽으로 무조건 1칸 이상 움직이므로, 세로 길이가 1인 체스판의 경우에 나이트는 한번도 이동 할 수 없다. 즉 세로가 1일때는 방문한 최대 칸 수는 1칸이다. 이제 이동 횟수가 4번 미만일 경우를 먼저 생각해보자. 이동 횟수가 4번 미만일 경우에는 이동방법에 제한이 없다는 것을 생각하고 다음을 살펴보자. 우선 세로 길이가 2인 체스판의 경우이다. (2 X 5) 최대로 방문할 수 있는 방법은 위 그림처럼 이동방법 2, 3번을 이용하여 가로 홀수 칸을 방문하는 방법이다. 이 방법을 사용하면 체스판의 가로 길이가 M이라고 했을때 나이트는 최대 (M + 1) / 2 칸을 방문할 수 있다. 하지만 위 규칙에 따라 이동횟수는 4번 미..
Algorithm/문제 2020. 3. 29. 00:55
한 줄로 서기 (백준 - 1138번)

그리디 알고리즘을 사용하는 문제였다. 입력에서 키 정보와 자신보다 키가 큰 사람이 왼쪽에 몇 명이 있는지에 대한 정보가 주어진다. 그렇게 때문에 줄을 어떻게 서야 하는지에 대한 정보를 저장할 배열 result를 만들어 놓고 가장 작은 키의 사람부터 정보에 맞게 result에 키를 나열해주면 된다. 사람의 수는 10을 넘기지 않으므로 키의 범위는 1~10이 될것이다. 이 범위를 넘어가는 11을 빈자리로 선언하고 result를 빈자리로 채워넣는다. 위의 예제를 예로들어 설명하겠다. 사람 4명이 있으므로 result 배열의 크기는 4일 것이다. 둘째 줄 입력에 정보를 바탕으로 result에 줄의 순서를 배치해보자. 우선 키 1인 사람은 자기보다 키큰 사람이 왼쪽에 2명이 있다. 그러므로 자신의 키보다 큰 EM..
Algorithm/문제 2020. 3. 29. 00:51
파도반 수열 (백준 - 9461번)

동적계획법을 사용하는 문제였다. 우선 점화식을 찾기 위해 규칙이 어떠한지 부터 살펴보자. P(1)~P(3)일때는 1로 모두 동일하다. 그리고 P(4)~P(5)일때 2이다. P(4)의 값은 P(1)과 P(2)를 더하여 2가 나오며, P(5)의 값은 P(2)와 P(3)을 더하여 2가 나온다. P(6)의 값은 P(3)과 P(4)를 더하여 3이 나온다. 이러한 규칙을 봤을때 점화식은 다음과 같을 것이다. P[N] = P[N - 3] + P[N - 2] 결과값이 int의 범위를 넘어가기 때문에 P(N)의 값을 저장할 dp 테이블 배열을 long long 형식으로 선언해주어야 한다. 코드는 다음과 같다. #include using namespace std; int main() { long long dp[100 + ..
Algorithm/문제 2020. 3. 29. 00:24
[DirectX 12] Direct3D 초기화 - 3 : 시간 측정 (타이머)

애니메이션을 정확하게 수행하려면 시간을 측정해야 한다. 특히, 프레임 간 경과 시간(Elapsed time), 다시 말해 애니메이션의 인접한 두 프레임 사이에 흐른 시간의 양을 측정할 수 있어야 한다. 프레임률이 높은 경우 프레임 간 경과 시간이 상당히 짧으므로, 정밀도가 높은 타이머를 사용할 필요가 있다. 성능 타이머 정밀한 시간 측정을 위해, Windows가 제공하는 성능 타이머(Perfomance timer)를 사용한다. 이를 성능 카운터(Performance counter) 라고도 부른다. 성능 타이머를 조회하는 메서드를 사용하려면 반드시 Windows.h를 포함시켜야 한다. 성능 타이머의 시간 측정 단위는 '지나간 클럭 틱들의 개수(count)' 이다. 성능 타이머로부터 틱 수 단위의 현재 시간..
DirectX/기초 2020. 3. 23. 12:27
Prev 1 ··· 49 50 51 52 53 54 55 ··· 63 Next