DP

정수론은 수학의 한 분야로서, 정수와 관련된 다양한 수학적 성질을 연구합니다. 이 분야는 기본적인 정수의 나눗셈부터 시작하여, 소수, 이차 형식, 다항식의 정수 해, 그리고 숫자의 분할과 같은 복잡한 주제까지 포괄합니다. 정수론은 수학 이론뿐만 아니라 컴퓨터 과학, 암호학, 그리고 수많은 응용 과학 분야에서도 중요한 역할을 합니다. 소수의 패턴, 정수들 사이의 관계, 그리고 숫자들의 이론적 특성을 탐구함으로써, 이 분야는 근본적인 수학적 이해를 제공합니다. 1. 유클리드 호제법 유클리드 호제법은 두 양의 정수의 최대공약수를 찾는 알고리즘입니다. 간단하면서도 매우 빠르게 최대공약수를 구할 수 있기 때문에, 컴퓨터 과학에서도 널리 사용되는 알고리즘 중 하나입니다. 구현 방식 두 수 a와 b (a > b)가 ..
문제 링크 문제 설명 현대모비스에서 전기차로 경사로 주행 테스트를 하려고 합니다. 경사로 테스트는 n×m 크기의 격자 형태의 공간에서 진행되며, 각 칸에 적힌 숫자는 높이를 나타냅니다. 전기차는 격자 내의 모든 칸에서 출발 가능하며, 상하좌우로 인접한 칸으로만 이동 가능하고 격자 밖을 벗어날 수는 없습니다. 전기차가 인접한 칸으로 이동하는 길의 경사는 이동하려는 칸의 높이에서 현재 칸의 높이를 뺀 값입니다. 예를 들어 높이가 5인 칸에서 7인 칸으로 이동하는 길의 경사는 2(= 7 - 5)이고, 높이가 6인 칸에서 높이가 1인 칸으로 이동하는 길의 경사는 -5(= 1 - 6)입니다. 경사 수열 d가 주어집니다. 경사 수열은 테스트에서 전기차가 이동할 길의 경사를 나타내며, d[i]는 전기차가 i+1번째로..
문제 링크 분류 비트마스킹, 다이나믹 프로그래밍, 비트필드를 이용한 다이나믹 프로그래밍, 외판원 순회 문제 제출 일자 2024년 1월 6일 14:18:11 문제 설명 외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자. 1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수..
문제 링크 분류 다이나믹 프로그래밍 문제 설명 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 위해 목적지까지 번호순서대로 일렬로 서서 걸어가도록 하였다. 이동 도중에 보니 아이들의 번호순서가 바뀌었다. 그래서 선생님은 다시 번호 순서대로 줄을 세우기 위해서 아이들의 위치를 옮기려고 한다. 그리고 아이들이 혼란스러워하지 않도록 하기 위해 위치를 옮기는 아이들의 수를 최소로 하려고 한다. 예를 들어, 7명의 아이들이 다음과 같은 순서대로 줄을 서 있다고 하자. 3 7 5 2 6 1 4 아이들을 순서대로 줄을 세우기 위해, 먼저 4번 아이를 7번 아이의 뒤로 옮겨보자...
NewtronVania
'DP' 태그의 글 목록