THINK-PRO BLOG

문제 출처: 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/ 로 이동

이 에러와 관련해서 이미 여러 블로그 포스팅이 있지만

한글로 된 포스팅 중에서 내 문제를 해결해준 경우는 없었다.

통상적으로 docker를 깔고 난 후

바로 docker ps 명령어 등을 하였을 때도 에러 없이 잘 나온다고 하면 다행인 것이지만,

Cannot connect to the Docker daemon at unix:///var/run/docker.sock. Is the docker daemon running?

혹은

Cannot connect to the Docker daemon at tcp:///localhost:2375. Is the docker daemon running?

와 같은 문제가 발생할 수 있다.

이 경우 아래 명령어들을 다 한 번씩 시도해보면 좋다.

우선, tcp localhost 2375가 나온다고 하면 DOCKER_HOST 환경변수가 알게 모르게 세팅되어 있는 경우가 있다. WSL 환경에서 도커를 세팅하고자 한다면 localhost:2375에 연결해두어야 하지만, 순수한 우분투 환경이라면 그렇게 하지 않아도 된다. 따라서 아래 명령어로 환경변수를 제거한다. 

unset DOCKER_HOST
unset DOCKER_TLS_VERIFY
unset DOCKER_TLS_PATH

위 명령어를 수행한 후에 다시금 "docker ps" 를 실행해보자. 그렇게 하면 적어도 tcp 에러가 아니라 unix~~ 에러로 변경되었을 것이다. 이때 해결이 그냥 잘되었으면 끝.

이제 at unix:///var/.... 까지 왔다면 그 다음에는 dockerd 명령어를 실행해보거나 아니면 status restart를 해보면 된다.

다른 블로그에서는 그냥 systemctl start랑 enable을 하라고 하지만, 이미 잘 켜져 있는 상태에서는 의미가 없다.

나의 경우 start와 enable로는 해결이 안되었지만 restart로는 해결이 되었다.

$ sudo dockerd

혹은

$ sudo service docker restart

git clone XXX 를 할 때, 

Cloning into '...' ...
fatal: unable to access 'XXX': Problem with the SSL CA cert (path? access rights?)

와 같은 문제가 발생하곤 한다.

이러한 문제를 해결하기 위해서는

cacert.pem 파일을 다운로드 받고 (https://curl.haxx.se/docs/caextract.html) 혹은 아래의 wget 명령어를 이용한다.

그리고 해당 파일을 ~/.ssh 등에 옮긴다. 다른 곳에 옮겨도 되지만, 여기서는 ~/.ssh에 옮겨두겠다.

wget https://curl.haxx.se/ca/cacert.pem
mv cacert.pem ~/.ssh

cacert.pem 파일을 확보했다면 해당 파일의 주소를 기억하고, 아래의 명령어를 입력한다.

~/.ssh가 아닌 다른 곳에 파일을 복사해두었다면 그 주소로 변경해야 한다.

git config --global http.sslBackend "openssl"
git config --global http.sslCAInfo ~/.ssh/cacert.pem

일반적으로 변수를 상수화시킬 떄 사용하는 예약어로 const키워드를 사용하곤 한다. 그런데, const키워드를 클래스의 멤버함수와 객체에도 사용할 수 있다. 이 경우 어떻게 사용되는지 알아보도록 하자.

1. const 멤버함수

멤버함수에 const를 사용하는 이유는 객체의 멤버변수를 변경시킬 수 없도록 하기 위해서이다.

예를 들어, Get함수의 경우 일반적으로는 private 멤버변수를 반환하는 역할만 하지, 그 멤버변수를 수정하는 일은 절대 없어야 한다.

위와 같이 GetX, GetY 함수는 단순히 private member 변수인 x_, y_의 값을 반환하기만 할 뿐 그 값을 수정하거나 변경하는 일이 없다. 따라서 이러한 함수에는 const키워드를 붙여주는 것이 옳다.

const 키워드가 붙은 const 멤버함수는 객체의 멤버변수를 변경할 수 없는 읽기 전용 함수가 된다. 또한 const 멤버함수는 const로 지정되지 않은 다른 멤버 함수를 호출할 수 없다. 왜냐하면 읽기 전용으로 지정된 const멤버함수에서 const로 지정되지 않은 멤버함수를 호출하게 되면 간접적으로 객체의 멤버변수를 변경시킬수도 있기 때문이다. 

따라서, 앞으로 GetX, GetY와 같은 함수는 const 멤버함수로 선언하는 것이 바람직하다. (그러지 않아도 컴파일 에러는 발생하지 않지만, 코드를 좀 더 견고하고 안전하게 만들기 위해서 필요한 키워드인 것이다.)

참고로 생성자와 소멸자는 const 예약어를 사용할 수 없다. 생성자와 소멸자는 항상 객체의 데이터를 변경시켜야 하기 때문이다.

2. const 객체

멤버변수나 멤버함수 뿐만 아니라 객체에도 const 키워드를 사용할 수 있다. 객체 생성시에 const 키워드를 사용하면, 그 객체는 상수로 취급되어 초기화된 데이터 외의 다른 데이터로 변경할 수 없다. 

위와 같은 코드는 컴파일 에러를 발생시킨다. 왜냐하면 SetX, SetY의 멤버함수에서 x_, y_ 멤버 변수값을 변경하려고 하기 때문이다. const키워드가 붙은 객체 인스턴스는 그 멤버변수의 값이 변경되지 않는다.

이러한 논리로 보건대, const 객체는 당연하게도 const 멤버함수만을 제대로 사용할 수 있다. const키워드가 없는 멤버함수는 멤버 변수의 값을 변경할 가능성이 있기 때문에, 호출을 시도하더라도 대부분은 컴파일 에러가 날 것이다.

c++언어에서는 인라인 함수라는 것을 제공한다. 인라인이라는 의미는 코드 라인 자체가 안으로 들어간다는 뜻. 즉, 함수의 내용을 호출을 통해서 실행시키는 것이 아니라, 호출하는 코드 자체가 함수 내용의 코드가 되는 효과가 된다는 점이다. 바로 이해한 사람도 있겠지만 아닐 수도 있으니, 예를 들자면...

와 같은 코드가 다음과 같이 바뀌게 된다는 뜻이다.

눈치챘는가? 인라인 함수는 성능 향상을 위한 것이다. 물론 이렇게 바꿈으로써 실행 코드가 늘어날 수 있다는 단점이 있다. 따라서 인라인 함수는 코드는 작지만(1~3줄 정도) 자주 호출되지 않는 경우에 주로 사용하는 것이 좋다.

| 인라인 함수의 장점

인라인함수는 #define 매크로와 기능이 유사하지만, 인라인 함수만의 장점이 있다.

| 인라인 함수의 단점

인라인 함수를 사용함으로써 성능의 향상과 매크로의 부작용을 해결할 수 있다고 하지만, 인라인 함수를 너무 남발하게 되면 실행 코드 자체가 커지게 되는 단점이 있다. 그리고 인라인 함수의 모토는 1~3줄 정도의 짧은 코드를 함수화시킴으로써 효율성의 낭비를 막고자 함이었는데, 코드가 5줄 이상이 되어버린다면 굳이 인라인 함수를 사용할 이유가 없다. 

switch문과 if문의 성능에 대해서 이야기를 하는 시간을 가져보고자 합니다.

프로그래밍을 배우다 보면 선택문을 사용해야 할 때 if문을 사용하거나 switch문을 사용합니다.

물론 switch문을 쓸 수 있는 경우는 전부 if문으로 대체 가능합니다만,

if문으로 가능한 것들 중 switch문으로 구현 불가능한 경우도 있죠.

이번 포스팅에서는 switch문과 if문 모두 가능한 경우에 대해서 따져보고자 합니다.

(당연한 이야기겠죠... 두 개 동시 사용 가능한 경우에 대해서 이런 논의가 의미가 있는 것이죠)

그리고, 단순히 고수준 언어의 측면에서 보기보단 ISA의 관점에서 풀어서 포스팅을 해보고자 합니다.

따라서, 특정 고수준 언어에 대해서는 이 포스팅의 내용이 옳지 않을수도 있습니다.

왜냐하면 고수준 언어들은 더욱 복잡한 컴파일러에 귀속되어 있는데, 

그 언어의 컴파일러가 어떠한 방식으로 instruction set (혹은 기계어나 어셈블리어)를 만들어가는지는 언어마다 다르기 때문입니다.

제가 공부한 ISA인 MIPS에는 branch statement와 jump statement가 있습니다.

branch statement는 레지스터 2개를 비교해서(혹은 레지스터와 상수를 비교해서) 특정 메모리 번지로 이동할 것이냐 말것이냐?를 결정합니다. 

jump statement는 즉시 특정 메모리 번지로 이동하는 기능을 합니다.

그리고 if문은 branch statement에 기반을 두고 있고,

switch문은 jump statement에 기반을 두고 있습니다.

왜냐하면, if문은 조건이 만족하면 실행/만족하지 않으면 무시 (실행을 할 것이냐 말것이냐?)

switch문은 입력된 값을 보고 특정 위치로 점프 (어떤 코드를 실행할 것이냐?)

switch문은 "점프테이블"을 만들고 switch문의 입력값으로 받은 변수 값만큼 점프 테이블 내에서 이동하면 됩니다.

if문보다 훨씬 쉽네요? 점프 테이블만 만들수 있다면 말이죠.

대충 이 정도 이야기를 하면 어느 정도 눈치를 채셨을 수도 있는데,

if-else문은 각 조건마다 그 조건 처리할수 있게 레지스터를 변경해주는 그런 인스트럭션들이 먼저 선행되야 합니다. 각 조건마다.

그런데, switch문은 점프 테이블을 만들기만 하면 조건이 몇개든 훨씬 빠르고 쉽게 넘어갈 수 있어요.

다만 점프 테이블을 만드는 오버헤드가 있는거죠.