분류 전체보기
-
알고리즘 - 최대공약수(GCD)와 최소공배수(LCM)study/알고리즘 2021. 2. 4. 23:06
최대공약수(GCD) 공통적인 약수 중 최댓값, 최대공약수가 1이면 서로소이다. def gcd(a, b): ret = 0 for i in range(min(a, b)):# 1부터 체크 if a % i == 0 and b % i == 0: ret = i return ret; a의 공약수는 a보다 작고, b의 공약수는 b보다 작으므로 최소값 까지만 구하면 되기 때문에 min(a, b)까지 검사 def gcd(a, b): ret = 0 for i in range(min(a, b), 0, -1):# min(a, b)부터 체크 if a % i == 0 and b % i == 0: return i 역방향으로 진행하면 O(1)만에 끝나는 경우가 있다. 유클리드 호제법 GCD(A, B) = GCD(B, A % B) de..
-
[백준 1629] 곱셈 python (수학)study/PS 2021. 2. 4. 22:49
자연수 A를 B번 곱한수를 만들고 이를 C로 나눈값을 출력하면 된다. A ** B % C 하면 될 것 같지만 시간 복잡도 O(B)이기 때문에 시간 초과한다... 매우 크게.. 이때 이진수를 활용하면 빠르게 풀이 할 수 있다. 아이디어 : 거듭제곱은 거듭제곱 간의 곱으로 표현 가능하다. A^13이라는 값을 이진수로 표현하면 A^1101이 되는데 1101 / 2 => 110 ... 1 110 / 2 => 11 ... 0 11 / 2 => 1 ... 1 1 / 2 => 0 ... 1 이렇게 2로 나누면 나머지가 원래 가지고 있던 이진수가 됨을 알 수 있다. A^13 = A * A^4 * A^8 조건문 + N진수 변환 방법으로 해결 가능하다는 것을 알 수 있다. def answer(a, b): ret = 1 w..
-
[1] IP주소에 대하여..study/네트워크 2021. 1. 2. 17:02
IP는 인터넷 프로토콜(Internet Protocol)의 약자로 네트워킹이 가능한 장비를 식별하는 주소이다. 각 장치들의 주민등록번호라 생각하면 쉽다. IPv4와 IPv6 두 가지 체계가 있는데 IPv4를 사용하는 기기가 전 세계적으로 많아짐에 따라 주소가 부족한 상황이 발생하여 이를 해결하고자 IPv6를 도입하기 시작하였다. IPv4 널리 사용되는 IP주소로 32비트의 값을 가진다. 8비트씩 끊어 이를 0~255의 10진수 숫자로 나타내며, 각 숫자는 마침표(.)로 구분한다. 총 32비트의 정보를 가질 수 있기 때문에 최대 2^32개, 약 43억 개의 고유한 주소를 부여할 수 있다. 예전에는 IP를 할당할 때 Class를 나누어 할당하였는데, 처음에는 주로 Class-B (128.0.0.1~191.2..
-
[0] 네트워크는 무엇인가?study/네트워크 2021. 1. 2. 16:22
네트워크는 Net+Work의 합성, 통신망이라 한다. 전자신호를 통해 통신하는 모든 기기가 서로 통신하기 위해 만든 하나의 망을 의미한다. 즉 어떤 연결을 통해 컴퓨터의 자원을 공유하는 것 국제 전기 전자공학회 (IEEE) 정의 네트워크는 전송방식, 연결형태, 망의 규모, 통신 방법, 서비스로 분류된다. 전송방식 : 아날로그, 디지털 연결형태 : 선형, 성형, 버스형, 트리형, 그물형, 혼합형 등.. 망의 규모 PAN ( Personal Area Network ) : 가장 작은 규모의 네트워크 (ex: 블루투스) LAN ( Local Area Network ) : 근거리 영역 네트워크근거리 통신 망을 의미하며 지역적 좁은 범위 내에서 고속 통신이 가능한 통신망. (ex: wifi) Man ( Metrop..
-
[백준 1309] 동물원 C++ (DP, 다차원)study/PS 2020. 2. 21. 16:02
다이나믹 프로그래밍으로 풀이가 가능한 대표적인 문제입니다. 일차원 배열을 사용하여 풀이할 수 있지만, 이차원 배열을 사용하여 풀이하는 방법도 존재합니다. 코드 #include using namespace std; const int mod = 9901; int n; int d[100010][4]; // d[n][m] = n은 2*n배열에 사자를 배치하는 경우의 수 // m은 배치 방식(배치x, 왼쪽, 오른쪽) int main(void) { scanf("%d", &n); d[1][1] = 1; //배치 x d[1][2] = 1; //왼쪽 배치 d[1][3] = 1; //오른쪽 배치 for (int i = 2; i
-
알고리즘 - 다이나믹 프로그래밍 (Dynamic Programming)study/알고리즘 2020. 2. 10. 17:03
알고리즘 풀이를 하다보면 많은 문제가 다이나믹 프로그래밍(DP)를 이용해 풀이가 가능합니다. 그렇기 때문에 알고리즘을 공부하기 위해서는 꼭 알아가야 하는 파트입니다. 다이나믹 프로그래밍은 동적 계획법으로도 불리는데, 어떤 문제가 여러 단계의 반복되는 부분 문제로 이루어지면 각 단계의 부분 문제에 대한 답을 기반으로 하여 전체 문제의 답을 구하는 방법 입니다. 정리하자면 큰 문제를 작은 문제들로 쪼개어 푸는 알고리즘이라 생각하면 됩니다. TMI - 다이나믹 프로그래밍의 이름은 알고리즘의 고안자인 리차드 벨만이 Dynamic이란 말이 멋있어서 붙였다고 합니다. 문제를 다이나믹 프로그래밍을 사용하여 풀기 위해서는 2가지 속성을 만족해야합니다. Overlapping Subproblem (부분 문제 반복) Opt..