[학습일기] HTTP 서비스 인증/인가 관련 이해한 내용 정리

들어가며인증과 인가와 관련해서 공부를 할 때 원리가 이해가 안 되어서 로그인과 CSRF와 같은 개념을 그냥 예시를 통해서 귀납적으로 학습하는 데에 그쳤다. 당연히 뭔가 답답한 느낌이 들었고 CSRF의 경우 외우고 까먹고를 반복했다.그러다가 최근에 갑자기 이 내용이 이해가 되었다. 방금 깨달은 사람의 따끈따끈한 이해를 말아드리고 싶어서 이 블로그글을 작성하게 되었다. (이랬는데 알고 보니 틀린 이해일 수도 있습니다ㅠㅠ 혹시 틀린 부분을 발견하시면 댓글 달아주시면 감사합니다!!)이해한 부분네트워크 서비스의 인증 및 인가와 관련해서 이해하는 데 개인적으로 다음 활동이 굉장히 도움이 많이 되었다.특정 사용자를 인증하기 위한 필요충분조건을 논리식으로 작성하기특정 서비스의 사용을 인가하기 위한 필요충분조건을 논리식으로 작성하기 이 관점에서 인증 및 인가를 다음과 같이 정리하게 되었다.인증(Authentication, Authn)정의위키피디아에서 찾아본 인증의 정의는 다음과 같다.특정 사용자의 본인확인을 증명하는 과정. 다시 말해, 특정 사용자가 본인이라고 주장하는 사람이 맞는지 확인하는 과정인증이라는 개념이 왜 필요하게 되었는지를 웹 서버의 입장이 되어 생각해보자.일반적인 웹 서비스에서 사용하는 웹 서버의 경우 대부분의 ip로부터 요청을 받을 수 있다. 비유하자면 불특정 다수로부터 쪽지를 받는 것과 같다. 다음 쪽지를 받았다고 가정해보자.안녕하세요, 미스터 비스트 유튜브 팀에서 연락드렸습니다.저희가 이번에 만들고 있는 영상에 초대드리고 싶습니다.아래의 주소에 접근해서 설명을 따라 주시면, 다음 영상에 출연하실 수 있습니다.https://example.com?phishing=true문제가 한두개가 아니다. 일단 미스터 비스트가 내게로 연락을 보낼 리가 없고, 글솜씨가 허접하다. (글쓴이의 글쓰기 스킬 이슈입니다.) 하지만 웹서버 입장에서 중요한 문제는 따로 있다. 본인이 알고 있는 주소에서만 접근하는 것도 아니고 불특정 다수의 ip 주소로부터 HTTP 요청을 받기 때문에 요청을 보낸 것이 실제 미스터 비스트인지 미스터 비스트인 척 하는 김 아무개씨인지를 확인할 방법이 없다. 다시 말해 웹 서비스에 가입한 특정 사용자 A가 있을 때, 본인이 사용자 A라고 주장하는 요청이 실제 사용자 A가 보낸 것인지 아닌지 확인하는 과정이 필요하다. 이런 맥락에서 인증이라는 개념이 자연스럽게 필요해진 것 같다.간단한 웹 서비스에서의 사용자 인증비밀번호를 통한 인증소개 및 필요충분조건웹 서비스를 누군가는 처음 만들었을 것이다. 만들면서 인증에 대한 문제를 다음과 같이 풀 생각을 하지 않았을까? (즉, 뇌피셜입니다.)인증의 문제를 다음과 같이 해결하면 어떨까?하나, 사용자 A가 가입하는 시점에 A와 웹 서비스 둘이서만 아는 비밀번호를 공유한다.둘, 앞으로 HTTP 요청을 보낼 때 본인이 A라고 주장하며 동일한 비밀번호를 제시하면, 그 사람은 A라고 유추할 수 있다.현재까지의 사고 과정을 필요충분조건으로 정리하면 다음과 같다.(사용자 A 인증) (HTTP 요청 시 A의 비밀번호가 제시됨)문제점위의 인증 방식은 조금만 생각해보면 사용성 또는 보안에서 엄청난 문제점이 있는 것을 확인할 수 있다. 웹사이트에 요청을 보낼 때마다 비밀번호를 제시해야 하기 때문이다. 사용자가 본인 페이지 내에서 이동할 때마다 비밀번호를 입력하게 하자니 사용성에서 하자가 있다. 또한 매 요청마다 평문으로 비밀번호가 전송되기 때문에 요청 중 하나라도 감청당한다면 비밀번호가 그대로 노출되게 된다.비밀번호 및 세션 토큰을 통한 인증소개사용자가 웹 서비스를 사용할 때 특정 시각부터 특정 시각까지 대화가 오가는 패턴이 자주 등장한다. 대화에서와 마찬가지로 이 대화 내의 나중의 요청은 이전의 요청들에 의해 쌓인 맥락을 가지고 있다. 이렇게 특정 시간 범위 동안 존재하는 고수준 양방향 연결을 세션이라고 한다. 보통 세션은 이전 요청들에서 쌓인 맥락을 가지고 있기에 stateful하다.이렇게 웹 서비스에서 흔하게 존재하는 세션이라는 개념을 활용하면 "매 요청마다 비밀번호가 평문으로 전송된다"는 문제를 다음과 같이 해결할 수 있다.이미 사용자 A에 대한 세션이 있는 경우 A의 세션에 대한 접근 권한을 A의 비밀번호 대신 사용할 수 있다.이 경우 연결이 감청당한 경우에도 세션 접근 권한 정보는 세션이 존재하는 동안만 유효하기 때문에 비밀번호가 유출되는 확률을 낮출 수 있다. (추가: 그러나 세션이 탈취당한 상황에서 이게 얼마나 의미가 있는지는 모르겠습니다.)따라서 매번 비밀번호를 입력받는 과정을 다음의 세 단계 과정으로 대체할 수 있다.하나, 사용자 A에 대한 아이디와 비밀번호를 받아서 서버에서 세션 저장소에 A를 위한 세션의 정보를 저장하고, 세션 정보에 접근할 수 있는 권한을 응답에 반환한다. 이를 보통 "로그인"이라고 칭한다.둘, 로그인 상태에서는 세션 접근 권한을 비밀번호 대신 인증 수단으로 사용한다.셋, 특정 시간이 지나거나 사용자가 직접 요청하는 경우 세션 정보를 파기한다. 이를 "로그아웃"이라고 칭한다.토큰 소개오해를 방지하기 위해 토큰에 대해서 짚고 넘어가보자. 위키피디아에 의하면 토큰의 정의는 다음과 같다.특정 작업에 대한 권한을 표현하는 소프트웨어 혹은 하드웨어 객체따라서 꼭 JWT의 형식이 아니더라도 세션 접근에 대한 권한을 표현하는 데이터를 모두 "세션 토큰"이라고 칭할 수 있는 것으로 보인다. (혹시 아니라면 알려주시면 감사드립니다!)필요충분조건위에서 정리한 내용을 필요충분조건으로 정리하면 다음과 같다.(사용자 A 인증) (A 비밀번호 제시) OR (현재 존재하는 A의 세션에 대한 토큰 제시)여기서 인상적인 점이 토큰이라는 개념은 바로 뒤에 다룰 내용인 인가에 대한 내용이지만, 인증 정책의 일환으로 A의 세션에 대한 권한이 있는 사용자를 A에 대한 인증의 충분조건으로 사용했기에 여기에 등장했다는 사실이다.정리여기까지 인증에 대한 내용을 간단하게나마 살펴보았다. 인증으로 접근 권한도 퉁쳐서 나타내면 안 되는 걸까? 여기서는 CSRF의 사례를 들어 둘을 분리해야 하는 이유 중 하나를 살펴보겠다.인가정의위키피디아에서는 다음과 같이 서술하고 있다.리소스에 접근할 수 있는 권한을 명시하는 것인증과 구별해야 하는 이유여기서 "A로 인증했으면 A가 권한이 있는 작업들을 모두 허용해도 되는 것 아닌가?"라는 의문이 당연하게 들 수 있다. 이 둘을 일치시켰을 때 발생할 수 있는 문제 중 하나로 CSRF 공격을 예로 들어보겠다.CSRFCSRF는 Cross-Site Request Forgery의 약자로, "사이트 간 요청 위조"를 뜻한다. 쉽게 말해 S1 사이트에서 사용자 A에게 본인의 의사와는 무관하게 S2 사이트로 특정 요청을 보내도록 시키는 공격이다. 예를 들어 S1이 해커 사이트이고, S2가 은행 사이트이고, S2가 CSRF에 대한 보호가 안 되어 있는 경우, S1 사이트에서 HTML Form과 자바스크립트를 통해 S1에 접속한 사용자 A로 하여금 해커에게 송금을 하라는 요청을 S2에 보내도록 시킬 수 있다. 자세한 정보는 MDN에서 잘 설명되어 있다.CSRF가 발생할 수 있는 이유는 사용자가 브라우저에서 S1 사이트를 방문했을 때 S2 사이트에 대신 요청을 보내도록 하는 것이 너무 쉽게 가능하기 때문이다. Form 태그의 action attribute를 활용하면 사용자로 하여금 다른 사이트에 요청을 보내도록 할 수 있고, 이 때 cookie에 저장된 인증 정보가 같이 전송되기 때문에 문제가 된다.CSRF 발생 원인 분석 및 해결사이트 S2 입장에서 다음과 같은 정책을 생각할 수 있다.(사용자 A의 송금 서비스 접근 권한) (사용자 A의 인증 정보)이렇게 할 경우 문제가 안 생기는 맥락이 어디엔가 있을지도 모르지만, 안타깝게도 웹 서비스 환경에서는 위에서 기술한 이유로 인해서 요청한 사용자가 정상적으로 웹 서비스를 사용해서 나온 요청인지, CSRF 공격의 피해를 당해서 발생하는 요청인지 구분할 수 없다.이에 대응해서 정상적으로 웹 서비스를 사용하는 사람에게만 발급해주는 토큰을 사용해서 해결할 수 있다. 구체적으로 HTML Form으로 웹 서비스를 제공하는 경우, Form의 hidden field에다가 매번 바뀌는 랜덤 문자열 토큰을 삽입해주고, Form을 제출했을 때 이 토큰을 확인함으로써 해결할 수 있다. 이 경우 토큰은 사이트 외부에서 접근 가능한 정보가 아니지만 요청에 꼭 필요한 정보이기 때문에, CSRF로 요청을 위조하는 것이 불가능하게 된다.이를 논리식으로 나타내면 다음과 같다.(사용자 A의 송금 서비스 접근 권한) (사용자 A의 인증 정보) AND (CSRF 방지 토큰 소유)정리하며생각보다 시간이 많이 걸렸습니다. 잘 이해했는지 모르겠네요...

[인프런 클론 6주 완성 챌린지] 선택 및 집중 과정에서 포기해야 하는 것들에 대한 고민

지난주는 nextjs에 익숙해지는 데 많은 시간을 할애했다.주어진 속도로는 시간을 최대한으로 투자해도 진도를 정해진 일정대로 따라가는 것은 무리라고 판단하였다. 그래서 어차피 챌린지 일정이 밀릴거라면, 1-2주차처럼 무리해서 시간을 배분하지 말고 챌린지 외 일정들을 챙기면서 진도를 천천히 따라가자는 계산을 했다.사실 지난주와 지금을 비교해봤을 때 실력적으로 큰 차이가 있지는 않지만 비슷한 패턴을 여러 번 반복해서 보다 보니 심적으로 익숙해지게 되었다. 그래서 다시 챌린지로 돌아와 프런트엔드 코드를 작성할 때 (할 일 계획) + (nextjs 코드 작성 및 이해)의 두 가지 변수 중에 후자가 해결되어 cursor에게 어떻게 일을 시킬지에 집중할 수 있게 되었고, 문제였던 불안도 어느 정도 해결되었다.각설하고 이제 급한 문제를 해결하고 보니 절대적인 시간이 부족하게 되어, 챌린지 기간 동안 어떤 부분을 챙기고 어떤 부분을 포기할지를 고민해야 하는 상황이다. 사실 이 생각을 하게 된 구체적인 이유가 있다.인프런의 지식공유자 강의 수정 화면은 다음과 같이 구성되어 있다.페이지상단 헤더: 현재 수정중인 강의 제목, 저장 및 제출 버튼 등메인 영역사이드바: 수정 과정의 모든 단계들 및 현재 단계 표시 강의 수정 영역: 강의 수정 정보 입력 폼반면 챌린지의 화면은 다음과 같이 구성되어 있다.페이지 사이드바메인 영역상단 헤더강의 수정 영역개인적으로 느끼기에 챌린지의 화면 구성이 훨씬 고민거리가 적기 때문에 챌린지 설계 과정에서 훌륭한 트레이드오프가 들어간 게 아닌가 생각하고 있다. (아닌가요...? 죄송합니다ㅠㅠ)이 파트를 구현하면서 챌린지 화면 구성에서 끝내도 되는 줄 모르고 이를 인프런 화면 구성으로 리팩터링을 시도하느라 하루를 보냈다. (결국 오늘 더 시간 쓰고 싶지 않아서 revert했습니다.) 이와 관련해서 글의 주제와는 관련 없는 몇 가지 흥미로운 생각이 들었는데 [여담]에서 따로 기술하였다.이 문제를 해결하면서 한 고민들은 nextjs를 이해하는 데 도움은 되었지만, 챌린지의 맥락에서 봤을 때 너무 지엽적인 내용인 것 같았다. 그래서 오늘 챌린지 전체 과정을 한 번 훑어보면서 내가 어떤 부분을 취하고 어떤 부분을 버려야 할지 다시 한 번 생각하게 되었다.개인적으로 챌린지를 하면서 가져가고 싶은 부분은 다음과 같다.백엔드 실 서비스 개발의 전체 흐름을 직접 경험해보기 (상세한 디테일은 챌린지 목차에서 확인 가능)이를 위해서 nextjs에 대한 이해는, 챌린지 코드의 큰 구조 및 데이터 흐름 및 AI 생성 코드를 이해할 수 있는 만큼만 가져가기로 결정했다. 그리고 "인프런 화면 구성 구현하기"는 이 관점에서 살펴봤을 때 욕심이라는 생각이 들었다.이상입니다. 읽어주셔서 감사드립니다.[여담] 여담이지만 위 현상을 경험하면서 몇 가지 생각이 들었다.스스로 무언가를 해보면서 발생하는 문제 상황을 해결할 때 배우는 게 많다. (주관적인 생각입니다.)AI가 이 과정을 방해한다고 생각했는데, 방금 배운 것을 돌아보니 AI를 활용한다고 해도 이 과정이 바뀌지는 않는구나 싶은 생각이 들었다.나는 AI가 작성하는 코드를 이해하고 싶은 마음이 크다. 혹시 관련이 있을지도?Context 왜 쓰는지 백날 고민해봤는데 한 번 리팩터링하면서 와닿는 게 더 많았다. 역시 직접경험이 짱인 것 같다.UI가 응집되는 방향성과 데이터/함수/메소드가 응집되는 방향성이 달라서 발생하는 문제를 해결한다고 생각했었고 이번 리팩터링에서 이를 실감했다. 개인적으로는 현재 리액트 주류 스택이나 MobX 활용 스택이나 주인공을 컴포넌트로 둘 것인지 객체로 둘 것인지의 관점의 차이만 있지 둘 다 이 문제를 훌륭하게 해결한다고 느꼈다. (물론 저는 말하는 감자입니다. 감자가 느낀 것을 그대로 믿으시면 안됩니다.)내가 초기 스타트업에서 일을 하는 상황이었다면 챌린지 화면처럼 구현하자고 기획자와 승부를 봐서 타협을 했을 것 같다.나는 AI가 작성한 코드를 더 쉽게 이해하고 싶어서 스타일링 최소화한 ui 코드 만들기 / 스타일링하기의 2단계로 쪼개서 일을 시키는 것을 좋아한다.또 리팩터링을 설계하고 AI 생성 코드를 이해하는 과정에서 다음과 같은 고민들을 했거나 진행중이다. 내가 생각하기에 괜찮은 고민인 것 같다.nextjs에서 서버 컴포넌트로 ViewModel A에 대한 초기 json 데이터를 얻고, 클라이언트 컴포넌트에서 A를 업데이트하는 패턴이 보이는데, 이 패턴을 공통으로 묶을 수 없을까? (고민중)인프런 화면 구성을 구현하려면 Layout 컴포넌트를 어떻게 설계해야 할까? (마음에 드는 솔루션 하나 확인)

[인프런 클론 6주 완성 챌린지] 배우기와 익히기의 밸런스

개인적으로 이번 챌린지를 신청하는 데 많은 용기가 필요했다.하나는 타인의 문제 해결을 클론코딩하면서 내가 문제를 해결하는 문제해결력이 떨어지는 것이 아닌가 걱정했기 때문이고,다른 하나는 내 자신의 문제해결력에 하자가 있다는 것을 인정해야 했기 때문이다. (주의: 개인적인 맥락 하에서만 맞는 얘기입니다. 일반적으로 클론코딩 수업을 듣는다고 문제해결력에 하자가 있다고는 생각하지 않습니다.)이번 챌린지를 신청했을 때 했던 생각은 약간 자포자기하는 심정으로 '내 문제해결력이 떨어지는 리스크를 감수해서라도 나는 백엔드 개발을 한 바퀴를 돌려봐서 흐름을 파악해야겠다'였다. 또 '지금 못해도 배워서 잘 하면 되지'라는 말로 못하는 내 자신을 용서하는 과정도 필요했다.뚜껑을 열어보니 예상외로 챌린지에 참여하기를 정말 잘한 것 같다는 생각이 들었다. 일단 지금까지는 그렇다. 모방하고 이를 돌아보는 과정에서 내 문제 해결의 어떤 부분에서 하자가 있는지를 파악할 수 있었기 때문이다.실마리는 불안한 상태에서도 퍼포먼스를 내는 방법을 고민하면서 찾아왔다. 문득 '불안한 상태에서도 손이 자동적으로 나가도록 무지성 연습을 하면 불안할 때도 내 실행 능력의 저점은 보장되지 않을까?'라는 생각이 들었다. 그래서 nestjs 첫 프로젝트 수업을 2회, 컨트롤러는 3회 반복해서 구현했다. 반복하면서 다음 생각이 들었다.내가 불안감을 느끼면서 막혔던 이유는 동시에 문제 2-3개를 해결해야 해서 압도당했기 때문이다.예를 들면 nestjs controller 구현 + 클론 코딩 과정에서 현재 단계에 대한 이해작업이 어려워서가 아니라 코드가 손에 안 익어서 막힌다.간단한 게시글에 대한 crud 작업 연습에서 사실 "이해"가 필요한 부분은 거의 없다. 반복하면서 막혔던 이유는 전부 nest가 손에 안 익어서였다.그러면서 이런 생각이 들었다.모든 학습 과정은 배우기('학')와 익히기('습')가 동반된다. 프로그래밍의 경우 과목 특성인지 배움 없이 익히기에 치중한 학습자들이 많아서인지는 모르겠지만 이 중 정확한 이해를 통한 배우기가 특히 강조된다고 개인적으로 느꼈다.배우기와 익히기의 비중은 프로그래밍의 하위 분야에 따라 많이 다른 것 같다. 알고리즘 학습의 경우 (PS만큼 어렵지는 않은 맥락에서는) 배우기를 잘 하면 익히기는 상대적으로 수월하게 되는 것 같고, 웹 개발의 경우 배우기와 익히기 둘 다 의식적인 노력이 필요한 것 같다.나는 지금까지 내가 알고리즘은 못하더라도 "뭔가 잘 맞고" 웹 개발은 "뭔가 잘 안 맞는다"고 생각했는데, 적성의 문제가 아니라 학습 방법의 문제인 것 같다는 생각이 들었다.이제 앞으로 할 일은 막힐 때 어떤 부분으로 인해 병목이 생기는지를 파악해서 그 부분의 문제를 하나씩 해결하면 되지 않을까 싶다.

[인프런 클론 6주 완성 챌린지] 오늘을 기억하고 싶다.

오늘은 처음으로 불안에 직면했을 때 긍정적인 피드백을 받은 날이다.처음 노트북을 꺼내들었을 때는 불안에 떨고 있었는데, 중간에 tailwind 스타일링 할 때 따라해보면서 변주를 주는 과정에서 몰입이 되었고, 시간 가는 줄 모르고 강의 끝까지 따라치게 되었다. 강의가 끝났을 때의 성취감, 효능감이 장난이 아니었다.물론 객관적으로는 한 것은 정말 아무것도 없다. 강의에서의 로그인 플로우를 따라 친 것이 전부이다. 그리고 냉정하게 돌아본다면 내가 몰입할 수 있는 일의 난이도는 tailwind 스타일링 및 강의를 그대로 따라치는 수준에 불과하다.하지만 오늘은 그런 것보다도 일주일동안 불안한 상태로 애쓴 내 자신에게 고생했다는 말을 해주고 싶다.그리고 미래에는 조금씩 더 어려운 일들에도 직면할 수 있을지도 모르니 희망을 잃지 말자는 생각이 들었다.이 순간을 기억하기 위해 조금만 쉬었다 다음 강의로 넘어가야겠다.

[인프런 클론 6주 완성 챌린지] 불안으로 인한 미루기 및 해결 시도

불안이 또 찾아왔다.개인적으로 데드라인에 대한 불안으로 일을 그르친 것이 한두번이 아니었다. 고질병이었던 불안으로 인해 나는 일을 미루는 습관을 가지고 있었고 간단한 일조차도 너무 크게 느껴졌다.(글을 잘 쓰려고 하지 말자. 사실은 지금도 불안하다.)나는 분명 저번에 불안한 일들에 내 자신을 노출시키면서 어느 정도 해결되었다고 생각했는데 웬걸, 이번 주에 챌린지 1주차 과제 마감 때문에 또다시 불안이 찾아왔고 3일 동안 벌벌 떨며 기본 세팅을 미루었다.그러다 어떤 글을 봤는데 나와 비슷하게 불안을 느끼는 사람의 글이었다. 본인이 불안할 때 아무 생각 없이 딱 할 수 있는 부분을 시작한다고 한다.이 글을 보고 목표를 바꿨다. 원래는 챌린지를 통해서 백엔드 프로젝트를 기획하고 기능 구현하고 배포하는 것과 관련된 문제 해결 능력을 기르려고 했는데, 다 필요없고 일단 챌린지를 따라치되 일부 디테일에서 변주를 주는 것을 목표로 하고 있다. 예를 들어 원래는 Configuration을 config server를 따로 구성하면서 삽질해보고 싶었는데, 아니 지금도 그렇게 해보고 싶은데 다 포기하고 강의에 나온 .env 파일로 해결하려고 한다. 변주를 주고 싶은 부분의 예는 db 스키마에서 pk이다. 아무리 불안핑이어도 uuid pk는 쉽지 않기 때문에, 아니 실은 bigint pk, uuid pk를 둘 다 잘 몰라서 bigint row_id (pk) + uuid entity_id (index) 조합으로 실험해보고 싶고 이 정도는 해도 될 것 같아서 이 정도의 변주만 주려고 한다.아래 글은 다른 글인데 나중에 읽으려고 추가합니다. 공감되는 부분도 많고 나중에 시도해볼 부분도 많은 것 같습니다.https://brunch.co.kr/magazine/discipline

[수학로그] 그룹 액션, 실로우 정리 WIP

개인적으로 수학 공부를 하고 있었는데 이걸 기록으로 남겨도 누군가에겐 쓸모가 있겠다는 생각이 들었다.(설명을 위한 글이 아니라 뭐라도 남기는 것이라 설명이 깔끔하지 못한 점 양해 부탁드립니다.)An infinitely large napkin이라는 책을 예전에 한 번 읽어본 적이 있는데, 그 때는 실로우 정리를 그냥 확인만 하고 넘어갔다.며칠 전에 문득 그룹 액션이 궁금해져서 이 부분만 확인하는 과정에서 실로우의 정리의 앞부분까지 보게 되었다.실로우 정리 중반부에서 "여기서 미친 발상이 나옵니다!" 이러는데 내가 미쳐버릴 것 같아서 책을 덮었다. 그룹 액션(G, X) -> X의 타입을 가지는 함수를 정했지만 G -> (X -> X)로 해석해도 좋은 것 같다.상황에 따라 유리한 관점으로 해석하면 좋을 것 같다.그룹 액션의 정의만 만족한다면 X에 아무거나 들어갈 수 있어서 첫인상보다 범용성이 넓다는 느낌을 받았다. 실로우 정리 앞부분에 그룹 액션 적용하는 것 보면서 느낀 점이다G랑 X의 구조에 따라 그룹 액션의 의미도 달라지는 것 같은데 이걸 엄밀한 수식으로 표현할 줄 몰라서 아쉽다.Orbit-Stabilizer Theorem각 Orbit을 { Gx | x in X }의 원소로 생각하자.Orbit을 사용하면 G와 X를 연결지을 수 있다.각 Orbit과 동형사상을 이루는 G의 subgroup이 존재한다.뭔가 이상하다, 왜 kernel이 아니라 image가 subgroup인 거지? kernel이 normal한가? 검토가 필요하다. 앞부분 차근차근 복습해서 오개념을 확실히 잡아야겠다.Sylow 정리에서 X도 군인 경우에 그룹 액션을 적용해서 착각한 것 같다.각 Orbit은 X를 분할한다.그룹 액션을 a: G -> X -> X로 보고, X가 Orbit들 O_1, O_2, ... O_k로 분할된다고 가정하자.이 때 임의의 g: G에 대해 a(g): X -> X를 각각 O_1 -> O_1, O_2 -> O_2, ..., O_k -> O_k에 속하는 k개의 함수들의 순서쌍(= 곱집합의 원소)으로 나타낼 수 있다. Stabilizer얘는 G의 부분군이 맞다.임의의 Orbit의 임의의 두 원소 x, g*x에 대해서 Stab(g*x) = g Stab(x) g^(-1)이라는 사실이 이해에 도움이 많이 되었다.실로우 정리 증명에서 이 2가지를 가지고 주구장창 우려먹는 느낌을 받았다.Bernstein's Lemma처음 볼 때는 집합 { (g, x) | x = g * x }의 크기를 2가지의 서로 다른 방법으로 세는 방식으로 증명했었다.지금은 각 Orbit에 대해 |O| |S| / |G|를 합해서 Orbit의 갯수를 구했는데 더 직접적으로 증명하는 것 같아서 마음에 들었다.실로우 정리Napkin에 나온 증명은 Sylow p-group의 존재성 증명 -> p-group의 성질 밝히기 -> 실로우 정리 증명이었다.존재성 증명까지는 따라갔던 것 같은데 p-group의 성질은 따라가는 데 급급해서인지 지금은 까먹었고 실로우 정리 증명에서 책을 덮었다.모르는 부분은 나중에 다시 보면 된다.증명에서 새로운 개념을 많이 도입하는데 이 때 이 개념의 타입을 명시적으로 생각하는 게 이해에 도움이 많이 된다.

[학습일기] 디자인 패턴 관련 학습 정리 - 실습 관련

개요스프링 입문 강의의 예제 코드 강의를 보고 따라해보면서 모듈화를 하는 전략에 대해서 고민하고 어느 정도 정해진 루틴을 생각해보았습니다.기본적으로 이 정해진 루틴으로 초안을 작성하고 나서 상황에 맞는 리팩토링하는 방법으로 빠르게 설계 및 구현을 시도해볼 계획입니다. 루틴먼저 구현하고자 하는 기능을 책임으로 나눕니다.책임을 더 작은 책임들로 분할합니다.이 때 책임의 분할에 도움이 되는 전략으로는 다음을 사용하였습니다.책임을 수행하기 위해 필요한 정보에 따라서 분할하였습니다.예를 들면 어떤 정보는 객체를 생성할 때만 필요하고 사용할 때는 필요하지 않을 수 있습니다.이 이유로 저번 블로그 글에서 디자인 패턴을 관심사의 분리 측면에서 관찰하게 되었습니다.같은 맥락에서 사용되고 변하는 정보의 경우 맥락을 객체로 캡슐화하였습니다.다른 맥락에서 사용되는 정보의 경우, 다른 객체에서 정보를 제공할 수 있도록 책임을 분할하거나, 분할이 어려운 경우 고차함수를 이용해서 책임을 따로따로 주입할 수 있도록 하였습니다.지금 생각났는데 일단 구현하고 나서 리팩토링하는 것도 시도해볼 만한 전략인 것 같습니다.예시많이 많이 부끄럽습니다만 해당 커밋에 코멘트 형식으로 사고 과정을 달아놓았습니다.원래 공개할 계획이 없던 리포지토리다 보니 깔끔하지 못한 부분이 있습니다. 죄송합니다ㅠㅠ앞으로는 비공개 리포도 깔끔하게 정리해야겠습니다.

[학습일기] 디자인 패턴 관련 학습 정리 - 이론 관련

설계 시간 문제설계와 구현의 밸런스 중에서 설계에 치중해 있었던 것 같습니다.문제: 저는 설계할 때 생각과 고민이 너무 너무 많습니다.시도한 해결 방안오히려 설계를 열심히 파서 고민을 해결하고 제 나름대로의 설계 방법론이 생기면 빠르게 설계를 끝내고 구현으로 넘어갈 수 있지 않을까 생각했습니다."오브젝트" 책 보기"오브젝트"를 도서관에서 빌렸지만 훑어만 보고 깊게 읽어보지 못한 상태로 반납했습니다. 훑어보기밖에 하지 못했지만 고민을 해결해준 부분, 모르는 것을 알려준 부분, 생각만 하던 것을 확인해준 부분들을 많이 확인할 수 있었습니다. 책임을 어떻게 배분해야 할지에 대해서 고민거리를 던져주었습니다. 취업 시 구매 목록 1순위에 있습니다. 소장하고 있다가 필요할 때마다 발췌독을 해야겠다고 생각했습니다.디자인 패턴들 확인refactoring.guru 사이트에 나온 디자인 패턴 중 몇 개를 관심사의 분리 측면에서 개인적으로 재해석해보았습니다.생성과 관련된 디자인 패턴: 객체의 생성 // 객체의 사용 분리, 객체의 생성을 심도있게 다루기객체의 생성과 객체의 사용은 대부분 필요로 하는 정보가 다릅니다. 따라서 객체의 생성과 사용을 분리해서 생각하는 것, 생성과 관련해서 구체적인 디자인 패턴이 나오는 것이 이상한 일이 아닙니다.객체의 생성: 객체의 구체적인 구현체의 클래스 및 생성자 파라미터 등등객체의 사용: 객체 자체의 인터페이스구체적인 패턴들은 필요할 때마다 간간이 보기행동과 관련된 디자인 패턴: 책임을 "누구"에게 할당해야 하는지와 관련이 큼 중재자: M*N 형태의 관계를 M*1 형태 + 1*N 형태로 분리중재자 패턴에 들어맞지는 않더라도 이런 식의 분리 전략이 유용한 경우를 생각할 수 있었습니다.커맨드, 옵서버: 책임의 "언제"와 "무엇"을 분리커맨드 패턴: 언제 무엇을 할지가 정적으로 미리 고정되어 있는 경우옵서버 패턴: 언제 무엇을 할지가 동적으로 추가되거나 제거될 수 있는 경우전략: 책임의 "무엇"과 "어떻게"를 분리반복자: 순회 + 전략 + 역 IoC전략: 순회할 때 각 원소를 가지고 어떻게 할 것인지에 대한 전략구현하면 Array.prototype.forEach와 같은 메소드가 됨역 IoC: 많은 언어에서 제어를 뺏어가는 forEach 메소드보다 제어를 클라이언트 코드에게 넘기는 Iterator가 범용성 측면에서 유리예: 두 Iterator를 번갈아가며 순회하는 Iterator 구현 비지터, 상태: M * N 형태의 관계에서 한쪽을 고정시키고 다른 쪽을 유연하게 설정하는 기법Expression Problem과 비슷하게 때로는 한 요소는 M가지 중 하나, 다른 요소는 N가지 중 하나에 의존해서 실제로 양쪽 요소가 모두 변할 때 구현체들의 종류는 MN가지이고 두 요소 모두에 대해서 깔끔하게 확장이 안 되는 경우가 존재합니다. 한쪽 축을 고정시켜 희생시키고 다른 쪽을 유연하게 만드는 기법입니다.비지터는 Sum Type으로 나타낼 수 있는 정보를 전달하는 맥락으로 사용됩니다. Sum Type의 각 항들이 고정되고, Sum Type을 사용하는 쪽이 변경에 용이합니다. DDD 책 보기아직 DDD에 대해서 깊게 공부할 시기는 아니라고 생각하지만, 왜 Controller, Service, Repository의 설계가 아닌 다른 설계는 없는지 고민하느라 시간을 많이 허비하고 있었고, 이를 해소하기 위해 DDD 책이 필요하다고 판단하였습니다. 당연하게도 책의 모든 부분을 깊게 이해하지 못했지만 다행히도 의문을 해소할 수 있었고 더이상의 시간 소모를 막을 수 있었습니다. 구체적으로 아래와 같은 의문들을 가졌습니다.(Entity의 생명주기가 request마다 새로 생성되는 개념적 모델을 가진 상태였습니다.) 'Entity에게 save 메소드를 부여하면 Repository의 도움 없이 Entity 객체가 자율적으로 저장될 수 있지 않을까?'보통 해결하고자 하는 도메인에서 Entity는 데이터베이스에 영속적으로 저장된 채로 request/response 한 주기보다 긴 생명주기를 가진다고 이해했습니다.'Domain Layer에서는 Entity를 인터페이스로 설계하고 Data Access Layer에서는 이 인터페이스의 구현체를 만들면 Domain에서 메시지만 주고받을테니 더 객체지향적인 설계가 가능하지 않을까?'이 의문을 해결해준 링크이자 DDD 책을 보게 된 원인입니다.다음의 4단 의문'HTTP 요청 데이터도 데이터이고, 관계형 데이터베이스에서 저장되는 것도 관계형 데이터이고, 반환하는 것도 HTTP 응답 데이터인데, 왜 중간에 객체를 꼭 거쳐야 할까?''관계형 데이터를 불러오는 수단으로 객체를 거치는 것이 아니라 객체를 저장하기 위해서 관계형 데이터베이스를 사용하나 보다.''왜 도메인을 나타내는데 객체를 사용했을까?''Entity를 나타내는데 객체가 효과적이어서 그렇지 않을까?'비고제가 스프링 강의를 듣기 직전에 데이터베이스 강의를 들어서 이 의문이 정말 오랫동안 남았습니다.책의 저자께서는 제가 기억하기로는 다음과 같은 취지의 말씀을 하셨습니다. "도메인에 따라 절차지향적 프로그래밍, 함수형 프로그래밍, 논리 프로그래밍이 더 잘 맞는 도메인도 있다. 하지만 객체지향은 도메인 모델링 시에 놀랍도록 유연해서 넓은 범위의 도메인에서 효과적이며 생태계도 발전해 있으니 객체지향 패러다임을 택하는 것은 기술적으로 추천할 만한 선택이다."효과열심히 생각해보고 구현하면서 루틴이 생기는 것 같기는 한데, 루틴과 그 결과가 괜찮은지 잘 모르겠습니다. 다음 블로그 글은 실습 관련으로 올리겠습니다. 괜찮았으면...!

ostep / 가상화 / CPU / MLFQ (한글판 11장, 영문판 8장)

들어가며이번 장에서는 멀티 레벨 피드백 큐(MLFQ, Multi-Level Feedback Queue)에 대해서 다룹니다.이전 장에서 다룬 내용 중 이번 장에서 가장 중요한 내용 2가지를 꼽자면 다음과 같습니다.반환 시간을 최적화하기 위해서는 짧은 작업을 먼저 실행시켜야 한다. 평균적으로 대기하는 작업 수를 최소화해야 해서 그렇습니다.연관 개념: SJF, STCF 알고리즘응답 시간이 짧아지면 짧아질수록 반환 시간이 길어진다. 평균적으로 대기하는 작업 수가 늘어나서 그렇습니다.연관 개념: 라운드 로빈 알고리즘, 타임 슬라이스MLFQ 알고리즘은 이전 장에서 다루었던 가정 중 마지막 가정인 "작업의 시간이 사전에 알려져 있다"마저 없앤 현실적인 가정 하에 동작합니다. 현대 운영체제에서 적용하는 알고리즘의 뼈대가 됩니다.Ostep에서 이 장을 진행하는 구성은 다음과 같습니다.먼저 특정 시각에 MLFQ가 어떻게 동작하는지를 먼저 기술합니다. (Multi, Level, Queue)그리고 시간에 따라 피드백을 받으며 조정하는 부분을 기술합니다. (Feedback)개요MLFQ 알고리즘이 달성하고자 하는 목표는 다음과 같습니다.사용자가 실시간으로 기다리는 대화형 작업의 경우 응답 시간을 최소화이외의 작업의 경우 반환 시간을 최소화이를 어렵게 하는 난관은 다음과 같습니다. 사용자 작업의 소요 시간 및 특성을 사전에 알 수 없습니다.응답 시간을 최적화할 경우 반환 시간이 안 좋아지는 트레이드오프가 있습니다.이를 해결하기 위한 전략은 다음과 같습니다.작업이 지금까지 보여준 과거를 통해서 미래를 예측한다.기본적인 모델먼저 MLFQ가 특정 시각에 어떻게 동작하는지 살펴보겠습니다.먼저 MLFQ의 M, L, Q에 해당되는 부분입니다.Queue: 작업은 큐에서 대기합니다.Multi: 그런데 큐를 여러 개를 둡니다.Level: 그런데 그 여러 개의 큐들의 우선순위에 차등을 둡니다.우선 순위에 따른 동작은 다음과 같습니다. 규칙 1: 우선 순위가 높은 작업이 먼저 실행된다.규칙 2: 우선 순위가 같은 작업은 라운드 로빈 알고리즘으로 실행된다.이를 구현하기 위해서는 다음과 같습니다.우선 순위가 가장 높은 큐에 작업이 있으면, 라운드 로빈 알고리즘에 따라 다음 실행할 작업을 결정한다.우선 순위가 가장 높은 큐에 작업이 없으면, 다음 우선순위 큐로 넘어간다.우선 순위가 가장 낮은 큐까지 반복한다.시간에 따른 변화를 고려한 모델 (mk1)특정 시각으로 시간을 고정할 경우 작업마다 (과거에 실행된 것을 바탕으로) 우선 순위가 고정되어 있습니다. 하지만 특정 시각의 동작만 가지고는 초기에 정보가 없을 때 우선 순위를 어떻게 설정해야 하는지, 또 어떻게 변하는지에 대하는지 이해할 수 없습니다. 따라서 이 섹션에서는 시간에 따른 변화를 고려해보겠습니다. 일단 규칙부터 보여드리겠습니다.규칙 3: 모든 작업은 초기에는 가장 높은 우선순위로 실행된다.다시 말해 처음 생성된 작업은 우선순위가 가장 높은 큐에 대기시킵니다.규칙 4a: 주어진 타임 슬라이스를 모두 사용하면 우선순위를 한 단계 강등시킨다.즉, 우선 순위가 한 단계 낮은 큐에서 대기시킵니다.규칙 4b: 주어진 타임슬라이스를 모두 사용하지 않으면 우선순위를 유지시킨다.즉, 같은 큐에서 대기시킵니다.ostep에서 Q2 > Q1 > Q0인 3개의 큐를 둔 예시를 설명하고 있습니다. 책을 보시는 게 좋을 것 같아 여기서는 결론만 정리하겠습니다.실행 시간에 따른 분석긴 실행 시간을 가진 작업: Q2 -> Q1 -> Q0로 떨어져서 낮은 우선 순위로 실행짧은 실행시간을 가진 작업: Q2, Q1 등 높은 우선 순위에서 실행 후 완료짧은 실행 시간을 가진 작업을 더 높은 우선순위로 실행시켜 반환 시간을 최적화하는 것을 알 수 있습니다.입출력 작업: 주어진 타임 슬라이스가 끝나기 전에 입출력을 수행한다면 우선 순위 유지한다고 가정대화형 작업의 경우 타임 슬라이스가 종료되기 전에 입출력을 수행해 높은 우선 순위로 실행되어 응답 시간을 최적화할 수 있습니다.mk1의 문제점기아 상태(starvation)대화형 작업 여러 개가 존재한다면, 높은 우선순위의 큐만 실행하느라 낮은 우선순위 큐에 있는 CPU 위주 작업은 계속 실행되지 못하는 가능성이 있습니다.높은 우선순위를 유지하는 꼼수 존재CPU를 오래 사용하는 작업이더라도 타임 슬라이스가 끝나기 직전에 입출력을 수행한다면 높은 우선 순위를 유지할 수 있습니다.따라서 이 문제를 해결하기 위해서 타임 슬라이스 사용 여부의 boolean이 아닌, 타임 슬라이스의 얼마가 남아있는지를 저장해야 합니다.시간에 따른 작업의 특성 변화 고려 못함CPU 작업이 대화형 작업으로 변화할 수 있지만, mk1에서는 우선 순위가 내려간 작업은 다시 올라오지 않기 때문에 대화형 작업의 응답 시간이 길어질 가능성이 있습니다.시간에 따른 변화를 고려한 모델 (mk2)꼼수 문제를 해결하기 위해서 4번 규칙을 보완하겠습니다.규칙 4: 주어진 타임 슬라이스를 모두 사용하면 우선순위를 한 단계 강등시킨다. 단, CPU를 몇 번 양도하였는지와 상관없이 시간 할당량을 소진하는 것으로 강등 여부를 판단한다.즉, 남은 시간을 확인해서 0이라면 우선 순위가 한 단계 낮은 큐에서 대기시킵니다. 반면 0이 아니라면 같은 큐에서 대기시키되, 남은 시간을 저장하여 다음 실행 시에는 타임 슬라이스 시간이 아닌 남은 시간동안만 실행되도록 합니다.기아 상태 문제와 작업 특성 변화 문제를 해결하기 위해서 규칙을 하나 더 만들겠습니다.규칙 5: 일정 시간 S가 지나면 모든 작업을 최상위 큐로 이동시킨다. MLFQ의 조정과 다른 쟁점들MLFQ에는 정확하게 결정하기 위해서는 흑마법이 필요해 보이는 "부두 상수"들이 몇 가지 있습니다.큐의 개수큐 별 타임 슬라이스 길이우선 순위가 높으면 대개 타임 슬라이스가 짧습니다. 대화형 작업이 많기 때문입니다. (우선 순위가 낮으면 응답 시간보다는 반환 시간을 최적화하기 위해서 타임 슬라이스가 깁니다.ostep에서 다룬 것과 같이 정확한 규칙이 아닌, 수학 공식을 사용하여 우선순위를 조정하기도 합니다.또한 스케줄러는 다른 기능을 제공하기도 합니다. 사용자 작업에 대해서 우선순위를 정하게 해주는 nice와 같은 기능이 그 예입니다. 정리Ostep에서 다룬 MLFQ 알고리즘의 경우 다음 5가지 규칙으로 정리할 수 있습니다.규칙 1: 우선 순위가 높은 작업이 먼저 실행된다.규칙 2: 우선 순위가 같은 작업은 라운드 로빈 알고리즘으로 실행된다.규칙 3: 모든 작업은 초기에는 가장 높은 우선순위로 실행된다.규칙 4: 주어진 타임 슬라이스를 모두 사용하면 우선순위를 한 단계 강등시킨다. 단, CPU를 몇 번 양도하였는지와 상관없이 시간 할당량을 소진하는 것으로 강등 여부를 판단한다.규칙 5: 일정 시간 S가 지나면 모든 작업을 최상위 큐로 이동시킨다.그 결과로 MLFQ는 반환 시간과 응답 시간을 모두 최적화합니다. 짧게 실행되는 작업은 SJF/STCF처럼 처리해 전반적인 성능을 개선시키고, 오래 실행되는 CPU 작업의 경우 공정하게 실행되도록 기아 상태를 방지하고 조금이라도 진행되게 합니다. 이런 이유로 많은 운영체제에서 MLFQ를 기본 스케줄러로 사용하고 있습니다.출처강의: https://pages.cs.wisc.edu/~remzi/Classes/537/Fall2021/Discussion/videos.html책: https://pages.cs.wisc.edu/~remzi/OSTEP/Korean/

알고리즘 / self-balancing binary tree

red-black tree와 유사하지만 경우의 수가 더 적은 2-3 트리와 일대일 대응이 되는 self-balancing binary tree를 구현해보았다.red-black tree는 아주 아주 오래 걸릴 것 같아서 더 쉬운 버전을 구현한다고 했는데 하루 종일 걸렸다.red-black tree보다는 간단해서 순한 맛인데,트리 회전에 대해서 생각하지 않고 순수 함수를 이용한 순한 맛인데타입스크립트의 표현력 깊은 타입 시스템까지 활용해서 분명히 순한 맛인데어려웠다.고려할 경우의 수가 많았다.테스트도 제대로 못 해보았지만 구현한 것에 의미를 두고 잘 동작하길 기원만 하고 넘어가기로 했다. 부끄럽다. // Copyright 2024-2024 Dongook Lee // SPDX-License-Identifier: MIT // AA-like tree implementation with one tag bit per node // https://en.wikipedia.org/wiki/AA_tree type Tree = null | Node2 | Node3 // A tag value of true corresponds to black nodes in a red-black tree type Node2 = [tag: true, l: Tree, x: number, r: Tree] type Node3 = [tag: true, l: Tree, x: number, [tag: false, m: Tree, y: number, r: Tree]] function isNode2(tree: Tree): tree is Node2 { return tree !== null && (tree[3] === null || tree[3][0]) } const node2 = (l: Tree, x: number, r: Tree): Node2 => [true, l, x, r] const replaceLeft2 = ([, _l, x, r]: Node2, l2: Tree): Node2 => node2(l2, x, r) const replaceValue2 = ([, l, _x, r]: Node2, x2: number): Node2 => node2(l, x2, r) const replaceRight2 = ([, l, x, _r]: Node2, r2: Tree): Node2 => node2(l, x, r2) const node3 = (l: Tree, x: number, m: Tree, y: number, r: Tree): Node3 => [true, l, x, [false, m, y, r]] const replaceLeft3 = ([, _l, x, [, m, y, r]]: Node3, l2: Tree): Node3 => node3(l2, x, m, y, r) const replaceLeftValue3 = ([, l, _x, [, m, y, r]]: Node3, x2: number): Node3 => node3(l, x2, m, y, r) const replaceMiddle3 = ([, l, x, [, _m, y, r]]: Node3, m2: Tree): Node3 => node3(l, x, m2, y, r) const replaceRightValue3 = ([, l, x, [, m, _y, r]]: Node3, y2: number): Node3 => node3(l, x, m, y2, r) const replaceRight3 = ([, l, x, [, m, y, _r]]: Node3, r2: Tree): Node3 => node3(l, x, m, y, r2) // Insert const upgradeLeft2 = ([, _l, x, r]: Node2, [, ll, y, lr]: Node2): Node3 => node3(ll, y, lr, x, r) const upgradeRight2 = ([, l, x, _r]: Node2, [, rl, y, rr]: Node2): Node3 => node3(l, x, rl, y, rr) function upgradeLeft3([, _l, x, [, m, y, r]]: Node3, [, ll, z, lr]: Node2): Node2 { return node2(node2(ll, z, lr), x, node2(m, y, r)) } function upgradeMiddle3([, l, x, [, _m, y, r]]: Node3, [, ml, z, mr]: Node2): Node2 { return node2(node2(l, x, ml), z, node2(mr, y, r)) } function upgradeRight3([, l, x, [, m, y, _r]]: Node3, [, rl, z, rr]: Node2): Node2 { return node2(node2(l, x, m), y, node2(rl, z, rr)) } type InsertionResult = | [upgraded: false, newNode: Tree] | [upgraded: true, newNode: Node2] function insert(tree: Tree, v: number): InsertionResult { if (tree === null) { return [true, node2(null, v, null)] } if (isNode2(tree)) { const [, l, x, r] = tree if (v >= x) { const [up, r2] = insert(r, v) return up ? [false, upgradeRight2(tree, r2)] : [false, replaceRight2(tree, r2)] } const [up, l2] = insert(l, v) return up ? [false, upgradeLeft2(tree, l2)] : [false, replaceLeft2(tree, l2)] } // Node3 const [, l, x, [, m, y, r]] = tree if (v >= y) { const [up, r2] = insert(r, v) return up ? [true, upgradeRight3(tree, r2)] : [false, replaceRight3(tree, r2)] } if (v >= x) { const [up, m2] = insert(m, v) return up ? [true, upgradeMiddle3(tree, m2)] : [false, replaceMiddle3(tree, m2)] } const [up, l2] = insert(l, v) return up ? [true, upgradeLeft3(tree, l2)] : [false, replaceLeft3(tree, l2)] } type DeletionResult = | [downgraded: false, newNode: Tree] | [downgraded: true, newNode: Node3 | null] function downgradeLeft2([, _l, x, r]: Node2, l2: Node3 | null): DeletionResult { if (r === null) { throw new TypeError("expected non-null sibling, got null") } if (isNode2(r)) { const [, rl, y, rr] = r return [true, node3(l2, x, rl, y, rr)] } const [, rl, y, [, rm, z, rr]] = r return [false, node2(node2(l2, x, rl), y, node2(rm, z, rr))] } function downgradeRight2([, l, x, _r]: Node2, r2: Node3 | null): DeletionResult { if (l === null) { throw new TypeError("expected non-null sibling, got null") } if (isNode2(l)) { const [, ll, y, lr] = l return [true, node3(ll, y, lr, x, r2)] } const [, ll, y, [, lm, z, lr]] = l return [false, node2(node2(ll, y, lm), z, node2(lr, x, r2))] } function downgradeLeft3([, _l, x, [, m, y, r]]: Node3, l2: Node3 | null): DeletionResult { if (m === null) { throw new TypeError("expected non-null sibling, got null") } if (isNode2(m)) { const [, ml, z, mr] = m return [false, node2(node3(l2, x, ml, z, mr), y, r)] } const [, ml, z, [, mm, w, mr]] = m return [false, node3(node2(l2, x, ml), z, node2(mm, w, mr), y, r)] } function downgradeMiddle3([, l, x, [, _m, y, r]]: Node3, m2: Node3 | null): DeletionResult { if (r === null) { throw new TypeError("expected non-null sibling, got null") } if (isNode2(r)) { const [, rl, z, rr] = r return [false, node2(l, x, node3(m2, y, rl, z, rr))] } const [, rl, z, [, rm, w, rr]] = r return [false, node2(l, x, node2(node2(m2, y, rl), z, node2(rm, w, rr)))] } function downgradeRight3([, l, x, [, m, y, _r]]: Node3, r2: Node3 | null): DeletionResult { if (m === null) { throw new TypeError("expected non-null sibling, got null") } if (isNode2(m)) { const [, ml, z, mr] = m return [false, node2(l, x, node3(ml, z, mr, y, r2))] } const [, ml, z, [, mm, w, mr]] = m return [false, node2(l, x, node2(node2(ml, z, mm), w, node2(mr, y, r2)))] } function isLeafNode(node: Node2 | Node3): boolean { return node[1] === null } function popMinValue(tree: Tree): [number, DeletionResult] { if (tree === null) { throw new Error("expected non-empty tree, got null") } if (isLeafNode(tree)) { if (isNode2(tree)) { const [, _l, x, _r] = tree return [x, [true, null]] } const [, _l, x, [, _m, y, _r]] = tree return [x, [false, node2(null, y, null)]] } if (isNode2(tree)) { const [, l] = tree const [x2, [down, l2]] = popMinValue(l) return down ? [x2, downgradeLeft2(tree, l2)] : [x2, [false, replaceLeft2(tree, l2)]] } const [, l] = tree const [x2, [down, l2]] = popMinValue(l) return down ? [x2, downgradeLeft3(tree, l2)] : [x2, [false, replaceLeft3(tree, l2)]] } function remove(tree: Tree, v: number): DeletionResult { if (tree === null) { throw new Error("value not found") } if (isLeafNode(tree)) { if (isNode2(tree)) { const [, _l, x, _r] = tree if (v === x) { return [true, null] } throw new Error("value not found") } const [, _l, x, [, _m, y, _r]] = tree if (v === x) { return [false, node2(null, y, null)] } if (v === y) { return [false, node2(null, x, null)] } throw new Error("value not found") } if (isNode2(tree)) { const [, l, x, r] = tree if (v > x) { const [down, r2] = remove(r, v) return down ? downgradeRight2(tree, r2) : [false, replaceRight2(tree, r2)] } if (v === x) { const [x2, [down, r2]] = popMinValue(r) return down ? downgradeRight2(replaceValue2(tree, x2), r2) : [false, node2(l, x2, r2)] } const [down, l2] = remove(l, v) return down ? downgradeLeft2(tree, l2) : [false, replaceLeft2(tree, l2)] } const [, l, x, [, m, y, r]] = tree if (v > y) { const [down, r2] = remove(r, v) return down ? downgradeRight3(tree, r2) : [false, replaceRight3(tree, r2)] } if (v === y) { const [y2, [down, r2]] = popMinValue(r) return down ? downgradeRight3(replaceRightValue3(tree, y2), r2) : [false, node3(l, x, m, y2, r2)] } if (v > x) { const [down, m2] = remove(m, v) return down ? downgradeMiddle3(tree, m2) : [false, replaceMiddle3(tree, m2)] } if (v === x) { const [x2, [down, m2]] = popMinValue(m) return down ? downgradeMiddle3(replaceLeftValue3(tree, x2), m2) : [false, node3(l, x2, m2, y, r)] } const [down, l2] = remove(l, v) return down ? downgradeLeft3(tree, l2) : [false, replaceLeft3(tree, l2)] } export function toInserted(t: Tree, v: number): Tree { return insert(t, v)[1] } export function toRemoved(t: Tree, v: number): Tree { return remove(t, v)[1] }