스터디룸

2020년 봄 즈음에 모바일 서비스 회의를 시작하며 더워질 즈음부터 서비스 개발을 진행하고 연말에 런칭하면서 개발자로의 직군 전환 준비를 시작했으니 대충 1년 3개월 정도의 기간 동안 공부를 했다. 그리고 3개월 간 기업 전형을 진행해서 네이버 신입 공채에 합격해 개발자로서의 첫번째 커리어를 시작했다. 좋은 회사들이 아주 많지만 으레 "네카라쿠배하당토"라는 기업들 중 하나에 붙어 뭔가 결과를 연말에 선물로 받은 기분이다. 세간에선 '네카라쿠배하당토'보다는 "네카라쿠배당토"라고들 하는데 갠적으로 여기에 하이퍼 없이 직방, 야놀자가 먼저 붙는다는 게 도저히 이해가 되질 않아 그냥 맘대로 붙였다.

지원사항

2021 네이버웹툰 개발 챌린지 - 과제 포기
2021 토스 NEXT 개발자 공채 - 서류 탈락
2021 그렙 채용 챌린지 - 서류 탈락
2021 LINE 하반기 공채 - 필기 탈락
2022 KAKAO BLIND 공채 - 코테 탈락
2021 NHN 그룹사 신입 개발자 공채 - 코테 탈락
2021 네이버 파이낸셜 개발자 채용 챌린지 - 과제 포기
2021 Dev-Matching: 웹 백엔드 개발자(하반기)

• 올거나이즈 코리아 - 면접 탈락
• 그렙 - 1차 면접 거절
• 카카오 엔터프라이즈 - 2차 최종 면접 거절

2021 Dev-Matching: Sillicon Valley

• MOLOCO - 1차 면접 탈락
• 쓰리덕스 - 면접 거절

2021 NAVER 하반기 공채: 개발직군 - 최종 합격

이것들 외에도 알고리즘 대회나 다른 언어로 출제되는 채용 챌린지는 눈으로 풀어보기도 했으니 되돌아보면 정말 많은 공개 채용 챌린지 등에 지원했었다. 19-20년 동안 틈틈히 운동했던 게 그나마 다행이었지 싶다. 지금은 다 소진해버려 다시 체력을 쌓아야 한다 ;ㅅ;

준비했던 내용

(포폴 관련 상세내용은 메뉴의 주인장 프로필 노션 링크에 있습니다.)
모바일 서비스 런칭 - 서비스 이름 : 승진왕
블로깅 -공부하거나 프로젝트 구현 시 배웠던 내용 일체
알고리즘
자료구조
CS - 운영체제, 네트워크

서비스 런칭

인력도 부족하고 협업하는 개발자 선배가 구글에서 SE 포지션으로 일하시는 분이라 나도 그냥 SE 포지션으로 참가한다 생각하고 임했다. 2-3명이서 기능단위로 일을 배분하느라 안드부터 Serverless API까지 다양하게 다뤘다. 비즈니스 로직을 수립하고 그 로직을 왜 도입해야 하는지, 어떤 기술을 사용했는데 왜 그걸 사용해야 하는지 다른 후보군과 어떤 차별점이 있는지 등 항상 질문하는 습관이 중요하다고 생각한다. 개인적으로 실제 개발자와 협업하며 로직 설계와 코드 작성 측면에서 정말 많이 배웠다. 프로젝트 단 하나이고 출시된 제품이라 깃헙 공개조차 못했지만 나름 점수를 크게 받았다고 여겨진다.

블로깅

고등학교는 이과를 나왔으나 대학 4년을 행정학과에 다니고 직장생활도 경찰 간부로 수많은 공문을 처리하느라 기록에 익숙했다. 블로깅도 온전히 내 지식으로 만들었다는 하나의 증표를 남기고자 시작했다. 개념 공부를 할 땐 키워드를 검색하여 외국 사이트 2-3개와 국내 블로그 5-7개를 참고해 하나의 문서로 종이에 포스팅 형식으로 정리한 뒤 마크다운으로 그대로 옮기며 다시 복습하는 과정을 거쳤다. 프로젝트 구현하면서 배웠던 내용을 정리할 땐 아예 새롭게 테스트 프로젝트를 만들면서 캡처화면을 만들고 역시 종이에 포스트를 미리 쓰면서 문장을 다듬고 마크다운으로 옮겨 블로그에 업로드했다. 고생은 2-3배가 들 정도로 꽤 힘든 작업이다. 그러나 기억이 희미해지더라도 다시 포스트를 보면 왜 이 문장을 썼는지, 왜 이렇게 개념을 설명했는지 빠르게 복구해낼 수 있어 여전히 이 방법을 채택하고 있다. 블로그 포스팅을 시작했을 때부터 지금까지 단순히 내용을 채워넣으려고만 하지 않고 모든 문장에 책임을 진다는 생각으로 최대한 남들이 보고 이해할 수 있게 작성하려고 노력 중이다. 그래선지 블로깅도 좋게 봐주는 분들이 많았다.

알고리즘&자료구조

원래 Geeks for Geeks 사이트를 보면서 공부하고 있었는데 이러다가 한세월 걸리겠다 싶어 친구에게 "파이썬 알고리즘 인터뷰(박상길)"이라는 소위 상길북을 추천받아 2회독을 했다. 백준(실버-골드), 리트코드(이지-미디엄), 프로그래머스(레벨1~4) 문제들을 풀며 막힌 문제는 답을 보되 다음 날 다시 풀어낸 뒤 종이에 직접 포스팅을 한다 생각하며 적고 그걸 md파일로 옮겨 블로그에 올렸다. 이것이 코딩테스트인가 하는 다른 책도 좋다는데 개인적으로는 상길북으로 기초를 잡고 "알고리즘 문제해결전략(구종만)" 소위 종만북으로 넘어가는 걸 추천한다. 다만, 종만북은 난이도가 괴랄해 코드잼 등 외국계 기업을 위한 알고리즘 대회를 염두하는 게 아니라면 상길북 선에서 대부분의 국내 기업 코딩테스트를 무난하게 응시할 수 있다. 단, 카카오는 조금 더 공부를 해야한다. 필자는 3.5솔을 했으나 동일하게 3.5솔로 1차 통과한 후기가 있는 걸로 봐선 문제 간 배점이 다른 듯하다.

CS

CS는 정리할 생각이 있긴 했는데 1차 라인 필기 테스트를 응시한 뒤 제대로 정리할 필요성을 크게 느끼고 즉시 기록을 시작했다. 기본적으로 추천받은 책을 기반으로 하되 다른 이들이 신입 개발자를 위해 깃헙에 정리해둔 항목들을 보며 없는 내용들은 따로 더 첨가하는 방식으로 포스트를 작성했다.

• 운영체제
  운영체제는 반효경 교수님의 "운영체제와 정보기술의 원리" 책을 강력히 추천한다. 책에는 프로세스와 데드락이 조금 미흡해 다른 이들이 깃헙에 기술면접을 위해 정리한 항목들을 보며 없는 내용을 채워넣어 정리했다.
• 네트워크
  첫 번째로 추천받은 책은 "성공과 실패를 결정하는 1%의 네트워크 원리"였다. 일본 도서를 번역한 책인데 난이도는 네트워크 엔지니어 수준이다. 지금도 1회독을 못했지만 챕터 2까지는 정말 유용하게 봤다.
  두 번째로 추천받은 책은 "그림으로 배우는 네트워크 원리"였다. 이 책은 네트워크 개관을 알 수 있도록 잘 설명된 책이다. 블로그에 정리된 포스트는 개략적으로 두 번째 책을 베이스로 조금 심화된 내용은 첫 번째 책을 참고했다.

결론

결국 제목의 "네카라쿠배하당토"는 그냥 어그로용 단어였다. 늦었지만 사죄의 말씀을 드린다. '쿠배하당토'는 경력 채용을 주로 하고 있어 이런 방식의 준비가 맞지 않을 수 있다. '네카라'를 제외한 기업들은 좀 더 견고한 프로젝트 경험과 전공지식이 뒷받침되어야 할지도 모른다. 그러나 말하고 싶은 점은 적어도 '지식'을 습득하는 자세는 항상 겸손해야 한다는 점이다. 사실 필자는 최종 합격 시기를 내년 상반기로 예상했다. 글에서 볼 수 있듯이 실제로 공채 서류에 깃헙 주소조차 적지 않았다. 단지 블로그 주소 하나만을 적어서 제출했었다. 그래서인지 '네카라'를 제외한 대부분의 기업은 백엔드 프레임워크 경험(특히 스프링!)을 자격요건으로 걸어두고 있었기 때문에 프레임워크는 커녕 온전한 서버조차 올려본 적이 없어서 대부분의 채용 기회를 놓쳤기 때문이다. 필자도 그걸 깨닫고 빠르게 학원(F-Lab)에 등록하여 백엔드 프레임워크를 사용한 프로젝트를 만들 준비를 했다. 막상 학원 과정을 진행하다가 공채에 합격해 환불 절차를 진행하고 있지만 너무나도 좋은 멘토를 만나 개발자의 마인드셋과 공부하는 자세 등을 배워 면접 준비를 정말 편하게 했다. 필자는 소위 "비전공자"이기에 공채 준비에 몰두할 수밖에 없었다. 합격하기까지 많은 분들로부터 도움을 받았기에 나 역시 필요로 하는 분들을 위해 도움을 줄 수 있는 사람이 되고자 한다.

막상 1차 면접을 복기하며 애매하게 답했던 내용을 다시금 복습하는 동안 생각보다 키워드 꺼낼 내용은 다 꺼냈음을 보고 생각보다 1차 면접은 통과할 가능성이 높겠다는 생각이 들었다. 다만, "혹시 모른다"는 일말의 불안감은 굉장하긴 했다.

네이버 2차 면접은 정말 면바면이라는 단어가 정확히 들어맞는 면접이 아닐까 싶다. 검색해서 볼 수 있는 모든 2차 면접 후기, 유튜브에 업로드 된 후기 영상들을 모조리 찾아보면서 인성 100%, 기술/인성 50%, 기술 100% 등 굉장히 비율이 다양했다. 필자는 인성 90%에 기술 10% 정도로 볼 수 있겠다. 초반에 자칫 기술 10%를 더 할 수 있었으나 감점을 각오한 혼신의 드리블로 기술 질문을 틀어막아 인성 면접 위주로 면접을 유도했다.

면접은 연차가 높아보이는 면접관 분들이 들어오시고 JD를 보면서 궁금한 것들 툭툭 던지며 꼬리물기로 이어나가는 방식으로 진행되었다. 그게 기술일 수도 인성 관련일 수도 있다. 인성면접은 면바면이 없게 만들 수 있다는 말에 따라 예상 질문을 거의 11페이지를 만들어간 덕분인지 생각보다 답변을 잘 할 수 있었다. 인성 면접을 진행하면서 느낀 점은 질문 1-2개는 압박을 해보려고 억까스러운 질문을 만들기는 하는데 아무 생각없이 본인 포폴과 자소서만 정리해 온 공대생이라면 답변이 힘들 수도 있겠다는 생각이 들었다. 대학과 직장생활이 문과라 살았지 싶다. 1차 면접 후기에서 자소서에 정말 자신있는 내용을 넣으라고 했는데 학력으로 넣어둔 석사과정과 관련해서 질문이 박힐 줄은 몰랐다. 반쯤 포기했던 석사라 그나마 관심있게 보던 주제가 있었어서 찾아봤던 내용들을 두루뭉실하게 기술 질문이 들어올 수 없게끔 방어했다. 아마 여기서 감점이 조금 되었으리라 생각한다.

기술 면접은 질문이 두 개 들어왔는데 생각보다 깊이가 깊어서 순간 속으로 "엌" 소리가 절로 나왔다. 아주 어려운 개념은 아닌 듯한데 그렇다고 신입 개발자 면접 질문으로 들어올 만한 문제는 전혀 아니란 생각이 들었다. 하나는 완전히 헤맸고 하나는 석사과정 수업 때 스치듯 들었던 기억이 나 답변을 해서 겨우 무마했다. 면접이 끝나고서 찾아본 결과 실무 관점에서 한 번쯤은 반드시 겪게 될 개념이었고 남들이 으레 전공지식을 깃헙에 정리한 목록 그 어디에서도 볼 수 없는 내용이었다. 주변에 물어보니 학부 전공수업 때도 다루지 않는 내용이고 교수님이 스쳐가듯이 한 번 꺼내봄직한 주제라는 답변을 들었다. 개발자로 활동 중인 아는 동생은 관련된 문제를 다루는 동료 개발자로부터 언뜻 들어봤다는 답을 주었다. 면접 순간에는 내가 말하는 내용이 정답인지 모르겠어서 최대한 문제를 명확하게 이해하려고 범위를 좁히며 명확하게 define하고자 했다. 그리고 답변은 알고 있는 개념들 하나씩 꺼내보면서 풀어나가는 자세를 보여주려고 했다. 물론 경력직 면접에서 이러면 나가리겠지만...'-`

2차 면접의 총평은 이력서 및 지원자가 제출한 내용들 하나씩 보며 가볍게 던지는 듯한데 생각보다 오고가는 질문이 많아 결국 거의 다 훑어본 듯 했다. 심지어 나는 포폴도 적었어서 1차 때 면접 결과가 같이 왔을테니 더 이상 털어낼 게 없었다. 그래도 개발자의 성장 키워드나 개발자로의 직군 전환 이유, 공부하는 방법 및 지식을 습득하는 자세 등 다양한 예상 질문을 뽑아내고 답하기 위해 "나"라는 사람의 세계관을 견고하게 구축하는 과정이 정말 큰 도움이 되었다. 인성면접은 감점요소가 거의 없었다고 자신한다. 기술면접 비중이 더 높았으면 대참사가 났을텐데 그렇지 않아 다행인 면접이었다. 

결과 : 2차 면접 통과해서 최종합격 통보받았습니다. 예전부터 2-3년 간 컴퓨터에 관심을 두고 있었으나 간단히 파이썬이나 다루며 코드 리딩이 가능한 수준이었고 본격적인 "개발자"로 직군을 전환하기 위한 준비는 대략 1년 3개월 정도 했습니다. 여러 기업에 동시에 지원서를 걸어두고 전형을 진행하느라 최종적으로는 1년 반만에 결과가 나왔습니다. 그래도 면접관으로 들어오신 분들이 저를 좋게 봐주셔서 그런지 예상보다 빠르게 자리를 잡을 수 있게 되었습니다. 남들보다 경험도 없고 전공지식도 얕은 편이라 계속 키워드를 찾으며 공부를 이어나가려 합니다.

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 사용해보면서 배운 점을 정리한 글입니다.

Peer to Peer 통신 관련해서 질문이 들어온 바 있다. 정확히는 사설 네트워크 내 호스트 간 통신인데 조사를 해보니 NAT 네트워크에 대한 전반적인 이해가 선행되고 나서 심화 개념에 대해 정리를 해야 함이 올바른 순서라고 판단했다. 기술면접을 위한 Network 개념정리 04 - IP에서 NAT에 관한 간략한 설명을 달아두었으나 정확히 사설 네트워크의 호스트 - 공인 서버 간 통신 과정에 대해서는 순서대로 파악한 적이 없어 이번 기회에 정리해보고자 한다.

NAT(Network Address Translation)

NAT는 하나의 공인 IP 주소에 여러 개의 호스트가 사설 IP를 가지고 통신할 수 있게끔 해주는 기법이다. 공인 IP 끼리의 패킷 전송은 IP 헤더가 바뀌지 않고 맥주소만 변경된 패킷을 송신한다고 작성한 바 있다. 그러나 사설 IP에서 공인 IP로 전환하는 작업은 IP 헤더의 정보를 수정한다.

효과

• 공인 IP 주소의 절약
• 하나의 공인 IP로 구성된 사설 subnet을 외부로부터 보호(방화벽)
  • 방화벽을 설치하여 공인 IP만 노출, 공격자는 방화벽이 숨겨둔 사설 IP 주소를 알아내야 함

Static NAT(1:1)

1개의 공인 IP에 하나의 사설 IP를 매핑한다. 그렇기 때문에 공인 IP 주소의 개수와 사설 IP의 주소 개수가 동일해야 한다.

1:1 매핑이므로 외부에서 내부로의 접근도 가능하다.

Dynamic NAT(N:M)

사설 IP 그룹과 공인 IP그룹을 매핑한다. 내부에서 외부로 통신 시 NAT를 수행하는 장치가 정보를 기록한다. 공인 IP 주소의 개수가 사설 IP 주소 개수보다 적을 때 사용한다. 1:1 매핑이 아니므로 NAT 테이블은 Static NAT처럼 고정적인 정보를 갖지 않는다. 따라서, Dynamic NAT에서의 NAT 테이블 레코드는 통신이 시작되면 그때마다 기록하는 임시 정보로 이해할 수 있다. 고정 매핑 방식이 아니기에 Static NAT와는 달리 외부에서 내부로 진입할 수가 없다. 오로지 내부에서 외부로의 통신만 가능하다.

NAT의 문제

NAT는 라우터가 사설-공인 IP 매핑 정보를 저장해두고 회신받은 패킷을 조사하여 정보가 일치하는 경우 해당 호스트로 보내주는 과정이다. 그런데 두 개의 호스트가 동시에 같은 외부 네트워크 목적지와 통신하는 경우 동일한 공인 IP가 목적지로 설정된 패킷들을 전송한다. 패킷들을 수신받은 외부 네트워크에 속한 상대는 두 호스트가 소속된 Subnet의 공인 IP를 목적지로 패킷들을 구성하여 회신한다. 그러나, 기존의 NAT만으로는 라우터가 어느 호스트에 보내줘야 할 지 알 수가 없다.

공인 IP 주소를 갖는 외부 서버가 사설 Subnet의 대표 공인 IP로 전송하긴 했으나 두 호스트를 구별할 정보가 없어 문제가 발생했다. 외부 공인 IP 전송처에서 목적지가 같은 패킷을 보내더라도 Subnet으로 패킷을 전달하는 라우터가 어느 호스트가 받아야 하는지 알 수 있는 정보(포트)를 추가해야 한다.

NAPT(Network Address Port Translation)

1:N PAT라고도 한다. NAT에서 Port 정보 해석을 추가한 기법이다. 사설 네트워크에서 외부 공인 IP로 전송할 때 라우터에서 사설 IP|사설 포트|공인 IP|공인 포트를 기록해두고 원격지 서버로 패킷을 보낸다. 원격지 발송처는 동일한 공인 IP 주소를 목적지로 갖는 패킷을 보냈어도 포트를 첨부함으로써 사설 subnet의 호스트들을 구분하여 통신할 수 있다.

Dynamic NAT처럼 사설 Subnet에서의 호스트들은 고정 포트로 구분된 상태가 아니기 때문에 내부에서 외부로 통신을 할 수 있으나 외부에서 내부로의 통신은 불가하다.

포트 포워딩(Port Forwarding)

그렇다면 NAPT를 수행하는 기기에 호스트들이 고정 포트로 매핑된 상태면 외부에서 내부로 통신을 할 수 있겠다는 생각이 든다. 바로 그 개념이 포트 포워딩이다. 그리고 고정 포트를 포워딩하기 때문에 역시 두 개의 IP가 동일 포트로 포워딩할 수 없다는 제약사항이 있다. 그리고 특정 포트로 포워딩 하기 위해선 반드시 사설 IP 주소:포트 형식으로 매핑 정보가 필요하다.

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

LeetCode #97 Interleaving String

문제 풀이

dp로 풀어야 하나 고민했는데 dfs로도, bfs로도 풀리는 문제였다. 아직 문자열 다루는 심화문제에 약한 감이 있다. 별개로 이 문제는 생각할 점이 많은 좋은 문제기도 하다.

문제의 요지는 두 개의 스트링을 적당한 순서를 갖고 차례대로 추출하여 배열했을 때 주어진 스트링으로 만들 수 있는지 여부를 리턴해야 한다. 따라서 두 스트링의 길이가 주어진 스트링과 맞지 않으면 우선적으로 false를 리턴할 수 있다. 그리고 dfs건 bfs건 dp건 이전까지의 검증 좌표와 현재 탐색 좌표의 기준에 맞춰 탐색을 진행한 뒤 마지막 좌표의 결과를 리턴하면 된다. 성능은 bfs - dfs가 더 좋지만 공간복잡도는 dp가 더 좋았다.

• s1 길이 + s2길이 != s3 길이면 s1과 s2를 합쳐도 s3를 만들 수 없으므로 False
• dfs와 bfs로 구현할 경우 방문 대기열을 담을 stack이나 queue를 선언하여 set 자료형으로 방문체크를 한다.
• 시작점은 0, 0이고 시작점에 대해 다음 탐색지점을 담을지 결정해야 한다.
  • s1과 s2를 서로 구분하여 각각에 대해 검사를 진행한 뒤 대기열에 넣어야 한다.
  • (pos1 + 1, pos2)를 넣는 조건과 (pos1, pos2 + 1)를 넣는 조건 두 개가 필요하다.
  • 전자는 s1[pos1]과 s3[pos1 + pos2]의 검증이고 후자는 s2[pos2]과 s3[pos1 + pos2]의 검증이다.
  • 대기열에 좌표를 넣을 때 대기열에 넣는 좌표는 더 이상 탐색할 이유가 없으므로 visited set에 담는다.
• 대기열에서 좌표 추출 시 두 점의 좌표가 s3 길이와 동일하다면 True 반환
• 대기열에서 모든 좌표를 추출하여 탐색했음에도 True를 반환하지 못했다면 False 리턴

python 코드 - DFS

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        s1Len, s2Len, s3Len = len(s1), len(s2), len(s3)
        if s1Len + s2Len != s3Len:
            return False
        stack, visited = [(0, 0)], set((0, 0))
        while stack:
            pos1, pos2 = stack.pop()
            if pos1 + pos2 == s3Len:
                return True
            if pos1 < s1Len and s1[pos1] == s3[pos1 + pos2] and (pos1 + 1, pos2) not in visited:
                stack.append((pos1 + 1, pos2))
                visited.add((pos1 + 1, pos2))
            if pos2 < s2Len and s2[pos2] == s3[pos1 + pos2] and (pos1, pos2 + 1) not in visited:
                stack.append((pos1, pos2 + 1))
                visited.add((pos1, pos2 + 1))
        return False

python 코드 - BFS

from collections import deque
class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        s1Len, s2Len, s3Len = len(s1), len(s2), len(s3)
        if s1Len + s2Len != s3Len:
            return False
        queue, visited = deque([(0, 0)]), set()
        while queue:
            pos1, pos2 = queue.popleft()
            if pos1 + pos2 == s3Len:
                return True
            if pos1 < s1Len and s1[pos1] == s3[pos1 + pos2] and (pos1 + 1, pos2) not in visited:
                queue.append((pos1 + 1, pos2))
                visited.add((pos1 + 1, pos2))
            if pos2 < s2Len and s2[pos2] == s3[pos1 + pos2] and (pos1, pos2 + 1) not in visited:
                queue.append((pos1, pos2 + 1))
                visited.add((pos1, pos2 + 1))
        return False

python 코드 - DP

만약 dp인 경우에는 2차원 배열을 선언하여 두 개의 스트링에 대한 이전 좌표를 탐색하여 결정할 수 있다.

• [s1길이 + 1][s2길이 + 1]의 2차원 배열 생성(True로 초기화)
• s1, s2에 대해 다른 한 쪽을 고려하지 않고 s3의 좌표와 일치하는지 초기값 입력
  • 초기값을 세팅하는 이유는 본격적인 탐색 시 [i - 1][j] or [i][j - 1]좌표에 대해 탐색을 진행하는데 0좌표 기준으로 초기 값이 설정되지 않으면 유효하지 않은 조건임에도 True로 인지하기 때문이다. 마찬가지로 False로 초기화를 하더라도 유효한 조건임에도 False로 인지할 수 있기 때문에 어느쪽이건 초기화를 해야 한다.
• 이중 for문을 수행하되 [i][j]좌표의 값 입력은 [i - 1][j]가 유효하고 s1[i - 1] == s3[i - 1 + j]를 만족하거나 [i][j - 1]이 유효하고 s2[j - 1] == s3[i - 1 + j]를 만족해야 True로 간주한다. 그게 아니라면 False로 간주
• [s1길이][s2길이]좌표값의 결과를 리턴한다.

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        s1Len, s2Len, s3Len = len(s1), len(s2), len(s3)
        if s1Len + s2Len != s3Len:
            return False
        dp = [[True for _ in range(s2Len + 1)] for _ in range(s1Len = 1)]
        for i in range(1, s1Len + 1):
            dp[i][0] = dp[i - 1][0] and s1[i - 1] == s3[i - 1]
        for i in range(1, s2Len + 1):
            dp[0][i] = dp[0][i - 1] and s2[i - 1] == s3[i - 1]
        for i in range(1, s1Len + 1):
            for j in range(1, s2Len + 1):
                dp[i][j] = (dp[i - 1][j] and s1[i - 1] == s3[i - 1 + j]) or \
                (dp[i][j - 1] and s2[j - 1] == s3[i - 1 + j])
        return dp[s1Len][s2Len]

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

LeetCode #1143 Longest Common Subsequence

문제 풀이

text1, text2로 두 개의 스트링이 주어진다. 이 스트링들이 서로 갖는 최대의 substring 길이를 리턴하면 된다. 전형적인 dp문제로 꽤 좋은 문제라 생각한다.

• 좌표 기준으로 이전까지의 substring 최댓값을 관리해야 함
• [text1의 길이 + 1][text2의 길이 + 1]만큼의 2차원 배열 생성
  • 탐색 좌표 기준 이전 좌표값까지의 substring 길이를 참조해야 하므로 1좌표부터 입력
• 이중 for문으로 탐색, 1부터 text1까지, 1부터 text2까지 탐색
• dp배열 [i][j]는 i - 1번째 좌표와 j - 1번째 좌표의 탐색 결과를 담는다고 간주
• text1[i - 1] == text2[j - 1]이면 substring 길이가 1 증가했다는 의미로 dp[i - 1][j - 1] + 1을 입력
• 만약 같지 않다면 1을 더할 여지가 없으므로 max(dp[i - 1][j], dp[i][j - 1])을 입력

python 코드 - 1

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        text1Len, text2Len = len(text1), len(text2)
        dp = [[0 for _ in range(text2Len + 1)] for _ in range(text1Len + 1)]
        for i in range(1, text1Len + 1):
            for j in range(1, text2Len + 1):
                if text1Len[i - 1] == text2Len[j - 1]:
                    dp[i][j] = 1 + dp[i - 1][j - 1]
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        return dp[text1Len][text2Len]

python 코드 - 2 (공간복잡도 개선)

어차피 좌표기준으로 탐색하고 1부터 끝까지 진행한다는 점에서 누적합의 개념을 생각해볼 수 있다. 그렇다면 text1, text2 중 하나는 차원을 2로 줄여서 홀-짝으로 구분해볼 수 있겠다.

만약 text1 탐색 매개변수 i에 대해 짝수라고 가정하자.

• 검사하는 좌표의 글자가 같고 i가 짝수라면 [홀수][j - 1]의 값에서 + 1 한 결과를 입력
• 글자가 같지 않다면 max([짝수][j - 1], [홀수][j])를 입력

결국 리턴해야 하는 값은 [text1Len % 2][text2Len]이므로 리턴될 좌표에 최종 탐색값이 입력되게끔만 보장해주면 된다.

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        text1Len, text2Len = len(text1), len(text2)
        dp = [[0 for _ in range(text2Len + 1)] for _ in range(2)]
        for i in range(1, text1Len):
            for j in range(1, text2Len):
                if text1[i - 1] == text2[j - 1]:
                    dp[i % 2][j] = 1 + dp[1 - i % 2][j - 1]
                else:
                    dp[i % 2][j] = max(dp[1 - i % 2][j], dp[i % 2][j - 1])
        return dp[text1Len % 2][text2Len]