'이득우의 게임 수학' 책을 보고 정리한 글입니다. [4장] 삼각함수 삼각비 : 직각삼각형을 구성하는 세 변에서 두 변을 뽑아 각각의 비례관계를 나타낸 것 사인, 코사인, 탄젠트 단위 원 위의 좌표는 피타고라스 정리에 의해 해당 공식을 얻을 수 있음 단위 원의 반지름을 r로 일반화 → 길이가 1인 벡터와 평행, 길이는 r배 증가 → 스칼라 곱셈에 의해 r⋅(cosθ, sinθ) → 밑변의 길이 r⋅cosθ, 높이의 길이 r⋅sinθ 삼각함수의 성질 데카르트 좌표계의 각도 : x축에서 원의 궤적을 따라 반시계 방향으로 회전한 크기 sin 함수와 cos 함수는 항상 -1에서 1 사이를 일정하게 반복하는 패턴을 띤다. sin 함수와 cos 함수의 값은 360° 주기로 반복된다. y축을 기준으로 좌우를 접어 포..
'이득우의 게임 수학' 책을 보고 정리한 글입니다. [3장] 데카르트 좌표계 데카르트 좌표계 : 직선의 수 집합을 수직으로 배치해 평면을 표기하는 방식 좌표 : 데카르트 좌표계의 한 원소는 곱집합과 동일하게 순서쌍으로 표현 좌표는 점 또는 원점으로부터의 화살표로 표현, 크기와 방향 두가지 속성을 지님 벡터 공간과 벡터 스칼라와 벡터 벡터의 표기 벡터 공간의 연산 벡터와 벡터의 덧셈(벡터의 합) 스칼라와 벡터의 곱셈(스칼라 곱셈) 벡터 공간의 공리 벡터의 합의 결합법칙 벡터의 합의 교환법칙 벡터의 합의 항등원 벡터의 합의 역원 스칼라 곱셈의 호환성 스칼라 곱셈의 항등원 벡터의 합에 대한 분배법칙 스칼라 덧셈에 대한 분배법칙 벡터의 크기와 이동 단위 벡터 : 크기가 1인 벡터 벡터의 결합과 생성 선형 결합 ..
'이득우의 게임 수학' 책을 보고 정리한 글입니다. [2장] 수와 집합 자연수, 정수, 유리수, 실수, 복소수, 사원수 연산과 수의 구조 수집합의 고유한 특징인 원소를 이용한 연산 : 덧셈, 뺄셈, 곱셈, 나눗셈 → 두 개의 원소를 사용해 새로운 원소를 만들어냄 : 이항연산 이항연산의 성질 : 같은 집합에 속한 두 수를 투입한 이항연산의 결과가 항상 투입한 집합에 속한다면, 그 이항연산은 해당 집합에 대해 닫혀 있다(Closure)고 함 교환 법칙 : 순서와 관계 없이 항상 동일한 결과 ex) a+b = b+a, a·b = b∙a 결합 법칙 : 연산이 두 번 이상 연속될 때, 앞의 연산을 먼저 계산한 결과와 뒤의 연산을 계산한 결과가 같음 ex) (a+b)+c = a+(b+c), (a∙b)∙c = a∙(..
문제 링크 1707번: 이분 그래프 풀이 이분 그래프란 두 집합이 있을 때 하나의 정점은 하나의 집합에 속해야 하는데, 인접한 정점은 같은 집합에 포함되면 안된다는 그래프이다. 주의할 점은 시작 정점에서 연결되지 않은 정점도 체크를 해줘야한다는 것. 테스트 케이스의 수만큼 입력을 받고, 각 테스트 케이스마다 인접 리스트를 초기화해준다. 무방향 그래프이기 때문에 입력 받은 두 정점을 양쪽에 다 넣어줘야한다. BFS를 시작할텐데 정점을 돌며 visit이 0인 (방문하지 않은 정점)일 경우 BFS를 시작해준다. 연결되지 않은 정점 체크를 위함이다. 다른 BFS문제와 같이 queue를 이용하는데, 현재 정점을 q에 넣고, visit도 집합 1로 설정해주며 q가 빌 때까지 반복한다. 다음 정점의 visit이 0이..
문제 링크 16928번: 뱀과 사다리 게임 풀이 BFS 문제 뱀과 사다리 입력을 받으며 인접리스트 adj를 초기화해준다. BFS를 시작한다. 주사위 횟수가 담기는 dist 배열을 INF로 초기화해준다. 이 때 INF는 주사위를 1로 돌려 100칸까지 가는 경우가 최대이기 때문에 101로 정의했다. 첫번째 칸부터 시작해서 queue가 빌 때까지 반복한다. adj[cur].size()가 0보다 큰 경우는 뱀이나 사다리를 타야하고, 아닌 경우는 주사위를 돌려야하기 때문에 경우를 나누어준다. 뱀이나 사다리가 있다면 인접 리스트를 확인해 다음 칸의 dist가 현재 칸의 dist보다 클 경우, 다음 칸을 작은 값으로 갱신해준 뒤 q에 넣어준다. 주사위를 돌릴 경우 1~6까지 주사위를 돌릴 수 있으므로 dist[ne..
문제 링크 11401번: 이항 계수 3 풀이 이항 계수의 식과, 페르마의 소정리, 모듈러 연산을 알아야 풀 수 있는 문제 보통 이항 계수 문제는 DP나 재귀로 풀 수 있는데 입력값이 너무 크기 때문에 시간 초과가 난다. 이런 경우 공식을 이용해 풀어야한다. 우리가 구해야 할 것은 이항 계수를 1000000007 (이하 mod)로 나눈 값이다. 해당 값을 바로 구할 수 있다면 좋겠지만 분수의 나머지 구하기는 힘들기 때문에 페르마의 소정리를 이용해야 한다. 페르마의 소정리란 p가 소수일 때, a^p를 p로 나눈 나머지가 a를 p로 나눈 나머지와 같다는 정리이다. 해당 식을 변형해서 맨 마지막 식까지 만들 수 있고 저 식을 우리가 구해야 하는 값의 공식에 적용할 것이다. 이항계수의 분자를 A, 분모를 B, 나..
문제 링크 16139번: 인간-컴퓨터 상호작용 풀이 각 알파벳마다 누적합을 구하는 문제 개행할 때 \n을 써주어야 하고, 누적합 구할 때 난 현재 인덱스부터 문자열 끝까지를 갱신해줬는데, 이렇게 하면 시간 초과가 나는 듯 하다. 입력받은 문자열 s를 하나씩 돌면서 각 알파벳의 누적합을 구해준다. 현재 인덱스의 a~z의 누적합을 갱신해주고, 현재 알파벳은 +1해준다. 질문을 입력 받으면서, stt-1이 0보다 작다면 alpha[c-'a'][end]를, 아니라면 alph[c-'a'][end] - alpha[c-'a'][stt-1]을 출력한다. 코드 #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); ..
문제 링크 14889번: 스타트와 링크 풀이 백트래킹 문제 먼저 팀은 두 개로 나누어지기 때문에 한 쪽 팀을 구하면 자동으로 다른 팀이 만들어진다. 그래서 n명의 사람 중에 n/2의 사람만 뽑으면 됨. 또한 순열이 아닌 조합이기 때문에 해당 팀에 그 사람이 있는지 확인하는 작업이 필요없이 바로 curIdx+1부터 뽑으면 된다.(왜냐면 그 전에 뽑힌 조합일 것이기 때문) 그렇게 func 함수로 team의 사이즈가 n/2가 될 때까지 뽑고, 다 뽑히면 각 팀의 능력치를 계산한다.(calculate) calculate 함수에서는, 0~n-1의 사람을 한 명씩 체크하면서, 다른 사람들을 체크한다. 해당하는 사람이 team에 있다면, 다른 선수도 그 team에 있어야 능력치를 더해주기 때문에 찾아주는 작업을 해준..
문제 링크 14888번: 연산자 끼워넣기 풀이 백트래킹문제 먼저 숫자가 담긴 arr와 연산자 oper를 입력받는다. func함수에서 DFS를 한다. 현재 인덱스인 curIdx가 arr.size()와 같다면 연산이 끝난 것이기 때문에 최댓값과 최솟값을 갱신한 후 return한다. 연산자를 하나씩 보면서 0보다 큰 경우 연산자를 사용(oper[i] -= 1)하고 재귀호출한다. 재귀호출시, 현재 인덱스는 +1해주고, 현재까지 연산값 curSum을 갱신해주어 넣는다. 해당 함수 호출이 끝나면 연산자는 원래대로 돌려놓아야 제대로 작동한다. 최댓값과 최솟값을 출력한다. 코드 #include #include #define INF 1000000001 using namespace std; int minAns = INF;..
문제 링크 1992번: 쿼드트리 풀이 분할 정복 문제 먼저 모두 같은지 확인하는 check함수로 해당 영역이 모두 같은 숫자라면 true, 아니라면 false를 return한다. 영역이 모두 같으면 answer에 해당 숫자를 추가한다. 아니라면 영역을 나눠주는데, (괄호를 먼저 추가하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순으로 재귀호출한다. 이 때 size는 반으로 줄여준다. 모든 호출이 끝나면 answer에 )괄호를 추가해준다. 코드 #include #include #include using namespace std; string answer = ""; bool check(vector &v, int size, int y, int x) { char c = v[y][x]; for (int ..
