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/ 로 이동

| 맥북에 괜찮은 마우스 어디 없을까?

  맥북에 괜찮은 마우스 어디 없을까? 이런 생각으로 시작된 마우스 찾기... 저는 매직마우스는 예전에 몇 번 써봐서 이왕이면 새로운 것에 도전해보고자 매직마우스는 사지 않기로 했습니다. 그러면 애플 브랜드가 아닌 마우스를 사야 할텐데... 어떤 브랜드의 마우스를 사야 할까?? 이런 생각을 가지고 있었는데, 결국 저는 '로지텍' 회사를 선택하기로 했습니다. 물론 로지텍 회사가 몇몇 제품들에 대해서는 욕을 먹고 있는 경우도 많은데요. 대부분 맥에서 쓸 마우스로 애플의 매직 마우스가 아닌 다른 마우스를 써야 한다면 거의 무조건 '로지텍' 마우스를 선택하시더라구요~

  그래서 저도... 로지텍 마우스로 선택하였습니다!

  문제는... 로지텍 마우스에서도 Mac OS X을 지원하는 제품들이 정말 많더라는 것입니다... 저는 '무선 마우스'여야 한다는 점과 여러 가지 기능 키가 '커스터마이징' 될 수 있어야 한다는 점이 중요했습니다. (Mac OS X의 수려한 제스처를 마우스에서도 사용해야 했거든요 :) ) 엄청난 고민과 연구(?) 끝에 저는 두 가지 모델로 선택폭을 줄였습니다... m705 vs m557 둘 중에 선택하겠다고 다짐을 한 것이죠. 

| m705 vs m557, 둘 중에 누가 더 좋을까?

●  m705는 무한 스크롤이 가능하다는 점과 사람 손에 특화된 디자인이 장점으로 있는 반면 단점은 USB 리시버를 사용해야 하고, 가격이 비교적 더 비싸다는 점이었습니다. 

● m557은 가격이 더 저렴하고 더 앙증맞은 디자인을 갖추고 있으며 블루투스 기능을 사용하여 리시버를 쓸 필요가 없다는 장점을 가지고 있으나, 성인 남자에게 너무 작지 않느냐하는 점이 단점으로 떠올랐습니다.

  저는 리시버의 유무는 크게 신경쓰지 않았지만, 결국 m557로 선택하게 되었습니다. 왜냐하면, Mac OS X에서 사용할 것이므로 무한 스크롤 기능이 오히려 역효과가 날 것(Mac OS X에서는 마우스 가속 기능이 있으므로 무한 스크롤을 쓰다보면 걷잡을 수 없는 무한 스크롤 속도가 나올 것이므로 더 안 좋을 것이다.)과 그리고 가격 차이가 맘에 걸렸고, 왠지 맥과 더 어울리는 앙증맞은 마우스를 써보고 싶다는 생각 때문이었습니다.

| m557, 맥북에서 활용 가능한가?

  m557은 맥북에서 활용이 쉽게 잘될까요? 솔직히 말해서 이게 저의 제일 큰 화두이겠죠. 맥에서 마우스를 잘 쓰기 위해서는 마우스 제조회사 자체의 소프트웨어가 맥을 지원해주고, 그로 인해 마우스 감도에 대한 불편함이나, Mac OS 의 수려한 제스처 기능을 손쉽게 접근할 수 있는지가 중요한 것인데, m557은 이 모든 것을 만족해줍니다. 

  아시다시피, 로지텍의 지원 소프트웨어를 설치하지 않으시면 마우스 감도도 엉망, 거기다가 마우스 특별한 버튼들(윈도우 버튼이라던지... 앞으로/뒤로 가기 제스처 라던지..)이 사용조차 안됩니다! 반드시 로지텍 지원 소프트웨어를 까세요! 아래에 로지텍 m557 지원 소프트웨어 다운로드 링크를 걸어드렸습니다. :)

► http://www.logitech.com/ko-kr/support/bluetooth-mouse-m557?section=downloads&bit=&osid=36

  그리고, 로지텍 지원 소프트웨어를 자세히 살펴보면 다음과 같이 손쉽게 커스터마이징이 가능함을 아실 수 있습니다.

Scroll direction > Standard(윈도우처럼), Natural(맥처럼)

Secondary click > Right/Left Mouse click

Tilt Wheel (스크롤 휠을 왼쪽 오른쪽으로 움직일 떄) > Move between pages(앞으로/뒤로 가기), Move between full-screen apps(데스크탑 전환하기), Horizontal Scrolling(수평 스크롤링)

Wheel Button (스크롤 휠 자체를 클릭할 때) > Smart Zoom, Mission Control, App Exposé, Launchpad, Look up, Middle Button

Center Button (윈도우 로고가 있는 버튼을 클릭할 때) >  Smart Zoom, Mission Control, App Exposé, Launchpad, Look up, Middle Button

위와 같이 커스터마이징이 가능합니다. 여러분이 원하시는데로 마음대로 커스터마이징하면 애플 매직마우스 뺨 치는... 제스처 접근이 가능하실거에요...! :)

| 너무 작지 않을까? m557?

  참고로 저는 성인 남자입니다만, 손이 되게 작습니다. 성인 여자보다 약간 큰 수준이거나 비슷한 정도입니다. 그렇게 생각하시고 손 착용(??) 샷 보여드리도록 하겠습니다. 혹시, 성인 남자분들 혹은 손 큰 성인 여자분들, 너무 작지 않을까? 하는 생각에 망설이기도 하실 거 같은데요. 그 고민 제가 어느 정도...? 덜어드릴 수 있으면 좋겠습니다.

※ 사진이 너무 작다고 생각하시면 클릭해주시면 기본 크기로 나옵니다.

※ 혹시 제 손에서 조차도 작다고 생각하신다면 일반적인 성인 남자들에게 확실히 작은 겁니다. 제가 손이 남자 치고 작은 편이에요!! 

※ 그래도 그립감은 꽤 발군입니다. 제 작은 손조차도 가득 채우지는 못하지만, 가득 채운다고 무조건 그립감이 좋은건 아니더라구요 :)

마우스의 엉덩이(?)가 손바닥에는 닿입니다. 그렇기 때문인지 그렇게 작아서 불편하다는 걸 느끼진 못했네요

| 결론... 전반적으로 괜찮은거 같다!

  솔직히 제가 맘에 들었으니까 포스팅한거 아니겠어요? ㅋㅋㅋ 여러분은 맘에 안드는 제품 이렇게 정성스레(?) 사진도 찍고 정리도 하고 하시겠습니까? 그렇습니다. 저한테는 너무나도 맘에 드네요. 다만, 블루투스 마우스 대부분이 그렇듯, 마우스 크기가 작게 나오니까, 반드시 손에 차는 마우스만 살 거야! 이러시는 분은 구매를 보류해주세요 ^^ 

  마우스 크기가 크게 문제가 안된다면, 정말 구매를 추천드립니다. 저 뭐 로지텍에서 부탁받은 거 아닌데.. 그냥 추천 막 하고 싶네요. 그만큼 제가 잘 쓰고 있고 너무나도 만족하는 제품입니다! 

그렇다면 한 번에 인접한 메모리를 할당하려고 한다면 어떻게 해야 할까?

이 포스트에서, C언어로 다차원 배열을 할당하는 경우 메모리를 인접하게 할당하는 방법에 대해서 다룰 것이다.

| 일반적인 코딩 방법

우리는 일반적으로 다차원 배열을 동적으로 할당할 때, 다음과 같이 코딩을 한다.

 int rows = 2;
 int columns = 5;
 int i=0, j=0;

 int ** matrix = (int**) malloc(rows*sizeof(int*));

 for(i=0; i<rows; i++){
         matrix[i] = (int*)malloc(columns * sizeof(int));
 }

그런데, 이렇게 해버리면 다음과 같이 결과가 나타난다.

▲ [0][4] 원소와 [1][0] 원소 사이에 16바이트 갭이 생겼다.

첫 번째 행의 마지막 원소와 두 번째 행의 첫번쨰 원소의 주소가 int 변수의 크기인 4 byte만큼 차이가 나는 것이 아니라 16 byte가 차이난다. (위 숫자들은 전부 16진수임을 알기를 바란다. 40에서 50으로 갔음은 10바이트가 아니라 16바이트가 차이났음을 의미한다.)

이제, 해결책에 대해서 알아보자.

2차원 배열에 인접한 메모리를 할당하는 두 가지 접근 방법이 있다. 첫 번째 기법은 '바깥쪽' 배열을 먼저 할당한 후 전체 열에 대한 메모리를 할당하는 방법이고, 두 번째 기법은 모든 메모리를 한 번에 할당하는 방법이다. 

| 첫 번째 방법

첫 번째 기법을 다음 예제 코드에서 설명하고 있다. 첫 번째 malloc 함수 호출로 정수에 대한 포인터의 배열을 할당한다. 각 요소는 열에 대한 포인터를 가지게 된다. 두 번째 malloc 함수 호출은 우리가 선언할 다차원 배열의 제일 첫 번째 원소의 주소에 모든 요소에 대한 메모리를 할당하게 된다. (말이 어렵다면, 그냥 배열의 이름에다가 이후에 저장할 모든 메모리의 크기를 한 번에 할당한다고 생각하자.) 그리고 for 루프는 첫 번째 배열의 각 요소에 두 번째 malloc에서 할당한 메모리의 일부분을 지정한다.

int rows = 2;
int columns = 5;
int i=0, j=0;

int ** matrix = (int**)malloc(rows*sizeof(int*));
matrix[0] = (int*)malloc(rows*columns*sizeof(int));
for(i=1; i<rows; i++)
        matrix[i] = matrix[0] + i*columns;

엄밀히 따지면, 첫 번째 배열의 메모리는 배열의 '본체(body)' 부분과 떨어져 있을 수도 있다. 하지만 배열의 본체 부분에서는 메모리의 인접한 영역이 할당된다. 

▲ 배열의 모든 요소들이 인접하게 나열됬다.

| 두 번째 방법

다음 예제 코드에서는 두 번째 기법을 설명하고 있다. 

int * matrix = (int*)malloc(rows*columns*sizeof(int));

결과는 다음과 같다.

나중에 코드 안에서 이 배열을 참조할 때는 배열 첨자를 사용할 수 없다. 대신, 다음 코드에서 설명하는 것처럼 배열에 대한 인덱스를 수동으로 계산해야 한다. 각 배열 요소는 그 인덱스의 곱으로 초기화한다. (컴파일러가 배열 첨자를 허용할 때 필요한 배열의 형태에 대한 정보가 없으므로 배열 첨자를 사용할 수 없기 때문에 배열 첨자를 사용할 수 없는 것이다.)

int i=0, j=0;

for(i=0; i<rows;i++){
        for(j=0; j<columns; j++){
                *(matrix+(i*columns)+j) = i*j;
        }       
} 

2차원 배열에 대한 인접한 메모리를 할당하는 두 가지 일반적인 접근 방법에 대해 설명했다. 어떤 방법을 이용할 것인지는 어플리케이션에 따라 다르다. 하지만 두 번째 접근 방법이 '전체'배열에 대한 단일 메모리 블록을 생성한다.