THINK-PRO BLOG

authentication: 인증

누군가 자신을 A라고 말하고 있을 때 그것이 사실인지 확인하는 과정.

authorization: 권한 부여

A라는 사람이 특정한 일을 하려고 할 때 (특정 장소로 가려고 하거나, 원하는 정보를 얻도록 할 때) 그것을 허용하는 행위.

completeness: 모든 정답 사례를 찾아낼 수 있다.

soundness: 어떠한 오답 사례도 정답 사례라고 잘못 판단하지 않는다. 

true/false positive/negative 개념을 동원하면 이해하기가 비교적 쉽다.

true positive = 참이라고 예측했고 실제로도 참인 경우

false positive = 참이라고 예측했으나 실제로는 거짓인 경우

false negative = 거짓이라고 예측했으나 실제로는 참인 경우

true negative = 거짓이라고 예측했고 실제로도 거짓인 경우

예를 들어 보자.

A B C D E F 라는 사람이 있고, A B C 는 거짓말 쟁이고, D E F는 보통 사람이라고 하자.

그리고 우리는 보통 사람을 찾아내는 알고리즘을 구현해야 한다.

우리가 만든 알고리즘이 completeness를 만족한다면 그 알고리즘은 반드시 D E F 에 대해서 보통 사람이라고 이야기한다. 하지만 이것이  A B C가 거짓말 쟁이임을 말하지는 않는다. 즉, completeness를 만족하지만 soundness를 만족하지 않았다면 A B C 중 최소 한 명 이상을 평범한 사람이라고 잘못 지적한 것이다. (false positive)

우리가 만든 알고리즘이 soundness를 만족한다면 그 알고리즘은 A B C를 평범한 사람이라고 잘못 지적하지는 않는다. 만약 soundness는 만족하지만 completeness를 만족하지 않는다면, A B C 에 대해서는 거짓말 쟁이임을 잘 찾아내지만, D E F 중에서 최소 한 명을 거짓말 쟁이라고 잘못 판단하게 될 것이다. (false negative)

따라서, completeness와 soundness를 전부 만족한다면, 어떠한 false 결정도 하지 않게 된다.

completeness 만족 & soundness 만족 => D E F 보통 사람 / A B C 거짓말 쟁이 (완벽하게 모든 사례 정답!)

completeness 만족 & soundness 불만족 => A D E F 보통 사람 / B C 거짓말 쟁이 (이 경우 A가 false positive)

completeness 불만족 & soundness 만족 => E F 보통 사람 / A B C D 거짓말 쟁이 (이 경우 D가 false negative)

문제 출처: https://www.acmicpc.net/problem/9078

문제

주어진 숫자 열을 정렬하는데, 사용할 수 있는 연산은 이웃하는 두 숫자를 다른 두 수 사이나 숫자열의 맨 앞 혹은 맨 뒤에 끼워 넣는 것 뿐이다. 즉, 한 번에 숫자를 하나씩 옮기는 것이 아니라, 이웃하는 숫자를 두 개씩 묶어서 옮긴다. 4 1 5 3 2의 경우 다음과 같이 정렬할 수 있다.

4 1 5 3 2 → 3 2 4 1 5 → 3 4 1 2 5 → 1 2 3 4 5

그러나 2 1 3의 경우에는 어떻게 하더라도 정렬할 수 없다.

이와 같이 입력으로 1에서 N까지의 서로 다른 N의 정수로 구성된 숫자 열이 주어졌을 때, 그것이 위의 연산만으로 정렬가능한지 여부를 결정하는 프로그램을 작성하시오.

입력

입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스는 두 줄로 이루어져 있다. 첫째 줄에는 정수 N(1 ≤ N ≤ 100)이 주어지고, 둘째 줄에는 N개의 정수가 공백을 사이에 두고 주어진다.

출력

각 테스트 케이스에 대해서 정렬 가능하면 YES를, 아니면 NO를 한 줄에 하나씩 출력한다.

내 해답: https://github.com/jeongmincha/solving-algorithm/blob/master/BOJ/9078.py

설명

이미 정렬 가능한 배열 = A (예를 들어 12)가 있다고 가정했을 때, 이후에 원소를 2개 추가한다고 했을 때, 그 추가되는 두 개의 숫자도 이미 정렬되어 있어야만 새로운 배열의 정답이 YES가 됩니다.
(예를 들어 12 배열에 3,4를 추가한다면->1234, 3412, 3124, 즉 3과 4는 어떤 곳에 위치하든 정렬된 상태여야만 합니다)

여기서 count 변수를 각 배열의 원소 뒤에 오는 다른 원소의 크기 비교를 한 값을 전부 합한 sum값이라고 합시다.
1. 1234의 경우
34가 뒤에 추가되었으나 count가 변하지 않음.
2. 3412의 경우
34가 앞에 추가되었으므로 count가 +4 (3이 12보다 크므로 +2, 4가 12보다 크므로 +2해서 총 +4)
3. 3124의 경우
3이 앞에 추가되었으므로 count가 +2 (3이 12보다 크므로 +2, 4는 뒤에 왔으므로 count 변화 없음)

즉, 기존에 이미 정렬 가능한 배열에서 새로운 원소를 추가시킬 때마다 count의 변화는 짝수로 변하게 됨.

참고로 위 사례에서는 12와 같이 짝수개의 원소 배열부터 시작했지만, 123과 같이 홀수개의 원소 배열에서 출발하더라도 같은 논리를 도출하게 됨. 또한, 태초에 12나 123같은 정렬된 배열에 대해서 count값은 0을 가지므로 어떠한 길이의 배열도 count가 짝수여야 YES가 됨.

블로그 백업중... https://jeongmincha.github.io/posts/00007/ 로 이동