Per ardua ad astra.

map(맵) 특징연관 컨테이너(Associative Container) 중 하나이다.연관 컨테이너에는 set, multiset, map, multimap 이 있다.string : int 형태로 값을 할당해야 할 때 맵을 사용한다.키(Key)와 값(Value) 형태로 이루어져 있고, 레드-블랙 트리(Red-Black Tree)라는 구조를 내장하고 있다.노드 기반으로 이루어져 있고, 균형 이진 트리 구조이다.pair 객체 형태로 키(Key)와 값(Value)이 저장된다.Key는 고유한 값이므로 중복이 불가능하다.중복 Key를 사용하려면 multimap을 사용하면 된다.삽입, 삭제, 탐색에 대해서 $O(logN)$ 정도의 시간 복잡도를 가진다.집합(Set)과 마찬가지로 삽입이 되면서 자동으로 정렬이 된다.데이..

문제 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워즈를 만들 때, 스타워즈 1, 스타워즈 2, 스타워즈 3, 스타워즈 4, 스타워즈 5, 스타워즈 6과 같이 이름을 지었고, 피터 잭슨은 반지의 제왕을 만들 때, 반지의 제왕 1, 반지의 제왕 2, 반지의 제왕 3과 같이 영화 제목을 지었다. 하지만 숌은 자신이 조지 루카스와 피터 잭슨을 뛰어넘는다는 것을 보여주기 위해서 영화 제목을 좀 다르게 만들기로 했다. 종말의 숫자란 어떤 수에 6이 적어도 3개이상 연속으로 들어가는 수를 말한다. 제일 작은 종말의 숫자는 666이고, 그 다음으로 큰 수는 1666, 2..

문제 지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다. 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다. 보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8..

이산 확률 변수 이산 확률 변수의 의미 동전을 두 번 던지는 게임에서 앞면이 나온 횟수를 `X` 로 나타내면, `X` 를 이용하여 앞면이 나온 횟수라는 특성에 따라 구분된 사건을 다음과 같이 간단히 표현할 수 있다. $$ \eqalign{ \{ HH \} &\Leftrightarrow X = 2 \\ \{ HT, TH \} &\Leftrightarrow X = 1 \\ \{ TT \} &\Leftrightarrow X = 0}$$ 그러므로 앞면이 나온 횟수인 `X` 는 아래와 같이 표본 공간 `S` 에서 실수 전체의 집합 `R` 로의 함수로 생각할 수 있다. 이 때 앞면이 나온 횟수인 `X` 를 확률 변수(Random Variable)라고 한다. 확률 변수(Random Variable) 표본 공간 `S`..

동치 관계와 부분 순서 관계 관계 `R` 이 어떤 성질을 갖느냐에 따라 관계에 의미를 부여하여 그 의미에 따라 관계의 순서쌍을 구성하는 원소들을 활용할 수 있다. 관계에 부여되는 의미에는 동치 관계나 부분 순서 관계가 있는데, 동치 관계의 경우 그 관계의 순서쌍을 구성하는 원소들이 같은 의미라는 것을 뜻하며, 부분 순서 관계의 경우는 그 관계의 순서쌍을 구성하는 원소들 사이에 순서가 존재한다는 것을 뜻한다. 동치 관계(Equivalence Relation) 반사 관계, 대칭 관계, 추이 관계가 모두 성립하는 관계 동치는 표현이 달라도 의미가 같아서 동등하게 사용할 수 있음을 의미한다. 예) 10진수 $7_{10}$ 과 2진수 $111_{2}$ 이 표현은 다르지만 같은 값으로 사용되므로 동치라고 할 수 있..

관계의 폐포 학번을 입력하면 학생의 이름을 비롯한 학생의 기타 정보를 검색할 수 있는 시스템이 있다고 하자. 하지만, 이 시스템은 등록된 전체 학생 중 재학생만 검색할 수 있다. 이 시스템에서 휴학생의 정보도 검색할 수 있으려면 휴학생의 학번과 정보도 추가해야할 것이다. 이처럼 자료 집합에 필요한 원소를 추가하여 특정 조건을 만족하도록 만드는 것을 관계의 폐포라고 한다. 관계의 폐포(Closure) 집합 `A` 에 대한 관계를 `R` 이라 하고 관계 `R` 이 가져야 하는 성질을 `P` 라고 할 때, 관계 `R` 을 포함하면서 성질 `P` 를 갖는 가장 작은 집합 `A` 에 대한 관계 `S` 성질 `P` 를 갖지 않는 관계 `R` 이 성질 `P`를 갖도록 순서쌍을 추가할 때는 반드시 필요한 최소한의 순서..

pair(페어)와 tuple(튜플) pair(페어)개념사용자가 지정한 2개의 타입의 데이터를 저장하기 위해 사용되는 클래스서로 연관된 2개의 데이터를 한 쌍으로 묶어서 다룰 때 사용하면 편리하다.구조체(struct) 대신 편리하게 2개의 데이터를 관리할 수 있다. 헤더 파일페어(pair)를 사용하려면 다음의 헤더를 불러와야 한다.#include 하지만, , 헤더를 사용할 경우, 헤더가 포함되어 있어 따로 불러와 주지 않아도 된다.#include // 헤더 포함#include // 헤더 포함 형태페어(pair)의 형태는 다음과 같다. template struct pair;T1에 첫 번째 인자를, T2에 두 번째 인자를 넣어주면 된다. 사용 방법초기화다음과 같이 페어(pair)를 초기..

문제 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩치가 각각 (x, y), (p, q)라고 할 때 x > p 그리고 y > q 이라면 우리는 A의 덩치가 B의 덩치보다 "더 크다"고 말한다. 예를 들어 어떤 A, B 두 사람의 덩치가 각각 (56, 177), (45, 165) 라고 한다면 A의 덩치가 B보다 큰 셈이 된다. 그런데 서로 다른 덩치끼리 크기를 정할 수 없는 경우도 있다. 예를 들어 두 사람 C와 D의 덩치가 각각 (45, 181), (55, 173)이라면 몸무게는 D가 C보다 더 무겁고, 키는 C가 더 크므로, "덩치"로만 볼..

문제 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다. 자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 출력 첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다. 예제 입력 1 216 예제 출력 1 198 출처 ICPC > Regionals > Asia ..

문제 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다. 한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다. 김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다. 이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다. N장의 카드에 써져 있는 숫자가 주어졌을 때, ..

브루트 포스(Brute Force) 개념 브루트(Brute)와 포스(Force)가 결합되어 만들어진 단어이며, "난폭한 힘(폭력)" 이라는 뜻이다. 문제 해결을 위해 오래 걸리고 자원이 많이 들어서 무식하다고 생각될 수도 있지만, 항상 100%의 정확성을 보인다. 정답(Solution)이 발견될 때까지 가능한 모든 선택지를 찾는 방법이다. 예) 4자리 숫자의 패스워드를 찾기 위해 0000부터 9999까지 하나씩 입력하여 찾아보는 경우 따라서 브루트 포스 알고리즘은 완전 탐색 알고리즘이라고 할 수 있다. 간단하고 일관적이지만, 매우 느리다는 단점이 있다. 거의 완벽하게 병렬 작업이 가능하여 병렬 프로그래밍에서 사용된다. 패턴 매칭(Pattern Matching) 등의 작업에 사용될 수 있다. 너비 우선 탐..

하노이 탑(Tower of Hanoi) 개념 프랑스의 수학자 에두아르 뤼카(François Édouard Anatole Lucas)가 1883년 소개한 유명한 문제 재귀(Recursion)를 연습하는데 도움이 되는 알고리즘 다음과 같이 3개의 막대와 N개의 원판(Disk)이 있을 때, 원판을 다음의 순서를 지키면서 A에서 C로 옮기는 작업 각 원판의 크기는 모두 다르다. 원판의 크기는 아래에서부터 위로 갈수로 점점 작아진다. ① 한 번에 하나의 원판만 이동한다. ② 맨 위에 있는 원판만 이동한다. ③ 크기가 작은 원판 위에 큰 원판을 쌓을 수 없다. 이 조건에서 다음을 구하는 것이 하노이 탑의 문제가 된다. ① 최소의 이동 횟수로 옮기는 가짓수 ($2^{N} - 1$) ② 최소의 이동 횟수로 옮길 때, ..

문제 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다. 아래 그림은 원판이 5개인 경우의 예시이다. 입력 첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다. 출력 첫째 줄에 옮긴 횟수 K를 출력한다. 두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈..

문제 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다. *** * * *** N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다. 입력 첫째 줄에 $N$이 주어진다. $N$은 3의 거듭제곱이다. 즉 어떤 정수 $k$에 대해 $N=3^k$이며, 이때 $1 ≤ k < 8$이다. 출력 첫째 줄부터 N번째 줄까지 별을 출력한다. 예제 입력 1 27 예제 출력 1 ***************..

문제 오늘도 서준이는 병합 정렬 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. N개의 서로 다른 양의 정수가 저장된 배열 A가 있다. 병합 정렬로 배열 A를 오름차순 정렬할 경우 배열 A에 K 번째 저장되는 수를 구해서 우리 서준이를 도와주자. 크기가 N인 배열에 대한 병합 정렬 의사 코드는 다음과 같다. merge_sort(A[p..r]) { # A[p..r]을 오름차순 정렬한다. if (p < r) then { q

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 (추가 시간 없음) 1024 MB (추가 메모리 없음) 4810 2613 2251 56.887% 문제 정휘는 후배들이 재귀 함수를 잘 다루는 재귀의 귀재인지 알아보기 위해 재귀 함수와 관련된 문제를 출제하기로 했다. 팰린드롬이란, 앞에서부터 읽었을 때와 뒤에서부터 읽었을 때가 같은 문자열을 말한다. 팰린드롬의 예시로 AAA, ABBA, ABABA 등이 있고, 팰린드롬이 아닌 문자열의 예시로 ABCA, PALINDROME 등이 있다. 어떤 문자열이 팰린드롬인지 판별하는 문제는 재귀 함수를 이용해 쉽게 해결할 수 있다. 아래 코드의 isPalindrome 함수는 주어진 문자열이 팰린드롬이면 1, 팰린드롬이 아니면 0을 반환하는 함수다. #incl..

문제 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 $F_{n} = F_{n-1} + F_{n-2} (n ≥ 2)$ 가 된다. `n=17` 일때 까지 피보나치 수를 써보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 `n`이 주어졌을 때, `n`번째 피보나치 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 `n`이 주어진다. `n`은 20보다 작거나 같은 자연수 또는 0이다. 출력 첫째 줄에 n번째 피보나치 수를 출력한다. 예제 입력 1 10 예제 출력 1 55 알고리즘 분류..

문제 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 정수 N(0 ≤ N ≤ 12)이 주어진다. 출력 첫째 줄에 N!을 출력한다. 예제 입력 1 10 예제 출력 1 3628800 예제 입력 2 0 예제 출력 2 1 알고리즘 분류 수하 구현 집합론 문제 출처 https://www.acmicpc.net/problem/10872 10872번: 팩토리얼 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net 문제 해결 방법 재귀 함수를 이용하여 팩토리얼을 구현하였다. 0!와 1!는 1임을 주의한다. int factorial(int n) { if (n N; cout

lower_bound(), upper_bound() ; 이진 탐색(Binary Search) 소개이진 탐색(Binary Search)으로 원소를 탐색하는 함수시간 복잡도가 $O(\log_{2} N)$ 으로, 빠른 속도로 탐색을 수행할 수 있다.탐색을 진행할 컨테이너는 반드시 오름차순으로 정렬되어 있어야 한다. 필요한 헤더#include  형식찾은 값(val)의 주소를 Iterator 형으로 반환한다.lower_bound(ForwardIterator first, ForwardIterator last, const T& val)lower_bound(ForwardIterator first, ForwardIterator last, const T& val) lower_bound()찾으려는 키 값보다 크거나 같은(이..

문제 수직선 위에 $N$ 개의 좌표 $X_{1}, X_{2}, ..., X_{N}$이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. $X_{i}$를 좌표 압축한 결과 $X'_{i}$의 값은 $X_{i} > X_{j}$를 만족하는 서로 다른 좌표의 개수와 같아야 한다. $X_{1}, X_{2}, ..., X_{N}$에 좌표 압축을 적용한 결과 $X'_{1}, X'_{2}, ..., X'_{N}$를 출력해보자. 입력 첫째 줄에 $N$이 주어진다. 둘째 줄에는 공백 한 칸으로 구분된 $X_{1}, X_{2}, ..., X_{N}$이 주어진다. 출력 첫째 줄에 $X'_{1}, X'_{2}, ..., X'_{N}$을 공백 한 칸으로 구분해서 출력한다. 제한 $1 ≤ N ≤ 1,000,000$ $-10^{9} ≤..

문제 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 온라인 저지 회원의 수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄부터 N개의 줄에는 각 회원의 나이와 이름이 공백으로 구분되어 주어진다. 나이는 1보다 크거나 같으며, 200보다 작거나 같은 정수이고, 이름은 알파벳 대소문자로 이루어져 있고, 길이가 100보다 작거나 같은 문자열이다. 입력은 가입한 순서로 주어진다. 출력 첫째 줄부터 총 N개의 줄에 걸쳐 온라인 저지 회원을 나이 순, 나이가 같으면 가입한 순으로 한 줄에 한 명씩 나이와 이름을 공백으로 구분해 출력한다. 예제..

문제 알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오. 길이가 짧은 것부터 길이가 같으면 사전 순으로 입력 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. 출력 조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다. 예제 입력 1 13 but i wont hesitate no more no more it cannot wait im yours 예제 출력 1 i im it no but more wait wont yours cannot hesitate..

베이즈 정리 확률이 0이 아닌 사건들 $A_{1}, A_{2}, \cdots, A_{n}$ 이 어떤 사건 `B` 의 발생에 원인이 된다고 하자. 이 때, 주어진 사건 $A_{i}, \; i = 1, 2, \cdots, n$ 의 조건부 확률을 이용하여 사건 `B` 가 발생할 확률을 구할 수 있다. 또한 사건 `B` 가 발생했을 때, 사건 `B` 의 발생 요인들 중에서 어느 특정한 요인이 작용할 확률을 구할 수 있다. 전확률 공식(Formula of Total Probability) 확률이 0이 아닌 사건 $A_{1}, A_{2}, \cdots, A_{n}$ 을 표본 공간 `S` 의 분할이라 하면, 임의의 사건 `B` 의 확률은 다음과 같다. $$P(B) = \sum_{i=1}^{n}P(A_{i})P(B|A..

조건부 확률 어떤 제한된 조건 아래에서 확률을 계산해야 할 경우가 있다. 예) 내일 비가 오든지 그렇지 않든지 관계 없이 모레 비가 올 확률을 구하는 경우와 내일 비가 온다는 전제 조건 아래에서 모레 비가 올 확률은 다르게 나타난다. 조건부 확률의 정의 통계학 교과목을 수강하는 50명의 학생이 아래와 같이 구성되었을 때, 담당 교수가 이 학생들 중에서 임의로 선정한 학생이 2학년 남학생일 확률을 구한다고 하자. 구분 1학년 2학년 3학년 합계 남학생 22 6 3 32 여학생 13 4 2 16 합계 35 10 5 50 이 확률을 구하기 위해 선정된 학생이 남학생인 사건을 `A`, 선정된 학생이 2학년인 사건을 `B` 라고 하면 다음을 얻을 수있다. $$P(A) = \frac{32}{50}, \quad P(..

확률 확률의 의미 동전 하나를 던져서 앞면이 나올 가능성을 알아보자. 동전을 던져서 나올 수 있는 모든 경우는 앞면(`H`)과 뒷면(`T`) 뿐이다. 동전을 던지는 실험에서 표본 공간은 $S = \{ H, T \}$ 이고, 앞면이 나오는 사건은 $A = \{ H \}$ 로 나타낼 수 있다. 이 때, `H` 와 `T` 가 모두 같은 정도로 나온다고 가정하면 사건 `A` 가 일어날 가능성은 $\frac{1}{2}$ 라고 추측할 수 있다. 그리고 이러한 추측에는 동전이 공정하다는 전제 조건(앞면과 뒷면이 나올 가능성이 동등하다)이 필요하다. 그러면 사건 `A` 가 일어날 가능성인 숫자 $\frac{1}{2}$ 에 대해, 분모의 숫자 2는 표본 공간 안의 원소의 개수이고, 분자의 숫자 1은 사건 `A` 안에 있..

시행과 사건 동전 던지기나 주사위 던지기 등과 같은 어떤 통계적 실험을 실시할 때 나타날 수 있는 모든 경우에 대해, 특정한 실험 결과로 구성된 집합을 사건이라고 한다. 따라서 확률론에서 사용하는 용어인 사건은 집합의 개념과 동일하다. 시행(Trial) 동일한 조건 아래서 반복할 수 있으며, 그 결과가 우연에 의해 달라질 수 있는 실험 또는 관찰 동전을 던져서 앞면이 나오면 `H`, 뒷면이 나오면 `T`라고 할 때, 동전을 두 번 반복하여 던진다면 나올 수 있는 모든 경우는 $\{ HH, HT, TH, TT \}$ 뿐이다. 그리고 주사위를 한 번 던진다면 나올 수 있는 모든 경우는 $1, 2, 3, 4, 5, 6$ 뿐이다. 이와 같이 동일한 조건 아래에서 동전이나 주사위를 몇 번이고 반복하여 던질 수 있..

합성 관계 2개 이상의 관계를 이용해 새로운 관계를 만드는 것을 '관계를 합성한다'고 하고, 이렇게 만든 관계를 합성 관계라고 한다. 합성 관계(Composite Relation : $S \circ R$) 집합 `A` 에서 집합 `B` 로의 관계 `R` 과 집합 `B` 에서 집합 `C` 로의 관계 `S` 가 있을 때, 이 두 관계를 이용해 구하는 집합 `A` 에서 집합 `C` 로의 관계 $$S \circ R = \{(a, c) ∈ A \times C \; | \; a ∈ A, \; b ∈ B, \; c ∈ C, \; (a, b) ∈ R, \; (b, c) ∈ S \}$$ 합성 관계를 구하려면 둘 이상의 관계 사이에 공통으로 사용되는 자료 집합이 있어야 한다. 예 수강과목 담당교수 정보 학번 과목코드 교수..

관계의 성질 하나의 집합에 대한 관계의 경우, 순서쌍 원소의 구성에 따라 관계의 성질을 판별할 수 있다. 관계의 성질에는 반사, 비반사, 대칭, 반대칭, 추이 5가지가 있다. 반사 관계와 비반사 관계 반사 관계(Reflexive Relation) 집합 `A` 에 대한 관계 `R` 이 있을 때, 모든 $a ∈ A$ 에 대해 $(a, a) ∈ R$ 인 관계 ($Δ_{A} = \{ (a, a) \; | \; a ∈ A \}$) 비반사 관계(Irreflexive Relation) 집합 `A` 에 대한 관계 `R` 이 있을 때, 모든 $a ∈ A$ 에 대해 $(a, a) \not ∈ R$ 인 관계 집합 `A` 에 대한 관계 `R` 이 반사 관계이려면, 집합 `A` 에 포함되는 모든 원소 `a` 에 대해 자기 자신..

문제 2차원 평면 위의 점 N개가 주어진다. 좌표를 y좌표가 증가하는 순으로, y좌표가 같으면 x좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 `x_{i}`와 `y_{i}`가 주어진다. (-100,000 ≤ `x_{i}`, `y_{i}` ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. 출력 첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다. 예제 입력 1 5 0 4 1 2 1 -1 2 2 3 3 예제 출력 1 1 -1 1 2 2 2 3 3 0 4 알고리즘 분류 정렬 문제 출처 https://www.acmicpc.net/problem/11651..

관계의 표현 관계는 일반적으로 순서쌍의 집합으로 표현하지만, 이 외에도 화살표 선도, 좌표 도표, 관계 행렬, 방향 그래프 등 여러 가지 방식으로 표현할 수 있다. 화살표 선도를 이용한 관계 표기 화살표 선도(Arrow Diagram) 집합 `A` 에서 집합 `B` 로 가는 관계 `R` 이 있을 때, 두 집합의 원소 간의 관계를 화살표로 나타낸 도표 화살표 선도에서 화살표의 방향은 관계에 포함되는 순서쌍의 앞에 오는 원소에서 시작하여 뒤에 오는 원소로 향하도록 한다. 역관계의 경우, 관계 `R` 의 화살표 선도와 화살표 방향이 반대이다. 좌표 도표를 이용한 관계 표기 좌표 도표(Coordinate Diagram) 집합 `A` 에서 집합 `B` 로 가는 관계 `R` 이 있을 때, 집합 `A` (정의역)의 ..