HTTP (HyperText Transfer Protocol)

하이퍼 텍스트 전송 프로토콜로, 인터넷을 작동시키는 역할을 하며, 웹 서버 및 웹 브라우저 상호 간의 데이터 전송을 위한 응용 계층 프로토콜이다.

어려우니까 한 줄 요약.

서버/클라이언트 모델을 따라 데이터를 주고 받기 위한 프로토콜.

즉, HTTP는 인터넷에서 하이퍼텍스트를 교환하기 위한 통신 규약으로, 80번 포트를 사용하고 있다.

따라서 HTTP 서버가 80번 포트에서 요청을 기다리고 있으며, 클라이언트는 80번 포트로 요청을 보내게 된다.

HTTP의 구조

HTTP는 애플리케이션 레벨의 프로토콜로 TCP/IP 위에서 작동한다.

HTTP는 상태를 가지고 있지 않는 Stateless 프로토콜이며 Method, Path, Version, Headers, Body 등으로 구성된다.

Stateless 와 Connectionless

Stateless, 무상태성

서버는 클라이언트의 상태를 보존하지 않는다.

Connectionless, 비연결성

클라이언트가 서버에 요청을 하고 응답을 받으면 TCP/IP 연결을 끊어 연결을 유지 하지 않는다.

하지만 HTTP는 암호화가 되지 않은 평문 데이터를 전송하는 프로토콜이다.

따라서 HTTP로 비밀번호나 주민등록번호 등을 주고 받으면 제3자가 정보를 조회할 수 있었다.

그리고 이러한 문제를 해결하기 위해 HTTPS가 등장하게 되었다.

HTTPS (HyperText Transfer Protocol Secure)

HTTP에 Secure만 더해졌다. HTTP와 동일한 방식으로 작동한다.

서버와 주고받는 데이터가 암호화되기 때문에 웹 사이트에 추가적인 보호를 제공한다.

HTTPS는 HTTP와 다르게 443번 포트를 사용하며, 네트워크 상에서 중간에 제3자가 정보를 볼 수 없도록 암호화를 지원하고 있다.

SSL

웹 사이트를 HTTPS에서 실행하려면 SSL(Security Sockets Layer) 인증서가 필요하다.

이 인증서는 웹 사이트의 데이터를 암호화하고 웹 사이트 방문자에게 나의 웹 사이트가 안전하다는 것을 증명하는 역할을 해준다.

대칭키 암호화와 비대칭키 암호화

HTTPS는 대칭키 암호화 방식과 비대칭키 암호화 방식을 모두 사용하고 있다.

각각의 암호화 방식은 다음과 같다.

대칭키 암호화

클라이언트와 서버가 동일한 키를 사용해 암호화/복호화를 진행함

키가 노출되면 매우 위험하지만 연산 속도가 빠름

비대칭키 암호화

1개의 쌍으로 구성된 공개키와 개인키를 암호화/복호화 하는데 사용함

키가 노출되어도 비교적 안전하지만 연산 속도가 느림

비대칭키 암호화는 공개키/개인키 암호화 방식을 이용해 데이터를 암호화하고 있다.

공개키와 개인키는 서로를 위한 1쌍의 키이다.

공개키: 모두에게 공개가능한 키

개인키: 나만 가지고 알고 있어야 하는 키

암호화를 공개키로 하느냐 개인키로 하느냐에 따라 얻는 효과가 다른데, 공개키와 개인키로 암호화하면 각각 다음과 같은 효과를 얻을 수 있다.

공개키 암호화

공개키로 암호화를 하면 개인키로만 복호화할 수 있다.

개인키는 나만 가지고 있으므로, 나만 볼 수 있다.

개인키 암호화

개인키로 암호화하면 공개키로만 복호화할 수 있다.

공개키는 모두에게 공개되어 있으므로, 내가 인증한 정보임을 알려 신뢰성을 보장할 수 있다.

HTTPS의 동작 과정

HTTPS는 대칭키 암호화와 비대칭키 암호화를 모두 사용하여 빠른 연산 속도와 안정성을 모두 얻고 있다.

HTTPS 연결 과정(Hand-Shaking)에서는 먼저 서버와 클라이언트 간에 세션키를 교환한다.

여기서 세션키는 주고 받는 데이터를 암호화하기 위해 사용되는 대칭키이며, 데이터 간의 교환에는 빠른 연산 속도가 필요하므로 세션키는 대칭키로 만들어진다.

문제는 이 세션키를 클라이언트와 서버가 어떻게 교환할 것이냐 하는 문제인데, 이 과정에서 비대칭키가 사용된다.

즉, 처음 연결을 성립하여 안전하게 세션키를 공유하는 과정에서 비대칭키가 사용되는 것이고, 이후에 데이터를 교환하는 과정에서 빠른 연산 속도를 위해 대칭키가 사용되는 것이다.

실제 HTTPS 연결 과정이 성립되는 흐름을 살펴보면 다음과 같다.

• 클라이언트(브라우저)가 서버로 최초 연결 시도를 함
• 서버는 공개키(엄밀히는 인증서)를 브라우저에게 넘겨줌
• 브라우저는 인증서의 유효성을 검사하고 세션키를 발급함
• 브라우저는 세션키를 보관하며 추가로 서버의 공개키로 세션키를 암호화하여 서버로 전송함
• 서버는 개인키로 암호화된 세션키를 복호화하여 세션키를 얻음
• 클라이언트와 서버는 동일한 세션키를 공유하므로 데이터를 전달할 때 세션키로 암호화/복호화를 진행함

HTTPS의 발급 과정

위의 과정에서 추가로 살펴봐야 할 부분은 서버가 비대칭키를 발급받는 과정이다.

서버는 클라이언트와 세션키를 공유하기 위한 공개키를 생성해야 하는데, 일반적으로는 인증된 기관(Certificate Authority)에 공개키를 전송하여 인증서를 발급받는다.

자세한 과정은 다음과 같다.

1. A기업은 HTTP 기반의 애플리케이션에 HTTPS를 적용하기 위해 공개키/개인키를 발급함
2. CA 기업에게 돈을 지불하고, 공개키를 저장하는 인증서의 발급을 요청함
3. CA 기업은 CA기업의 이름, 서버의 공개키, 서버의 정보 등을 기반으로 인증서를 생성하고, CA 기업의 개인키로 암호화하여 A기업에게 이를 제공함
4. A기업은 클라이언트에게 암호화된 인증서를 제공함
5. 브라우저는 CA기업의 공개키를 미리 다운받아 갖고 있어, 암호화된 인증서를 복호화함
6. 암호화된 인증서를 복호화하여 얻은 A기업의 공개키로 세션키를 공유함

Sources …

HTTP와 HTTPS의 개념 및 차이점

HTTP Stateless - Connectionless

http와 https의 차이

Stack overflow

Http와 Https 이해와 차이점 그리고 오해(?)

how does https work rsa encryption explained

Database 관점에서 Index란 무엇인가?

조금 딱딱하게 정의하자면 다음과 같다.

추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료구조

Index를 설명할 때 주로 색인 이라는 표현을 사용한다.

Index는 마치 책의 목차처럼 우리가 찾는 페이지를 빠르게 찾게 도와주는 역할을 한다.

UPDATE USER SET NAME = 'Primrose' WHERE NAME = 'Prim';

인덱스를 활용하면, 데이터를 조회하는 SELECT 외에도 UPDATE나 DELETE의 성능이 함께 향상된다.

만약 Index를 사용하지 않는다면 Full Scan 작업을 수행해야하는데, 이는 처리 속도가 떨어질 수 밖에 없다.

인덱스(index)의 관리

DBMS는 index를 항상 최신의 정렬된 상태로 유지해야 원하는 값을 빠르게 탐색할 수 있다.

그렇기 때문에 인덱스가 적용된 컬럼에 INSERT, UPDATE, DELETE가 수행된다면 각각 다음과 같은 연산을 추가적으로 해주어야 하며 그에 따른 오버헤드가 발생한다.

INSERT: 새로운 데이터에 대한 인덱스를 추가함

기존 Block에 여유가 없을 때, 새로운 Data가 입력된다. 새로운 Block을 할당받은 후, Key를 옮기는 작업을 수행한다. Index split 작업 동안, 해당 Block의 Key값에 대해서 DML이 블로킹 된다.

DELETE: 삭제하는 데이터의 인덱스를 사용하지 않는다는 작업을 진행함

<Table과 Index 상황비교> Table에서 Data가 DELETE 되는 경우   Data가 지워지고 다른 Data가 해당 공간 사용 가능 Index에서 Data가 DELETE 되는 경우   Data가 지워지지 않고, 사용 안 됨 표시만 해둔다.

고로 Table의 Data수와 Index의 Data 수가 다를 수 있다.

UPDATE: 기존의 인덱스를 사용하지 않음 처리하고, 갱신된 데이터에 대해 인덱스를 추가함

Table에서 UPDATE가 발생하면 Index는 UPDATE 할 수 있다.

Index에서는 DELETE가 발생하고, 새로운 작업의 INSERT 작업을 하므로 2배의 작업이 소요.

인덱스(index)의 장점과 단점

장점

1. 테이블을 조회하는 속도와 그에 따른 성능을 향상시킬 수 있다.
2. 전반적인 시스템의 부하를 줄일 수 있다.

단점

1. 인덱스를 관리하기 위해 DB의 약 10%에 해당하는 저장공간이 필요하다.
2. 인덱스를 관리하기 위해 추가 작업이 필요하다.
3. 인덱스를 잘못 사용할 경우 오히려 성능이 저하되는 역효과가 발생할 수 있다.

만약 CREATE, DELETE, UPDATE가 빈번한 속성에 인덱스를 걸게 되면 인덱스의 크기가 비대해져서 성능이 오히려 저하되는 역효과가 발생할 수 있다.

그러한 이유 중 하나는 DELETE와 UPDATE 연산 때문이다.

앞에서 설명한대로, UPDATE와 DELETE는 기존의 인덱스를 삭제하지 않고 '사용하지 않음' 처리를 해준다고 하였다.

만약 어떤 테이블에 UPDATE와 DELETE가 빈번하게 발생된다면 실제 데이터는 10만건이지만 인덱스는 100만 건이 넘어가게 되어, SQL문 처리 시 비대해진 인덱스에 의해 오히려 성능이 떨어지게 될 것이다.

사용하면 좋은 경우

(1) Where 절에서 자주 사용되는 Column (2) 외래키가 사용되는 Column (3) Join에 자주 사용되는 Column

Index 사용을 피해야 하는 경우

(1) Data 중복도가 높은 Column (2) DML이 자주 일어나는 Column (DML에 취약하기 때문에)

Sources …

Index Database Index Database Index란

연결을 성립하고 해제하는 과정을 말한다.

3 way handshake

TCP는 장치들 사이에 논리적인 접속을 성립시키기 위해 3 way handshake를 사용한다.

TCP 3 way handshake(이하 3way)는 TCP/IP 프로토콜을 이용해서 통신을 하는 응용프로그램이

데이터를 전송하기 전에 먼저 정확한 전송을 보장하기 위해 상대방 컴퓨터와 사전에 세션을 수립하는 과정을 의미한다.

TCP 통신은 PAR(Positive Acknowledgement with Re-transmission)을 통해 신뢰적인 통신을 제공한다.

PAR을 사용하는 기기는 ack을 받을 때까지 데이터 유닛을 재전송한다.

수신자가 데이터 유닛(세그먼트)이 손상된 것을 확인하면 해당 세그먼트를 없앤다.

그러면 sender는 positive ack이 오지 않은 데이터 유닛을 다시 보내야 한다.

작동방식

HOST P와 HOST Q가 있을 때, HOST P가 클라이언트, HOST Q가 서버 라고 가정해보자.

1. 클라이언트가 서버에게 SYN 패킷을 보냄.
   Client > Server : TCP SYN
2. 서버가 SYN(x)을 받고 클라이언트로 받았다는 신호 ACK(x + 1)와 SYN(y)패킷을 보냄.
   Server > Client : TCP SYN, ACK
3. 클라이언트는 서버의 응답(ACK(x+1), SYN(y))을 받고, ACK(y+1)를 서버로 보냄.
   Client > Server : TCP ACK

• SYN : 'Synchronize sequence numbers', 연결 요청. 세션을 설정하는데 사용되며 초기에 시퀀스 번호를 보냄.
• ACK : 'Acknowledgement', 보낸 시퀀스 번호에 TCP 계층에서의 길이 또는 양을 더한 것과 같은 값을 ACK에 포함하여 전송.

동기화 요청에 대한 답변: Client의 Sequence Number + 1을 하여 ACK로 돌려준다.

이렇게 3번의 통신이 완료되면 연결이 성립된다.

SYN을 보내면 ACK를 받을 때 까지 재전송한다. ACK가 와야 완료된다는 뜻이다.

이러한 행위로 양쪽 모두 데이터를 전송할 준비가 되었다는 것을 보장하고,

실제로 데이터 전달이 시작하기 전에 한쪽이 다른 쪽이 준비되었다는 것을 알 수 있도록 한다.

4 way handshake

4 way handshake는 연결을 해제하는 과정이다. 여기서는 FIN 플래그를 이용한다.

• FIN : 세션을 종료시키는데 사용되며, 더 이상 보낸 데이터가 없음을 나타낸다.

Termination의 종류

TCP는 두 가지 연결 해제 방식이 있다.

1. Graceful connection release(정상적인 연결 해제)

정상적인 연결 해제에서는 양쪽이 커넥션을 모두 닫을 때까지 연결되어 있다.

2. Abrupt connection release(갑작스런 연결 해제)
   1. 갑자기 한 TCP 엔티티가 연결을 강제로 닫는 경우
   2. 한 사용자가 두 데이터 전송 방향을 모두 닫는 경우

Abrupt

RST(TCP reset) 세그먼트가 전송되면 갑작스러운 연결 해제가 수행되는데, RST 세그먼트는 다음과 같은 경우에 전송된다.

1. 존재하지 않는 TCP 연결에 대해 비 SYN 세그먼트가 수신된 경우
2. 열린 커넥션에서 일부 TCP 구현이 잘못된 헤더가 있는 세그먼트가 수신된 경우
   • RST 세그먼트를 보내, 해당 커넥션을 닫아 공격을 방지한다.
3. 일부 구현에서 기존 TCP 연결을 종료해야 하는 경우

Graceful

연결 종료 요청 역시, 요청을 먼저 시도한 요청자를 Client로, 요청을 받은 수신자를 Server 쪽으로 생각하면 된다.

1. 클라이언트는 서버에게 연결을 종료한다는 FIN 플래그 보냄.
2. 서버는 FIN을 받고, 확인했다는 ACK를 클라이언트에게 보낸다. 이 때, 모든 데이터를 보내기 위해 CLOSE_WAIT 상태가 된다.
3. 데이터를 모두 보냈다면, 연결이 종료되었다는 FIN 플래그를 클라이언트에게 보낸다.
4. 클라이언트는 FIN을 받고, 확인했다는 ACK를 서버에게 보낸다. 이 때 아직 서버로부터 받지 못한 데이터가 있을 수 있으므로 TIME_WAIT을 통해 기다린다.
   1. 서버는 ACK를 받고, 소켓을 닫는다(Closed)
   2. TIME_WAIT 시간이 끝나면 클라이언트도 닫는다 (Closed) => 의도치 않은 에러로 연결이 데드락으로 빠지는 것을 방지한다.

이렇게 4번의 통신이 완료되면 연결이 해제된다.

IPFS는 분산형 파일 시스템에 데이터를 저장하고 인터넷으로 공유하기 위한 프로토콜이다.

조금 더 구체적으로 접근하면, 탈중앙화, 개인간(P2P), 무신뢰 방식으로 모든 종류의 파일을 저장하는 데 사용되는 블록체인 네트워크이다.

인터넷은 연결이며, HTTP 프로토콜은 서로 데이터를 주고 받는 방식에 대한 약속이다.

Web은 인터넷 상에서 HTTP 프로토콜에 따라 주고 받는 공간이다.

일상적으로 우리는 인터넷과 웹을 동의어처럼 사용하지만, 엄밀하게 말하면 다르다.

인터넷은 방대한 네트워크, 혹은 네트워크 인프라를 의미한다.

인터넷이 연결되어 있다면, 컴퓨터는 다른 컴퓨터와 통신이 가능하다.

웹은 인터넷을 통해 데이터를 얻는 방법 중 하나에 지나지 않는다.

웹은 인터넷 계층 위에 설계된, HTTP 프로토콜을 사용하는 데이터공유 모델이다.

기존 HTTP Web은 불안정적이고, 중앙화 되어있으며, 비효율적이고, 느리며, 고도의 연결성을 필요로 한다.

IPFS는 이러한 Web의 문제점들을 해결하고 모든 컴퓨터를 연결하고자 하는 분산된 P2P 파일 시스템이다.

InterPlanetary(행성 간의)라는 표현이 사용된 이유는 뭐... 다른 행성의 컴퓨터까지 연결하겠다는 비전이라고 한다.

IPFS Web에서는 파일을 데이터, 정보, 컨텐츠의 개념으로 보면 된다.

IPFS 특징

• 중앙화된 서버 없이 노드들의 P2P 통신으로 실현한 더 빠르고 안전하고 열린 네트워크이다.
  • 대형 서버의 연결이 차단되면 치명적인 HTTP Web과는 달리, 몇몇 노드들 연결이 끊어져도 생태계가 유지된다.
• 고용량파일을 빠르고 효율적으로 전달할 수 있으며, 파일들의 중복을 알 수 있기 떄문에 저장소도 효율적으로 사용할 수 있다.
• IPFS 상에 업로드된 파일의 이름은 영원히 기록되며, 만약 IPFS 상에서 지키고 싶은 파일은 원하는 만큼 지켜낼 수 있다.
  • 파일의 버전관리(Git)가 가능하다.

IPFS 원리

각각의 파일은 여러 개의 블록으로 이루어져 있으며, 각각의 블록은 해시로 표현된 고유의 이름이 있다.

IPFS는 모든 파일의 이름을 데이터베이스 속에 저장하며, 동일 파일의 중복을 배제하고, 각 파일의 버전 정보를 트래킹한다.

각 노드는 본인이 관심있는 파일만 저장소에 보관하며, 인덱싱 정보를 통해 누가 어떤 파일을 저장하고 있는지 알 수 있다.

네트워크에서 파일을 찾기 위해서는, 파일명을 조회하고 해당 파일을 갖고 있는 노드를 물어보면 된다.

모든 파일명은 읽기 쉬운 형태로 변환 가능하다.

IPFS를 구성하는 기술

IPFS Web은 다양한 기술들의 조합으로 이루어져 있다.

Distributed Hash Tables(DHT)

네트워크에 참여한 노드들이 해시 테이블을 각자 관리함으로써 중앙화된 서버 없이

고도의 P2P 네트워크를 실현할 수 있으며, 이를 분산 해시 테이블 기술(DHT)이라고 말한다.

어떤 방식으로 DHT를 운영하느냐에 따라서 얼마나 빠르고 효율적으로 네트워크 요청을 소화해낼 수 있는지 그 역량이 결정되며,

노드의 네트워크 진입/이탈, 신규 컨텐츠 등록 등이 어떻게 관리되는 지 달라진다.

DHT의 등장으로 수십억개의 노드를 운용해도 네트워크의 부하를 억제할 수 있다고 한다.

기존의 HTTP에서는 컨텐츠의 위치(IP)를 알고 찾아갔으나, 사라진 주소(IP)거나 컨텐츠가 없으면 에러를 겪곤 했다.

IPFS에서는 컨텐츠 자체를 찾는다. 컨텐츠 자체가 주소의 역할을 하는데, 이를 _content-addressed_라고 한다.

해시테이블 상에서 컨텐츠 이름을 찾으면 해당 컨텐츠를 보유하고 있는 노드를 알 수 있다 !

Bittorrent

Bittorrent는 P2P 파일 교환 프로토콜이다. 종전의 방식은 서버가 파일을 가지고 있고, 클라이언트가 받아가는 형태였다.

반연 Bittorrent는 하나의 파일을 여러 조각으로 나누어서,

각 노드끼리 자신이 갖고 있는 조각의 정보를알려주고 다른 노드들에게 자신이 필요한 조각을 요청한다.

다른 노드들과 많은 세션을 생성하게 되며, 세션이 늘어남에 따라 사용자의 다운로드 속도는 전적으로 늘어나,

노드가 사용하는 인터넷 환경의 최대 대역폭까지 다운로드 속도가 증가한다.

IPFS BitSwap Protocol

BitSwap은 BitTorrent에서 영감을 얻은 프로토콜이다.

Peer들은 본인이 얻고 싶은 파일 블록과 본인이 갖고 있는 파일 블록이 있다.

BitTorrent에서는 하나의 파일을 받고자 할 때 그 파일의 블록들만 한정적으로 받아올 수 있는 반면,

BitSwap에서는 일치하는 파일 블록이라면 어떤 파일에 속해 있든지 받아올 수 있다고 한다. (???)

노드들이 받기만 하려고 하고 줄 생각이 없다면 문제가 되기 때문에, BitSwap은 기본적으로 물물교환 시스템을 표방한다.

무언가를 받기 위해서는 무언가를 주어아 하고, 대가로 줄 파일을 얻기 위해서 파일 블록들을 더 배포, 확산시키는 시스템이다.

이것은 Filecoin 구상이 시작된 배경이기도 하다.

BitSwap Credit 시스템을 통해 노드들이 peer에게 파일을 보내주면 보낸 노드는 자산이 증가하며, 받은 노드는 부채가 증가한다.

이로써 받기만 하려고 하는 어뷰징을 막을 수 있고, 파일 블록을 보유하고 보내주는 것에 인센티브가 생기게 된다.

Source

IPFS(InterPlanetary File System)이해하기 1부 : HTTP Web을 넘어서, IPFS Web으로

IPFS란 무엇인가: 웹의 미래

Filecoin은 IPFS 팀에서 IPFS 형식의 파일 저장을 장려하기 위해 만들어낸 탈중앙화 저장소 네트워크이다.

따라서 IPFS 형태의 파일 표준만 맞춘다면, 용량 제공자(Filecoin에서의 마이너)의 유휴 데이터 용량을 활용할 수 있다.

이때 그 반대급부로 마이너에게 지불하게 되는 것이 'Filecoin'이라는 코인인데,

이렇게 되면 암호화폐를 지불하고 활용하게 되는 일종의 시장, 또는 공유 경제 모델이 형성된다.

정리하면 다음과 같다.

Filecoin이란 클라우드 저장소를 알고리즘 시장으로 이끌어낸 탈중앙화 방식의 스토리지 네트워크이다. 
이 알고리즘 시장은 프로토콜 토큰 ‘Filecoin’을 활용한 블록체인 위에서 형성되는데, 
채굴자들은 자신들의 저장소를 클라이언트들에게 제공함으로써 이 토큰을 얻게 된다.

Filecoin의 특징

1. DSN

DSN은 Decentralized Storage Network의 약자로, Filecoin이 활용되는 네트워크 자체를 의미한다.

사용자들은 DSN 상에서 데이터 용량을 제공하는 마이너들에게 보상을 지불한다.

이 때, 채굴자들은 그들의 서비스 제공이 올바르게 이루어졌다고 '감사(Audit)'을 받는 경우에만 이 보상을 받을 수 있다.

2. 합의 알고리즘(Consensus) 방식

블록체인에서는 합의 알고리즘이 어떻게 짜여지냐에 따라 블록체인 서비스나 비즈니스 모델이 변동한다.

Filecoin이 제공하는 DSN도 결국 구성원들의 자발적 합의에 의해 돌아가게끔 하는 독특한 합의 알고리즘이 있는데,

복제 증명방식과 시공간 증명 방식이 그것이다.

복제증명

복제증명은 특정 서버가 데이터를 저장함에 있어 고유한 물리적 저장소임을 입증하는 역할을 한다.

이 서버 내에서 특정 데이터는 두 번씩 복제되기 어렵고, 중복된 복제는 제거된다.

이 구조는 클라우드 저장소 또는 DSN 세팅에 유용하게 활용되는데,

이런 구조 내에서는 복제의 적절한 레벨을 입증하는 것이 중요해지거나,

해당 서비스를 동일한 유저에게 중복해서 팔게 될 수도 있기 때문이다.

시공간 증명

시공간 증명 방식은 유저에게 특정 서버가 spacetime(어느 정도 사용된 스토리지) 자원을 이미 소비했음을 입증한다.

시공간 증명 방식은 공간 증명 방식이 시간이 지나면서 여러 번 확인된 '결과물'로 볼 수 있다.

기존의 공간 증명 방식에서 조금 더 나아간 개념이라고 보면 된다.

Source

Filecoin (파일코인) - P2P 드랍박스 시대 도래할까?
공간 증명 방식

IPFS는 탈중앙화 웹이다. 하나의 서버가 다운되거나 파괴되더라도 우리는 파일을 잃지 않는다.

블록체인을 통해 탈중앙화된 토큰 economy를 구상할 때, IPFS는 파일 저장 및 보관의 측면에서도 탈중앙화를 실현할 수 있다.

IPFS를 통해 우리는 모든 파일을 블록체인 상에 올릴 수 있다.

그러나 이것이 해당 파일을 직접 블록체인에 올린다는 의미는 아니다.

우리가 2GB 용량의 파일을 올린다면, 엄청난 양의 GAS를 소모하게 될 것이다.

IPFS 네트워크에 해당 파일을 업로드(Merkle DAG==Git에 해당 파일을 추가)하면, 파일 고유의 해시값이 산출된다.

이제 이 해시값은 IPFS상에서 해당 파일의 영구적인 이름이 된다.

Content-Addressing으로 해당 파일을 찾을 때 이 해시를 이용하게 될 것이다.

이는 영구적인 링크와 같으므로, 변조의 위험이 없다.

IPFS를 사용하는 시나리오

Scenario 1

• 해당 파일에 대한 저작권을 등록하고 싶다.
• 내가 만들었음을 증명하기 위해 블록체인에 기록하려고 한다.
• 해당 파일의 해시값을 등록한다.

Scenario 2

• 송금을 하면 어떤 파일을 지급하는 스마트 컨트랙트를 만들었다.
• 파일 용량이 너무 커서 스마트 컨트랙트 자체에 파일을 넣어둘 수는 없다.
• IPFS 상에서 해당 파일을 암호화하여 키를 갖고 있는 사람만 열람할 수 있도록 한다.
  • 해시값을 가진 사람만이 content-address로 접근해 열람이 가능할 것.
• 스마트 컨트랙트에서는 해당 파일의 해시값과 복호화 키를 담아놓는다.
• 송금한 사람은 해시값과 복호화 키를 가지고 IPFS 상에서 파일을 수령할 수 있다.

IPFS와 파일코인

파일코인은 IPFS의 인센티브 레이어이다.

IPFS 웹이 원활하게 운영되기 위해서는 노드들이 파일을 저장하고,

해당 파일을 원하는 노드에게 파일을 제공해주어야 하낟.

그러나 모든 노드들이 파일을 받기만 하려 한다면 IPFS 웹은 실현될 수 없을 것이다.

또한 여러 노드가 파일을 저장해야 더욱 안전하고, 쉽고 빠르게 공유할 수 있다.

따라서 IPFS 개발진은 파일코인이라는 토큰을 기반으로 시장을 형성하여, IPFS 웹 발전에 기여할수록 보상 받는 구조를 만들었다.

파일코인에는 두 가지 시장이 존재한다. 저장소 시장(Storage)과 검색 시장(Retrieval)이 그것이다.

각 시장에는 Miner라고 불리는 일꾼들이 있다.

저장소 시장에서 클라이언트는 저장소 마이너에게 토큰을 지불하고 파일을 저장할 수 있다.

검색 시장에서 클라이언트는 저장소 마이너에게 토큰을 지불하고 파일을 전달받을 수 있다.

두 시장 모두 클라이언트와-마이너가 거래하게 되며, 자신의 주문을 설정하거나 가격을 제시할 수 있으며,

상대방의 제안을 승낙할 수 있다.

Proof-of-Spacetime, 공간 증명 방식은 저장소 마이너가 일을 제대로 수행했음을 증명하는 것을 의미한다.

즉, 어떤 파일이 일정 기간동안 저장되고 있음을 증명하는 것이다.

저장소 마이너는 지속적으로 증명을 생성해내고, 불시에 파일코인 블록체인이 증명을 요구할 경우, 증명을 제출해야 한다.

파일코인 블록체인 마이너는 해당 증명을 검증하고, 블록에 기록한다.

빠른 오픈 소스 인 메모리 키 값 데이터 구조 스토어

Redis의 정의

Key - Value 구조의 비정형 데이터를 저장하고 관리하기 위한 오픈 소스 기반의 비관계형 데이터 베이스 관리 시스템이다.

데이터베이스, 캐시, 메세지 브로커로 사용되며 인메모리 데이터 구조를 가진 저장소이다.

db.engines.com에서 Key-value store중에 가장 순위가 높다

Redis의 특징

보통 데이터베이스는 하드 디스크나 SSD에 저장한다.

하지만 Redis는 메모리(RAM)에 저장해서 디스크 스캐닝이 필요없어 매우 빠르다.

캐싱도 가능하기 때문에 실시간 채팅에 적합하며 세션 공유를 위해 세션 클러스터링에도 활용된다.

캐시 서버의 패턴

캐시 서버는 Look aside cache 패턴과 Write Back 패턴이 존재한다.

- Look aside cache

1. 클라이언트가 데이터를 요청

2. 웹서버는 데이터가 존재하는지 Cache 서버에 먼저 확인
3. Cache 서버에 데이터가 있으면 DB에 데이터를 조회하지 않고 Cache 서버에 있는 결과값을 클라이언트에게 바로 반환 (Cache Hit)
4. Cache 서버에 데이터가 없으면 DB에 데이터를 조회하여 Cache 서버에 저장하고 결과값을 클라이언트에게 반환 (Cache Miss)

- Write Back

1. 웹서버는 모든 데이터를 Cache 서버에 저장
2. Cache 서버에 특정 시간 동안 데이터가 저장됨
3. Cache 서버에 있는 데이터를 DB에 저장
4. DB에 저장된 Cache 서버의 데이터를 삭제

• insert 쿼리를 한 번씩 500번 날리는 것보다 insert 쿼리 500개를 붙여서 한 번에 날리는 것이 더 효율적이라는 원리다.
• 이 방식은 들어오는 데이터들이 저장되기 전에 메모리 공간에 머무르는데 이때 서버에 장애가 발생하여 다운된다면 데이터가 손실될 수 있다는 단점이 있다.

...Redis의 특징

그러나 이 때, RAM은 휘발성이라 컴퓨터가 꺼지면 정보가 다 날아가버린다는 약점이 있다.

이를 막기위한 백업 과정이 다음 두 가지로 나뉜다.

1. Snapshot : 특정 지점을 설정하고 디스크에 백업.
2. AOF : 명령(쿼리)들을 저장해두고, 서버가 셧다운되면 재실행해서 다시 만들어 놓는 것.

Redis의 경우 Key-value구조이기 때문에 쿼리를 사용할 필요가 없다. 대신 Redis 명령어를 사용한다.

지원하는 자료구조는 String, Sets, Lists, Sorted Sets, Hashes 자료구조가 있다.

또한 레디스는 Single Threaded이다. 따라서 한 번에 하나의 명령만 처리할 수 있다.

그렇기 때문에 동기적으로 명령들이 처리가 되는데, get, set 명령어의 경우 초당 처리속도가 10만개를 넘어가기 때문에 의미는 없다.

Redis 사용의 주의할 점

서버에 장애가 발생했을 경우 그에 대한 운영 플랜이 반드시 필요하다.

인메모리 저장방식이기 때문에 데이터 유실이 발생할 수 있는데, 이것을 어떻게 효과적으로 방지할 것인지?

또한, 당연한 얘기지만, 메모리 관리가 매우 중요하다.

그리고 싱글 스레드의 특성상 한 번에 하나의 명령만을 처리하기 때문에, 처리하는데 시간이 오래 걸릴 수 있는 요청은 최대한 피하는 것이 좋겠다.

Sources

참고 링크

참고 링크

Definitions

Race Condition이란 두 개 이상의 프로세스가 공통 자원을 Concurrently하게 읽거나 쓰는 동작을 할 때,

공용 데이터에 대한 접근이 어떤 순서에 따라 이루어졌는지에 따라 그 실행 결과가 같지 않고 달라지는 상황을 말한다.

EXAMPLES

1. 커널 작업을 수행하는 중에 인터럽트 발생

문제점 : 커널 모드에서 데이터를 로드하여 작업을 수행하다가 인터럽트가 발생하여 같은 데이터를 조작하는 경우

해결법 : 커널모드에서 작업을 수행하는 동안, 인터럽트를 disable 시켜 CPU 제어권을 가져가지 못하도록 한다.

2. 프로세스가 System Call을 하여 커널 모드로 진입하여 작업을 수행하는 도중 문맥 교환(Context Switching)이 발생할 때.

문제점 : 프로세스1이 커널모드에서 데이터를 조작하는 도중, 시간이 초과되어 CPU 제어권이 프로세스2로 넘어가 같은 데이터를 조작하는 경우. ( 프로세스2가 작업에 반영되지 않음 )

해결법 : 프로세스가 커널모드에서 작업을 하는 경우 시간이 초과되어도 CPU 제어권이 다른 프로세스에게 넘어가지 않도록 함.

3. 멀티 프로세서 환경에서 공유 메모리 내의 커널 데이터에 접근할 때

문제점 : 멀티 프로세서 환경에서 2개의 CPU가 동시에 커널 내부의 공유 데이터에 접근하여 조작하는 경우

해결법 : 커널 내부에 있는 각 공유 데이터에 접근할 때마다, 그 데이터에 대한 lock/unlock을 하는 방법

Race의 뜻 그대로, 간단히 말하면 경쟁하는 상태, 즉 두 개의 스레드가 하나의 자원을 놓고 서로 사용하려고 경쟁하는 상황을 말한다.

이러한 경쟁 프로세스의 경우, 다음 세 가지 제어문제에 직면한다.

Mutual Exclusion

Race condition을 막기 위해서는 두 개 이상의 프로세스가 공용 데이터에 동시에 접근을 하는 것을 막아야 한다.

즉, 한 프로세스가 공용 데이터를 사용하고 있으면 그 자원을 사용하지 못하도록 막거나,

다른 프로세스가 그 자원을 사용하지 못하도록 막으면 이 문제를 피할 수 있다. 이것을 상호 배제(mutual exclusion)라고 부른다.

DeadLock

그러나 위와 같은 상호 배제를 시행하면 추가적인 제어 문제가 발생한다. 하나는 교착상태 즉 여기서 말하는 Deadlock이다.

프로세스가 각자 프로그램을 실행하기 위해 두 자원 모두에 엑세스 해야 한다고 가정할 때,

프로세스는 두 자원 모두를 필요로 하므로 필요한 두 리소스를 사용하여 프로그램을 수행할 때까지 이미 소유한 리소스를 해제하지 않는다.

이러한 상황에서 두 프로세스는 교착 상태에 빠지게 되는 문제가 발생할 수 있다.

Starvation

이 제어 문제는 ‘기아 상태’라고도 한다. 이러한 문제는 프로세스들이 더 이상 진행을 하지 못하고 영구적으로 블록되어 있는 상태로,

시스템 자원에 대한 경쟁 도중에 발생할 수 있고 프로세스 간의 통신 과정에도 발생할 수 있는 문제이다.

두 개 이상의 작업이 서로 상대방의 작업이 끝나기만을 기다리고 있기 때문에 결과적으로는 아무것도 완료되지 못하는 상태가 되게 된다.

이렇게 race condition 인 경우에는 스레드의 실행 순서를 잘 조절해주지 않으면 이상한 상태, 비정상적인 상태가 나오게 된다.

이 문제는 항상 발생하는 것이 아니라 특정한 순서대로 수행되었을 때 발생하는 것이다.

이 문제는 디버깅을 할 때에는 전혀 보이지 않는 문제점이고,

발생 시에 모든 프로세스에 원하는 결과가 발생하는 것을 보장할 수 없으므로 후에 더욱 큰 문제를 야기할 수 있으므로 반드시 피해야 하는 상황이다.

이러한 문제가 발생하지 않도록, OS는 다른 프로세스의 의도하지 않은 간섭으로부터 각 프로세스의 데이터 및 물리적 자원을 보호해야 하며

여기에 메모리, 파일 및 I/O 장치와 관련된 내용이 포함된다.

그리고 프로세스에서 수행하는 내용과 프로세스가 생성하는 결과는, 다른 동시 프로세스의 실행 속도와 무관, 즉 기능과 결과는 서로 독립적이어야 한다.

Sources

참고1

참고2

참고3

참고4

프로세스는 운영체제가 자원을 할당하는 단위이다.

프로세스가 메모리를 할당 받으면, 자신만의 방법으로 메모리를 관리하기 위해 이 공간들을 어떤 구조로 관리하는데, 우리는 이를 프로세스 주소 공간이라고 부른다.

프로세스 주소공간은 다음과 같이 나뉘어진다.

Stack 영역

함수의 호출과 관계되는 지역변수와 매개변수가 저장되는 영역.

Stack 영역의 값은 함수의 호출과 함께 할당되며, 함수의 호출이 완료되면 소멸한다.

메모리의 높은 주소에서 낮은 주소의 방향으로 할당된다.

재귀 함수가 너무 깊게 호출되거나 함수가 지역변수를 너무 많이 가지고 있어 stack 영역을 초과하면 stack overflow 에러가 발생한다.

Heap 영역

런타임에 크기가 결정되는 영역. 사용자에 의해 공간이 동적으로 할당 및 해제된다.

주로 참조형 데이터 (ex. 클래스) 등의 데이터가 할당된다.

메모리의 낮은 주소에서 높은 주소의 방향으로 할당된다.

Data 영역

전역 변수나 Static 변수 등 프로그램이 사용할 수 있는 데이터를 저장하는 영역이다.

어떤 프로그램에 전역/static 변수를 참조하는 코드가 존재한다면, 이 프로그램은 컴파일 된 후에 data 영역을 참조하게 된다.

프로그램의 시작과 함께 할당되며, 프로그램이 종료되면 소멸한다.

단, 초기화 되지 않은 변수가 존재한다면, 이는 (그림에는 표현되지는 않았지만 BSS 영역에 저장된다.)

Text(Code) 영역

프로그램이 실행될 수 있도록 CPU가 해석 가능한 기계어 코드가 저장되어 있는 공간으로,

프로그램이 수정되면 안 되므로 ReadOnly 상태로 저장 되어있다.

결국 메모리는 한정되어 있기 때문에, 프로세스는 다양한 방법으로 메모리를 절약하려고 시도한다.

Data 영역과 Stack 영역

Code 영역은 기계어 코드가 들어있으니 다른 구역과 너무 다르고, Heap 영역은 런타임에 크기가 결정되는 영역이다.

그렇다면 Stack 영역과 Data 영역을 구분한 이유는 무엇일까? 가장 큰 이유는 역할의 분배이다.

우리는 Stack 영역을 통해 함수의 흐름을 관리하고, Data 영역을 통해 전역 변수, static 변수를 관리한다.

만약 한 프로세스가 여러개의 스레드를 갖는다면, 각각의 스레드는 자신만의 Stack 영역을 갖는다.

이는 스레드 내에서 수행되는 함수의 흐름을 각각 관리하기 위함이다.

여기에서 영역을 구분한 또 다른 중요한 이유가 나오는데, 바로 Data 영역의 공유이다.

각각의 스레드는 Stack 영역을 갖긴 하지만 Data 영역은 공유한다.

즉, 각각의 스레드가 사용하기 위해 Data 영역의 동일한 내용을 공유함으로써, 똑같은 공간을 여러개 만들지 않고 메모리를 절약할 수 있다.

Sources

참고 링크

참고 링크

참고 링크

Definition

애플리케이션이 시작될 때, 어떤 클래스가 최초 한 번만 메모리를 할당(static)하고 해당 메모리에 인스턴스를 만들어 사용하는 패턴.

쉽게 얘기하면 싱글톤 패턴은 하나의 인스턴스만 생성하여 사용하는 디자인 패턴,

즉, 객체의 인스턴스가 오직 1개만 생성되는 패턴을 의미한다.

싱글톤 패턴을 구현하는 방법은 여러 가지가 있지만, 객체를 미리 생성해두고 가져오는 방법이 가장 단순하고 안전하다.

Example

Java

public class Singleton {

    private static Singleton instance = new Singleton();

    private Singleton() {
        // ...
    }

    public static Singleton getInstance() {
        return instance;
    }

    public void say() {
        System.out.println("hi, there");
    }
}

Golang

type Singleton struct {
    Instance string
}

// private 
func (sg *Singleton) instanceConstructor() {
    // ...
}

// public
func (sg *Singleton) GetInstance() {
    return sg.Instance
}

func (sg *Singleton) Say() {
    fmt.Println("hi, there");
}

인스턴스가 필요할 때, 똑같은 인스턴스를 만들지 않고 기존의 인스턴스를 활용.

Why Singleton Pattern ?

이렇게 인스턴스를 오직 한 개로만 가져가게 되면 몇 가지 이점이 있다.

1. 메모리 측면

최초 한번만 고정된 메모리 영역을 사용하기 때문에 추후 해당 객체에 접근할 때 메모리 낭비를 방지할 수 있다.

또한 이미 생성된 인스턴스를 활용하니 속도 측면에서도 이점이 있다고 볼 수 있다.

2. 공유의 이점

싱글톤 인스턴스는 전역으로 사용되기 때문에 서로 다른 객체간에 데이터 공유가 쉽다.

하지만 여러 객체의 인스턴스에서 싱글턴 인스턴스의 데이터에 동시에 접근하게 되면 동시성 문제가 발생할 수 있어서 이 점에 유의해야한다.

보통 싱글톤 패턴은 공통된 객체를 여러 개 생성해서 사용해야 하는 상황,

예를 들면 데이터베이스의 커넥션 풀, 스레드 풀, 캐시, 로그 기록 객체 등에 많이 사용한다.

이 외에도 도메인 관점에서 인스턴스가 한 개만 존재하는 것을 보증하고 싶은 경우 싱글톤 패턴을 사용하기도 한다.

Problems

싱글톤 패턴을 적용하면 위와 같은 효율적인 측면에서의 이점이 있지만, 다음과 같은 문제점이 발생할 수 있다.

개발자는 이러한 문제점과 이점의 trade-off를 잘 고려해야한다.

개방-폐쇄 원칙 위배

만약 싱글톤 인스턴스가 혼자 너무 많은 일을 하거나, 많은 데이터를 공유시키면 다른 클래스들 간의 결합도가 높아지게 되는데, 이때 개방-폐쇄 원칙이 위배된다.

결합도가 높아지면 유지보수가 힘들고 테스트도 원활하게 진행하기 힘들다.

동시성 문제

정적 팩토리 메서드에서 객체 생성을 확인하고 생성자를 호출하는 경우에, 멀티스레드 환경에서는 동시성 문제가 발생할 수 있다.

멀티 스레드 환경에서 동기화 처리를 하지 않았다면 인스턴스가 2개가 생성되는 문제도 발생할 수 있다.

이러한 문제를 해결하기 위해서 동기화 처리를 한다면 효율 저하 및 추가적인 코드 작성이 발생한다.

 N개의 양의 정수 X{i}와 곱하기 연산자, 더하기 연산자가 총 N−1개가 존재하고 괄호는 무수히 많이 사용해도 된다. 이 연산에는 곱하기 연산자와 더하기 연산자의 우선순위가 동일하다.

정수와 연산자는 아래와 같이 배치해야한다. 정수의 순서는 바꿔도 상관없다.

예를 들어 정수 1, 2, 3이 있고 더하기 연산자와 곱하기 연산자가 각각 하나 있다고 가정하면 아래와 같이 만들 수 있다. 

예를 들어, 수 1,2,4,5,7,8와 더하기 연산자가 4개 곱하기 연산자가 1개 있다고 하자. 괄호를 이용하여 최대값을 구하는 방법 중 일부이다.

•  (((1+2)+4)+7)×(5+8)
•  ((1+2)+(4+7))×(5+8)
•  (1+(2+4)+7)×(5+8)
•  (1+2+4+7)×(5+8)

연산을 잘 이용하여 값을 최대로 만들어 보자.

풀이

이 문제는 꽤 어려웠는데 의외로 한 번에 풀었다. 하지만 고민하는 시간이 매우 길었던 것 같다.

덧셈을 이용해 작은 수들을 큰 수로 만들고, [큰 수 * 큰 수]의 꼴로 만들어야 한다는 것이 핵심 아이디어였는데,

숫자의 순서가 바뀌어도 된다는 부분에서 고민을 많이 했다.

결국 이렇게도 해보고 저렇게도 해보다가 직접 구현했던 조합 함수를 가져와서 이용했다.

특이 사항은 조합 함수에서 next + [arr[i]]로 구현을 한 것인데,

이렇게 한 이유는 dfs 함수 내에서 뽑아낸 조합의 함을 pop으로 꺼내오면서 더해줄 때

뒤에 있는 index부터 꺼내오게 해야 정확하게 원하는 값들을 가져올 수 있다.

import sys

si = sys.stdin.readline


def MIIS(): return map(int, si().split())


n = int(si())
lst = sorted(MIIS())
p, q = MIIS()
answer = 0
'''
곱하기 개수 + 1개 덩어리로 나누어서 각 수의 곱이 최대로 하는 값 찾기
곱하기 개수 + 1개의 덩어리로 나누는 경우의 수를 전부 찾는다.
--> 조합으로 경우의 수 찾아내고 dfs로 max값 갱신시켜나간다. 
'''
# arr에서 r개를 뽑는 조합


def combinations(arr, r):
    for i in range(len(arr)):
        if r == 1:
            yield [arr[i]]
        else:
            for next in combinations(arr[i+1:], r-1):
                yield next + [arr[i]]

# dfs로 구현


def dfs(arr, count, now):
    # 곱하기가 0이 들어오면 남은 숫자 전부 더하면 된다.
    if count == 0:
        global answer
        answer = max(answer, now * sum(arr))
        return now * sum(arr)
    # 들어온 arr의 인덱스를 가지는 리스트
    idx = range(len(arr))
    for i in range(1, len(arr) - count + 1):
        # j는 [0,1,2,3,4,5]에서 i개를 뽑는 경우의 수
        for j in combinations(idx, i):
            temp = arr[:]
            # print(f"temp = {temp}")
            # 현재 조합의 합을 들어온 이전 결과에 곱해준다.
            multiple_to = 0
            # 인덱스를 기준으로 뽑아내서 담는다.
            for k in j:
                multiple_to += temp.pop(k)
            # print(f"temp_sum = {multiple_to}")
            # 복사한 리스트, 덩어리 하나 선택, 현재 곱셈한 결과 보냄
            dfs(temp, count - 1, now * multiple_to)
    return answer


answer = dfs(lst, q, 1)
print(answer)

송훈이는 로봇 동아리 회원이다. 로봇 동아리에서 필요한 부품이 있을 경우 자유롭게 빌려서 쓰고 다시 돌려놓으면 된다.

하지만 부품 정리를 하다가 부품 관리가 너무 힘들어져 새로운 시스템을 도입하려고 한다.

부품을 빌려갈 경우 부품 대여장에 정보를 반드시 작성해야한다. 또한 빌려간 부품을 반납 할 경우에도 부품 대여장에 정보를 작성해야한다.

또한 대여기간을 정하고 대여기간을 넘길 경우 1분당 벌금을 부여하도록 하는 시스템이다.

만약 대여기간이 5분, 1분당 벌금이 5원이라 했을 때 대여한 시각이 2021년 1월 1일 1시 5분이라면 2021년 1월 1일 1시 10분까지 반납해야한다.

2021년 1월 1일 1시 14분에 반납을 했다면 4분 늦었기 때문에 벌금을 20원을 내야한다.

부품 대여장에 쓰는 형식은 아래와 같다.

yyyy-MM-dd hh:mm [부품 이름] [동아리 회원 닉네임]

아래는 예시를 위한 부품 대여장에 작성된 정보이다. 대여기간이 5분, 벌금은 1원이라 가정하자.

2021-01-01 09:12 arduino tony9402
2021-01-01 09:13 monitor chansol
2021-01-01 09:18 arduino tony9402
2021-01-01 09:18 monitor chansol

위의 정보를 정리하면 아래와 같다.

tony9402가 2021년 1월 1일 오전 9시 12분에 arduino를 빌렸다.
chansol이 2021년 1월 1일 오전 9시 13분에 monitor를 빌렸다.
tony9402가 2021년 1월 1일 오전 9시 18분에 arduino를 반납했다.
chansol이 2021년 1월 1일 오전 9시 18분에 monitor를 반납했다.

tony9402는 1분 늦게 반납했기 때문에 벌금 1원을 내야한다.

부품을 대여할 때 지켜야 하는 조건이 있다.

1. 한 사람이 같은 종류의 부품을 두개 이상 대여하고 있는 상태일 수 없다.
2. 한 사람이 같은 시각에 서로 다른 종류의 부품들을 대여하는 것이 가능하다.
3. 같은 사람이더라도, 대여 기간은 부품마다 별도로 적용된다.

풀이

진짜 문제를 안읽고 풀면 어떻게 되는 지 반성할 수 있는 좋은 사례.

시간 순으로 입력이 들어오는데 굳이 처리를 따로 해줬다. 시간에 따라 heapq를 사용해서 꺼내오는 방식을 사용했는데,

당연히 안됐다. 아래는 삽질 코드

import sys
from heapq import heappush, heappop
from datetime import datetime, timedelta


def si(): return sys.stdin.readline()


def msis(): return map(str, si().split())


n, l, f = msis()
n, f, penalty = int(n), int(f), timedelta(days=int(l[:3]), hours=int(l[4:6]), minutes=int(l[7:]))
minute = timedelta(minutes=1)
p_table = {}
f_table = {}
heap = []
for _ in range(n):
    date, time, part, nickname = si().split()
    date = datetime.strptime(date + ' ' + time, '%Y-%m-%d %H:%M')
    p_table[part] = []
    f_table[nickname] = 0
    heappush(heap, (date, part, nickname))

while heap:
    d, p, m = heappop(heap)
    flag = True
    for lst in p_table[p]:
        if m == lst[1]:
            flag = False
            period = d - lst[0]
            if period > penalty:
                f_table[m] += ((period - penalty) // minute) * f
            p_table[p].remove(lst)
            break
    if flag:
        p_table[p].append((d, m))

result = [(k, v) for k, v in f_table.items() if v]
result.sort(key=lambda x: x[0])
for nick, val in result:
    print(nick, val)

문제를 다시 읽고, 단단히 잘못 하고 있다는 것을 알고 다시 풀었다. 

timedelta를 이용해서 날짜 연산을 해주는 방식으로 진행했고, 딕셔너리를 이용해 빌려간 요청인지 빌리는 요청인지 구분.

알고리즘 없는 구현문제였던 것 같다. 

import sys
from collections import defaultdict
from datetime import datetime, timedelta


def si(): return sys.stdin.readline()


def msis(): return map(str, si().split())


n, l, f = msis()
n, f, maximum = int(n), int(f), timedelta(days=int(l[:3]), hours=int(l[4:6]), minutes=int(l[7:]))
minute = timedelta(minutes=1)
table = defaultdict(dict)
p_table = defaultdict()
for _ in range(n):
    line = si()
    now = datetime.strptime(line[:16], '%Y-%m-%d %H:%M')
    part, name = line[16:].split()
    if not p_table.get(name):
        p_table[name] = 0
    if table[name].get(part):
        period = now - table[name][part]
        if period > maximum:
            p_table[name] += ((period - maximum) // minute) * f
        del table[name][part]
    else:
        table[name][part] = now

ret = [(k, v) for k, v in p_table.items() if v]
if ret:
    for name, val in sorted(ret, key=lambda x: x[0]):
        print(name, val)
else:
    print(-1)

지우고 싶은 문자열 S와 지울 수 있는 문자열 A{1}, A{2}, ..., A{M}이 주어진다. 문자열 A{i}들은 각자 X{i}라는 점수를 가진다. 이 때, 문자열 S를 삭제 연산을 이용하여 모두 제거하려고 한다.

삭제 연산은 두 가지 방법이 존재하며, 원하는 만큼 여러 번에 걸쳐서 수행할 수 있다.

1. 문자열 S의 부분 문자열 중에 문자열 A{i} 가 존재한다면 해당하는 부분을 지우고 X{i} 만큼의 점수를 얻는다(여러 부분 존재해도 한 번만 지운다).
2. 문자열 S에서 문자 하나를 지우고 점수를 1점을 얻을 수 있다.

예를 들어, 문자열 S가 "abcxyzxabc"이 있고 "abc" 문자열을 지울 경우 10점, "xyz" 문자열을 지울 경우 5점을 얻는다고 하자. 문자열을 모두 제거하여 최대 점수를 얻을 수 있는 과정은 아래와 같다.

• 문자열 S에서 문자열 "xyz" 하나를 지운다. 현재 총 얻은 점수는 5점이고 문자열 S$S$는 "abc___xabc"가 된다. 이때, '_'는 문자가 지워진 자리를 의미한다.
• 문자열 S에서 문자열 "abc" 하나를 지운다. 현재 총 얻은 점수는 15점이고 문자열 S는 "______xabc"가 된다.
• 문자열 S에서 문자열 "abc" 하나를 지운다. 현재 총 얻은 점수는 25점이고 문자열 S는 "______x___"가 된다.
• 남은 문자들을 하나씩 지운다. 현재 총 얻은 점수는 26점이고 문자열 S는 빈 문자열이 된다.

문자열을 모두 제거하여 얻을 수 있는 최대 점수는 26점이다. 이보다 더 얻을 수 있는 점수는 없다.

삭제 연산을 이용하여 문자열 S을 지울려고 할 때 얻을 수 있는 최대 점수는 몇 점인지 계산하자.

풀이

여러 가지 방법을 시도해봤다. re를 이용해서 문자열을 줄이는 방법과, 단순 슬라이싱으로 바꾸는 방법, replace 등등

많은 삽질이 있었으나 전부 실패했다. 투포인터를 이용해서 인덱스로 접근을 해보려다가,

같은 스터디원이 전에 무슨 문제인지 모르겠으면 다이나믹 프로그래밍 문제라는 말을 했던 것이 생각나서 dp로 구현해봤다.

문자열을 하나 지우면 1점을 얻을 수 있기 때문에 이를 식으로 만들어서 재귀함수와 dp로 구현했다.

주의할 점은 이미 갱신 되었는지 체크해주는 것과 문자열의 길이를 인덱스가 초과하면 바로 return 0을 해줘야 한다.

import sys
from math import inf


si = sys.stdin.readline
sys.setrecursionlimit(10**8)

def MSIS():
    return map(str, si().split())


s = si().rstrip()
m = int(si())

table = []
score = [-inf for _ in range(len(s))]
for _ in range(m):
    temp = list(MSIS())
    table.append([temp[0], int(temp[1])])


def solution(start):
    global score
    # 문자열 s의 길이를 초과하면 얻는 점수 0
    if start >= len(s):
        return 0
    if score[start] != -inf:
        return score[start]
    # start번째의 점수는 start + 1번째의 함수가 가질 수 있는 점수 + start번째를 삭제하는 점수
    score[start] = solution(start + 1) + 1
    # key value를 받아온다.
    for k, v in table:
        # print(f"start = {start}, k = {k}, v = {v}")
        # s의 start번째에서 k가 발견되면
        if s[start:start + len(k)] == k:
            # score의 start번째에서 얻을수 있는 점수를 구해낸다.
            # 원래 점수와 k번째 문자열로 점수를 얻었을 때를 비교
            score[start] = max(score[start], solution(start + len(k)) + v)
            # print(f"start = {start}, score is now {score}")

    return score[start]


print(solution(0))

준형이는 내일 친구들을 만나기로 했다. 준형이와 친구들은 서로 다른 도시에 살고 있다.

도시를 연결하는 도로는 일방 통행만 있어서 도시 A{i}에서 도시 B{i}로 가는 시간과 도시 B{i}에서 도시 A{i}로 가는 시간이 다를 수 있다.

준형이와 친구들은 아래 조건을 만족하는 도시 X를 선택하여 거기서 만나려고 한다.

• 왕복시간은 자신이 살고 있는 도시에서 도시 X로 이동하는 시간과 도시 X에서 다시 자신이 살고 있는 도시로 이동하는 시간을 합한 것이다.
• 준형이와 친구들이 도로를 이용하여 갈 수 있는 도시만 선택한다.
• 준형이와 친구들의 왕복시간 들 중 최대가 최소가 되는 도시 X를 선택한다.
• 준형이와 친구들이 이동할 수 있는 도시가 최소한 하나 이상이 있음을 보장한다.

도시가 많다보니 계산하기 힘들다. 준형이와 친구들을 대신하여 도시 X를 알려주자.

위 조건을 만족하는 도시 X의 번호를 출력한다. 만약 가능한 도시 X가 여러 개인 경우는 도시의 번호를 오름차순으로 출력한다.

풀이

초기에 heapq를 이용해서 날먹을 하려다 실패했다.

문제를 잘 읽어야 하는 것이, a에서 b를 갈 수 있는데, b에서 a를 가는 길은 없을 수도 있다.

여러 시행착오를 겪다가, n이 충분히 작아서 전부 탐색을 해도 되겠다는 생각이 들었다. 

우선모든 도시까지의 최단거리를 구해준 다음, 친구들 집에서 모든 도시까지의 왕복시간을 구하면서 최대값을 갱신한다.

이 논리로 친구들 도시에서 index번 도시까지의 왕복시간 중 최대값을 answer에 담고, min값을 담은 인덱스를 리턴했다.

친구들 도시에서 index번 도시를 왕복할 수 있다는 것이 이동할 수 있는 도시가 최소한 하나 이상 보장된다는 반증인 것을 이용한 풀이.

import sys
from heapq import heappush, heappop
from math import inf

si = sys.stdin.readline


def MIIS(): return map(int, si().split())


n, m = MIIS()

graph = [[inf] * (n + 1) for _ in range(n + 1)]
for a in range(1, n + 1):
    for b in range(1, n + 1):
        if a == b:
            graph[a][b] = 0

for _ in range(m):
    s, e, d = MIIS()
    graph[s][e] = d

k = int(si())
friends = list(MIIS())

# j에서 k까지 가는 시간과 i를 경유해서 가는 시간을 비교해서
for i in range(1, n + 1):
    for j in range(1, n + 1):
        for k in range(1, n + 1):
            graph[j][k] = min(graph[j][k], graph[j][i] + graph[i][k])

answer = [0]
for o in range(1, n + 1):
    _max = -inf
    for f in friends:
        # 친구집이 도착지와 같으면 0이니까 패스, 친구집에서 도착지 혹은 그 반대가 경로가 없으면 패스
        if f != o and graph[f][o] != inf and graph[o][f] != inf:
            # 각 친구 집에서 목적지까지의 왕복시간이 현재 최대값보다 크면 갱신
            if _max < graph[f][o] + graph[o][f]:
                _max = graph[f][o] + graph[o][f]
    answer.append(_max)

_min = min(answer[1:])
for ans in range(1, n + 1):
    if answer[ans] == _min:
        print(ans, end=" ")

tony9402는 최근 깃헙에 코딩테스트 대비 문제를 직접 뽑아서 "문제 번호, 난이도"로 정리해놨다.

깃헙을 이용하여 공부하시는 분들을 위해 새로운 기능을 추가해보려고 한다.

만들려고 하는 명령어는 총 3가지가 있다. 아래 표는 각 명령어에 대한 설명이다.

명령어 recommend는 추천 문제 리스트에 문제가 하나 이상 있을 때만 주어진다.

명령어 solved는 추천 문제 리스트에 문제 번호가 하나 이상 있을 때만 주어진다.

위 명령어들을 수행하는 추천 시스템을 만들어보자.

풀이

노가다로 해결한 문제. 단순히 분기를 나누고 min, max값을 구해서 해결할 수 있다고 생각했는데, 어림도 없었다.

이런 저런 방법들을 전부 사용해보다가, 같은 스터디원이 heap을 쓰다가 포기했다는 것을 듣고 heap으로 구현해봤다.

아래는 초기 실패 코드

import sys
from collections import Counter

si = sys.stdin.readline
def MIIS(): return map(int, si().split())


n = int(si())

prob = {k: [] for k in range(101)}
idx = {}
for _ in range(n):
    num, difficulty = MIIS()
    prob[difficulty].append(num)
    idx[num] = difficulty

_max = max(x for x in prob if prob[x])
_min = min(x for x in prob if prob[x])
m = int(si())
ret = []

for _ in range(m):
    line = si().split()
    if line[0] == 'add':
        num, diff = map(int, line[1:])
        if diff < _min:
            _min = diff
        elif diff > _max:
            _max = diff
        prob[diff].append(num)
        idx[num] = diff
    elif line[0] == 'solved':
        num = int(line[1])
        if num in prob[_min]:
            prob[idx[num]].remove(num)
            _min = min(x for x in prob if prob[x])
        elif num in prob[_max]:
            prob[idx[num]].remove(num)
            _max = max(x for x in prob if prob[x])
        else:
            prob[idx[num]].remove(num)
    elif line[0] == 'recommend':
        if line[1] == '-1':
            ret.append(sorted(prob[_min])[0])
        else:
            ret.append(sorted(prob[_max])[-1])

for a in ret:
    print(a)

삽질의 흔적...

아래는 성공한 코드이다. 

defaultdict를 이용하면서 해결 했는 지 체크하고, 명령어에 따라 min_heap과 max_heap을 적절히 섞어가며 사용했다.

애를 먹었던 부분은 add하는 부분에서 같은 문제가 해결되고 다른 난이도로 다시 들어올 수 있다는 사실을 간과했던 것이다.

이를 막기 위해 add에서도 해결된 문제들을 전부 빼주는 방식으로 진행했더니 해결되었다. 

from collections import defaultdict
import sys
import heapq

si = sys.stdin.readline
def MIIS(): return map(int, si().split())


n = int(si())

# recommend 용
min_heap = []
max_heap = []
ret = []

visited = defaultdict()

for _ in range(n):
    num, difficulty = MIIS()
    heapq.heappush(min_heap, (difficulty, num))
    heapq.heappush(max_heap, (-difficulty, -num))
    visited[num] = False
m = int(si())
for _ in range(m):
    line = si().split()
    if line[0] == 'add':
        num, difficulty = map(int, line[1:])
        while visited[(min_heap[0][1])]:
            heapq.heappop(min_heap)
        while visited[-(max_heap[0][1])]:
            heapq.heappop(max_heap)
        heapq.heappush(min_heap, (difficulty, num))
        heapq.heappush(max_heap, (-difficulty, -num))
        visited[num] = False

    elif line[0] == 'solved':
        visited[int(line[1])] = True

    else:
        if line[1] == '1':
            while visited[-(max_heap[0][1])]:
                heapq.heappop(max_heap)
            ret.append(-max_heap[0][1])
        else:
            while visited[min_heap[0][1]]:
                heapq.heappop(min_heap)
            ret.append(min_heap[0][1])


for ans in ret:
    print(ans)

간단하지만 귀찮은 영상처리 과제가 주어졌다. 과제의 명세는 다음과 같다.

세로 길이가 N\이고 가로 길이가 M인 화면은 총 N × M개의 픽셀로 구성되어 있고 (i, j)에 있는 픽셀은 R{i,j} (Red), G{i,j} (Green), B{i,j} (Blue) 3가지 색상의 의미를 담고 있다. 각 색상은 0이상 255이하인 값으로 표현 가능하다.

모든 픽셀에서 세 가지 색상을 평균내어 경계값 T보다 크거나 같으면 픽셀의 값을 255로, 작으면 0으로 바꿔서 새로운 화면으로 저장한다.

새로 만들어진 화면에서 값이 255인 픽셀은 물체로 인식한다. 값이 255인 픽셀들이 상하좌우로 인접해있다면 이 픽셀들은 같은 물체로 인식된다.

화면에서 물체가 총 몇 개 있는지 구하는 프로그램을 작성하시오.

풀이

너비 탐색을 이용해서 풀었다. 초기에 문제를 잘못 이해해서 삽질을 좀 했던 문제.

case를 음수로 만들어놓고 주변으로 퍼져나가면서 -1, -2, ... 점점 내려가서 결국 minimum값을 양수로 만들어주면 답이 된다.

파싱하는 부분이 귀찮았는데, 다른 방법을 강구해보는 것도 좋을 것 같다. 

import sys
from collections import deque, Counter

si = sys.stdin.readline
def MIIS(): return map(int, si().split())


n, m = MIIS()
screen = [list(MIIS()) for _ in range(n)]
t = int(si())

graph = [[] * m for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
visited = [[False] * m for _ in range(n)]

for i in range(n):
    line = screen[i]
    col = 0
    for j in range(0, (3 * m), 3):
        avg = sum(line[j:j + 3])
        if avg >= (t * 3):
            avg = 255
        else:
            avg = 0
        graph[i].append(avg)
        col += 1


def bfs(start, num):
    q = deque()
    q.append(start)
    while q:
        x, y = q.popleft()
        graph[x][y] = num
        for d in range(4):
            nx, ny = x + dx[d], y + dy[d]
            if 0 <= nx < n and 0 <= ny < m:
                if graph[nx][ny] == 255 and not visited[nx][ny]:
                    visited[nx][ny] = True
                    q.append((nx, ny))


case = -1
for i in range(n):
    for j in range(m):
        if graph[i][j] == 255:
            bfs((i, j), case)
            case -= 1


answer = min([min(arg) for arg in graph])
print(answer * - 1)

민상이는 자신이 해야할 작업 N개를 아래와 같이 작업 순서도로 그려보았다.

위 그림에서 5번 작업을 하기 위해 제일 먼저 2번 작업을 끝내야 하고 그 다음으로 4번 작업을 끝내야 5번 작업을 할 수 있다. 3번 작업은 먼저 해야하는 작업이 없으므로 3번 작업을 바로 시작 할 수 있다.

작업 순서를 정할때 위배되는 작업 순서는 없다. 예를 들어, A 작업을 하려면 B 작업을 먼저 해야하고, B 작업을 해야하기 전에 A 작업을 해야하는 상황은 없다.

민상이는 오늘 반드시 끝낼 작업 X가 있다. 민상이가 작업 X 을 끝내기 위해서 먼저 해야하는 작업의 개수를 구해주자!

풀이

단순히 재귀함수 구현으로 풀 수 있는 문제였다. 깊이 탐색을 이용해서 각 작업의 선행 작업들을 처리하게 하고,

스택에서 빠져 나오면서 답을 도출할 수 있었다. 

from collections import deque
import sys

si = sys.stdin.readline
def MIIS(): return map(int, si().split())


n, m = MIIS()
todo = [[] * (n + 1) for _ in range(n + 1)]
tree = [0] * (n + 1)
visited = [False] * (n + 1)
sys.setrecursionlimit(10 ** 6)

for _ in range(m):
    a, b = MIIS()
    todo[b].append(a)

x = int(si())


def dfs(x):
    if not todo[x]:
        visited[x] = True
        return 0
    for node in todo[x]:
        if not visited[node]:
            tree[x] += dfs(node) + 1
            visited[node] = True
    return tree[x]


print(dfs(x))

채완이는 신도시에 건물 사이를 잇는 양방향 도로를 만들려는 공사 계획을 세웠다.

공사 계획을 검토하면서 비용이 생각보다 많이 드는 것을 확인했다.

채완이는 공사하는 데 드는 비용을 아끼려고 한다. 

모든 건물이 도로를 통해 연결되도록 최소한의 도로를 만들려고 한다.

채완이는 도로가 너무 많아 절약되는 금액을 계산하는 데 어려움을 겪고 있다.

채완이를 대신해 얼마나 절약이 되는지 계산해주자.

예산을 얼마나 절약 할 수 있는지 출력한다. 만약 모든 건물이 연결되어 있지 않는다면 -1을 출력한다.

풀이

핵심 아이디어는 n개의 도시를 위해 n-1개의 간선을 설치한다는 것 이다.

MST 유형의 문제라고 판단하고 Prim 알고리즘을 이용해서 풀었다.

초기에 다른 문제를 풀 때 처럼 코드를 짰는데, 시간 초과도 아니고 메모리 초과가 떴다.

from collections import deque
import sys

si = sys.stdin.readline
n, m = map(int, si().split())

graph = [[0] * (n + 1) for _ in range(n + 1)]
total_cost = 0
for i in range(m):
    b1, b2, cost = map(int, si().split())
    graph[b1][b2] = cost
    graph[b2][b1] = cost
    total_cost += cost


def solution(g):
    visited = set()
    visited.add(1)
    w = 0
    for _ in range(n - 1):
        _min, _next = sys.maxsize, -1
        for node in visited:
            for j in range(1, n + 1):
                if j not in visited and 0 < g[node][j] < _min:
                    _min = g[node][j]
                    _next = j
        w += _min
        visited.add(_next)
    return w


print(total_cost - solution(graph))

아무래도 graph가 너무 무거워진 것이 원인인 듯 싶다. 코드를 조금만 바꿔서 구현하려고 했으나 실패.

heapq를 이용해서 같은 로직을 구현하니 바로 성공했다.

from heapq import *
from collections import defaultdict
import sys

si = sys.stdin.readline
n, m = map(int, si().split())
total = 0
graph = []
for _ in range(m):
    n1, n2, weight = map(int, si().split())
    graph.append((weight, n1, n2))
    total += weight


def prim(g, start):
    mst = 0
    # 모든 간선의 정보를 담을 트리
    tree = defaultdict(list)
    for w, b1, b2 in g:
        tree[b1].append((w, b1, b2))
        tree[b2].append((w, b2, b1))
    # 방문할 노드가 담긴 세트
    visited = set()
    visited.add(start)
    # 시작노드와 연결된 간선들의 리스트
    candidate_arr = tree[start]
    # 시작 노드와 연결된 간선들을 힙 자료구조로 만든다. --> 가중치가 작은 순서로 나온다.
    heapify(candidate_arr)
    # print(f"candidate arr = {candidate_arr}")
    while candidate_arr:
        # 가중치, 현재 노드와 연결된 노드가 나옴.
        w, b1, b2 = heappop(candidate_arr)
        # print(f"heappop! w = {w}, b1 = {b1}, b2 = {b2}")
        # 만약 연결된 노드가 방문하지 않았다면
        if b2 not in visited:
            # 방문처리를 한다. --> 현재 노드와 연결된 간선중 가장 가중치가 작으면서 가본 적이 없는 노드
            visited.add(b2)
            # 가중치를 더해준다.
            mst += w
            # print(f"visited = {visited}, now answer is {mst}")
            # 다음 방문할 노드와 연결된 노드들을 순회
            for node in tree[b2]:
                # 방문한 적이 없는 노드라면 힙에 넣는다.
                if node[2] not in visited:
                    # print(f"add candidate {node[2]}")
                    heappush(candidate_arr, node)
                    # print(f"now candidate_arr = {candidate_arr}")
    # print(f"total = {total}")
    # print(f"mst = {mst}")
    return visited, total - mst


check, answer = prim(graph, 1)
if len(check) == n:
    print(answer)
else:
    print(-1)

동헌이는 모형 비행기 조종 대회에 참가하였다. 이 대회에서는 격자 모양의 공간에서 모형 비행기를 조종하여 얻는 비행 점수로 순위를 매긴다. 격자의 각 칸에는 점수가 부여되어 있고, 비행 점수는 "상승 비행을 할 때 지나간 칸에 부여된 점수의 총합"과 "하강 비행을 할 때 지나간 칸에 부여된 점수의 총합"을 더한 값이다. 출발한 칸과 도착한 칸도 지나간 칸으로 간주한다.

<그림 1> 시작과 끝 칸 및 가능한 이동 방향

모형 비행기는 맨 왼쪽 아래 칸에서 상승 비행으로 비행을 시작해야 하고, 중간에 상승 비행에서 하강 비행으로 변경한 후, 맨 오른쪽 아래 칸에서 하강 비행으로 비행을 종료해야 한다. 상승 비행에서 하강 비행으로 변경할 때에는 다른 칸으로 이동할 수 없다. 즉, 상승 비행이 끝난 칸에서 하강 비행을 시작해야 한다.

모형 비행기는 상승 비행 중에는 앞 또는 위로만 이동할 수 있고, 하강 비행 중에는 앞 또는 아래로만 이동할 수 있다.

동헌이는 이 대회에서 얻을 수 있는 최대 비행 점수가 궁금하다. 동헌이를 위해 얻을 수 있는 최대 비행 점수를 구해주자.

풀이

꽤나 까다로운 dp 문제였던 것 같다. 우선 상승 비행과 하강 비행으로 나누어 두 번 진행해야 한다는 번거로움이 있었다.

테이블을 두 개를 만들어 행렬 덧셈으로 답을 도출하려고 했는데, 이런 저런 예외처리를 하느라 꽤 고생했다.

상승 비행과 하강 비행의 테이블을 zip을 이용해서 행렬 덧셈을 해주고, 나온 최대 값이 얻을 수 있는 최대 점수가 된다.

import sys

si = sys.stdin.readline
n, m = map(int, si().split())
graph = [list(map(int, si().split())) for _ in range(n)]
go_up = [[-sys.maxsize] * m for _ in range(n)]
go_down = [[-sys.maxsize] * m for _ in range(n)]


def flight():
    sx, sy = n - 1, 0
    ex, ey = n - 1, m - 1
    up = [(1, 0), (0, -1)]
    down = [(1, 0), (0, 1)]
    go_up[sx][sy] = graph[sx][sy]
    go_down[ex][ey] = graph[ex][ey]
    for r in range(sx, -1, -1):
        for c in range(0, m):
            for nx, ny in up:
                tx, ty = r + nx, c + ny
                if 0 <= tx < n and 0 <= ty < m:
                    go_up[r][c] = max(go_up[r][c], graph[r][c] + go_up[tx][ty])
    for r in range(ex, -1, -1):
        for c in range(ey, -1, -1):
            for nx, ny in down:
                tx, ty = r + nx, c + ny
                if 0 <= tx < n and 0 <= ty < m:
                    go_down[r][c] = max(go_down[r][c], go_down[tx][ty] + graph[r][c])

    ans = [[c + d for c, d in zip(a, b)] for a, b in zip(go_down, go_up)]
    _max = -sys.maxsize
    for i in ans:
        if max(i) > _max:
            _max = max(i)
    return _max


answer = flight()
print(answer)

학부 연구생으로 새로 연구실에 들어온 민상이는 사용할 자리를 정하려고 한다.

연구실은 격자 모양으로 되어있고 에어컨에서 바람이 상,하,좌,우 4방향으로 분다. 물론 에어컨이 위치한 곳에도 바람이 분다.

민상이는 더위를 많이 타서 에어컨 바람이 지나가는 곳 중 하나를 선택하여 앉으려고 한다.

연구실에는 다양한 물건들이 있어 바람의 방향을 바꾼다.

연구실에 있는 물건의 종류는 총 4가지가 있다. 아래 화살표의 의미는 바람이 각 물건에서 바람의 이동을 표시한 것이다.

연구실 어디든 민상이가 앉을 수 있는 자리이다. 즉 에어컨이 위치한 자리와 물건이 있는 자리 모두 앉을 수 있다.

민상이가 원하는 자리는 몇 개 있는지 계산해주자.

풀이

from collections import deque
import sys

si = sys.stdin.readline

n, m = map(int, si().split())
graph = [list(map(int, si().split())) for _ in range(n)]
visited = [[0] * m for _ in range(n)]


queue = deque()

for i in range(n):
    for j in range(m):
        if graph[i][j] == 9:
            queue.append((i, j))


def bfs(g, q):
    xd = [-1, 1, 0, 0]
    yd = [0, 0, -1, 1]
    while q:
        x, y = q.popleft()
        for i in range(4):
            r, c = x, y
            nx, ny = xd[i], yd[i]
            while 0 <= r < n and 0 <= c < m:
                visited[r][c] = 1
                if (graph[r][c] == 1 and nx == 0) or (graph[r][c] == 2 and ny == 0):
                    break
                elif graph[r][c] == 3:
                    nx, ny = -ny, -nx
                elif graph[r][c] == 4:
                    nx, ny = ny, nx
                r += nx
                c += ny
    return sum(sum(visited, []))


print(bfs(graph, queue))

이 문제는  너비 탐색을 이용해서 풀었다. 

진행하던 방향에 따라서 어떻게 달라지는 지에 대해서 공식을 세워두고, 분기를 나누어서 처리했다. 계속해서 시간 초과가 났었는데,

알고보니 sum(sum(visited, [])) 부분에서 시간 초과가 났다. 단순히 count로만 바꿔도 python으로 풀 수 있다. 

from collections import deque
import sys

si = sys.stdin.readline

n, m = map(int, si().split())
visited = [[0] * m for _ in range(n)]


queue = deque()

graph = []
for i in range(n):
    line = list(map(int, si().split()))
    for j in range(m):
        if line[j] == 9:
            queue.append((i, j))
            visited[i][j] = 1
    graph.append(line)


def bfs(g, q):
    xd = [-1, 1, 0, 0]
    yd = [0, 0, -1, 1]
    while q:
        x, y = q.popleft()
        for idx in range(4):
            nx, ny = xd[idx], yd[idx]
            r, c = x + nx, y + ny
            while 0 <= r < n and 0 <= c < m:
                visited[r][c] = 1
                if g[r][c] == 9:
                    break
                if g[r][c] == 3:
                    nx, ny = -ny, -nx
                elif g[r][c] == 4:
                    nx, ny = ny, nx
                elif (g[r][c] == 1 and nx == 0) or (g[r][c] == 2 and ny == 0):
                    break
                r += nx
                c += ny
    answer = 0
    for ans in visited:
        answer += ans.count(1)
    return answer


print(bfs(graph, queue))