목록2024/03 (38)
넘치게 채우기
만일 m이 a-b를 나눌 때, a와 b가 모듈러 m에 대해 합동이다. 특히, a를 m으로 나눈 나머지가 r이면, a와 r는 모듈러 m에 대해 합동이다. 이떄, 나머지 r은 0 = 1이고 gcd(a, m) = g를 만족한다고 하자. 만일 g !| b이면, 합동방정식 은 해를 가지지 않는다. 만일 g | b이면, 합동방정식 정확히 g개의 서로 다른 해를 가진다. 모든 해를 찾으려면, 우선 일차방정식 au + mv = g의 해 (u0, v0)을 찾는다. x0 = cu/g가 의 해가 되고, 모든 합동이 아닌 해는 과 같이 나타낼 수 있다. 주의 선형 합동방정식 정리에서 가장 중요한 경우는 gcd(a, m) = 1인 경우이다. 이 경우, 합동방정식은 단 하나의 해를 가진다. 고차 합동방정식 고차 합동방정식도 수론..
https://leetcode.com/problems/intersection-of-two-arrays/description/ Leetcode - Intersection of Two Arrays 문제 유형 : 해시, 그리디 문제 난이도 : Easy 문제 Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order. 두 정수배열 nums1과 nums2가 주어진다. 교차점을 반환하시오. 결과의 각 요소는 값이 겹치면 안되고, 순서는 상관없습니다. 풀이 해시맵에 nums1의 요소..
통신 및 네트워크 개요 통신을 한다는 것은, 정보다 네이터를 공유하는 것이다. 네트워크란? 네트워크(network): 상호 연결이 가능한 통신 장치의 집합체이다. 통신 장비란 컴퓨터, 데스크톱, 스마트iot장치, 스마트폰, 스마트워치 등의 호스트(host)도 있고, 이외에도 라우터, 스위치, 모뎀 등의 연결 장치(connectiong device)도 있다. 네트워크의 평가기준은 다음과 같다: 성능(performance) - 전달시간, 응답시간 등. 흔히 처리율(throughtput)과 지연(delay)이라는 두 가지 척도로 평가된다. 신뢰성(reliability) - 고장의 빈도수, 해결시간, 안정성 등.. 보안(security) - 데이터 보호, 정책, 침해나 손실시 복구절차 등. 네트워크의 종류 LA..
2 이상의 정수 p의 약수가 1과 p 뿐일 때, p를 소수(prime number)라고 부른다. 2 이상의 소수가 아닌 수를 합성수(composite number)라고 부른다. 소수 p가 곱 ab를 나눈다고 가정하자. 그러면 p는 a를 나누거나, b를 나눈다. (또는 a와 b 모두 나눈다.) 증명) p가 곱 ab를 나눈다고 하자. 만일 p가 a를 나눈다면 증명이 끝나므로, 나누지 않는다고 가정하면, gcd(p, a)가 어떤 수인지 생각해야 한다. 이 수는 p를 나누므로, 1 또는 p이다. p가 a를 나누지 않으므로, p는 1이다. 6장의 정리를 이용하여, px + ay = 1에서 양변에 b를 곱한다. pbx + aby = b pbx는 p로 나누어지고, p가 ab를 나누므로, aby 역시 p로 나누어진다...
https://leetcode.com/problems/minimum-common-value/description/ Leetcode - Minimum Common Value 문제 유형 : 그리디, 투포인터 문제 난이도 : Easy 문제 Given two integer arrays nums1 and nums2, sorted in non-decreasing order, return the minimum integer common to both arrays. If there is no common integer amongst nums1 and nums2, return -1. Note that an integer is said to be common to nums1 and nums2 if both arrays h..
두 개의 정수 a, b가 주어졌을 때, a의 배수와 b의 배수로 만들 수 있는 수를 모두 찾아보자. 다시말해, ax + by에서 x와 y에 대입해 만들 수 있는 수를 찾아보자. a=42, b = 30으로 해보자. x = -3 x = -2 x = -1 x = 0 x = 1 x = 2 x = 3 y = -3 -216 -174 -132 -90 -48 -6 36 y = -2 -186 -144 -102 -60 -18 24 66 y = -1 -156 -114 -72 -30 12 54 96 0 -126 -84 -42 0 42 84 126 y = 1 -96 -54 -12 30 72 114 156 y = 2 -66 -24 18 60 102 144 186 y = 3 -36 6 48 90 132 174 216 표의 수들이 ..
https://leetcode.com/problems/count-elements-with-maximum-frequency/description/ Leetcode - Count Elements With Maximum Frequency 문제 유형 : 해시, 그리디 문제 난이도 : Easy 문제 You are given an array nums consisting of positive integers. Return the total frequencies of elements in nums such that those elements all have the maximum frequency. The frequency of an element is the number of occurrences of that ele..
인 정수 m과 n이 있다고 해보자. 만일 n이 m의 배수라면, n=mk를 만족한다면, 'm이 n을 나눈다'라고 한다. 만일 m이 n을 나누면 우리는 m|n이라고 쓴다. n을 나누는 수를 n의 약수라고 부른다. 만일 우리가 두 개의 정수를 가지고 있다면, 우리는 이 두 정수를 모두 나누는 공약수(common divisor)를 찾을 수 있다. 모두 0은 아닌 두 수 a와 b의 최대공약수는 a와 b를 모두 나누는 수 중에서 가장 큰 수이다. 기호로는 gcd(a, b)로 표기한다. 만일 gcd(a, b) = 1일때, 우리는 'a와 b는 서로소이다'라고 한다. 최대공약수를 찾는 가장 효율적인 방법은 유클리드 호제법(Euclidian algorithm)이다. 이 방법은 나머지가 0이 되도록 나눗셈을 반복하는 것이다..
https://leetcode.com/problems/middle-of-the-linked-list/description/ Leetcode - Middle of the Linked List 문제 유형 : 연결리스트, 투포인터 문제 난이도 : Easy 문제 Given the head of a singly linked list, return the middle node of the linked list. If there are two middle nodes, return the second middle node. 단순 연결리스트의 헤드가 주어진다. 중간 노드를 반환하라. 두 개의 중앙 노드가 있다면, 두 번째 중앙 노드를 반환하라. 풀이 투 포인터를 이용해서 풀어주면 된다. 두 칸씩 이동하는 fast 한 칸..
우리는 앞장에서 방정식 이 여러 개의 정수해를 갖는다는 것을 확인하였다. 그렇다면 지수가 2보다 큰 수일 경우에는 어떨까? 은 0이 아닌 정수해를 가질 수 있을까? 답은 '아니오'이다. 1673년즈음, 페르마는 지수가 4인 경우를 증명했고, 18세기와 19세기, 가우스와 오일러는 지수가 3인 경우를 증명했고, 디리클레와 르장드르는 지수가 5인 경우를 다루었다. 이는 페르마의 마지막 정리(Fermat's last theorem)으로 알려져 있다. 세제곱수를 두 개의 세제곱수로, 네제곱수를 두 개의 네제곱수로 쪼개는 것은 불가능하다. 혹은 일반적으로 n-제곱수를 두 개의 n-제곱수로 나누는 것은 불가능한 일이다. 나는 이에 대해 놀라운 증명을 발견했지만, 이를 남기기에는 여백이 부족하다. - 페르마 페르마의..