프로그래밍/이산 수학20 경우의 수, 순열, 조합 조합론(Combinatorics) - 물건들을 여러 가지 형태로 그룹짓는 방법을 연구하는 학문이다. 경우의 수 - 어떤 시도(trial)를 통해 일어날 수 있는 사건(event)의 가짓수이다. 곱의 법칙 - 다중 for문이 예이다. 경우의 수가 늘어나서 시간 복잡도가 늘어난다. 합의 법칙 - for문이 여러 개인 코드가 예이다. 포함-배제 원리 - 중복되는 부분이 있다면 중복된 만큼의 수를 뺀다. 트리 - 노드와 가지로 구성되어 있는 자료구조이다. 데이터 저장 순서는 뿌리에서 시작해 가지를 따라 다른 노드로 진행된다. 노드(Node) - 어떤 데이터를 저장한다. 가지(Branch) - 어떤 노드에서 뻗어 나온 다른 노드를 연결시키는 줄기이다. 뿌리(Root) - 처음 시작하는 노드를 말한다. 순열(Per.. 2023. 1. 21. 벡터, 튜플, 행렬 벡터(Vector) - 힘의 방향과 크기를 나타낸다. 성분 표기법으로 나타낼 수 있다. v(2, 5) 여러 개의 성분으로 구성된 자료 구조이다. 한 개체의 특성을 담고 있는 정보라고 할 수 있다. 데이터의 형이 모두 같다. 데이터를 정형화된 형태로 저장할 수 있다. 단위 벡터(Unit Vector) - 길이가 1인 벡터이다. 길이가 1인 벡터를 모두 모아놓으면 원이 된다. 내적(Inner product) - 벡터의 곱셈 중 하나이다. 결과는 스칼라 값이다. dot product라고도 한다. 튜플(Tuple) - 데이터를 저장하는 것이다. 각각 데이터 형이 다를 수 있다. 데이터베이스의 데이터 한 줄이 보통 튜플이다. 집합과 벡터, 튜플은 다른 개념이다. 중복을 허용하고, 순서가 중요하다. 행렬(Matri.. 2023. 1. 17. 수학적 귀납법, 재귀 수학적 귀납법 - 모든 자연수 n에 대해 어떤 명제가 참임을 증명할 때 사용하는 것이다. 모순에 의한 증명과 더불어 가장 어려운 증명방법이다. 연역법의 한 종류이다. 재귀함수 설계에 도움을 줄 수 있다. 재귀 - 한 함수에서 자기 자신을 다시 호출해 작업을 수행하는 것이다. 동일한 문제를 조금 더 작은 단위로 해결함으로써 그 문제를 해결한다. 다중 분기 재귀 - 문제의 일부만 방문하는 것만으로 원하는 결과를 찾을 수 있다. 분할 정복 알고리즘의 영역이다. 분할 정복 - 문제의 영역을 여러 부분으로 나눈 뒤 한 부분씩 문제를 해결해 나가는 걸 반복한다. 시간 복잡도 - O(n) 이진 탐색 - 정렬되어 있는 데이터 집단에서 어떤 값을 찾을 때 유용한 알고리즘이다. 절반의 영역만 재귀적으로 탐색하면 답을 찾을.. 2023. 1. 15. 비트마스킹 a xor a = 모든 비트를 0으로 만든다. xor 3번하면 a, b 변수를 서로 바꿀 수 있다. a = a^b b = a^b a = a^b 2진수가 짝수인지 홀수인지 확인하려면 맨 마지막 비트(2^0 = 1) 이 1인지 확인하면 알 수 있다. 0이면 짝수, 1이면 홀수이다. 나머지 비트는 모두 짝수이다. 마스크 - 비트 필드에 대한 비트 연산을 할 때 사용하는 데이터이다. 비트 마스킹 - 마스크를 이용해서 특정 비트 값을 뽑아오거나 반전시키는 행위이다. 비트 마스킹을 통해 양수와 음수(0x80000000), 짝수와 홀수(0x1)를 확인할 수 있다. 비트 플래그 - 비트 필드가 여러개 모인 것을 의미한다. 1바이트의 경우 8개 상태를 저장할 수 있다. 각각 하나의 불리언처럼 사용한다. 적은 수의 비트로.. 2023. 1. 13. 이전 1 2 3 4 5 다음