• 본 리뷰는 길벗 출판사의 24차 개발자 리뷰어로 선정되어 책을 제공받아 작성했습니다.

저는 컴퓨터공학과 학부를 졸업하고 네트워크 보안 연구실 소속으로 블록체인 관련 연구를 수행하며 석사학위를 취득했습니다.

책을 전체적으로 읽으면서 기존에 존재하던 다양한 컴퓨터 구조 책과 비교하여, 내용이 보다 깊다는 느낌을 받았습니다. 전공 지식이 있으신 분들은 흥미롭게 받아들이실 수 있지만, 아예 처음 컴퓨터구조를 접하는 분들은 조금 어려울 수 있겠다는 생각을 했습니다.

컴퓨터구조 및 운영체제의 특성 상 눈으로 보이지 않는 부분에 대해 생각하며 책을 읽어야 하는데, 개념을 설명하는 대부분의 파트에 그림이 함께 삽입되어 있어 구체적인 이해가 가능한 부분이 참 좋은 것 같습니다.
(설명도 친절하게 서술되어 있다고 생각됩니다)

각 챕터가 끝날 때마다 학습한 내용을 리마인드할 수 있는 핵심요약과 퀴즈 형식의 문제들이 존재하기 때문에 '내가 잘 이해한 것이 맞나?'라는 의문을 해소하기에 적합하다고 생각합니다.

또한, 책을 볼 때 중요하게 생각하는 부분 중 하나가 "읽고 싶은 글꼴 및 디자인"이라는 생각을 가지고 있는데, 저자께서 하나하나 그린 그림이 귀여우면서도 가독성이 좋아 지루하지 않았던 것 같습니다.

스레드를 설명할 때 알고리즘의 표현이 정확하고 간결하여 코드를 읽음에 부담이 없고, 정확한 이해를 도와주었습니다.

• 추천하는 독자

1. 컴퓨터 구조 및 운영체제에 기본 지식이 있는 전공자
2. 자격증을 준비하는 사람

• 본 리뷰는 길벗 출판사의 24차 개발자 리뷰어로 선정되어 E-book을 제공받아 작성했습니다.

저는 컴퓨터공학과 학부를 졸업하고 네트워크 보안 연구실 소속으로 블록체인 관련 연구를 수행하며 석사학위를 취득했습니다.

책을 전체적으로 읽으면서, 네트워크를 공부하며 배운 기초 내용이 대체적으로 잘 정리되어있다는 느낌을 받았습니다.

책을 훑으면서 네트워크를 처음 접하시는 분들이나, 네트워크에 대한 지식에 대해 환기하고 싶으신 분들에게 좋은 책이라는 생각이 들었습니다.

• 그림 예시 (E-book 285쪽, 그림 7-24 이메일 송신)

또한, 책을 볼 때 중요하게 생각하는 부분 중 하나가 "읽고 싶은 글꼴 및 디자인"이라는 생각을 가지고 있는데, 저자께서 하나하나 그린 그림이 귀여우면서도 가독성이 좋아 지루하지 않았던 것 같습니다.

• 문제 예시 (E-book 251쪽, 6장 복습 부분)

또한, 각 챕터가 끝날 때마다 학습한 내용을 리마인드할 수 있는 퀴즈 형식의 문제들이 존재하기 때문에 '내가 잘 이해한 것이 맞나?'라는 의문을 해소하기에 적합하다고 생각합니다.

하지만, 전공 지식에 대해 깊은 이해를 가지고 계신 분들이나, 네트워크에 대한 구체적인 내용 학습을 원하시는 분들에게는 조금 아쉬울 수 있을 것 같습니다.

1. 정보보안의 기본이라 불리는 기밀성, 무결성, 가용성이란 무엇입니까?

기밀성이란, 어떤 시스템에 접근할 때, 시스템에 접근할 수 있는 권한을 가진 자만 접근해야 하는 성질입니다. 무결성이란, 데이터를 다룰 때 데이터의 주체를 제외한 타인으로 인해 위조, 변조되지 않고 보호받아야 하는 성질입니다. 가용성이란, 어떤 주체가 필요한 데이터가 있을 때 그 데이터에 문제없이 필요로 하는 시점에 접근할 수 있어야 하는 성질입니다.

2. 아래는 과기부 산하 진행중인 연구들입니다 (정보공개 청구를 통해 받아낸 자료) 현재는 어떤 취약점과 리스크가 알려져 있습니까? 분산앱은 무엇이고 소스 SW 리스크는 무엇입니까?

• A. 블록체인 플랫폼 보안 취약성 분석 연구
• B. 블록체인 분산앱 취약점 분석 연구
• C. 블록체인 모든 소스 sw 리스크 분석 연구
• D. 안정성 보장 연구

분산 앱은, DAPP을 의미하는데, 분산 컴퓨팅 환경이나 블록체인에서 스마트 계약을 통해 자율적으로 혼자 작동할 수 있는 시스템을 의미합니다. 사용자가 일반적으로 사용하는 시스템들은 중앙 서버를 통해 인터랙션을 처리하지만, 분산 앱은 블록체인과 같이 탈중앙화 되어 스마트 계약을 통해 인터랙션을 처리합니다.

• 탈중앙화: 중앙집중화를 벗어나 분산된 소규모 단위로 자율적으로 운영될 수 있는 성질
• 스마트 계약: 블록체인 상에서 계약의 주체가 사전에 협의한 내용을 미리 프로그래밍하여 전자 계약서 안에 넣어두고, 계약의 조건을 만족하면 자동으로 계약 내용이 실행되는 시스템

소스 소프트웨어 리스크는 아마 오픈소스 소프트웨어에 대한 리스크를 말씀하신 것 같은데, 먼저 오픈소스란 제이쿼리나 부트스트랩과 같이 저작권 없이 자유롭게 누구나 사용할 수 있는 소프트웨어를 의미합니다.
오픈소스 소프트웨어 사용에 대한 리스크의 예로, 많은 기업에서 자체 시스템을 개발할 때 오픈소스 소프트웨어를 사용하는데, 오픈소스 소프트웨어는 때로는 주기적으로 가끔은 갑작스럽게 보안 취약점에 대한 업데이트를 진행합니다.
하지만 기업에서 이를 놓치고 업데이트를 하지 않은 채 구버전의 오픈소스 소프트웨어를 사용하고 있다면, 공격자들은 해당 오픈소스 소프트웨어의 취약점을 이용해 공격해 시스템에 악영향을 끼칠 수 있습니다.

• 제이쿼리: HTML의 클라이언트 측 조작을 단순화하도록 설계된 자바스크립트 라이브러리
• 부트스트랩: 웹사이트를 쉽게 만들 수 있게 도와주는 HTML, CSS, 자바스크립트 프레임워크

블록체인에 가장 위협적인 취약점은 코드 오류인 것 같습니다. 블록체인 역시 하나의 소프트웨어이기 때문에, 소스코드 상 오류가 발생할 가능성이 있습니다. 대표적인 예로 이더리움 DAO 공격과 이중지불 버그 등이 있습니다.
DAO 해킹은 이더리움에 스마트 계약 프로젝트로부터 시작되었는데, 2016년 6월 DAO를 구성하고 있는 소스코드에 오류가 발생하여 재귀호출이 무한정으로 발생하는 일이 생깁니다. 이로 인해 DAO 프로젝트에 투자한 투자금을 이더리움으로 반환하는 기능이 계속해서 실행되었고, 약 243만개의 이더리움을 탈취당한 사건이 있습니다. 다행스럽게도 이더리움 네트워크에서 하드포크를 통해 탈취된 이더리움을 복구시켰지만, 소스코드 오류로 인해 발생할 수 있는 많은 문제점을 보여준 사건입니다.

• 하드포크: 블록체인의 기본 기능 자체를 수정하는 업데이트, 하드포크 수행 시 기존과 다른 블록체인 네트워크가 됨
  이중지불 버그는, 오픈소스 프로젝트의 비트코인 특성상 코드 반영이 신중히 결정되지 않아 발생한 문제로, 2016년 12월에 속도 향상을 위해 반영된 잘못된 코드로 인해 단일 블록에 대한 이중지불 확인과정이 필요하지 않은 것으로 처리되어 트랜잭션이 두 번 실행되는 블록이 생성된 문제가 있었습니다.
  또한, 블록체인에서 블록에 대한 무결성과 부인방지 등을 위해 사용자의 전자서명과 같은 암호화 기술이 사용되는데, 이때 전자서명에 사용되는 공개키는 사용자의 식별주소가 되고 개인키는 사용자의 자산에 접근할 수 있는 열쇠가 됩니다. 그러므로 개인키의 유실이나 분실, 탈취와 같은 문제점은 사용자의 자산을 한순간에 0으로 만들 수 있는 문제임을 알고, 관리적 보안이 최우선이어야 합니다.

3. 메타콩즈 디스코드 해킹사건 - 봇, 웹훅이 무엇입니까? 링크 한 번 누른다고 채널의 관리자 권한이 그렇게 쉽게 탈취당할 수 있는겁니까?

봇이란, 특정한 작업을 수행하도록 프로그래밍된 소프트웨어 응용 프로그램으로, 대부분 네트워크에서 작동하는 경우가 많습니다. 봇으로부터 공격을 받는 사용자는 특정 프로그램을 실행하지 않았는데 알아서 혼자 실행되고 있다던가, 모르는 프로그램이 계속해서 실행되고 있을 수 있습니다.
웹훅이란, 특정 웹이나 앱에서 다른 시스템으로 관련 이벤트 데이터를 실시간으로 제공하기 위한 방법으로, 특정 이벤트에 대한 커스터마이즈 된 콜백으로 해석할 수 있습니다. 즉, 앱이나 웹에서 이벤트가 발생한 즉시 미리 설계해 둔 URL을 통해 다른 시스템으로 이벤트 관련 정보를 보내는 것입니다.

• 콜백: 특정 함수의 작업이 끝나면 수행되는 함수
  관리자에게 DM을 통해 업무협업인 척을 하는 스미싱의 형태로 공격을 시작했고, 평소 업무협업이 잦았던 관리자는 아무런 의심 없이 해당 URL을 클릭했을 것입니다. 해당 URL에는 실제 협업 관련 내용인 것처럼 보이지만 실제로는 악성 봇을 설치하기 위한 함정이었고, 관리자 몰래 설치된 악성 봇은 시스템을 서서히 장악할 수 있기 때문에, URL을 클릭한 순간 관리자 권한은 넘어갔다고 판단됩니다. 이런 일을 방지하기 위해서 모르는 사용자가 보낸 URL은 확인하지 않고, 신뢰할 수 있는 사용자의 메일만 확인해야 합니다.
  
• 스미싱: 문자 메시지를 이용한 피싱

4. 전통 금융권은 망분리나 레이어 나눔 등이 잘 되어 있다는데, 이것이 무엇입니까?

망분리란, 기업에서 사용하는 내부 네트워크를 외부 인터넷의 불법적인 접근이나 내부정보 유출 등과 같은 행위들을 차단하기 위해 기업에서 업무를 수행하는 업무망과 외부 인터넷망을 분리하는 행위입니다.
우리나라에서는 2012년 정보통신망법을 개정하여 100만명 이상의 개인정보를 보유했거나 매출이 100억원 이상인 정보통신서비스 사업자의 경우 망분리를 의무적으로 도입하도록 했습니다. 금융권에서는 외부로 데이터가 빠져나가거나 외부 인터넷으로부터 공격을 받게 될 경우, 사용자들의 자산이 위험해질 수 있기에 더욱 정밀하고 예민하게 설계하는 것으로 알고 있습니다.

레이어 나눔이란, 실제 서비스가 수행되는 중앙서버나 기타 서비스 주체들에 대한 접근을 제어하기 위해 IPS 및 IDS, 방화벽, DMZ, 내부 네트워크와 외부 네트워크를 분리 등 시스템 주체를 보호하기 위한 수단을 층별로 설계하여 손쉽게 시스템에 영향을 끼칠 수 없도록 하는 행위입니다. 이 또한 망분리와 마찬가지로 금융권에서는, 사용자들의 자산이 위험해질 수 있는 경우를 방지하기 위해 더욱 정밀하고 세밀하게 설계하는 것으로 알고 있습니다.

• IPS(Intrusion Prevention System): 침입 방지 시스템
• IDS(Intrusion Detection System): 침입 감지 시스템
• DMZ(Demilitarized Zone): 비무장지대

5. 전통 금융권에 비해 블록체인은 상대적으로 보안에 구멍이 많고, 업계 자체가 취약하다는데 왜 그런가요?

아무래도, 전통 금융권 같은 경우 거래나 돈에 있어 중앙집중식으로 정보를 관리하고 장부의 복제본을 많이 만들어 이상 행위 등을 탐지하기 때문에 자동화나 모니터링 시스템이 잘 되어 있는 현재에서 서버를 해킹하는 방법 말고는 실질적인 보안 공격이 어렵습니다.
블록체인의 경우 탈중앙화를 이루어내면서 누군지도 모르는 사람들이 네트워크에 참여하고, 악의적인 마음을 가진 사용자인지 순수한 사람인지 구분하기에도 어려울 뿐만 아니라 실질적인 법률이 존재하지 않아 범죄 행위를 저지르고도 처벌을 받지 않기 때문에 더 많은 보안 공격 시도가 있는 점도 의미가 있고, 엄청나게 큰 규모의 기업 서버를 해킹하는 것보다 일반인의 블록체인 네트워크 지갑 주소를 해킹하는 게 더 쉬운 점도 의미가 있는 것 같습니다.

6. NFT 해킹 수법의 종류에는 어떤 것이 있습니까?

NFT 해킹 수법은 다른 해킹 수법에 비해 많이 다양하지는 않은 것으로 알고 있습니다. 관련된 데이터가 분산시스템인 블록체인이나 IPFS 등에 담겨 있어 손쉽게 해킹할 수 없기 때문입니다. 그래서 대부분의 NFT 관련 보안 공격은 NFT를 사고 파는 주체인 사용자를 방심하게 만들고, 이를 이용해 부적절한 링크라던가 공격 의지가 담긴 메일을 통해 지갑 주소를 탈취하는 게 일반적인 해킹 수법입니다. 지갑을 탈취하게 되면 모든 게 공격자 마음대로 조종될 수 있어, 항상 조심해야 합니다.

• IPFS(InterPlanetary File System): 분산 파일 시스템에서 사용하는 데이터베이스

A. 원본 훼손

아무래도, NFT를 발급한 디지털 자산의 메타데이터를 블록체인에 저장하게 되면서, 메타데이터 속 자산의 주소를 쉽게 파악할 수 있고 공개 저장소일 경우 디지털 자산의 비밀성이 보장되지 않아, 디지털 자산의 원본을 훼손하고자 하는 공격 방법이 아닐까 생각됩니다.

• 메타데이터: 구조화된 데이터, 다른 데이터를 설명해주는 데이터

B. 설계(알고리즘), 소프트웨어 구현 간 관계

설계와 소프트웨어 구현 간 관계는 서로 관계가 적어보이지만, 소프트웨어 구현에 필요한 기초가 설계라고 생각합니다. 소프트웨어를 구현할 때 사용하는 알고리즘 기법에 따라 메모리 사용을 효율적으로 사용할 수도 있고 낭비하는 코드를 작성할 수도 있습니다.
현재 많은 IT 기업에서 이력서만 넣으면 코딩테스트를 보게 해주는 것도, 실제 소프트웨어 구현을 위해 작성할 코드의 효율성을 볼 때 가장 쉽게 판별할 수 있는 지표이기 때문입니다. 그러므로, 소프트웨어 구현 시에는 설계 단계가 매우 중요하다고 개인적으로는 생각합니다.

C. 논리적 오류란 무엇인가요?

논리적 오류란, 사전적 의미로 논증을 구성하거나 추론을 진행하는 데 있어 타당하지 않은 방식을 사용하는 것이다. 즉, 겉에서 봤을 때는 타당한 것처럼 보이지만, 그 속내를 보고 구체적으로 조사해보면 옳지 않은 것으로 증명되는 경우입니다.
블록체인에서의 논리적 오류로 예를 들면, 개발자의 실수 등으로 인해 블록체인 거래에 사용되는 기능에서 잘못된 응답이나 요청이 이루어지고 있지만, 겉으로 봐서는 정상적으로 실행되는 상황이나, 실제 자산의 움직임과 사용자가 확인하는 자산이 다른 경우 등을 들 수 있을 것 같습니다.
또한, 다른 경우로 코딩을 진행할 때 관리자의 권한에서 할 수 있는 일과 사용자의 권한에서 할 수 있는 일을 반대로 구현해 사용자들이 접근해서는 안 될 영역에 접근한 예도 있다고 합니다.

D. 오류 발생 시 왜 해킹에 취약해지나요?

오류가 발생한 것은 시스템이 정상적으로 작동하지 않는다는 의미로 해석할 수 있고, 시스템을 운영하던 도중 오류가 발생한다면, 연쇄적인 시스템 손상이 발생할 수밖에 없습니다.
이런 경우 공격으로부터 시스템을 방어하는 방화벽, IPS, IDS 등이 정상작동하지 않을 수 있고 시스템의 관리자 또한 오류를 파악하고 해결하기 위해 몰두할 가능성이 많아, 오류가 발생하면 해킹에 매우 취약해집니다.

E. 전자지갑 키 유출로 인해 NFT 소유권이 쉽게 상실될 수 있나요?

네, 전자지갑의 키를 유출하게 되면 아무런 제약 없이 손쉽게 계정을 탈취할 수 있습니다. 그렇게 되면 NFT 소유권 또한, 유출된 전자지갑 키를 이용해 공격을 시도한 공격자 마음대로 제어할 수 있습니다. 그래서 전자지갑 키는 꼭 자신만 확인할 수 있는 종이 같은 곳에 적어놓으라고 당부하곤 합니다.

F. 인터넷 교란 시에도 NFT 탈취가 가능하다고 하는데, 인터넷 통신체계의 구조적 취약점 때문이라고 합니다. 이것이 무엇인가요?

인터넷 교란 시에는 인터넷이 지연되거나 정상적으로 작동하지 않는 상황을 의미하는데, 이러한 상황에서 NFT를 저장하고 있는 노드가 인터넷과 연결이 끊겨 작동을 멈추거나 블록체인 상에서 디지털 자산에 대한 NFT 발급과 관련된 트랜잭션이 담긴 블록이 확정되기 전에 공격자의 트랜잭션이 담긴 블록이 확정되는 등의 상황이 발생하면, 디지털 자산에 대한 소유권이 공격자에게 넘어갈 수 있는데, 그러한 상황을 의미하는 것 같습니다.

7. 가상자산 시장의 전망에 대해 어떻게 생각하십니까?

NFT와 관련된 가상자산 시장은 향후 5년 정도는 계속 증가하는 추세가 지속될 것으로 생각하고 있습니다. 그 후에는 점차 시장이 안정화되면서 수요가 있는 게임이나 미술품, 캐릭터쪽 분야가 활발히 발전할 것으로 생각합니다. 비트코인, 이더리움과 같이 실제로 많이 사용되며 다른 시스템과 연동이 가능한 가상화폐들만 살아남을 것으로 생각합니다.

8. 연구자의 입장에서 법적, 제도적으로 어떤게 필요하다고 생각하십니까?

현재 블록체인 쪽 시장에는 법적으로나 제도적으로 어떤 조치를 하는 행위 자체가 정의되어 있지 않습니다. 예를 들어, 가상화폐에 투자했다가 화폐가 아무런 이유 없이 소멸해도 아무런 조치를 할 수 없고, 한풀이할 곳도 없습니다.
어떻게 보면 중앙에서 관리하는 주체가 없다는 개념이 블록체인 시스템에서 가장 중요한 개념인데, 법이나 제도가 생겨 블록체인이 갖는 의미가 퇴색될 수 있는 단점은 존재한다고 생각합니다. 하지만 순수한 소비자나 아무것도 모르는 사람들을 사기 치려고 하는 악의적 공격자들을 차단하거나 심판할 수 있는 법이나 제도는 필요하다고 생각합니다.

색으로 구역을 의미하는 R G B로 이루어진 n * n의 크기의 지역에서 적색과 녹색을 구분하지 못하는 적록색약과 일반인에서의 구역 수를 구하는 프로그램이다.

접근 방법

• bfs를 활용해 모든 위치를 방문하며, 같은 색깔이면서 아직 방문하지 않은 곳을 모두 탐색

• 2중 for문을 사용해 탐색 수행, 탐색이 끝날 때 마다 영역 수 1 증가하는 방식으로 작성
• 색약의 경우에는, 초록을 의미하는 G를 R로 치환하여 동일한 과정 반복 수행

작성한 코드

import sys
from collections import deque

input = sys.stdin.readline

n = int(input())

def bfs(x, y, area):
    queue.append((x, y))

    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]

    visit[x][y] = 1

    while queue:
        x, y = queue.popleft()

        for j in range(4):
            ax = x + dx[j]
            ay = y + dy[j]

            if 0 <= ax < n and 0 <= ay < n and area[ax][ay] == area[x][y] and not visit[ax][ay]:
                 visit[ax][ay] = 1
                 queue.append((ax, ay))

map = []
map_v2 = []

for i in range(n):
    line = input().rstrip()
    map.append(list(line))
    map_v2.append(list(line.replace("G", "R")))

queue = deque()

# 일반인

visit = [[0] * n for _ in range(n)]
count1 = 0

for i in range(n):
    for k in range(n):
        if not visit[i][k]:
            bfs(i, k, map)
            count1 += 1

# 적록색약
visit = [[0] * n for _ in range(n)]
count2 = 0

for i in range(n):
    for k in range(n):
        if not visit[i][k]:
            bfs(i, k, map_v2)
            count2 += 1

print(count1, count2)

상담 일을 하며, 얻을 수 있는 최대 수익을 계산하는 문제다.

가능한 많은 일을 하는 게 항상 최선이 아닐 수 있다.

접근 방법

• i번째 일까지 일했을 때, 얻을 수 있는 최대 수익을 담기 위한 dp배열

• 배열의 가장 마지막 값이 답
• i번째까지 일했을 때 얻는 최대 수익을 계산
• j는 i번째 날에 상담을 진행했을 때, 상담이 가능한 모든 날짜, == i + i번째 날의 상담 기간부터 마지막날까지
• j를 기준으로 상담했을 때 얻는 최대 수익을 dp[j]에 저장

해결하지 못한 코드

import sys

input = sys.stdin.readline

n = int(input())

work = []

for i in range(n):
    time, price = map(int, input().split())
    work.append([time, price])

total_list = []

for i in range(n):
    total = 0

    while i < n:
        if i + work[i][0] > n:
            break

        total += work[i][1]
        i += work[i][0]

    total_list.append(total)

print(max(total_list))

그리디하게 접근하다가, 고려하지 못한 경우의 수가 생기는 것을 알았다.

해결한 코드

import sys

input = sys.stdin.readline

n = int(input())

work = []

for i in range(n):
    time, price = map(int, input().split())

    work.append([time, price])

dp = [0 for i in range(n+1)]

for i in range(n):
    for j in range(i + work[i][0], n+1):
        if dp[j] < dp[i] + work[i][1]:
            dp[j] = dp[i] + work[i][1]

print(dp[-1])

문제 해결 방법이 떠오르지 않아, 블로그를 참고했고, dp배열을 활용해 해결했다.

파이썬의 정규표현식에 대해 알아보자.

메타 문자

메타 문자란, 정규표현식에서 사용했을 때, 원래의 의미가 아닌 특별한 의미로 사용되는 아래 문자를 의미한다.

. ^ $ * + ? { } [ ] \ | ( )

1. [ ] 문자 - 문자 클래스

문자 클래스로 만들어진 정규식은 [와 ] 사이의 문자들과 매치 라는 의미를 갖는다.

예를 들어, 표현식이 [abc]인 경우, a b c 중 한 개의 문자와 매치를 의미한다.

• a: [abc] 중 a가 존재하므로, 매치된다.
• before: [abc] 중 b가 존재하므로, 매치된다.
• dude: [abc] 중 어느 하나도 포함하고 있지 않으므로, 매치되지 않는다.

[] 안에서 두 문자 사이에 -을 사용하면, 두 문자 사이의 범위를 의미한다.

예를 들어, 아래와 같다.

• [a-zA-Z] : 모든 알파벳
• [0-9] : 모든 숫자

문자 클래스 [] 안에는 어떤 문자나 메타 문자를 사용할 수 있지만, ^을 사용할 때, 주의해야 한다. ^은 반대(not)의 의미를 가져, [^0-9]라는 정규 표현식은 숫자가 아닌 문자만 매치된다.

2. . (dot) 문자 - \n을 제외한 모든 문자

정규 표현식의 . 메타 문자는 줄바꿈 문자인 \n을 제외한 모든 문자와 매치되는 것을 의미한다.

a.b => "a + 모든 문자 + b" , a와 b 문자 사이에 어떤 문자가 들어가도 모두 매치된다는 뜻

• aab : 가운데 존재하는 'a'가 모든 문자를 의미하는 .과 일치하므로, 정규식과 매치
• a0b : 가운데 존재하는 '0'이 모든 문자를 의미하는 .과 일치하므로, 정규식과 매치
• abc : a 와 b 사이에 어떤 문자라도 존재하지 않기 때문에, 매치되지 않음

하지만, a[.]b의 경우는 위와 다르게, 문자 그대로를 의미한다.

"a + . + b"

3. * 문자

* 문자는 반복을 의미한다. * 바로 앞에 있는 문자 a가 0부터 무한대까지 반복될 수 있다는 의미로 사용한다.

ca*t

• ct : "a"가 0번 반복되어 매치
• cat : "a"가 1번 반복되어 매치
• caat : "a"가 2번 반복되어 매치

4. + 문자

* 문자가 최소 0번부터 사용할 수 있는거라면, +는 반복 횟수가 1부터 시작한다.

ca+t

• ct : "a"가 0번 반복되어 매치되지 않음
• cat : "a"가 1번 반복되어 매치
• caat : "a"가 2번 반복되어 매치

5. { }, ? 문자

반복횟수를 제한하고 싶을 때 { }을 사용해 고정할 수 있다. {m, n} 정규식을 사용하면, 반복횟수가 m부터 n까지인 문자와 매치할 수 있다.

만약, {3,}처럼 사용하면 반복 횟수가 3 이상인 경우이고, {, 3}처럼 사용하면 반복 횟수가 3이하인 경우를 의미한다.

생략된 m은 0과 동일하며, 생략된 n은 무한대를 의미한다. (실제로는 약 2억개)

{1, }은 +와 같고, {0, }은 *와 동일하다.

• {m} -> ca{2}t -> "c + a를 반드시 2번 반복 + t"
• {m, n} -> ca{2, 5}t -> "c + a를 2~5회 반복 + t"

반복은 아니지만, ? 문자는 {0, 1}을 의미한다.

• ab?c -> "a + b가 있어도 되고, 없어도 된다 + c" => abc, ac 둘 다 가능

파이썬 re 모듈

파이썬은 re(regular expression) 모델을 제공한다. 파이썬을 설치할 때 자동으로 설치되는 표준 라이브러리로, 다음과 같이 사용한다.

import re
p = re.compile('ab*') # re.compile을 사용하여, 정규표현식을 컴파일한다. 

1. 문자열 검색

컴파일된 패턴 객체를 사용해 문자열 검색을 수행할 수 있다.

• match() : 문자열의 처음부터 정규식과 매치되는지 조사한다.
• search() : 문자열 전체를 검색하여 정규식과 매치되는지 조사한다.
• findall() : 정규식과 매치되는 모든 문자열(substring)을 리스트로 리턴한다.
• finditer() : 정규식과 매치되는 모든 문자열(substring)을 반복 가능한 객체로 리턴한다.\

match(), search()는 정규식과 매치될 때 match 객체를 리턴하고, 매치되지 않을 때 None을 리턴한다.

match()

import re
p = re.compile('[a-z]+')

m = p.match("python")
print(m)

>>> <re.Match object; span=(0, 6), match='python'>  # python은 정규식에 부합

m = p.match("3 python")                                # 3이 부합하지 않아 None 리턴 
print(m)
None

match()의 결과로 match 객체 또는 None을 리턴하기 때문에, 보통 다음과 같은 흐름으로 작성한다.

p = re.compile(정규표현식)
m = p.match('조사할 문자열')

if m:     # match의 결과값이 존재하는 경우에만 다음 작업 수행
    print('Match found: ', m.group())
else:
    print('No match')

search()

m = p.search("python")
print(m)
<re.Match object; span=(0, 6), match='python'> 

m = p.search("3 python")
print(m)
<re.Match object; span=(2, 8), match='python'>

python 문자열에 search() 메서드를 수행하면, match() 메서드를 수행했을 때와 동일하게 매치된다.

'3 python' 문자열의 첫 번째 문자는 '3' 이지만, 'search'는 문자열의 처음부터 검색하는 것이 아니라 문자열 전체를 검색하기 때문에, '3' 이후의 'python' 문자열과 매치된다.

findall()

result = p.findall("life is too short")
print(result)
['life', 'is', 'too', 'short']

findall()은 패턴 [a-z]+과 매치되는 모든 값을 찾아 리스트로 리턴한다.

finditer

result = p.finditer("life is too short")
print(result)
<callable_iterator object at 0x01F5E390>

for r in result: print(r)
...
<re.Match object; span=(0, 4), match='life'>
<re.Match object; span=(5, 7), match='is'>
<re.Match object; span=(8, 11), match='too'>
<re.Match object; span=(12, 17), match='short'>

finditer는 findall과 동일하지만, 그 결과로 반복 가능한 객체 (iterator object)를 리턴한다. 반복 가능한 객체가 포함하는 각각의 요소는 match는 객체다.

match 객체의 메서드

match 객체란 앞에서 살펴본 p.match, p.search, p.finditer 메서드에 의해 리턴된 매치 객체(Match Object)를 의미한다.

• group : 매치된 문자열을 리턴한다.
• start : 매치된 문자열의 시작 위치를 리턴한다.
• end : 매치된 문자열의 끝 위치를 리턴한다.
• span : 매치된 문자열의 (시작, 끝)에 해당하는 튜플을 리턴한다.

m = p.match("python")

m.group()
'python'

m.start()
0

m.end()
6

m.span()
(0, 6)

match 메서드를 수행한 결과로 리턴된 match 객체로 start 메서드를 사용했을 때, 결과값은 항상 0일 수 밖에 없다. match 메서드는 항상 문자열의 시작부터 조사하기 때문이다.

만약 search 메서드를 사용했다면, 다른 값이 나올 수 있다.

m = p.search("3 python")

m.group()
'python'

m.start()
2

m.end()
8

m.span()
(2, 8)

컴파일 옵션

• DOTALL(S): .(dot)이 줄바꿈 문자를 포함해 모든 문자와 매치될 수 있게 한다.
• IGNORECASE(I): 대소문자에 관계없이 매치될 수 있게 한다.
• MULTILINE(M): 여러 줄과 매치될 수 있게 한다. ^, $ 메타 문자 사용과 관계 있는 옵션이다.
• VERBOSE(X): verbose 모드를 사용할 수 있게 한다. 정규식을 보기 편하게 만들 수 있고 주석 등을 사용할 수 있게 된다.

옵션을 사용할 때는 re.DOTALL 처럼 전체 옵션 이름을 써도 되고, re.S처럼 약어를 써도 된다.

DOTALL, S

. 메타 문자는 줄바꿈 문자 \n를 제외한 모든 문자와 매치되는 규칙이 있다. 만약 \n 문자도 포함하여 매치하고 싶다면, re.DOTALL, re.S 옵션을 사용해 정규식을 컴파일하면 된다.

import re
p = re.compile('a.b')
m = p.match('a\nb')

print(m)
None

정규식이 a.b인 경우, 문자열 a\nb는 매치되지 않는다는 것을 알 수 있다. \n은 .메타 문자와 매치되지 않기 때문이다. \n 문자와도 매치되게 하려면 다음과 같이 re.DOTALL 옵션을 사용해야 한다.

p = re.compile('a.b', re.DOTALL)
m = p.match('a\nb')
print(m)

<re.Match object; span=(0, 3), match='a\nb'>

re.DOTALL 옵션은 여러 줄로 이루어진 문자열에서 줄바꿈 문자에 상관없이 검색할 때 많이 사용한다.

IGNORECASE, I

re.IGNORECASE 또는 re.I 옵션은 대소문자 구별 없이 매치를 수행할 때 사용하는 옵션이다.

p = re.compile('[a-z]+', re.I)
p.match('python')
<re.Match object; span=(0, 6), match='python'>

p.match('Python')
<re.Match object; span=(0, 6), match='Python'>

p.match('PYTHON')
<re.Match object; span=(0, 6), match='PYTHON'>

[a-z]+ 정규식은 소문자만을 의미하지만, re.I 옵션으로 대소문자 구별 없이 매치된다.

MULTILINE, M

re.MULTILINE, re.M 옵션은 ^, $와 연관된 옵션이다.

^는 문자열의 처음, $는 문자열의 마지막을 의미한다.

예를 들어, ^python인 경우, 문자열의 처음은 항상 python으로 시작해야 매치하고, python$이라면, 문자열의 마지막은 항상 python으로 끝나야 매치된다.

# multiline.py
import re
p = re.compile("^python\s\w+")

data = """python one
life is too short
python two
you need python
python three"""

print(p.findall(data))

정규식 ^python\s\w+은 python이라는 문자열로 시작하고, 그 뒤에 화이트스페이스, 그 뒤에 단어가 와야 한다는 의미다.

해당 스크립트를 실행하면, 다음과 같은 결과를 리턴한다.

['python one']

^ 메타 문자에 의해 python이라는 문자열을 사용한 첫 번째 줄만 매치된 것이다.

하지만 ^ 메타 문제를 문자열 전체의 처음이 아니라, 각 라인의 처음으로 인식시키고 싶은 경우에는 re.MULTILINE, re.M을 활용한다.

# multiline.py
import re
p = re.compile("^python\s\w+", re.MULTILINE)

data = """python one
life is too short
python two
you need python
python three"""

print(p.findall(data))

re.MULTILINE 옵션으로 인해 ^ 메타 문자가 문자열 전체가 아닌 각 줄의 처음이라는 의미를 가지게 되었다.

['python one', 'python two', 'python three']

즉, re.MULTILINE 옵션은 ^, $ 메타 문자를 문자열의 각 줄마다 적용해 주는 것이다.

VERBOSE, X

charref = re.compile(r'&[#](0[0-7]+|[0-9]+|x[0-9a-fA-F]+);')

어려운 정규식을 주석 단위, 줄 단위로 구분하기 위해 re.VERVOSE, re.X 옵션을 사용한다.

charref = re.compile(r"""
 &[#]                # Start of a numeric entity reference
 (
     0[0-7]+         # Octal form
   | [0-9]+          # Decimal form
   | x[0-9a-fA-F]+   # Hexadecimal form
 )
 ;                   # Trailing semicolon
""", re.VERBOSE)

re.VERBOSE 옵션을 사용하면, 문자열에 사용된 화이트스페이스는 컴파일할 때 제거된다.

역슬래시 문제

정규표현식을 파이썬에서 사용할 때 혼란을 주는 요소가 1가지 존재하는데, 바로 역슬래시(\)다.

어떤 파일안에 있는 \section 문자열을 찾기 위한 정규식을 만든다고 가정해본다.

\section 이 정규식은 \s 문자가 whitespace로 해석되어 의도한 대로 매치가 이루어지지 않는다.

이 표현은 다음과 동일한 의미로 사용할 수 있다.

[ \t\n\r\f\v]ection

의도한대로 매치하고 싶다면, 다음과 같이 변경해야 한다.

\\section

즉, 앞 정규식에서 사용한 \ 문자가 문자열 자체라는 것을 알려주기 위해 역슬래시 2개를 사용해 이스케이프 처리를 해야 한다.

해당 정규식을 컴파일하려면 다음과 같이 작성해야 한다.

p = re.compile('\\section')

이처럼 정규식을 만들어서 컴파일하면, 실제 파이썬 정규식 엔진에는 파이썬 문자열 리터럴 규칙에 따라, \\이 \로 변경되어 \section이 전달된다.

결국, 아래와 같이 역슬래시 4개를 사용해야 하는 상황이 발생한다.

p = re.compile('\\\\section')

이를 해결하기 위해 raw string을 사용한다.

p = re.compile(r'\\section')

이와 같이 정규식 문자열 앞에 r 문자를 삽입하면, 이 정규식은 raw string 규칙에 의해 역슬래시 2개 대신 1개만 써도 2개를 쓴 것과 동일한 의미를 가지게 된다.

내용 참고

7단계에 걸쳐, 아이디를 필터링 하는 문제다.

접근 방법

• 주어진 조건에 맞춰, 하나씩 조건문을 작성

• 2번과 3번에서는 정규표현식을 사용해 문자들을 제거
• Regular Expression
• [^a-z0-9-_.] : - _ . , 영어 소문자, 숫자를 의미
• \. : 실제 마침표
• {2,} : 2번 이상 연속해서 반복

작성한 코드

import re

def solution(new_id):

    # 1. 대문자 -> 소문자
    answer = new_id.lower()

    # 2. 알파벳 소문자, 숫자, -, _, . 제외한 모든 문자 제거
    pattern = r'[^a-z0-9-_.]'
    answer = re.sub(pattern, '', answer)

    # 3. 마침표 2번 이상 연속된 부분을 하나의 마침표로 치환
    pattern2 = r'\.{2,}'
    answer = re.sub(pattern2, '.', answer)

    # 4. 마침표가 처음이나 끝에 위치한다면 제거
    if len(answer) >= 1 and answer[0] == ".":
        answer = answer[1:]

    if len(answer) >= 1 and answer[-1] == ".":
        answer = answer[:-1]

    # 5. 빈 문자열이라면, a를 대입
    if answer == "":
        answer = 'a'

    # 6. 길이가 16자 이상이라면, 첫 15개 문자를 제외한 나머지 문자 제거, 
    #    마침표가 끝에 위치한다면 마침표 제거
    if len(answer) >= 16:
        answer = answer[:15]

    if answer[-1] == ".":
        answer = answer[:-1]

    # 7. 길이가 2자 이하라면, 마지막 문자 복사
    if len(answer) <= 2:
        while(len(answer) < 3):
            answer += answer[-1]

    return answer

2차원 표면에 존재하는 직사각형 도형의 점에 대한 좌표를 구하는 문제다.

정사각형이 존재하기 위해 필요한 4개의 점 중 3개는 v 배열에 존재한다.

존재하지 않는 나머지 한 점을 찾아 출력하는 문제다.

접근 방법

• 결국 사각형에 존재하는 좌표는 x가 같거나, y가 같음

• v에 존재하는 3개의 좌표에서 1번만 나온 좌표를 조합하면 정답
• XOR 연산을 활용해 1번만 존재하는 x와 y를 추출

예)

v = [3, 5], [3, 1], [10, 5]

x = 3 XOR 3 XOR 10  ==> 10
y = 5 XOR 1 XOR 5 == > 1

answer = [10, 1]

작성한 코드

def solution(v):
    answer = []

    x = v[0][0] ^ v[1][0] ^ v[2][0]
    y = v[0][1] ^ v[1][1] ^ v[2][1]

    answer = [x, y]

    return answer

피보나치 수를 계산하는 고전적인 문제이며, n이 주어졌을 때 n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하면 된다.

접근 방식

• 피보나치 수의 핵심은 F(5) = F(3) + F(4)가 되는 것과 같이 이전의 상태가 계속해서 체인처럼 연결된다는 것

• for문을 이용해 계속해서 갱신되는 형태로 코드를 작성하면 빠른 성능을 보일 수 있음

작성한 코드

def solution(n):

    pre, cur = 0, 1

    for i in range(2, n+1):
        cur, pre = cur+pre, cur
        print("i번째: ", cur, pre)

    return cur % 1234567

결과

해당 내용은 코딩 테스트 합격자 되기의 저자께서 작성한 코드를 기반으로 작성했습니다. 출처

계수 정렬 (Counting Sort)

계수 정렬이란, 정수 배열을 정렬함에 있어 비교를 진행하지 않고 정렬하는 방법으로 O(n+k)의 시간복잡도를 가진다. (n: 배열 크기, k: 최댓값과 최솟값 차이)

이는 입력 데이터의 분포가 정해져 있는 경우 매우 효율적이다.

계수 정렬의 동작 과정은 다음과 같다.

1. 입력 배열을 순회하며 각 숫자의 개수를 센다.
2. 개수를 기반으로 숫자를 정렬된 위치에 배치한다.
3. 정렬된 결과를 반환한다.

예를 들어, 입력 배열이 [4, 2, 2, 8, 3, 3, 1] 인 경우, 최댓값을 찾아 그만큼의 리스트를 만든 뒤, 각 숫자가 출현한 빈도를 센다.

-> [0, 1, 2, 2, 1, 0, 0, 0, 1]

코드로 나타내면 다음과 같다.

def counting_sort(arr):
    max_val = max(arr)
    count = [0] * (max_val + 1)

    for num in arr:                            # 각 원소 개수 세기
        count[num] += 1

    sorted_arr = []

    for i in range(len(count)):                # 정렬된 배열 생성
        sorted_arr.extend([i] * count[i])

    return sorted_arr

arr = [4, 2, 2, 8, 3, 3, 1]
sorted_arr = counting_sort(arr)
print(sorted_arr)

----------------------
[1, 2, 2, 3, 3, 4, 8]

삽입 정렬 (Insertion Sort)

삽입 정렬은 배열의 각 원소를 이미 정렬된 부분에 삽입하는 방식으로 동작하는 정렬 방식으로, 배열에 담긴 모든 원소에 대해 반복하며 정렬한다.

시간 복잡도의 경우 모든 배열을 돌아야 하기 때문에 아래와 같다.

• 최선의 경우: O(n)
• 최악의 경우: O(n^2)

예를 들어 입력 배열이 [5, 3, 8, 4, 2]인 경우, 진행되는 프로세스는 아래와 같다.

1. key = 3, [5, 5, 8, 4, 2] -> [3, 5, 8, 4, 2]
2. key = 8 8은 다른 숫자보다 크기에 앞으로 땡겨질 수 없어, 변동사항 없음
3. key = 4, [3, 5, 8, 8, 2] -> [3, 5, 5, 8, 2] -> [3, 4, 5, 8, 2]
4. key = 2, [3, 4, 5, 8, 8] -> [3, 4, 5, 5, 8] -> [3, 4, 4, 5, 8] -> [3, 3, 4, 5, 8] -> [2, 3, 4, 5, 8]

코드로 나타내면 아래와 같다.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i-1

        while j >= 0 and key < arr[j]:
            arr[j+1] = arr[j]
            j -= 1

        arr[j+1] = key

    return arr

arr = [5, 3, 8, 4, 2]
sorted_arr = insertion_arr(arr)
print(sorted_arr)

병합 정렬 (Merge Sort)

병합 정렬은 분할 정복(divide and conquer) 전략을 사용하는 정렬 알고리즘으로, 배열을 절반으로 계속해서 분할하다가 길이가 1이 되면, 이를 기준으로 다시 합치면서 정렬을 진행한다.

실질적인 정렬은 두 부분 배열을 합치는 과정에서 정렬이 이루어지기 때문에, 병합 정렬이라고 표현한다.

병합 정렬은 안정적인 정렬로, 순서가 같은 원소들의 상대적 순서가 정렬 후에도 유지되는 특징을 가진다.

시간복잡도는 O(n log n)으로, 배열을 절반씩 분할하는데 log n의 시간이 소요되며, 각 분할마다 n만큼의 연산이 필요하므로 n log n이 된다.

예를 들어 입력 배열이 [38, 27, 43, 3, 9, 82, 10]이라고 하면,

1. 입력 배열을 절반씩 분할한다.
   • [38, 27, 43, 3] <--> [9, 82, 10]
     
2. 각각의 배열을 다시 절반씩 분할한다.
   • [38, 27] <--> [43, 3]
   • [9] <--> [82, 10]
     
3. 분할된 배열들을 정렬하며 병합한다.
   • [38, 27] --> [27, 38]
   • [43, 3] --> [3, 43]
   • [82, 10] --> [10, 82]
   • [9]
     
4. 이전 단계의 정렬된 배열들을 병합한다.
   • [27, 38] and [3, 43] --> [3, 27, 38, 43]
   • [9] and [10, 82] --> [9, 10, 82]
     
5. 최종적으로 병합하며 완전히 정렬된 배열을 얻는다.
   • [3, 27, 38, 43] and [9, 10, 82] --> [3, 9, 10, 27, 38, 43, 82]

이를 코드로 나타내면 다음과 같다.

def merge_sort(arr):
    if len(arr) <= 1:        # 리스트의 길이가 1 이하면, 이미 정렬된 것으로 간주
        return arr 

    mid = len(arr) / 2                # 중간 지점 설정 
    left = merge_sort(arr[:mid])    # 좌, 우 분할
    right = merge_sort(arr[mid:])

    return merge(left, right)        # 두 부분 리스트 병합


def merge(left, right):
    result = []
    i = j = 0 

    while i < len(left) and j < len(right):

        if left[i] < right[j]:
            result.append(left[i])         # 좌측이 더 작은 경우
            i += 1

        else:
            result.append(right[j])        # 우측이 더 작은 경우
            j += 1

    while i < len(left):                # 남은 원소들 추가
        result.append(left[i])
        i += 1

    while j < len(right):                # 남은 원소들 추가
        result.append(right[j])
        j += 1

    return result

arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print(sorted_arr)

-------------------------
[3, 9, 10, 27, 38, 43, 82]    

위상 정렬 (Topological Sort)

위상 정렬은 방향성이 있는 그래프에서 노드를 선형 순서로 나열하는 방법이다. 이때 순서는 그래프의 간선 방향을 거스르지 않아야 한다.

즉, A -> B의 간선이 있는 경우, A는 B보다 선행되어야 한다. 또한, 그래프에 사이클이 존재하는 경우 위상 정렬을 수행할 수 없다.

위상 정렬의 시간복잡도는 그래프의 노드 수를 V, 간선 수를 E라고 할 때, O(V+E)가 된다.

위상 정렬 과정은 다음과 같다.

1. 진입 차수가 0인 노드를 선택
2. 선택한 노드와 연결된 간선을 제거
3. 진입 차수 갱신
4. 진입 차수가 0인 노드 선택
5. 1~4 반복

만약 진입 차수가 다음과 같은 그래프가 있다고 생각해보면, 노드(진입 차수)로 표현

0(0) --> 1(1) --> 3(1)
|        |        |
v        v        v
2(1) --> 4(2) --> 5(2)

결과 리스트: [] 큐: []

• 진입 차수가 0인 노드(0)을 큐에 추가 결과 리스트: [] 큐: [0]

• 큐에서 노드를 꺼내 결과 리스트에 추가 결과 리스트: [0] 큐: []

• 현재 노드 0 처리 진입 차수: 0(0), 1(0), 2(0), 3(1), 4(2), 5(2) 큐: []

• 진입 차수가 0인 노드(1)을 큐에 추가 결과 리스트: [0] 큐: [1]

• 큐에서 노드를 꺼내 결과 리스트에 추가 결과 리스트: [0, 1] 큐: []

• 현재 노드 1 처리 진입 차수: 0(0), 1(0), 2(0), 3(0), 4(1), 5(2) 큐: []

• 진입 차수가 0인 노드(2)을 큐에 추가 결과 리스트: [0, 1] 큐: [2]

• 큐에서 노드를 꺼내 결과 리스트에 추가 결과 리스트: [0, 1, 2] 큐: []

• 현재 노드 2 처리 진입 차수: 0(0), 1(0), 2(0), 3(0), 4(0), 5(2) 큐: []

• 진입 차수가 0인 노드(3)을 큐에 추가 결과 리스트: [0, 1, 2] 큐: [3]

• 큐에서 노드를 꺼내 결과 리스트에 추가 결과 리스트: [0, 1, 2, 3] 큐: []

• 현재 노드 3 처리 진입 차수: 0(0), 1(0), 2(0), 3(0), 4(0), 5(1) 큐: []

• 진입 차수가 0인 노드(4)을 큐에 추가 결과 리스트: [0, 1, 2, 3] 큐: [4]

• 큐에서 노드를 꺼내 결과 리스트에 추가 결과 리스트: [0, 1, 2, 3, 4] 큐: []

• 현재 노드 4 처리 진입 차수: 0(0), 1(0), 2(0), 3(0), 4(0), 5(0) 큐: []

• 진입 차수가 0인 노드(5)을 큐에 추가 결과 리스트: [0, 1, 2, 3] 큐: [4]

• 큐에서 노드를 꺼내 결과 리스트에 추가 결과 리스트: [0, 1, 2, 3, 4, 5] 큐: []

• 종료 결과 리스트: [0, 1, 2, 3, 4, 5]

이를 작성한 코드는 다음과 같다.

from collections import deque

def topology_sort(graph):
    # 진입 차수 계산
    num_nodes = len(graph)
    in_degree = [0] * num_nodes

    for nodes in graph:
        for neighbor in graph[node]:    # 진입 수 계산
            in_degree[neighbor] += 1

    result = []         # 결과 리스트

    # 진입 차수가 0인 노드를 큐에 추가
    queue = deque()

    for node in range(num_nodes):
        if in_degree[node] == 0:
            queue.append(node)

    # 위상 정렬 
    while queue:
        # 큐에서 노드를 꺼내 결과 리스트에 추가
        current_node = queue.popleft()
        result.append(current_node)

        # 해당 노드에서 나가는 간선 제거 및 진입 차수 갱신
        for neighbor in graph[current_node]:
            in_degree[neighbor] -= 1

            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    if len(result) != num_nodes:
        return "그래프에 사이클이 존재합니다!"

    return result

graph = {
    0: [1, 2],
    1: [3, 4],
    2: [4],
    3: [5],
    4: [5],
    5: []
}

result = topological_sort(graph)

if isinstance(result, list):            # result가 list 타입인지 확인
    print("위상 정렬 결과: ", result)    
else:
    print(result)

--------------------------------
위상 정렬 결과: [0, 1, 2, 3, 4, 5]

해당 내용은 코딩 테스트 합격자 되기의 저자께서 작성한 코드를 기반으로 작성했습니다. 출처

Combination

파이썬에서 조합은 itertools 라이브러리에 있는 combinations를 불러와 손쉽게 사용할 수 있다.

from itertools import combinations

def generate_combinations(arr, n):
    return list(combinations(arr, n))

arr = [1, 2, 3]
print(generate_combinations(arr, 2))

------------------------
[(1, 2), (1, 3), (2, 3)]

라이브러리를 사용하지 않고 구현하는 경우, 다음과 같이 코드를 작성한다.

def combinations(lst, r):
    result = []

    def generate_combination(chosen, remain, n):    

        if n == 0:                            # 원하는 r개의 원소를 선택한 경우
            result.append(chosen[:])
            return

        if not remain or len(remain) < n:    # 남은 원소 없거나, 선택 불가한 경우
            return

        # 현재 원소를 선택하는 경우
        chosen.append(remain[0])
        generate_combination(chosen, remain[1:], n-1)     # 재귀 호출
        chosen.pop()

        # 현재 원소를 선택하지 않는 경우
        generate_combination(chosen, remain[1:], n)        # 다음 원소

    generate_combination([], list, r)

    return result
lst = [1,2,3]
r = 2
print(combinations[lst, r])

----------------------
[[1,2], [1,3], [2,3]]       

Permutations

파이썬에서 순열은 Combinations와 함께 itertools에서 불러와 사용할 수 있다.

from itertools import permutations

def generate_permutations(arr):
    return list(permutations(arr))

arr = [1, 2, 3]
print(generate_permutations(arr)) 

------------------------------------------------------------------
[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]

라이브러리를 사용하지 않고 코드를 작성하는 경우 다음과 같이 작성할 수 있다.

def permutations(lst, r):
    result = []

    def generate_permutaion(chosen, remain):

        if len(chosen) == r:
            result.append(chosen[:])                            # 만들어진 결과 추가
            return

        for i in range(len(remain)):
            chosen.append(remain[i])                            # 현재 원소 선택
            remaining_elements = remain[:i] + remain[i+1:]        # 현재 원소 제외
            generate_permutation(chosen, remaining_elements)    
            chosen.pop()                                        # 현재 원소 제거

    generate_permutation([], lst)

    return result

lst = [1,2,3]
r = 2
print(permutations(lst, r))

AWS S3에 존재하는 엑셀 파일을 로컬 환경 python 코드에서 읽어오기

AWS S3 Bucket 권한 설정

AWS S3 Bucket의 경우 Public 접근이 가능하지 않도록하는 설정이 기본 값으로 사용된다.

이를 해제하기 위해 버킷 설정에서 퍼블릭 액세스 차단 편집(버킷 설정) 부분의 모든 퍼블릭 액세스 차단을 해제한다.

이후, 버킷 정책 부분에서 아래의 json 내용을 복사해서 붙여넣는다.

{
    "Version": "2012-10-17",
    "Statement": [
        {
            "Sid": "PublicRead",
            "Effect": "Allow",
            "Principal": "*",
            "Action": "s3:GetObject",
            "Resource": "arn:aws:s3:::bucketname/*"
        }
    ]
}

위 내용은 bucketname에 해당하는 모든 파일에 대해 읽기 작업을 모두에게 허락함을 의미한다.

bucketname 부분에 본인의 bucket 이름을 넣으면 된다.

Python 코드

import pandas as pd

try:
    df = pd.read_excel('file 주소')
    print(df)

except Exception as e:
    print(f"Error occurred while reading file from S3: {e}")

코드는 매우 간단하다.

위의 권한 설정이 완료된 경우, pandas 라이브러리를 불러온 후, read_excel() 함수를 이용해 객체를 불러올 수 있다.

사람들의 관계에서, 몇 번 다리를 건너야 모두 알 수 있는지를 확인하고, 그 중 인덱스가 작은 사람을 결과로서 출력하는 문제다.

접근 방법

1. 그래프 이론을 떠올려, 각 사람들의 관계를 리스트로서 표현
2. 첫 번째 사람부터 방문하여 관계가 있는 사람들을 먼저 방문
3. 관계가 있는 사람들의 관계를 이용하여 갈 수 있는 사람들 방문 (싸이월드 파도타기 같은 개념)
4. 2~3번을 반복하여 거리 측정
5. 모든 사람 반복한 후, result에 저장된 값들 중 작은 인덱스 출력

작성한 코드

import sys
from collections import deque

input = sys.stdin.readline

n, m = map(int, input().split())

relation = [[] for _ in range(n+1)]

for i in range(m):
    a, b = map(int, input().split())

    relation[a].append(b)
    relation[b].append(a)

result = []

for i in range(1, n+1):
    num = [0] * (n+1)
    visit = [i]
    queue = deque()        # deque 활용
    queue.append(i)

    while queue:
        idx = queue.popleft()
        for i in relation[idx]:
            if i not in visit:
                num[i] = num[idx] + 1
                visit.append(i)        # visit 방문 처리
                queue.append(i)        # queue에 넣기
    result.append(sum(num))

print(result.index(min(result))+1)

예) 1번 예시

코드로 디버깅 과정을 보이면 위와 같다.

순차적으로 BFS를 수행하며 모든 노드를 방문한다.

해당 내용은 코딩 테스트 합격자 되기의 저자께서 작성한 코드를 기반으로 작성했습니다. 출처

1. Counter

Counter 라이브러리는 Collections에 포함되어 있으며 iterable 객체의 정보를 한눈에 보여주기 위해 사용한다.

• Counter(iterable): iterable 객체(문자열, 리스트, 튜플 등)를 받아, 각 요소의 빈도수를 계산하여 Counter 객체를 생성한다. 시간 복잡도는 O(n)이며, n=len(lterable)이다.
  
• Counter.most_common(num): Counter 객체에서 가장 빈번하게 발생하는 num개의 요소와 그 개수를 리스트로 반환한다. num이 지정되지 않거나 None면 모든 요소를 반환한다. 시간 복잡도는 O(n log n)이며, n은 Counter 객체의 원소 개수다.
  
• Counter.elements(): Counter 객체에서 요소들을 횟수에 따라 반복하는 iterator를 반환한다. 시간 복잡도는 O(n), n은 elements의 총 개수다.

아래 코드는 예시를 나타낸다.

from collections import Counter

# 1. Counter(iterable)
iterable_example = 'abracadabra'
counter_obj = Counter(iterable_example)
print(counter_obj)


# 2. Counter.most_common(num)
most_common_elements = counter_obj.most_common(2)
print(most_common_elements)


# 3. Counter.elements()
elements_iterator = counter_obj.elements()
print(list(elements_iterator))


----------------
1 Counter({'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1})
2 [('a', 5), ('b', 2)]
3 ['a', 'a', 'a', 'a', 'a', 'b', 'b', 'r', 'r', 'c', 'd']

2. lambda

lambda 일명 람다는 익명 함수를 생성하는 키워드다. 이는 def를 사용해 생성하는 함수와 동일하지만, 이름 없이 정의되며 한 줄로 표현할 수 있다.

기본 구조는 다음과 같다.

lambda arguments : expression

이는 다양한 분야에 활용할 수 있으며, 일회성의 간단한 함수나 다른 함수의 인자로 전달될 수 있다.

• 리스트 정렬: lambda 함수를 사용해 리스트의 각 요소에 대한 정렬 키를 지정할 수 있다.
  
• filter()에서 활용: lambda 함수를 사용해 iterable에서 특정 조건을 만족하는 요소만 필터링할 수 있다.
  
• map()에서 활용: lambda 함수를 사용해 iterable의 모든 요소에 함수를 적용할 수 있다.
  
• reduce()에서 활용: lambda 함수를 사용해 iterable의 모든 요소를 단일 값으로 줄일 수 있다.

다음은 사용 예를 보여주는 코드다.

# 1. 기본적인 lambda 함수:
add = lambda x, y: x + y
print(add(1, 2))  

# 2. 리스트의 sort 메서드에서 key 인자로 사용:
my_list = [(1, 2), (3, 1), (5, 0), (4, 5)]
my_list.sort(key=lambda x: x[1])
print(my_list)  

# 3. filter 함수에서 사용:
nums = [0, 1, 2, 3, 4, 5]
even_nums = filter(lambda x: x % 2 == 0, nums)
print(list(even_nums))  

# 4. map 함수에서 사용:
nums = [0, 1, 2, 3, 4, 5]
squares = map(lambda x: x ** 2, nums)
print(list(squares))

# 5. reduce 함수에서 사용:
from functools import reduce
nums = [1, 2, 3, 4, 5]
sum_of_nums = reduce(lambda x, y: x + y, nums)
print(sum_of_nums)  


----------------
1 3
2 [(5, 0), (3, 1), (1, 2), (4, 5)]
3 [0, 2, 4]
4 [0, 1, 4, 9, 16, 25]
5 15

3. Set

Set은 파이썬에서 집합을 구현할 때 사용한다.

아래는 집합에서 수행할 수 있는 다양한 연산을 나타낸다.

# 집합 s 생성
s = set()

# s.add(item): 집합 s에 요소 item을 추가합니다.
# 시간 복잡도: O(1)
s.add(1)  # 현재 집합: {1}
print(s)  -----> {1}

# s.remove(item): 집합 s에서 요소 item을 제거합니다. 
# item이 s에 없을 경우 KeyError를 발생시킵니다.
# 시간 복잡도: O(1)
s.remove(1)  # 현재 집합: {}
print(s)  -----> set()

# s.discard(item): 집합 s에서 요소 item을 제거합니다. 
# item이 s에 없어도 에러가 발생하지 않습니다.
# 반환값: 없음
# 시간 복잡도: O(1)
s.discard(1)  # 현재 집합: {} (아무 변화 없음)
print(s)  -----> set()

# 집합 s와 s2 생성 및 초기화
s = {1, 2, 3}
s2 = {3, 4, 5}

# s.union(s2): 집합 s와 s2의 합집합을 반환합니다.
# 시간 복잡도: O(len(s) + len(s2))
print(s.union(s2))  -----> {1, 2, 3, 4, 5}

# s.intersection(s2): 집합 s와 s2의 교집합을 반환합니다.
# 시간 복잡도: O(min(len(s), len(s2)))
print(s.intersection(s2))  -----> {3}

# s.difference(s2): 집합 s에서 s2의 요소를 제거한 차집합을 반환합니다.
# 시간 복잡도: O(len(s))
print(s.difference(s2))  -----> {1, 2}

# set(list): 리스트를 집합으로 변환합니다.
# 시간 복잡도: O(len(list))
print(set([6, 7, 8]))  -----> {8,6,7}, {6,7,8}..  
# 집합은 순서를 보장하지 않으므로 순서 달라질수 있음

# item in s: 집합 s에 item이 포함되어 있는지 확인합니다.
# 반환값: bool (True 또는 False)
# 시간 복잡도: O(1)
print(1 in s)  -----> True

4. Zip

zip() 함수는 여러 개의 iterable 객체(리스트, 튜플 등)의 요소들을 포장하여 한 번에 하나씩 각 iterable의 동일한 인덱스에 있는 요소들을 튜플로 그룹화하여 반환한다.

zip()의 반환 값은 zip 객체이며, 이는 반복자 사용이 가능하다.

아래는 사용 예시를 나타낸다.

# 예시 1: 두 리스트를 zip 함수로 묶기
list1 = [1, 2, 3, 4]
list2 = ['a', 'b', 'c', 'd']
zipped = zip(list1, list2)
print(list(zipped))  
# 출력: [(1, 'a'), (2, 'b'), (3, 'c'), (4, 'd')]

# 예시 2: 세 리스트를 zip 함수로 묶기
list3 = ['apple', 'banana', 'cherry', 'date']
zipped = zip(list1, list2, list3)
print(list(zipped))  
# 출력: [(1, 'a', 'apple'), (2, 'b', 'banana'), 
#       (3, 'c', 'cherry'), (4, 'd', 'date')]

# 예시 3: zip 함수와 for 루프 함께 사용
# 아래의 코드는 zip 함수를 이용하여 두 리스트의 요소를 동시에 순회하는 예입니다.
for num, letter in zip(list1, list2):
    print(f"{num} is paired with '{letter}'")  
# 출력: 1 is paired with 'a', 2 is paired with 'b' .... 

# 참고: zip 함수는 가장 짧은 길이의 이터러블이 완료되면 중지됩니다.
# 따라서 iterable의 길이가 다르면, zip 함수는 
# 가장 짧은 이터러블의 길이에 맞춰서 그룹을 생성합니다.

해당 내용은 코딩 테스트 합격자 되기의 저자께서 작성한 코드를 기반으로 작성했습니다. 출처

1. append() vs +

리스트에 항목을 추가할 때, append()와 단순 + 연산의 동작 및 시간 복잡도에 대해 알아본다.

• append(): 리스트 끝에 새 요소를 추가하는 연산, 시간 복잡도는 O(1)
  
• +: 두 리스트를 합치는 연산으로, 시간 복잡도는 O(n) 리스트 크기에 비례하게 시간이 소요되며, 반복문 안에서 사용하는 경우 새 리스트를 매번 생성하기 때문에, 시간 소요가 큼

아래는 10,000만큼의 길이를 갖는 리스트 생성 비교 코드다.

import time

num_elements = 10000

# append() 사용
start_time = time.time()
lst_append = []
for i in range(num_elements):
    lst_append.append(i)
append_time = time.time() - start_time

# + 연산자 사용
start_time = time.time()
lst_plus = []
for i in range(num_elements):
    lst_plus = lst_plus + [i]
plus_time = time.time() - start_time

print(f"Using append() took: {append_time:.6f} seconds")# 
print(f"Using + operator took: {plus_time:.6f} seconds")# 

-------
Using   append() took: 0.002993 seconds
Using + operator took: 0.306183 seconds

2. for loop vs list comprehension

리스트를 생성하거나 초기화할 때 사용하는 for loop와 list comprehension의 시간 복잡도 및 성능에 대해 비교한다.

• for loop: 기본적인 반복문으로, 반복적인 메서드 호출을 통해 연산을 수행하며, 일반적인 시간 복잡도는 O(n)
  
• list comprehension: for loop와 비슷하게 반복연산을 수행하지만, 내부 로직의 최적화가 더 잘 되어있어 더 빠른 연산이 가능하다. 시간 복잡도는 O(n)로 같지만, 상수 시간 요소가 for loop보다 작다.

아래는 10,000,000까지 수의 제곱 수를 갖는 리스트 생성 비교 코드다.

import time

num_elements = 10000000

# for 루프 사용
start_time = time.time()
squared_numbers = []
for i in range(num_elements):
    squared_numbers.append(i * i)
for_loop_time = time.time() - start_time

# list comprehension 사용
start_time = time.time()
squared_numbers_comprehension = [i * i for i in range(num_elements)]
list_comprehension_time = time.time() - start_time

print(f"Using for loop took: {for_loop_time:.6f} seconds") 
print(f"Using list comprehension took: {list_comprehension_time:.6f} seconds") 

-----------
Using           for loop took: 1.523899 seconds
Using list comprehension took: 0.899564 seconds

3. list pop() vs deque pop()

list와 deque의 pop() 연산 수행 속도 및 시간 복잡도를 비교한다.

• list.pop(0): 리스트의 첫 번째 요소를 제거하고, 나머지 요소들을 한 칸씩 앞으로 이동한다. 시간 복잡도는 O(n)이지만, 반복적으로 수행할 경우 O(n^2)
  
• deque.popleft(): deque 라이브러리에서 제공하는 기능으로, 상수 시간 O(1)에 첫 번째 요소를 제거할 수 있다. 반복적으로 수행 할 경우 O(n)

아래 코드는 100,000개의 요소를 가진 list와 deque에서 pop()연산을 비교한다.

import time
from collections import deque

num_elements = 100000

# 리스트에서 pop(0) 사용
lst = list(range(num_elements))
start_time = time.time()
while lst:
    lst.pop(0)
list_pop_time = time.time() - start_time

# deque에서 popleft() 사용
dq = deque(range(num_elements))
start_time = time.time()
while dq:
    dq.popleft()
deque_popleft_time = time.time() - start_time

print(f"Using list's pop(0) took: {list_pop_time:.6f} seconds")
print(f"Using deque's popleft() took: {deque_popleft_time:.6f} seconds")

-------------
Using     list's pop(0) took: 1.441148 seconds
Using deque's popleft() took: 0.014957 seconds

4. list.sort() vs heapq.heappush()

정렬된 list를 만들 때, list.sort()와 heapq.heappush() 연산의 수행 속도 및 시간 복잡도를 비교한다.

• list.sort(): 리스트에 요소를 추가한 다음, 매번 정렬을 수행해야 한다. append() 연산의 경우 O(1)의 시간 복잡도를 가지지만, sort() 연산은 O(n log n)의 시간 복잡도를 가진다. 전체적으로는 O(n^2 log n)
  
• heapq.heappush(): heapq 라이브러리는 이진 힙 자료구조를 사용하여 요소를 추가하더라도 힙 속성을 유지한다. heappush() 연산의 시간 복잡도는 O(n log n)이므로, 전체적으로 O(n log n)

아래 코드는 10,000개의 요소를 생성하여 리스트에 넣고 정렬하는 연산을 비교한다.

import heapq
import time
import random

num_elements = 10000
lst = []
heap = []

# 일반 리스트 사용
start_time = time.time()
for _ in range(num_elements):
    val = random.randint(1, num_elements)
    lst.append(val)
    lst.sort()
list_time = time.time() - start_time

# heapq 사용
start_time = time.time()
for _ in range(num_elements):
    val = random.randint(1, num_elements)
    heapq.heappush(heap, val)
heap_time = time.time() - start_time

print(f"Insertion & sort in list took: {list_time:.6f} seconds")
print(f"Insertion using heapq took: {heap_time:.6f} seconds")

------------
Insertion & sort in list took: 0.428877 seconds
Insertion using    heapq took: 0.007989 seconds

5. list in vs set in

리스트와 set 자료구조 내에 특정 인자가 확인하는 in() 연산의 성능 및 시간 복잡도를 비교한다.

• list in: 리스트에서 in연산자를 사용하는 경우 O(n)의 시간 복잡도를 가진다. 이때, 각 요소를 처음부터 순차적으로 탐색하여 값을 검색한다.
  
• set in: 집합에서 in연산자를 사용하는 경우 일반적으로 O(1)의 시간 복잡도를 가진다. 이는 집합이 해시 테이블 기반의 자료구조이기 때문에, 요소의 해시 값을 사용하여 빠른 탐색이 가능하기 때문이다.

아래 코드는 1,000,000개의 요소에서 특정 값을 탐색하는 연산을 비교한다.

import time

# 데이터 준비
num_elements = 1000000
test_value = num_elements + 1  # 이 값은 리스트와 집합에 없음.

lst = list(range(num_elements))
s = set(lst)

# 리스트에서 in 테스트
start_time = time.time()
result_list = test_value in lst
end_time = time.time()
list_time = end_time - start_time

# 집합에서 in 테스트
start_time = time.time()
result_set = test_value in s
end_time = time.time()
set_time = end_time - start_time

print(f"List membership test took: {list_time:.6f} seconds")
print(f"Set membership test took: {set_time:.6f} seconds")


----------------
List membership test took: 0.015955 seconds
Set  membership test took: 0.000000 seconds

6. String += vs "".join()

문자열을 합칠 때 사용하는 += 연산과 "".join() 연산의 성능 및 시간 복잡도를 비교한다.

• +=: 문자열 결합을 위해 주로 사용되는 연산이다. 문자열은 변경이 불가능한 객체이므로, 매번 += 연산을 수행할 때 마다 새로운 문자열 객체가 생성되고, 이전 문자열의 내용과 새로운 문자열의 내용이 복사된다. 시간 복잡도 O(n^2)를 가진다.

  
  

• ''.join(): 문자열 리스트를 한 번에 결합하는 방법을 제공한다. 내부적으로 더 효율적인 메모리 관리를 수행하며, 문자열을 한 번에 합치기 때문에 O(n)의 시간 복잡도를 가진다.

• 문자열이 큰 경우 ''.join() 메소드가 훨씬 빠른 성능을 보인다.

아래 코드는 [abcd] 문자열을 1,000,000번 반복한 객체를 다른 문자열과 합치는 경우의 연산을 비교한다.

import time

num_elements = 1000000
strings = ["abcd"] * num_elements

# += 연산자 사용
start_time = time.time()
result_str = ""
for s in strings:
    result_str += s
plus_equals_time = time.time() - start_time

# join() 메서드 사용
start_time = time.time()
result_str = "".join(strings)
join_time = time.time() - start_time

print(f"Using += operator took: {plus_equals_time:.6f} seconds")
print(f"Using join() method took: {join_time:.6f} seconds")

------------------
Using     += operator took: 0.514103 seconds
Using join() operator took: 0.020838 seconds

이를 해결하기 KMP 알고리즘이 등장했다.

KMP 알고리즘이란, Knuth, Morris, Prett이 만든 알고리즘으로, 문자열 탐색을 수행할 때 O(N+M)의 시간복잡도로 문제를 해결할 수 있도록 도와준다.

접두사 Prefix 접미사 Suffix

1. KMP 알고리즘은 접두사와 접미사의 개념을 활용한다.

• Prefix 예) Apple --> A Ap App Appl Apple

• Suffix 예) Apple --> e le ple pple Apple

2. pi[i]는 길이가 i인 문자열이 있고, 0~i까지의 부분 문자열 중 Prefix == Suffix가 될 수 있는 부분 문자열 중에서 가장 큰 길이 (Prefix가 0~i 까지의 부분 문자열과 같으면 안됨)

• 예1) ABAABAB

i      sub_srting    pi[i]
-------------------------
0           A            0
1           AB            0
2           ABA            1
3        ABAA        1
4        ABAAB        2
5        ABAABA        3
6        ABAABAB        2

• 예2) AABAA

i      sub_srting    pi[i]
-------------------------
0           A            0
1           AA            1
2           AAB            0
3        AABA        1
4        AABAA        2

단순한 비교 알고리즘의 경우 다음과 같이 수행한다.

1번 수행 시

0 1 2 3 4 5 6 7 8 9 10
A B C D A B C D A B E
A B C D A B E  <-- ! 다름 !! (6번째 인덱스가 다름!!)

2번 수행 시

0 1 2 3 4 5 6 7 8 9 10
A B C D A B C D A B E
  A B C D A B E  <-- ! 다름 !! (1번째 인덱스가 다름!!)

이러한 과정에서, 1번 인덱스가 틀렸다는 정보만 사용한다.

즉, 1번 수행했을 때, 0~5번 인덱스가 일치한다는 정보를 활용하지 않았다는 뜻이다.

해당 정보를 활용하는 경우, 아래와 같이 사용할 수 있다.

0 1 2 3 4 5 6    7 8 9 10 11
A B C D A B C(i) D A B E  E            # i = 텍스트의 현재 비교위치
        A B C(j) D A B E              # j =   패턴의 현재 비교위치

위 과정이 가능한 이유는, 패턴 ABCDAB의 Prefix와 Suffix가 AB로 일치하기 때문이다.

또한, Prefix와 Suffix가 일치하는 최대 길이이므로, ABCDABE의 pi[i] = 2.

참고1 참고2

특정 수 N이 주어졌을 때, IO * N + I의 열이 문자열에 몇 번 포함되어 있는지를 구하는 문제다.

서브태스크 문제로, N과 M의 길이가 매우 큰 경우가 제한사항으로 걸려있다.

접근방법

• 서브태스크 50점

1. 주어진 문자열 s에서 I를 만날 때마다 탐색 문자열 길이만큼을 확인
2. 탐색 문자열과 같은 경우 결과 값 1 증가
3. 다른 경우 continue 활용

• 서브태스크 100점

1. KMP 알고리즘을 이용하여, prefix suffix 개념을 활용
2. 테이블 생성 후, 주어진 문자열에 대해 수행

작성한 코드 1 (50점)

import sys

input = sys.stdin.readline

n = int(input())
m = int(input())

s = input().rstrip()

find = n * "IO" + "I"

result = 0

for i in range(0, len(s)-2):

    if s[i] == "I":
        if s[i:i+len(find)] == find:
            result += 1
    else:
        continue

print(result)

작성한 코드 2 (100점)

import sys

input = sys.stdin.readline

def makeTable(pattern):
    table = [0 for i in range(len(pattern))]
    j = 0
    for i in range(1, len(pattern)):
        while(j>0 and pattern[i] != pattern[j]):
            j = table[j-1]

        if pattern[i] == pattern[j]:
            table[i] = j+1
            j += 1
    return table

def KMP(parent, pattern):
    table = makeTable(pattern)

    j = 0
    result = 0

    for i in range(len(parent)):                    # 전체 길이를 돌며
        while(j>0 and parent[i] != pattern[j]):     # 하나씩 비교
            j = table[j-1]                          # 

        if parent[i] == pattern[j]:                 # 글자가 일치하는 경우
            if j == len(pattern) - 1:               # 마지막 인덱스
                result += 1                         # 결과 +1
                j = table[j]                        
            else:
                j+= 1                               # 마지막 인덱스가 아닌 경우
    return result 

n = int(input())
m = int(input())
parent = input().rstrip()

pattern = n * "IO" + "I"

result = KMP(parent, pattern)
print(result)

N명의 MBTI가 주어졌을 때, 가장 적게 차이가 나는 3명을 선택하는 문제로, 여기서 차이는 MBTI의 각 항목이 다름을 의미한다.

예) ESTP <-> INFJ는 모두 다르기 때문에 차이가 4다.

접근 방법

1. 무작정 완전 탐색을 수행하려다가, N이 100,000까지 나올 수 있어 다른 방법을 생각
   
2. MBTI는 각 항목의 경우가 2개씩 존재하여 16개의 특성이 존재. N이 32가 넘어가면, 동일한 MBTI를 가지는 사람이 최소 3명 존재 (N이 16이 될 떄 마다 모든 MBTI는 1번씩 나올 수 있기 떄문)
   
3. N이 32보다 큰 경우에는 0 출력, 그렇지 않은 경우에는 완전탐색 수행
   
4. i j k로 3개의 인덱스를 생성하여 3중 중첩 for문으로 모든 경우를 탐색 (i j k가 같은 경우에는 탐색 생략)
   
5. result 변수에 현재까지 가장 작게 나온 경우를 집어넣고, min 구문을 이용해 더 작은 경우가 나오는 경우 변경

작성한 코드

import sys

input = sys.stdin.readline

test_case = int(input())

for i in range(test_case):

    n = int(input())
    result = 13
    mbti_list = list(map(str, input().split()))

    if n > 32:  # n이 32가 넘어가게 되면 동일한 mbti가 최소 3명
        print(0)

    else:
        for i in range(n):
            for j in range(n):
                for k in range(n):
                    if i == j or j == k or i == k:
                        continue
                    tmp = 0
                    for _ in range(4):
                        if mbti_list[i][_] != mbti_list[j][_]: 
                            tmp += 1
                        if mbti_list[j][_] != mbti_list[k][_]: 
                            tmp += 1
                        if mbti_list[i][_] != mbti_list[k][_]: 
                            tmp += 1
                    result = min(result, tmp)
        print(result)

실수한 부분

처음 채점할 떄, ValueError가 발생했다. 그 이유가 뭘까

import sys

input = sys.stdin.readline

test_case = int(input())

for i in range(test_case):

    n = int(input())
    result = 13


    if n > 32:  # n이 32가 넘어가게 되면 동일한 mbti가 최소 3명
        print(0)

    else:

           mbti_list = list(map(str, input().split())) # <<< 에러 발생

        for i in range(n):
            for j in range(n):
                for k in range(n):
                    if i == j or j == k or i == k:
                        continue
                    tmp = 0
                    for _ in range(4):
                        if mbti_list[i][_] != mbti_list[j][_]: 
                            tmp += 1
                        if mbti_list[j][_] != mbti_list[k][_]: 
                            tmp += 1
                        if mbti_list[i][_] != mbti_list[k][_]: 
                            tmp += 1
                    result = min(result, tmp)
        print(result)

위 코드에서와 같이 MBTI를 받는 경우를 else문 밑에 작성해서

n = int(input())

의 입력으로 mbti가 입력되어 에러가 발생했다.

타일을 이용하여, 주어진 크기의 직사각형을 채울 수 있는 모든 경우의 수를 고려하는 문제다.

접근 방법

1. 이러한 유형의 문제는 규칙을 찾아 답을 찾는 dynamic programming에 해당할 것 같아, 규칙 탐색
2. 그 결과, 2*n 크기를 갖는 직사각형을 채움에 있어, n번째 블록은 n-2 블록에 사용된 타일 수 * 2와 n-1 블록에 사용된 타일 수가 필요
3. 알아낸 규칙을 기반으로 코드 작성
4. 2*1, 2*2, 2*3인 경우는 리스트 상에서 미리 정의

작성한 코드

import sys

input = sys.stdin.readline

n = int(input())

num_list = [0 for _ in range(1001)] # n이 최대 1000

num_list[0] = 1        # 2*1
num_list[1] = 3        # 2*2
num_list[2] = 5        # 2*3

for i in range(3, n+1):
    num_list[i]= (num_list[i-2] * 2) + num_list[i-1]

print(num_list[n-1]%10007)

첫 시도에서 런타임 에러가 발생했는데,

num_list = [0 for _ in range(n+1)]

위와 같이 코드를 작성했을 때, 런타임 에러가 발생했다.

n이 1일 때 리스트 인덱스를 고려하지 못해 발생했다. (코드에서 num_list[2] 범위까지 값을 할당하기 때문에)

이후 n의 최대 범위인 1000에 1을 더한 1001을 할당하여 문제를 해결했다.

입력으로 옷과 옷의 종류가 주어지고, 동일한 종류의 옷은 동시에 입지 못한다고 할 때, 가능한 모든 경우의 수를 구하는 문제다.

접근 방법

1. 옷을 종류별로 구분하기 위해 딕셔너리 자료형을 사용
2. 딕셔너리에 옷의 개수가 저장되면, 가능한 모든 경우의 수를 계산
3. 동일한 종류의 옷은 입을 수 없고, 입지 않은 경우도 존재하기 때문에 투명 옷의 개념을 생각
4. 예를 들어 모자 3개, 상의 2개, 하의 2개인 경우 모자를 쓰지 않는 경우, 상의를 입지 않는 경우, 하의를 입지 않는 경우를 고려하여 4x3x3을 수행한 뒤, 모두 입지 않는 경우를 생각해 1을 빼준다.

작성한 코드

import sys

input = sys.stdin.readline

test_case = int(input())

for i in range(test_case):
    case = int(input())
    num = {}
    result = 1

    for j in range(case):

        name, wear = input().split()

        if wear in num.keys():    # 딕셔너리에 저장
            num[wear] += 1
        else:
            num[wear] = 1

    for i in num.values():
        result = result * (i+1)

    print(result-1)