여기 참조

개요

SK인터넷과 SK TV가 결합된 상품을 쓰고있는데,

이거말고 내가 익숙한 iptime 공유기를 메인으로 쓰고 싶다.

근데 아파트 벽에서 나오는 인터넷선으로 iptime 공유기 설정을 해보니, 외부 IP주소가 실제 외부IP주소가 아니라 192.168.55.51 이렇게 내부 주소로 나오는게 문제



헤딩과정

먼저 192.168.55.51이라는 IP가 보이니 http://192.168.55.1 로 접속을 시도해 보았다.

그랬더니 아래와 같은 공유기 설정화면에 진입 성공


여기서 암호는, 거실에 있는 공유기가 아닌, 벽속 단자함에 있는 공유기에 붙어있는 WAN뒤에 6자리_admin을 해야 로그인 가능했다(여기서 시간 많이 소요, 여기 참조해서 해결)

그러면 로그인이 되기는 하는데, 거실에 있는 H734G가 아닌 단자함에 있는 H614G로 로그인된다.


그럼 거실에 있는 H734G에 접속하는방법은?
해당 공유기에 wifi를 잡거나 랜선을 꼽은 다음 192.168.35.1을 치면 된다(iptime 공유기에 붙은상태에서는 안됨에 주의!)

이거는 당연히 벽속 단자함이 아닌 거실에 있는 공유기의 스티커를 보고 비번을 작성해서 치면된다. (유선MAC뒷자리6자리_admin)



다시 벽속 H614G설정으로 돌아와서.. UI를 보다보면 다음 화면을 볼 수 있다.
51번이 iptime공유기이고, 210번이 H734G임을 알 수 있고, 각각 LAN1과 LAN2에 물려있음을 알수 있고,
H734G의 경우 AP로 잡혀있음을 볼 수 있다.

정리하면
벽속 H614G의 경우 192.168.55.X 대역을 사용하며, 그 아래에 iptime공유기와 거실의H734G공유기가 있는데
iptime은 자체적으로 192.168.0.X대역을 사용하고,
H734G는 자체적으로 192.168.35.X 대역을 사용한다.

결론

H614G의 WAN모드를 NAT가 아닌 브릿지로 설정하면 문제가 해결된다.
이유는 여기에 자세히 나왔으니 읽어보시길



반응형

유용한 byobu 명령어

세로 split: Ctrl + F2

pane 전환: Shift + 화살표 

pane rotation: Ctrl + F3, Ctrl + F4

window탭이름수정: F8

 

유용한 tmux 명령어

(prefix가 Ctal + A라고 가정)

세로 split: ctrl + A, %

가로 split: Ctrl + A, |

pane 전환: Ctrl + A, 화살표

pane resize: Ctrl + A, Ctal + 화살표

window 순서를 Ctrl+좌우화살표로 바꾸기위해 다음 명령어 입력
Ctrl + A, :, bind-key -n C-Left swap-window -t -1
Ctrl + A, :, bind-key -n C-Right swap-window -t +1
 
만약 위의 키바인딩을 취소하고 싶으면, 다음과 같은 식으로 하면 된다. 
Ctal _ A, :, unbind-key -n C-Left 

그런데 C-[의 경우는 ESC키와 간섭이 있으므로 사용하지 말것!

반응형

'Programming > Linux' 카테고리의 다른 글

X Window System(X11) - 여러 호스트에서 ssh로 붙어서 사용하기  (0) 2021.01.08
Ansible  (1) 2020.10.22
vim  (0) 2020.09.20
리눅스 퍼미션 개념(파일 권한 관련)  (0) 2020.04.10
NTP설정  (0) 2020.03.30

virtualenv 관련해서는여기 참조

파이선환경

The ecosystem consisting of your particular installed version of python

plus all the third-party packages (“libraries”) it can access (and their precise versions)


requirements.txt

필요한 이유: 배포하고 나서 필요한 package들을 명시하기 위함



프로젝트 만드는 입장에서 requirements.txt 생성하기

$ pip freeze 하면 가상환경에서 현재까지 pip install된 라이브러리 목록이 버전과 함께 나열된다.


$ pip freeze > requirements.txt 하면 requirements.txt가 생성된다.

가상환경을 사용한 경우 이게 첨에는 아무것도 없을 수 있다.

여기에 뭔가 설치하고 나서(예를 들면 pip install numpy) 다시 해보면 나타나게 된다.

라이브러라(타 프로젝트) 사용하는 입장에서 필요한 모듈(필요한 버전으로) 설치하기

requirements.txt가 있는 경우 pip install -r requirements.txt를 통해 필요 모듈 설치

없는 경우 pip install numpy와 같은 방법으로 하나씩 설치(numpy module을 설치하고 싶다고 했을 때)

이때 설치되는 모듈들은 해당 virtual environment 안에서만 깔린다.

반응형

'Programming > Python' 카테고리의 다른 글

python 한글 스트링 인코딩 핸들링  (0) 2021.11.30
Python GUI Programming(Tkinter)  (0) 2021.01.02
Google Colab(Colaboratory Lab) 팁  (0) 2019.03.07
python array (indexing and slicing)  (0) 2019.02.28
pudb  (0) 2018.11.15

초기세팅

~/.vimrc 파일을 아래와 같이 편집

" search
set hlsearch  " highlights all search patterns
set ignorecase
set smartcase  " if you type, '/Copyright' it will be case sensitive

" auto indent
set autoindent     " 새로운 줄 시작시 이전줄의 들여쓰기를 복사
set cindent
set smarttab       " tab누르면 공백들이 대신 들어감(들여쓰기할때만)
set smartindent    " 중괄호나 주석등에 반응하여 들여쓰기 조정
set showmatch      " 중괄호등 짝보여주고 이동 가능

" tab size
set tabstop=4      " how many columns vim will use to print tab
set shiftwidth=4   " vim use when you hit >> or vim does auto indenting
set softtabstop=4  " vim use when you hit tab in insert mode
set expandtab      " tab will be converted to spaces

" scroll
set scrolloff=5  " when page up/down(ctrl + F/B)


" etc
syntax on   " syntax coloring
set number  " line number
set backspace=indent,eol,start  " backspace key will delete everything
set visualbell
set showcmd  " when you type 'y2d', intermediate command will be shown
map <leader>b Oimport pudb; pudb.set_trace()
" set colorcolumn=80
set termguicolors

 

vim plugin manager

vim을 정말 visual studio 수준의 IDE로 쓰려면 plugin manager를 통해 여러 plugin을 설치해서 써야한다.

plugin manager 자체도 여러가지가 있는데, 국산이기도 하고 심플하고 강력한 vim-plug를 추천

texteditor 색깔에 대해서는 여기를 참조하는걸 추천(사용가능한 airline theme list는 여기 참조)

 

그 이후 초기 설치 방법은 여기를 참조

다양한 plugin들은 여기서 검색 가능

 

 

 

반응형

'Programming > Linux' 카테고리의 다른 글

Ansible  (1) 2020.10.22
tmux and byobu  (0) 2020.09.21
리눅스 퍼미션 개념(파일 권한 관련)  (0) 2020.04.10
NTP설정  (0) 2020.03.30
supervisor  (0) 2020.03.18

교양 측면에서 우수한 영상자료들이 유툽에 이미 업로드 되어 있다.

예를 들면 여기여기

 

기술자료는 유툽보다 웹링크에 많다.

유툽에서는 이게 볼만하고,

기술적인 내용에 포커싱을 맞추면 이런  자료들이 있다.

 

블록체인이나 비트코인을 이해하려면 질의응답 형식이 편할수도 있다.

(특히 나중에 되새김할때 유용하리라 기대)

이미 아래처럼 질의응답이 제공되는 웹페이지도 존재

https://buybitcoinworldwide.com/how-many-bitcoins-are-there/

 

How Many Bitcoins Are There? (Circulating Supply - Live)

This is a complete guide to how many Bitcoins there are. Learn how many exist plus much more from this in-depth post (updated hourly).

buybitcoinworldwide.com

예를들면 다음과 같은 질문은 어떨까?

 

블럭체인 결제는 왜 느린가?

원장이 모든 노드에 공유되고 작업증명이 동반되기 때문일텐데,

작업증명이 아닌 지분증명등이 쓰이는 코인도 카드만큼 빠르진 않은 이유는 뭘까?

작업증명이 아니더라도 거래내역을 검증하는 합의 매커니즘 때문에 느려지며 이는 node수가 많아질수록 더 느려진다.

 

Nonce란 무엇이고 왜 쓰일까?

비트코인에 쓰이는 해시는 맨앞에 비트0이 연속되어서 나오는걸 요구한다.

이를 개념적인 식으로 써보면 다음과 같다.

SHA256(거래내역, Nonce) = "00000101101011011...0101"

위에 보면 앞자리 5비트가 0으로 시작함을 알 수 있는데, 이렇게 하기위한 nonce를 계속 브루트포스로 대입해보는게바로 작업증명을 수행하는 과정이 된다. 자세한건 여기 참조(근데 어렵다)

 

작업증명이 어려운건 알겠는데, 풀어낸 사람이 독점적인 블록추가를 권한 가질 수 있는 이유는 무엇인가?

문제를 풀어야 블록을 추가할 수 있으니, 문제를 풀지 못한사람은 할 수 없는 권한을 자연스럽게 가지게 된다.

 

서로다른 두 개의 노드에서 작업증명이 동시에 되어 충돌이 일어나면 어떻게 이를 처리하는가?

정상적으로 두 개의 노드에서 동시에 채굴에 성공하면 누구의 노드가 선택되는지는 우연에 의해 결정됩니다. 그러나 이러한 경우는 드물며, 이러한 상황이 발생할 때마다 블록체인 프로토콜은 이를 처리하기 위한 규칙을 갖고 있습니다. 예를 들어, 일부 프로토콜은 해시값의 크기를 기반으로 우선순위를 결정합니다.

이 과정에서 잠시동안 블록체인이 복수개 존재할 수도 있는데,  결국은 더 긴 블록체인이 올바른 것으로 인식한다(작업증명이 그만큼 더 들어가 더 난이도가 높고 해킹이 어렵다는 관점) 

길이가 동일하다면 하나가 더 길어질때까지 기다린다.

 

위조된 거래내역이 담긴 블록으로 작업증명 문제를 풀어서 블록추가를 하면 더 이득일텐데 왜 못하는가? 51%어택은?

유효한 서명 없이 비트코인에 이상거래를 쓰는 것 또한 가능하지 않습니다. 그러므로 난데없이 제어되지 않는 양의 비트코인을 생성한다든지, 다른 사용자들의 자금을 사용한다든지, 네트워크를 변질시킨다든지 하는 것은 가능하지 않으며 이들과 비슷한 어떠한 것도 마찬가지입니다.

그러나 다수결 원칙에 따라 다수의 채굴자들이 독단적으로 최근 거래들을 막거나 철회할 수 있습니다. 또한 이들은 이렇게 프로토콜의 변화를 입법하도록 압력을 가할수도 있습니다. 비트코인이 모든 사용자들간의 합의가 있어야만 작동하기 때문에, 프로토콜을 변경하는 것은 매우 어려운 일일 것이며, 소수의 사용자들이 선택의 여지가 없을 만큼 압도적인 다수가 변화를 원하여만 가능할 것입니다. 상식적으로 보았을 때 비트코인 사용자들의 자신들의 돈에 위험이 될만한 변화를 받아들이기를 원치는 않을 것입니다.

 

 

이전해시를 포함해서 해시를 하는 이유는 무엇인가?

이전 블록중 어느하나라도 위변조가 일어났을때 이를 탐지하고 방지하기 위해서이다.

 

이전해시가 포함된 형태로 다시 개념적인 식을 써보면?

이번해시 = SHA256(이전블록의해시, 거래내역, Nonce)  = "00000101101011011...0101"

그림으로는 다음과 같다. (Proof of work라고 되어 있는 부분이 Nonce이다)

좀더 자세하게는 아래와 같다.

하나의 블록은 "블록 헤더 + 블록 바디"로 만들어지고, 그 중 블록 헤더는 "이전 블록 헤더의 해시값 + 논스 + 트랜잭션의 해시값"으로 구성된다. 블록을 생성하려면 앞의 블록 헤더의 정보와 논스 및 그 블록에 포함된 모든 트랜잭션의 루트해시값을 포함시켜 해시 함수를 입력해야 한다.

 

채굴자에게 제공되는 보상(비트코인)은 어떻게 발생하는가?

거래내역에 비트코인 보상 정보를 끼워넣는 방식이다(아래 노란박스). 여기서 1개로 되어 있는데 규칙이 있고, 이 규칙을 따르지 않으면 다른 노드들이 인정해주지 않겠지.

비트코인 소스코드는 계속해서 업데이트 되는가?

비트코인 소프트웨어는 아직 베타 버전이며 많은 미완성의 기능들이 활발한 개발중에 있습니다. 더 안전하고 대중들이 쉽게 접근할 수 있는 비트코인을 만들기 위해 새로운 툴, 기능, 서비스가 개발중에 있습니다. 이중 일부는 아직 모든 사람이 사용하기에는 이릅니다. 대부분의 비트코인 사업은 최근에 생겼으며 아직 어떠한 보험도 제공하지 않습니다. 전반적으로, 비트코인은 아직도 성숙하는 과정에 있습니다.

 

그렇다면 업데이트로 인해 위험하지는 않은가?

이부분은 좀 모호하긴한데(예를들어 특정그룹에서 여론을 일으켜 이상한 방향으로 SW업데이트를 시킨다던지)

여기에서 다음과 같이 설명하고 있는것 같다.

비트코인에 대한 대부분의 신뢰는 그것이 신뢰가 필요없다는 데에서 나옵니다. 비트코인은 완전히 오픈소스이며 분권화되어 있습니다. 이는 누구나 언제 어디서나 전체 소스코드를 볼 수 있다는 뜻입니다. 고로 세계 어느 개발자든지 비트코인이 어떻게 작동하는지를 확인할 수 있습니다. 현재까지 발생된 모든 비트코인과 거래들을 누구나 투명하게 실시간으로 조사할 수 있습니다. 모든 지불이 제삼자의 존재여부와 상관없이 이루어질 수 있으며, 시스템 전체가 힘껏 상호 심시된 온라인 뱅킹에서 사용하는 것과 비슷한 암호 작성 알고리즘에 의해 보호됩니다. 어떤 개인이나 단체가 비트코인을 독점통제할 수 없으며, 구성원들 전부가 신뢰할 수 없더라도 네트워크는 안전하게 유지됩니다.

반응형

'비트코인' 카테고리의 다른 글

비트코인 관련 Q&A (자문자답)  (0) 2021.12.30
비트코인 논문 리뷰  (0) 2021.08.31
md5, sha  (0) 2017.12.12
비트코인 분석 연재를 시작하며  (0) 2017.12.10
암호화 해시 함수(cryptographic hash function)  (0) 2017.12.10

공인인증서

공인인증서의 역할

오프라인에서 주민등록증으로 신원확인을 하듯이 온라인에서 실제 내가 맞는지 신원확인

주민등록증은 동사무소에서 발급하듯, 공인인증서는 법으로 정해진 인증기관에서 발급함


비대칭키 방식

암호화/복호화에 같은 키를 사용하면 대칭키(AES, DES등) 방식, 다른키를 사용하면 비대칭키(RSA등)라고 함

비대칭키에서 암호화/복호화에 사용되는 두 개의 키를 공개키/개인키라 칭함


인증기관의 역할

해킹방지를 위해 인증기관은 공인인증서를 인증기관의 개인키로 암호화함

그리고서 암호화된 인증서와, 인증기관의 공개키는 모두에게 알려줌

암호화된 인증서가 공개키로 풀린다는 사실을 통해 인증기관의 개인키로 암호화된 문서라는게 입증됨 ← 중요

약간의 디테일

  • 전체 인증서를 암호화하면 느리므로, 실제로는 HASH하여 얻어진 해시값(MD, Message Digest)에 대해서 암호화 함
  • 인증기관의 공개키를 모두에게 알려준다고 썼는데, 실제로는 차상위 기관의 인증서 안에 인증기관의 공개키가 들어있는 체인 구조임
  • 인증기관 체인을 따라 올라가다보면 최상위 인증기관(Root CA)이 존재하는데, 이건 스스로 인증함
  • Root CA를 포함한 전체 체인을 위조하면 해킹될 수 있으나, OS에서 Root CA는 별도 검증을 해주므로 비교적 안전함
  • 후술하겠지만, 전자서명을 위해 개인의 공개키를 인증서 내용에 집어넣어서 같이 인증해줌



전자서명

일반적인 설명

오프라인에서 주민등록증만 필요한게 아니라, 문서마다 인감날인이나 서명이 필요한 경우가 있듯이,

온라인에서도 신원확인을 위한 공인인증서만 필요한게 아니라, 문서마다 인감날인 또는 서명에 해당하는 전자서명이 필요


기술적인 설명

전자서명은 원본문서를 HASH함수를 통해 짧게 줄인 해시값(MD, Message Digest)에 대해서 개인키로 암호화한 값을 의미

원본문서의 진위여부를 검증하고자 하는 측에서는 이 전자서명값을 공개키로 복원하고,

자체적으로 원본문서를 같은 방식으로 HASH함수를 통해 짧게 줄인 해시값(MD)과 비교하여 같은지 여부를 보는 식으로 진위여부를 판단함

(아래는 금결원 사이트의 설명그림 https://www.yessign.or.kr/home/subIndex/395.do)

공인인증서에서 개인의 공개키/개인키?

위의 공인인증서 설명에 나온 개인키와 공개키는 모두 인증기관의 것인데,

전자서명을 하기위해서는 개인의 공개키와 개인키가 필요함

개인의 공개키는 다음과 같이 인증서 내부에 포함되어 있으며,

개인의 개인키는 인증서가 저장되는 폴더의 signPri.key 파일에 저장되어 있고, 공인인증서 암호를 통해 다시한번 암호화 되어 있다.


반응형

netstat: listen 하고 있는 포트들 확인

$ sudo netstat -tln
Active Internet connections (only servers)
Proto Recv-Q Send-Q Local Address           Foreign Address         State
tcp        0      0 127.0.0.1:45249         0.0.0.0:*               LISTEN
tcp        0      0 0.0.0.0:9868            0.0.0.0:*               LISTEN
tcp        0      0 0.0.0.0:9993            0.0.0.0:*               LISTEN

lsof를 쓰게 되면 어떤 프로세스인지 확인할 수 있다.

$ sudo lsof -i -P -n | grep LISTEN
systemd-r    2642 systemd-resolve   14u  IPv4    25307      0t0  TCP 127.0.0.53:53 (LISTEN)
redis-ser    2796           redis    6u  IPv4    32072      0t0  TCP 127.0.0.1:6379 (LISTEN)
docker-pr 1047663            root    4u  IPv4 31617983      0t0  TCP *:9993 (LISTEN)
docker-pr 1047671            root    4u  IPv6 31620897      0t0  TCP *:9993 (LISTEN)

 

반응형

'Programming > Android' 카테고리의 다른 글

안드로이드 저장소(android storage), 파일 입출력  (2) 2019.03.06

여기여기여기, 여기 참조

특히 여기가 좋다.

 

완전이진트리 형태의 자료구조를 이용해서, element update가 존재하는 배열에 대해 특정 구간의 합, 곱, 최대값, 최소값 등을 효율적으로 구하는 자료구조

힙(heap)도 완전 이진트리를 이용하기 때문에 유사성이 있다고 볼 수 있다.

 

중간 중간에 element update가 존재하지 않는 경우, 세그먼트 트리까지는 필요없고 prefix sum등 간단한 테크닉을 쓰면 된다.

 

arr[12] = {3, 5, 6, 7, 2, 9, 4, 5, 2, 8, 1, 5} 이러한 배열이 있다고 하자.

 

완전이진트리 형태로 만들것이므로 $2^k >= 12$인 최소 k를 구해야한다. 

1
2
int k = (int)ceil(log2(n));
int tree_size = (1 << (k+1));  // base1 인덱스를 사용하기 때문에 +1을 해준다.
cs

 

 

반응형

여기여기여기, 여기 참조



수학적인 기초

먼저 절, 명제, 조건문 이 세가지가 헷갈리기 쉬운데, 이 알고리즘을 이해하려면 절대 헷갈리면 안된다.

절은 나중에 설명하고 명제부터 살펴보자.

명제란 대한민국의 수도는 서울이다, 사람은 날 수 있다. 처럼 true/false를 특정지을 수 있는 것을 말한다. 

나는 사람이다. 라는 명제를 P로 놓고, 나는 동물이다. 라는 명제를 Q로 놓은 다음 화살표로 연결하면

P->Q 이렇게 되고 조건문이된다.

조건문의 true/false는 생각보다 까다로운데 명제논리 링크를 참조해서 이해해보자.


P
Q
P → Q
T
T
T
T
F
F
F
T
T
F
F
T


위에서 다른건 다 상식선에서 이해가 되는데 P가 거짓이면 Q가 참이던 거짓이던 모순이 없는건 일상생활 명제에 대입하면 좀 받아들이기 힘들다.

(철희가 남자라면 철희는 남자가 아니다. 라는 조건문도 모순이 없는 참이 되어버리는 사태가 발생한다. 근데 생각해보면 남자라면 이라는게 거짓일때만 모순이 없는것이므로, 남자라는게 뻥이었으므로 뻥이 아닌 사실로는 남자일수도 있고 아닐수도 있는 상태가 되는걸로 이해는 가능하다. )

그럴때는 다음 문장을 참고해서 대략적으로 이해하고 넘어가자

P가 거짓일 때 참이되는 것이 아직 받아들이기 어렵다면 이렇게 생각해보자. 선생님이 학생에게 '체육대회에서 100m를 5초안에 뛸 수 있으면 72 km/h... 아이스크림을 주겠다'라고 말했다고 해보자. 이 말이 거짓말이 되는 경우는 "단 한가지" 뿐이다. 즉, (2) 학생이 100m를 5초 안에 들어왔는데 선생님이 아이스크림 안주는 경우만 거짓이다. (3) 학생이 5초안에 못뛰었을 때 선생님이 학생이 안쓰러워 아이스크림을 사준 경우 이는 선생님이 약속을 어겼다고 볼 수 없고 단순한 변심으로 보는게 타당할 것이다. 즉 위의 선생님의 약속(가언 명제) 자체는 여전히 이다. 그리고 마찬가지로 (4) 5초안에 못뛰었을 때 선생님이 아이스크림을 사주지 않는 경우 학생은 그런가보다 하고 넘어갈 수 있고 이 또한 선생님이 약속(가언 명제)을 어겼다고 할 수 없다. 즉, 으로 인정한다. 다시 정리하자면 학생이 100m를 5초 안에 뛰지 못한 경우에 대해서 선생님은 어떠한 약속도 하지않았으므로 선생님이 어떤 행동을 하든 약속이 거짓말이 될 수없다.[12]

2SAT이란

2-SAT(2-SATisfiability)문제는 충족 가능성 문제(satisfiability problem)의 한 종류입니다.

충족 가능성 문제란, 여러 개의 boolean변수들로 이루어진 식이 있을 때 각 변수에 값을 할당하여 식을 참으로 만드는 조합을 찾거나, 그러한 조합이 없음을 찾는 문제입니다.


f = (x2 ∨ ¬x1) ∧ (¬x1 ∨ ¬x2) ∧ (x1 ∨ x3) ∧ (¬x2 ∨ ¬x3) ∧ (x1 ∨ x4)

이 식은 {x1 : false, x2 : false, x3 : true, x4 : true} 인 경우에 참이 됩니다.

가만 보면, 나이브한 솔루션은  x1~x4값에 대해서 0과1을 대입해보는 식으로 2^n의 모든 부분집합을 테스트해보면 된다는 사실을 알 수 있다. 


위에보면 괄호안에 두개의 변수가 들어있는데, 그래서 2-SAT이고, 괄호하나를 절(clause)이라고 부른다.

괄호안은 항상 OR 연산자, 괄호밖은 항상 AND연산자로 되어 있다. 

이렇게 절의 AND 연산으로만 표현된 식의 형태를 CNF(Conjunctive Normal Form)라고 합니다.


1SAT문제는 트리비얼하게 O(N)에 풀린다.

3SAT이상은 다항시간 솔루션이 없다.

신기하게도 2SAT문제도 선형시간에 풀린다!


여기까지만 들으면 이런걸 왜 보고 있나하는 생각이 드는데, 의외로 많은 문제들이 2-SAT으로 변환 가능하고, SCC로 풀수 있다고 한다.

여기 참조

1. 답이 존재하는지 여부 구하기

여기까지는 할만한 느낌

핵심아이디어

1. 논리식을 조건문으로 바꾼다 : (A∨B) = ¬A → B 와 ¬B → A  !!

A가 거짓이라면 B는 무조건 참이여야 하며, B가 거짓이라면 A는 무조건 참이여야 한다.

2. 모든 절의 명제들을 합하여 하나의 유향그래프를 생성할 수 있다.

3. 사이클 전체가 true이거나 전체가 false로 통일되어야한다. A와 ¬A이 같은 사이클에 있을 수 없다.

P
Q
P → Q
T
T
T
T
F
F
F
T
T
F
F
T

3번을 잘 이해해야 하는데, true -> false이면(사실 그럴때만) 조건문에 모순이 생긴다는 걸 기억하면 된다.

(p → q에서 p가 참일 때는 q는 무조건 참이여야하며 p가 거짓일 때는 q가 무엇이든지 상관없음)


따라서, A→¬A가 나오면 A는 반드시 false여야 한다.

마찬가지로 ¬A→A가 나오면 A는 반드시 true여야 함

근데 (하나의 사이클에서 ) A→¬A도 발견되고 ¬A→A도 발견된다? 그럼 false도 될수 없고, true도 될수 없어서 모순!

(여기서 한가지 중요한 관찰은 같은 SCC가 아니면서 A→¬A 또는 ¬A→A 이렇게 단방향은 있을 수 있다는 것이다. 일상언어 조건문으로 바꾸면 남자이면 남자가 아니다. 이런게 되어서 무지 이상하지만, 상단에 서술했듯이 수학적으로는 모순이 없다. 조건문 왼쪽에 거짓이기만 한다면.)


내 코드는 다음과 같다. 이 문제의 답안이기도 하다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define REP1(i,n) for(int i=1;i<=(int)(n);i++)
using vi = vector<int>;
using vvi = vector<vi>;
 
struct result { vi scc_map;  vvi scc_list; vvi scc_adj_list; };
result scc_dag_kosaraju(int max_v, vvi& adj_list, vvi& adj_rlist, int base1)
{
    // step1. dfs로 방문하며 말단부터 stack push
    vi visit(max_v + base1); stack<int> S;
    function<void(int n)> dfs = [&](int n) {
        if (visit[n]) return;
        visit[n] = 1;
        for (int a : adj_list[n]) dfs(a);
        S.push(n);
    };
    for (int i = base1; i < max_v + base1; i++if (visit[i] == 0) dfs(i);
    // step2. stack에서 꺼내면서
    // 역방향으로 접근가능한 정점들을 SCC로 판정
    visit.clear(); visit.resize(max_v + base1);
    vi scc(max_v + base1);  // map. scc[v]=1 이면 v정점은 1번 SCC에 속한다고 하는것
    int scc_ix = base1;
    vvi scc_list; if (base1) scc_list.push_back(vi());
    while (S.size()) {
        int n = S.top(); S.pop();
        if (visit[n]) continue;
        vi sl;
        function<void(int n)> dfs = [&](int n) {
            if (visit[n]) return;
            visit[n] = 1;
            scc[n] = scc_ix;
            sl.push_back(n);
            for (auto a : adj_rlist[n]) dfs(a);
        };
        dfs(n);
        scc_list.push_back(sl);
        scc_ix++;
    }
    vvi scc_adj_list(scc_ix);
    for (int u = base1; u < max_v + base1; u++) {
        for (auto v : adj_list[u]) {
            if (scc[u] != scc[v]) {
                //cout << scc[u] << ' ' << scc[v] << endl;
                scc_adj_list[scc[u]].push_back(scc[v]);
            }
        }
    }
    return { scc, scc_list, scc_adj_list};
}
int32_t main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    int N, M; cin >> N >> M;
    vvi adj_list(2*+ 2), adj_list2(2*+ 2);
    for(int i=0;i<M;i++) {
        int a, b; cin >> a >> b;
        if (a < 0) a *= -2else a = a * 2 - 1;
        if (b < 0) b *= -2else b = b * 2 - 1;
        int na = (a % 2 == 0) ? a - 1 : a + 1;
        int nb = (b % 2 == 0) ? b - 1 : b + 1;
        //not a -> b
        adj_list[na].push_back(b);
        adj_list2[b].push_back(na); // 역방향
 
        //not b -> a
        adj_list[nb].push_back(a);
        adj_list2[a].push_back(nb); // 역방향
    }
    auto r = scc_dag_kosaraju(N*2+1, adj_list, adj_list2, true);
    int ok = 1;
    for(int i=1;i<=N;i++)
    {
        if (r.scc_map[i * 2== r.scc_map[i * 2 - 1]) ok = 0;
    }
    cout << ok << '\n';;
    return 0;
}
cs


2. 유효한 변수값들 구하기

난이도가 확 올라가는 느낌

여기여기 참조

추가로 필요한 아이디어

모든 정점에 대해서 위상정렬 순으로 처음만나면 거짓을 만들어주는식으로 채워주면 된다.

예를 들어 위상정렬순으로 not X3을 먼저 만났으면 not X3 = false 가 되어야 하므로 X3은 true로 확정해주는 식.

이런방법 말고도 굉장히 많은 방법이 있는것 같은데, 적당히 한가지로 외워두면 될듯하다.

아래는 내 코드고, 이 문제에 대한 답안이기도 하다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define REP1(i,n) for(int i=1;i<=(int)(n);i++)
using vi = vector<int>;
using vvi = vector<vi>;
 
struct result { vi scc_map;  vvi scc_list; };
result scc_dag_tarjan(vvi& adj_list, int base1)
{
    int max_v = (int)adj_list.size() - 1;  // base1==0일때 테스트 안됨!
    //타잔은 수행후 SCC들이 역순으로 위상정렬을 이루므로,
    //그 성질을 이용하면 좋다(2-SAT등)
 
    vvi ans;
    stack<int> S;
    //아래에서 visit는 ord와 통합가능하지만, 가독성을 위해 남겨둠
    vi scc_map(max_v + base1, -1), visit(max_v + base1), ord(max_v + base1), parent(max_v + base1); int g_ix = 0;
    // 코사라주나 단절선 구하는것과 다르게 finish 운영해줌
    // 일반적으로 finish배열이 dfs리턴할때 true해주는것과 다르게
    // SCC분리가 끝났음을 의미
    vi finish(max_v + base1);
    static int scc_ix = base1;
    function<int(int)> dfs = [&](int n)-> int  // low를 리턴
    {
        visit[n] = 1;
        ord[n] = ++g_ix;
        int low = ord[n];
        S.push(n);  // 스택에 먼저 푸시
        for (auto adj : adj_list[n])
        {
            if (visit[adj] == 0)  // tree edge 의 경우
            {
                int r = dfs(adj);
                // 단절점 로직의 경우 여기서 자식트리중 하나라도 자신위로 올라가지 못하면 단절점으로 판정하지만
                // SCC 타잔에서는 그러한 로직은 없고, 루프하단에 result == ord[n] 으로
                // 자신포함 자식트리중 도달가능한 가장 높은 정점이 자신일 경우 SCC 추출하는 로직으로 바뀐다.
                // if (r > ord[n]) ans.insert({ min(n,adj), max(n,adj) });
                low = min(low, r);
            }
            // 방문은 했으나 아직 SCC로 추출되지는 않은 이웃
            else if (finish[adj] == 0)  // back edge 또는 cross edge의 일부
                low = min(low, ord[adj]);  // 접근가능한 백정점 순서로 업데이트
        }
        // 자신포함 자식트리중 도달가능한 가장 높은 정점이 자신일 경우 SCC 추출
        if (low == ord[n])
        {
            vi scc;
            while (S.size())
            {
                int a = S.top(); S.pop();
                scc.push_back(a);
                scc_map[a] = scc_ix;
                finish[a] = 1;
                if (a == n) break;
            }
            sort(scc.begin(), scc.end());
            ans.push_back(scc);
            scc_ix++;
        }
 
        return low;
    };
    for (int i = base1; i < max_v + base1; i++if (visit[i] == 0) dfs(i);
    return { scc_map, ans };
}
 
#define DBL(a) (2*(a))
#define CONV(a) (a)<0?(a)*-2:(a)*2+1
int32_t main()
{
    ios::sync_with_stdio(false); cin.tie(0);
 
    int N, M; cin >> N >> M;
    vvi adj_list(DBL(N+1));
    for (int i = 0; i < M; i++) {
        int a, b; cin >> a >> b;
        a = CONV(a);
        b = CONV(b);
 
        //nice magic property!
        int na = a ^ 1;
        int nb = b ^ 1;
 
        //not a -> b
        adj_list[na].push_back(b);
 
        //not b -> a
        adj_list[nb].push_back(a);
    }
    auto r = scc_dag_tarjan(adj_list, true);
    for (int i = 1; i <= N; i++)
    {
        if (r.scc_map[CONV(i)] == r.scc_map[CONV(-i)]) { cout << 0 << '\n'return 0; }
    }
    // 여기까지 오면 변수조합이 있는건 보장된다. 모순만 없도록 배열해주면 됨
    cout << 1 << '\n';
    for (int i = 1; i <= N; i++) {
        // 아랫부분 아직 제대로 이해 못한 상태 ㅠ
        // 소스가 워낙 간결해서 일단 채택은 해 두었다.
        cout << (r.scc_map[CONV(i)] < r.scc_map[CONV(-i)]) << ' ';  
    }
    return 0;
}
 
cs



반응형

문제링크는 여기


풀이과정

출발점은 하나로 정해져 있고, 도착점은 여러개.

현금인출은 사이클 도는게 유리하므로 SCC단위로 생각하면 됨.

도착점도 SCC단위로 묶어서 생각하면 됨.

SCC단위로 묶고나서 보면, 간선 가중치는 없는 방향그래프 이므로, 위상정렬 개념 도입해서 longest 구하면 답

(여기서 위상정렬이 아닌 단순 BFS로는 안풀린다. 그래프 최장거리 참조)


헷갈렸던 점

아래 그래프가 SCC이후에 만들어진 DAG이라고 해보자. 

1번정점이 시작, 5번 정점이 끝이라고 해보자.


위의 그래프를 아래와 같은 코드로 위상정렬하면서 돌리게 되면

1
2
3
4
5
6
7
8
9
10
enqueue({ start_v, cost[start_v] });
while (q.size()) {
    auto n = q.front(); q.pop();
    max_dist[n.v] = max(max_dist[n.v], n.w);
    for (auto adj : adj_list[n.v]) {
        max_dist[adj] = max(max_dist[adj], n.w + cost[adj]), cal[adj]=1;
        in_edge[adj]--;
        if (enqueue({ adj, max_dist[adj] })) from[adj] = n.v;
    }
}
cs


1번노드를 처리한다음에 2번 노드처리하기전에 while()이 끝나게 된다. (2번 노드의 in_edge가 3이라서 1빼도 아직 2라서 3과 4를 처리하기 전까진 못들어가는데 3,4를 처리하지 않는 코드이다.)

하지만 정답은 1 -> 2 -> 3을 모두 계산한 최대비용이 답이었던것.. 


따라서, 아래처럼 처음에 indegree가 0인 모든 정점을 queue에 넣어주고, cal[v] 맵을 사용해서 유효한 경우에만 max_dist가 갱신되도록 해주면 OK

1
2
3
4
5
6
7
8
9
10
11
12
for (int i = base1; i < max_v + base1; i++) enqueue({ i,cost[i] });
if (start_v == -1for (int i = base1; i < max_v + base1; i++) max_dist[i] = cost[i];
else max_dist[start_v] = cost[start_v];
vi cal(max_v + base1); cal[start_v] = 1;
while (q.size()) {
    auto n = q.front(); q.pop();
    for (auto adj : adj_list[n.v]) {
        if (cal[n.v]) max_dist[adj] = max(max_dist[adj], n.w + cost[adj]), cal[adj] = 1;
        in_edge[adj]--;
        if (enqueue({ adj, max_dist[adj] })) from[adj] = n.v;
    }
}
cs



코드

scc_dag_kosaraju()를 라이브러리화 하고, 기존 longest()라이브러리를 활용하느라고, 범용성 관점에서 코드가 좀 길고 장황한면이 있습니다. 감안해서 봐주세요~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
/*{{{*/
#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
#include "dbg.h"  // https://github.com/sharkdp/dbg-macro
#define FileInput freopen("input.txt""rt", stdin)
#else
#define dbg(...)
#define FileInput
#endif
//#define int long long
#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define CASE_T int ___T; cin>>___T;for(int cs=1;cs<=___T;cs++)
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define REP1(i,n) for(int i=1;i<=(int)(n);i++)
using vi = vector<int>;
using vs = vector<string>;
using vvi = vector<vi>;
#define endl '\n';
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(), x.end()
#define IN(n) int n;cin>>n
#define IN2(a,b) int a,b;cin>>a>>b
#define OUT(x) cout << (x) << endl
template <class T>
void OUTV(vector<T>& v) { REP(i, SZ(v)) cout << v[i] << (i + 1 == SZ(v) ? '\n' : ' '); }
typedef long long ll;
const int INF = (int)1e9;
/*}}}*/
 
struct result { vvi scc_list; vvi scc_adj_list; vi scc_cost; int scc_start_v; vi scc_end_v; };
result scc_dag_kosaraju(int max_v, int start_v, vi& end_v, vvi& adj_list, vvi& adj_rlist, vi& cost, int base1)
{
    // step1. dfs로 방문하며 말단부터 stack push
    vi visit(max_v + base1); stack<int> S;
    function<void(int n)> dfs = [&](int n) {
        if (visit[n]) return;
        visit[n] = 1;
        for (int a : adj_list[n]) dfs(a);
        S.push(n);
    };
    for (int i = base1; i < max_v + base1; i++if (visit[i] == 0) dfs(i);
    // step2. stack에서 꺼내면서
    // 역방향으로 접근가능한 정점들을 SCC로 판정
    visit.clear(); visit.resize(max_v + base1);
    vi scc(max_v + base1);  // map. scc[v]=1 이면 v정점은 1번 SCC에 속한다고 하는것
    int scc_ix = base1;
    vvi scc_list; if (base1) scc_list.push_back(vi());
    while (S.size()) {
        int n = S.top(); S.pop();
        if (visit[n]) continue;
        vi sl;
        function<void(int n)> dfs = [&](int n) {
            if (visit[n]) return;
            visit[n] = 1;
            scc[n] = scc_ix;
            sl.push_back(n);
            for (auto a : adj_rlist[n]) dfs(a);
        };
        dfs(n);
        scc_list.push_back(sl);
        scc_ix++;
    }
    vvi scc_adj_list(scc_ix); int scc_start_v = -1; vi scc_end_v(scc_ix), scc_cost(scc_ix);
    for (int u = base1; u < max_v + base1; u++) {
        if (u == start_v) scc_start_v = scc[u];
        if (end_v[u]) scc_end_v[scc[u]] = 1;
        scc_cost[scc[u]] += cost[u];
        for (auto v : adj_list[u]) {
            if (scc[u] != scc[v]) {
                //cout << scc[u] << ' ' << scc[v] << endl;
                scc_adj_list[scc[u]].push_back(scc[v]);
            }
        }
    }
    return { scc_list, scc_adj_list, scc_cost, scc_start_v, scc_end_v };
}
struct node { int v, w; };
using vvn = vector<vector<node>>;
struct result2 { vi max_dist; int max_value; vi path; };
result2 longest(int max_v, int start_v, vvi& adj_list, vi& in_edge, vi& cost, vi& end_v, int base1) {
    vi visit(max_v + base1), max_dist(max_v + base1, -INF);
    vi from(max_v + base1, INF);
    queue<node> q;
    function<bool(node)> enqueue = [&](node n)->bool {
        if (in_edge[n.v] != 0return false;
        q.push(n);
        return true;
    };
    for (int i = base1; i < max_v + base1; i++) enqueue({ i,cost[i] });
    if (start_v == -1for (int i = base1; i < max_v + base1; i++) max_dist[i] = cost[i];
    else max_dist[start_v] = cost[start_v];
    vi cal(max_v + base1); cal[start_v] = 1;
    while (q.size()) {
        auto n = q.front(); q.pop();
        for (auto adj : adj_list[n.v]) {
            if (cal[n.v]) max_dist[adj] = max(max_dist[adj], n.w + cost[adj]), cal[adj] = 1;
            in_edge[adj]--;
            if (enqueue({ adj, max_dist[adj] })) from[adj] = n.v;
        }
    }
    //아래는 좀 비효율적, 위의 복잡도를 높이지 않게 하기위해 걍 놔둠
    int ra = -INF, rb = -1;
    for (int i = base1; i < max_v + base1; i++)
        if (end_v[i] && max_dist[i] > ra) ra = max_dist[i], rb = i;
    deque<int> s;
    int ix = rb;
    while (ix != INF)s.push_front(ix), ix = from[ix];
    return { max_dist, ra, vi(s.begin(), s.end()) };
}
int32_t main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    FileInput;
    int V, E; cin >> V >> E;
    vvi adj_list(V + 1), adj_list2(V + 1);
    REP(i, E) {
        int a, b; cin >> a >> b;
        adj_list[a].push_back(b);
        adj_list2[b].push_back(a); // 역방향
    }
    vi cost(V + 1);
    REP1(i, V)cin >> cost[i];
    IN2(S, P);
    vi end_v(V + 1);
    REP(i, P) { IN(p); end_v[p] = 1; }
    auto r = scc_dag_kosaraju(V, S, end_v, adj_list, adj_list2, cost, true);
    int N = SZ(r.scc_adj_list) - 1;
    vi in_edge(N + 1);
    REP1(u, N) for (auto v : r.scc_adj_list[u])in_edge[v]++;
    auto r2 = longest(N, r.scc_start_v, r.scc_adj_list, in_edge, r.scc_cost, r.scc_end_v, true);
    OUT(r2.max_value);
    return 0;
}
cs


반응형

'Programming > Problem Solving' 카테고리의 다른 글

cph  (0) 2024.07.21
double과 관련된 핸들링  (0) 2021.12.26
백준 15481 그래프와 MST  (0) 2020.05.02
BST 트리 구현  (0) 2020.04.09
인접행렬, 인접리스트  (0) 2020.04.09

+ Recent posts