Per ardua ad astra.

문제 호석이는 불면증에 걸렸다. 그래서 잠이 안 올 때의 민간요법 중 하나인 양 세기를 하려고 한다. 호석이는 1번 양부터 순서대로 세는 것이 재미없을 것 같아서 N의 배수 번호인 양을 세기로 하였다. 즉, 첫 번째에는 N번 양을 세고, 두 번째에는 2N번 양, … , k번째에는 kN번 양을 센다. 이렇게 숫자를 세던 호석이에게 잠은 더 오지 않고 다음과 같은 궁금증이 생겼다. 이전에 셌던 번호들의 각 자리수에서 0에서 9까지의 모든 숫자를 보는 것은 최소 몇 번 양을 센 시점일까? 예를 들어 N = 1295이라고 하자. 첫 번째로 N = 1295번 양을 센다. 현재 본 숫자는 1, 2, 5, 9이다. 두 번째로 2N = 2590번 양을 센다. 현재 본 숫자는 0, 2, 5, 9이다. 현재까지 본 숫자는..

문제 스도쿠는 숫자퍼즐로, 가로 9칸 세로 9칸으로 이루어져 있는 표에 1 부터 9 까지의 숫자를 채워넣는 퍼즐이다. 같은 줄에 1 에서 9 까지의 숫자를 한번씩만 넣고, 3 x 3 크기의 작은 격자 또한, 1 에서 9 까지의 숫자가 겹치지 않아야 한다. 입력으로 9 X 9 크기의 스도쿠 퍼즐의 숫자들이 주어졌을 때, 위와 같이 겹치는 숫자가 없을 경우, 1을 정답으로 출력하고 그렇지 않을 경우 0 을 출력한다. 제약 사항 1. 퍼즐은 모두 숫자로 채워진 상태로 주어진다. 2. 입력으로 주어지는 퍼즐의 모든 숫자는 1 이상 9 이하의 정수이다. 입력 입력은 첫 줄에 총 테스트 케이스의 개수 T가 온다. 다음 줄부터 각 테스트 케이스가 주어진다. 테스트 케이스는 9 x 9 크기의 퍼즐의 데이터이다. 출력 ..

문제 총 N개의 문자열로 이루어진 집합 S가 주어진다. 입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어진다. 입력으로 주어지는 문자열은 알파벳 소문자로만 이루어져 있으며, 길이는 500을 넘지 않는다. 집합 S에 같은 문자열이 여러 번 주어지는 경우는 없다. 출력 첫째 줄에 M개의 문자열 중에 총 몇 개가 집합 S에 포함되어 있는지 출력한다. 예제 입력 1 5 11 baekjoononlinejudge startlin..

문제 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이..

multiset(중복 집합) 특징연관 컨테이너(Associative Container) 중 하나이다.연관 컨테이너에는 set, multiset, map, multimap 이 있다.set과 비슷하지만, 중복된 키(Key)를 넣을 수 있다는 차이점이 있다.삽입된 요소들은 기본적으로 오름차순(less)으로 정렬된다. 헤더 파일multiset을 사용하려면 다음의 헤더 파일을 불러와야 한다.#include  멤버 함수 사용 방법set과 사용 방법이 비슷하다.바로가기 : https://dev-astra.tistory.com/247 [C++] set(집합)set(집합) 특징 연관 컨테이너(Associative Container) 중 하나이다. 연관 컨테이너에는 set, multiset, map, multimap 이 ..

set(집합) 특징연관 컨테이너(Associative Container) 중 하나이다.연관 컨테이너에는 set, multiset, map, multimap 이 있다.특정 순서에 따라 고유한 요소를 저장하는 컨테이너이다.기본적으로 요소들은 오름차순(less)으로 정렬되어 삽입된다.중복되는 요소는 없고, 오로지 희소한(Unique) 값만 저장된다.map과 거의 동일하지만, set은 map과 다르게 키(Key)와 값(Value)이 같다고 생각하면 된다.키(Key)라 불리는 요소들의 집합으로 이루어진 컨테이너라고 생각하면 된다.노드 기반 컨테이너이며, 균형 이진 트리로 구현되어 있다.이터레이터(Iterator)는 자동으로 중위 순회(Inordered Traversal)를 통하여 순서대로 키(Key)를 출력한다...

집합의 분할 인공지능에서 지식의 자원이 되는 데이터를 관리하려면 일정한 기준으로 전체 데이터를 분류하는 과정이 필요하다. 이 과정을 통해 분류한 데이터 집합은 반드시 하나 이상의 데이터를 포함해야 하고, 데이터 집합을 모두 합쳤을 때는 제외된 데이터가 없어야 한다. 또한 분류한 집합 사이에 공통으로 포함되는 데이터가 존재하지 않아야 한다. 이렇게 보유한 데이터를 정확하게 분류해서 관리해야 인공지능이 쓸데없는 추론 과정을 수행하지 않으면서 정확한 정보를 추론할 수 있다. 이러한 인공지능의 데이터 관리에 적용할 수 있는 개념이 집합의 분할이다. 분할(Partition : $A = \{A_{1}, A_{2}, \cdots, A_{n} \}$ ) 공집합이 아닌 임의의 집합 $A$ 를 서로소이면서 공집합이 아닌 ..

집합의 대수 법칙 수에 대한 사칙 연산에도 일정한 규칙이 있듯이, 집합 연산에도 일정한 규칙이 있다. 이를 집합의 대수 법칙이라고 하는데, 대수 법칙을 이용하면 복잡한 집합 연산을 간단히 할 수 있다. 집합의 대수 법칙 집합 연산 법칙 $A ∪ \varnothing = A$ $A ∩ U = A$ 항등 법칙(Identity Law) $A ∪ U = U$ $A ∩ \varnothing = \varnothing$ 지배 법칙(Domination Law) $A ∪ A = A$ $A ∩ A = A$ 멱등 법칙(Idempotent Law) $A ∪ B = B ∪ A$ $A ∩ B = B ∩ A$ 교환 법칙(Commutative Law) $A ∪ (B ∪ C) = (A ∪ B) ∪ C$ $A ∩ (B ∩ C) = (A..

집합의 연산 집합과 집합의 연산을 통해 새로운 집합을 구할 수 있다. 합집합과 교집합 합집합(Union : $A ∪ B$ ) 집합 `A` 와 `B` 에 모두 속하거나 둘 중 한 집합에만 속하는 원소들로 이루어진 집합 $$A ∪ B = \{ x \; | \; x ∈ A \lor x ∈ B \}$$ 합집합은 두 집합에 포함된 원소들을 모두 합쳐서 새로운 집합을 만드는 연산으로, 두 집합에 공통으로 존재하는 원소는 한 번만 작성한다. 예) $A = \{1, 2, 3, 4, 5 \}, \; B = \{4, 5, 6, 7 \}$ 일 때, $A ∪ B = \{ 1, 2, 3, 4, 5, 6, 7 \}$ 교집합(Intersection: $A ∩ B$ ) 집합 `A` 와 `B` 에 모두에 속하는 원소들로 이루어진 집합..

집합의 종류 집합은 구성되는 원소의 개수나 집합 간의 포함 관계에 따라 명칭이 정의된다. 전체 집합(Universal Set : $U$ ) 논의 대상이 되는 원소 전체를 포함하는 집합 전체 집합은 논의 대상에 따라 달라질 수 있으므로, 주어지는 문제에 따라 달라질 수 있다. 예) 집합 $A = \{ a \; | \; a > 13, \; a ∈ \mathbb{N} \}$ 가 주어질 때, 문제에 따라 집합 `A` 에 대한 전체 집합은 자연수 집합 $\mathbb{N}$ 이 될 수 있고, 집합 `A` 자체가 될 수 있다. 그러므로 전체 집합에 대한 판단은 문제에 따라 달라진다. 공집합(Empty Set : $\varnothing$ ) 원소를 하나도 포함하지 않는 집합으로 기수가 0인 집합 ($|\varnoth..

집합의 개념 컴퓨터가 활용하려는 데이터들은 정리되어 있지 않으면 효용 가치가 없다. 그렇기 때문에 컴퓨터에서 데이터를 효율적이고 효과적으로 활용하기 위해서는 기준에 따라 데이터를 정리하여 관리할 필요가 있다. 이 때 필요한 개념이 집합이다. 집합(Set : $A, B, C, \cdots$) 명확한 기준에 따라 공통 성질을 가지며 중복되지 않는 원소(Element, Member)의 모임 ① 유한 집합(Finite Set) : 집합을 구성하는 원소의 개수가 유한개인 집합 ② 무한 집합(Infinite Set) : 집합을 구성하는 원소의 개수가 무한히 많은 집합 집합은 공통 성질을 가지며, 중복되지 않는 원소로 구성된다. 그러므로 집합에 포함되는 원소들을 구분할 수 있는 명확한 기준이 있어야 하는데, 이 기준..

집합 집합은 확률과 통계를 학습하는 데 있어 기본적으로 필요한 개념이므로 집합에 대한 기본적인 개념과 성질에 대한 이해가 필요하다. 집합(Set) 집합(Set) : 주어진 조건에 대해서 그 대상을 명확하게 구별할 수 있는 모임 원소(Element) : 집합을 구성하는 대상들 보편적으로 집합은 대문자 알파벳 `A, B` 등으로 나타내고, 원소는 소문자 알파벳 `a, b` 등으로 나타낸다. 집합 `A` 의 원소를 `a, b, c` 라고 할 때, 원소 `a` 가 집합 `A` 에 포함될 경우 `a ∈ A` 와 같이 나타내고, 그렇지 않을 경우 `a \notin A` 로 나타낸다. ※ '집합' 을 향하도록 삼지창을 그린다. 집합의 표현 ① 원소 나열법(Tabular Form) 모든 원소를 나열하는 방법 예) `A..