Phoenix Up and Running

2월 13, 20232월 13, 2023 animato댓글 남기기

Phoenix 는 Elixir 를 위한 웹 개발 프레임워크이다. 피닉스 가이드 문서를 따라서 간단하게 피닉스 웹 서버를 띄운다.

설치

Elixir 설치

brew install elixir

다른 플랫폼의 경우 https://elixir-lang.org/install.html 참조

Hex 설치

Elixir 설치가 처음이면 Hex 설치가 필요하다. Hex 는 Erlang 에코시스템의 패키지 매니저이다.

mix local.hex

mix 는 Elixir 의 빌드 도구이다.

Mix is a build tool that ships with Elixir that provides tasks for creating, compiling, testing your application, managing its dependencies and much more

Phoenix 생성기 설치

Phoenix 프로젝트를 생성하기 위해 다음의 명령 실행. Phoenix 생성기를 설치한다.

mix archive.install hex phx_new

프로젝트 생성

hello 라는 이름의 Phoenix 프로젝트를 만든다.

mix phx.new hello

데이터베이스를 사용하지 않을 것이라면 –no-ecto 옵션을 추가한다. Ecto 는 Elixir 를 위한 데이터베이스 래퍼와 쿼리 생성기이다.

Fetch and instll dependencies? 를 Y 로 넘어가면 다음과 같은 결과를 얻을 수 있다.

Fetch and install dependencies? [Yn] Y

* running mix deps.get
* running mix deps.compile

We are almost there! The following steps are missing:

&nbsp; &nbsp; $ cd hello

Then configure your database in config/dev.exs and run:

&nbsp; &nbsp; $ mix ecto.create

Start your Phoenix app with:

&nbsp; &nbsp; $ mix phx.server

You can also run your app inside IEx (Interactive Elixir) as:

&nbsp; &nbsp; $ iex -S mix phx.server

프로젝트 폴더로 이동 한 다음 ecto 설정을 실행한다.

cd hello
mix ecto.create

ecto 명령어 실행 중 에러가 발생하면 다음 문서를 참고한다.

postgresql 을 처음 설치했다면 role 이 없어서 오류가 발생한다. psql 에서 다음 명령어를 실행한다.

=# CREATE ROLE postgres LOGIN CREATEDB;

실행

모두 완료가 되었다면 Phoenix 서버를 실행한다.

mix phx.server

[info] Running HelloWeb.Endpoint with cowboy 2.9.0 at 127.0.0.1:4000 (http)
[info] Access HelloWeb.Endpoint at http://localhost:4000

위와 같은 로그를 확인했다면 127.0.0.1:4000 에서 첫 화면을 확인.

완료!

소프트웨어 아키텍처 101 자율 평가 문제 – 6장 아키텍처 특성의 측정 및 거버넌스

2월 11, 20231월 6, 2024 animato댓글 남기기

이 이미지는 대체 속성이 비어있습니다. 그 파일 이름은 image.png입니다 — 소프트웨어 아키텍처 101, 한빛미디어

소프트웨어 아키텍처 101 내용 중 자율 평가 문제에 대한 제가 생각하는 답을 정리했습니다. 책에서 가르쳐준 내용을 토대로 최대한 정답이라고 생각하는 내용을 적었으나 잘못 정리 했거나 틀린 답을 적었을 수 있습니다. 정리한 내용 중 책의 저작권을 위배하는 사항이 있다면 내용이 수정될 수 있습니다.

1 아키텍처를 분석할 때 순환 복잡도가 중요한 메트릭인 이유는 무엇인가요?

순환 복잡도가 증가하면 코드의 모듈성, 시험성, 배포성 등 거의 모든 바람직한 코드베이스 특성을 저해하게 된다.

2 아키텍처 피트니스 함수는 무엇인가요? 아키텍처를 분석하는 데 이 함수를 어떻게 사용하나요?

어떤 아키텍처 특성의 객관적인 무결성을 평가하는 모든 메커니즘

아키텍처 피트니스 함수는 아키텍처가 아키텍처 목표를 달성하는데 얼마나 근접해 있는지를 나타낸다. 테스트 주도 개발에서 각각의 기능들이 얼마나 비즈니스 결과에 부합하는지 확인하기 위해 테스트 코드를 작성해서 확인하는 것 처럼 아키텍처 피트니스 함수를 통해 시스템이 아키텍처 목표에 얼마나 부합하는지 테스트 할 수 있다.

3 아키텍처 피트니스 함수를 이용해서 아키텍처 확장성을 측정하는 예를 들어보세요.

https://youtu.be/ipJtGdmyT-Y

책의 저자 중 한명인 마크 리처즈는 이 영상에서 아키텍처 확장성을 측정하는 방법을 설명하고 있다.

또한 이 글 에서는 다음과 같은 아키텍처 피트니스 함수를 통해 아키텍처 확장성을 측정할 수 있다고 한다.

describe "Performance" do
    it "completes a transaction under 10 seconds" do
        expect(transaction.check_transaction_round_trip_time()).to < 10
    end
    it "has less than 10% error rate for 10000 transactions" do
        expect(transaction.check_error_rate_for_transactions(10000)).to < .1
    end
end

4 아키텍트, 개발자가 피트니스 함수를 생성할 수 있게 하는, 아키텍처 특성의 가장 중요한 기준은 무엇인가요?

아키텍처 특성은 운영적, 구조적, 프로세스 측정 등의 기준으로 측정 할 수 있다.

참고자료

소프트웨어 아키텍처 101 자율 평가 문제 – 5장 아키텍처 특성 식별

2월 3, 20232월 20, 2023 animato댓글 남기기

1 아키텍처가 지원해야 할 아키텍처 특성의 가짓수를 제한하는 것이 왜 중요한가요?

아키텍처 특성 하나하나는 전체 시스템 설계를 복잡하게 만드는 요인이기 때문에 너무 많은 아키텍처 특성을 수용하면 아키텍트, 개발자가 당초 의도했던 문제 영역의 해결을 시도하기도 전에 아키텍처가 너무 복잡해져버리게 된다.

2 대부분의 아키텍처 특성은 비즈니스 요구사항과 유저 스토리에서 비롯됩니다. 맞는 말인가요, 틀린 말인가요?

많은 아키텍처 특성이 비즈니스 요구사항과 유저 스토리에서 비롯되지만 아키텍트가 알고 있는 도메인 지식에서 도출되는 특성들도 있다. 예를 들어 대학교 학사 관리 시스템의 수강 등록을 처리하는 애플리케이션을 설계한다고 했을 때 학생들의 성향과 습관 상 수강 신청 과정에서 많은 학생들이 마감 직전에 수강 시스템에 몰린다는 것을 알고 있는 아키텍트라면 요구사항 정의서에 탄력성이 적혀 있지 않더라도 탄력성을 도출해 낼 수 있다.

3 비즈니스 이해관계자는 시장 출시 시기(즉, 새로운 기능과 버그 조치 등의 서비스를 가능한 한 신속하게 고객에게 제공하는 것)를 가장 중요한 비즈니스 관심사라고 말합니다. 이런 상황이라면 어떤 아키텍처 특성이 가장 시급하게 지원되어야 하나요?

시장 출시 시기가 중요한 비즈니스 관심사라면 이 시스템은 민첩성, 시험성, 배포성이 시급하게 지원되어야 한다.

비즈니스 요구사항을 시스템에 신속히 적용하는 민첩성이 우선적으로 고려되겠지만 단순히 민첩성만 고려할 것이 아니라 제품 출시와 연관된 여러 특성이 같이 지원되어야 한다. 예를들어 시험성이 떨어지는 아키텍처라면 버그를 조기에 발견하기 어렵고 버그를 발견한다 하더라도 해결 이후에 적절히 해결되었는지 제대로 시험하기가 어렵다. 그러면 버그 조치등의 활동이 전체적으로 느려지게 되고 이는 시장 출시 시기에 부정적인 영향을 주게 된다. 또한 배포성을 제대로 지원하지 않는 아키텍처라면 새로운 기능이 추가 될 때마다 배포 하는 과정에서 많은 시간을 들여야 할 것이기 때문에 시장 출시 시기에 좋지 않은 영향을 줄 수 있다. 따라서 시장 출시 시기가 중요한 비즈니스 관심사라면 민첩성을 비롯하여 시험성, 배포성 등 제품 출시와 연관된 여러 특성을 종합적으로 고려해야 한다.

4 확장성과 탄력성의 차이점은 무엇인가요?

확장성은 유의미한 성능 저하 없이 다수의 동시 유저를 처리하는 능력을 말한다. 확장성이 있는 시스템은 이용자가 꾸준히 늘더라도 추가 이용자를 처리하기 위해 시스템을 변경하거나 추가 리소스를 할당하기 용이한 시스템이다.

반면 탄력성은 트래픽의 폭주하는 정도를 나타낸다. 탄력성의 목적은 할당된 리소스를 지정된 시점에 필요한 실제 리소스 양과 일치 시키는 것이다. 탄력성이 있는 시스템은 갑자기 사용자가 폭증하더라도 사용자 요청을 처리하기 위한 리소스 추가 할당이 적절한 시점에 이루어져 성능 저하 혹은 시스템 다운이 일어나지 않는 시스템이다.

5 고객사가 고객층을 크게 넓히고자 몇 가지 중요한 기업 인수를 추진할 계획이라고 합니다. 여러분은 어떤 아키텍처 특성을 가장 신경 써야 하나요?

기업 인수가 성사된다면 서로 다른 환경에서 만들어진 시스템이 통합 되어야 하는 상황이 일어날 수 있다. 따라서 이와 관련되는 시스템에서는 상호운용성, 확장성, 적응성, 신장성 등의 아키텍처 특성을 고려해야 한다.

참조

소프트웨어 아키텍처 101 자율 평가 문제 – 4장 아키텍처 특성 정의

1월 28, 20232월 20, 2023 animato댓글 남기기

1 어떤 속성이 아키텍처 특성이 되려면 충족해야 할 세 기준은 무엇인가요?

비도메인 설계 고려 사항을 명시한다.
설계의 구조적 측면에 영향을 미친다.
애플리케이션 성공에 (절대적으로) 중요하다.

2 암묵적 특성과 명시적 특성의 차이점은 무엇인가요? 각각의 예를 들어보세요.

암묵적 아키텍처 특성은 요구사항 정의서에는 거의 안 나오지만 프로젝트 성공을 위해 꼭 필요한 특성들이다.
예를들어, 가용성, 신뢰성, 보안은 거의 모든 애플리케이션에 필요한 특성이지만 설계 문서에는 잘 등장하지 않는다.

명시적 아키텍처 특성은 요구사항 정의서나 다른 지침서에 기재된다.

3 운영 특성(operational characteristic)의 예를 들어보세요.

특성	설명
가용성	시스템이 얼마나 오랫동안 사용 가능해야 하나?
연속성	재해 복구 능력
성능	스트레스 테스트, 피크 분석, 기능의 사용 빈도 분석, 필요 용량, 응답 시간 등
복구성	장애 발생 시 얼마나 신속하게 시스템을 재가동 시켜야 하나?
신뢰성/안전	시스템에 fail-safe 가 필요한가?
견고성	프로그램 실행 중 인터넷 접속 끊김, 정전, 하드웨어 실패 등 에러 및 경계 조건을 감당하는 능력
확장성	유저 수, 요청 수가 늘어나도 시스템이 그에 맞는 성능을 발휘하는 능력

4 구조 특성(structural characteristic)의 예를 들어보세요.

특성	설명
설정성	최종 유저가 소프트웨어 설정을 쉽게 바꿀 수 있는가?
신장성	새로운 기능을 삽입하는 일의 중요성
설치성	필요한 모든 플랫폼에 시스템을 얼마나 손쉽게 설치할 수 있나?
활용성/재사용	공통 컴포넌트를 여러 제품에서 활용할 수 있나?
지역성	데이터를 입력/조회하는 화면에서 다국어가 지원되는가?
유지보수성	시스템을 얼마나 쉽게 변경/개선할 수 있나?
이식성	하나 이상의 플랫폼에서 시스템을 실행할 수 있나?
지원성	애플리케이션은 어느 정도의 기술 지원을 필요로 하나?
업그레이드성	이 애플리케이션/솔루션의 구 버전을 새 버전으로 쉽고 빠르게 업그레이드 할 수 있는가?

5 공통 특성(cross-cutting characteristic)의 예를 들어보세요.

특성	설명
접근성	색맹, 청각 장애인 등 모든 유저가 접근하는 데 불편함이 없나?
보관성	데이터를 따로 아카이빙 해야하나, 아니면 일정 시간 경과 후 삭제해야 하나?
인증	유저가 본인이 맞다는 것을 증명하기 위해 필요한 보안 요구사항
인가	유저가 애플리케이션에서 정해진 기능만 사용할 수 있도록 강제하는 보안 요구사항
합법성	시스템 운영상 법적 제약조건이 있는가?
프라이버시	회사 내부 임직원의 트랜잭션을 외부에 드러내지 않는 기능
보안	데이터를 암호화 한 후 데이터베이스에 보관해야하나?
사용성/성취성	유저가 애플리케이션/솔루션을 이용하여 원하는 목적을 달성하기 위해 필요한 교육/훈련 수준

참고

소프트웨어 아키텍처 101

소프트웨어 아키텍처 101 자율 평가 문제 – 3장 모듈성

1월 23, 20232월 20, 2023 animato댓글 남기기

1. 커네이선스라는 용어는 무엇을 의미하나요?

두 컴포넌트 중 한쪽이 변경될 경우 다른 쪽도 변경해야 전체 시스템의 정합성이 맞는다면 이들은 커네이선스를 갖고 있다고 말할 수 있다.

2. 정적 커네이선스와 동적 커네이선스의 차이점은 무엇인가요?

정적 커네이선스: 소스 코드 레벨의 커플링
동적 커네이선스: 런타임 상황에서 확인할 수 있는 커네이선스

3. 타입 커네이선스는 무엇인가요? 이것은 정적 커네이선스인가요, 아니면 동적 커네이선스인가요?

타입 커네이선스는 정적 커네이선스 중 하나로 여러 컴포넌트의 엔티티 타입이 일치해야 하는것을 뜻한다.

4. 가장 강력한 형태의 커네이선스는 무엇인가요?

동적 커네이선스 중 식별 커네이선스
여러 컴포넌트가 동일한 엔티티를 참조하는 경우에 발생

5. 가장 약한 형태의 커네이선스는 무엇인가요?

정적 커네이선스 중 명칭 커네이선스
여러 컴포넌트의 엔티티명이 일치해야 하는 경우에 발생

6. 정적 커네이선스, 동적 커네이선스 중 코드베이스에서는 어느 쪽이 더 바람직한가요?

정적 커네이선스는 동적 커네이선스에 비해 쉽게 개선할 수 있고 동적 커네이선스는 효과적인 분석 도구가 많지 않아 파악하기 어려우므로 정적 커네이선스가 코드베이스에 더 바람직하다. 그리고 동일한 커네이선스가 널리 흩어져 있는 것 보다는 가까이 붙어 있는것이 더 바람직하다(커네이선스의 지역성). 또한 커네이선스가 미치는 영향의 규모 값(degree)이 작을수록 코드베이스에 바람직하다.

참고

소프트웨어 아키텍처 101 자율 평가 문제 – 2장 아키텍처 사고

1월 22, 20232월 20, 2023 animato댓글 남기기

아키텍처 대 개발의 기존 접근 방식을 설명하고, 이제는 더 이상 기존 접근 방식이 통하지 않는 이유를 설명하세요.

전통적인 아키텍트의 책임과 개발자의 책임은 다음과 같다. 아키텍트는 비즈니스 요구사항을 분석해서 아키텍처 특성을 도출/정의하고 각종 컴포넌트를 포함한 아티팩트를 만들어 개발팀에 전달 -> 개발팀은 각 컴포넌트의 설계를 하고 코드를 개발/테스트

전통적인 아키텍처 대 개발의 접근 방식은 아키텍트가 내린 결정이 개발팀에서 전혀 쓸모가 없는 경우가 있음에도 불구하고, 개발팀이 아키텍처를 변경하기로 결정한 내용이 다시 아키텍트에게 전달되는 일이 거의 없다.

변화에 둔감하고 융통성 없는 구식 폭포수 모델과 달리, 요즘 시스템 아키텍처는 매 프로젝트 단계마다, 또는 매 이터레이션마다 끊임없이 변화하고 발전하기 때문에 프로젝트를 성공으로 이끌려면 아키텍트와 개발팀이 모두 활발히 소통하고 프로젝트 생명 주기의 일부로서 항상 서로 동기화 되어야 한다.

지식 피라미드의 세 레벨의 지식을 열거하고 각각의 예를 들어보세요.

지식 피라미드의 세 레벨 (나의 예)

내가 알고 있는 것 (스프링 웹 백엔드 개발, 클라우드 서비스 활용 웹 개발 등)
내가 모른다는 사실을 아는 것 (NoSQL, 최신 프론트 웹 개발 등)
내가 모른다는 사실조차 모르는 것 (열거할 수 없음)

아키텍트에게는 왜 기술의 깊이보다 폭에 집중하는 것이 더 중요한가요?

아키텍트는 기술적인 제약 하에 어떤 기능이 가장 알맞는지 결정해야 하므로 아주 폭넓은 솔루션을 두루 꿰고 있어야 한다.

아키텍트로서 기술 깊이를 유지하고 실무 능력을 잃지 않으려면 어떻게 해야 하나요?

개념 증명(Proof of Concept)을 자주 해본다.
중요한 유저 스토리 작업은 개발팀에 맡기고 기술 부채 스토리나 아키텍처 스토리에 전념한다.
이터레이션 동안 버그를 잡는다.
간단한 커맨드라인 도구나 분석기를 만들어 개발팀의 일상 업무를 간소화, 자동화 한다.
아키텍처의 컴플라이언스 보장을 자동화하기 위한 피트니스 함수를 만든다.
자주 코드리뷰를 한다.

참고

소프트웨어 아키텍처 101, 한빛미디어

소프트웨어 아키텍처 101 자율 평가 문제 – 1 서론

1월 21, 20232월 20, 2023 animato댓글 남기기

소프트웨어 아키텍처를 정의하는 네 차원은 무엇인가요?

아키텍처 특성(architecture characteristic)
시스템의 기능과 직교하는 시스템의 성공 기준
시스템이 지원해야 하는 ‘~성’ 들 (ex: 가용성, 신뢰성, 시험성, 확장성, 보안, 민첩성 등)
아키텍처 결정(architecture decision)
시스템 구축에 필요한 규칙들
시스템의 제약조건을 형성, 개발자가 해도 되는 것과 하지 말아야 할 것을 알려줌
설계 원칙(design principle)
소프트웨어의 조건과 구현 방안에 대한 가이드라인
(ex: 마이크로서비스 아키텍처의 성능 향상을 위한 서비스 간 통신은 비동기 메시징을 활용해야함)
구조(structure)
시스템이 구현된 아키텍처 스타일(들)의 종류
(ex: 마이크로서비스, 레이어드, 마이크로커널 등)

아키텍처 결정과 설계 원칙은 어떤 차이점이 있나요?

아키텍처 결정이 반드시 지켜야 할 규칙이라면 설계 원칙은 가이드라인
소프트웨어의 모든 조건과 구현 방안을 아키텍처 결정(규칙)으로 다룰 수는 없기에 권장하는 방법에 관한 가이드를 설계 원칙으로 제공

소프트웨어 아키텍트의 8대 핵심 기대치를 나열하세요

아키텍처 결정을 내린다.
아키텍트는 기술 선택을 가이드 하는 사람이지 정해주는 사람이 아니다.
아키텍처를 지속적으로 분석한다.
ex: 3년 이전에 정의한 아키텍처가 지금도 얼마나 현실성 있는지 평가
최신 트렌드를 계속 유지한다.
항상 최신 기술과 업계 트렌드를 따라가야 함
아키텍처 결정의 컴플라이언스를 보장한다.
아키텍트가 정의하고 문서화하여 전달한 아키텍처 결정과 설계 원칙들을 개발팀이 제대로 준수하고 있는지 지속적으로 확인
다양한 기술과 경험에 노출된다.
유능한 아키텍트는 여러가지 언어, 플랫폼, 기술을 경험할 기회를 적극적으로 모색하면서 기술의 깊이보다는 폭에 초점을 둔다.
비즈니스 도메인 지식을 보유한다.
비즈니스 도메인 지식이 없으면 비즈니스의 문제점, 목표, 요구사항을 이해하기 어렵고, 따라서 비즈니스 요구사항을 수용할 만한 효율적인 아키텍처를 설계하기도 어려움.
대인 관계 기술이 뛰어나다.
아키텍트는 개발팀을 기술적으로 이끌기만 하는 사람이 아니라, 개발팀을 리드해서 아키텍처를 구현하는 사람이므로 직책 또는 역할과 상관 없이, 리더십 스킬은 아키텍트로서 성공하기 위해 필수 요구사항의 절반 이상은 차지함.
정치를 이해하고 처세를 잘한다.
아키텍트가 내린 거의 모든 결정은 사람들의 반발에 부딪히게 마련이다. 따라서 대부분의 결정을 사람들이 수용하도록 기본적인 협상 기술을 발휘해야 함.

소프트웨어 아키텍처 제1법칙은 무엇인가요?

소프트웨어 아키텍처의 모든 것은 다 트레이드오프다.

참고

소프트웨어 아키텍처 101

[HackerRank] 연락처

4월 30, 2018 animato댓글 남기기

Tries: Contacts

아주 간단한 연락처 어플리케이션을 만들어 보자.

이 문제는 Trie라는 자료구조를 사용해서 푸는 문제이다. 사실 나는 Trie라는 자료구조를 이 문제를 통해 처음 알게 되었다. ‘트라이’ 라고 발음하는 것 같다. 역시 마찬가지로 간단하게 정리해 보자.

트라이(Trie):

n-차 트리
접두사 트리(prefix tree) 라고 부르기도 함
루트는 빈 노드
텍스트를 검색하는데 속도가 빠름

검색어 자동완성 기능에 이런 류의 자료 구조가 쓰이는 구나 싶었다.

문제는 두가지 요구사항이 있다.

add name: name 부분으로 입력된 문자열을 입력한다.
find partial: partial 부분으로 입력된 문자열로 시작하는 이름의 개수를 반환한다.

아래와 같이 풀어보았다.

	import java.io.*;
	import java.util.*;
	import java.text.*;
	import java.math.*;
	import java.util.regex.*;


	public class Solution {
	static class Trie {
	public int countChildWordNode = 0;
	public String value;
	public Trie [] nodeArray = new Trie[26];
	}
	public static void main(String[] args) {
	Scanner in = new Scanner(System.in);
	int n = in.nextInt();
	Trie root = new Trie();
	for(int a0 = 0; a0 < n; a0++){
	String op = in.next();
	String contact = in.next();
	if (op.equals("add")) {
	add(contact, root);
	} else if (op.equals("find")) {
	System.out.println(find(contact, root));
	}
	}
	}
	public static void add(String name, Trie root) {
	for (int i = 0; i < name.length(); i++) {
	String value = name.substring(0, i+1);
	char[] charArray = value.toCharArray();

	int length = charArray.length;
	int index = charArray[length-1] - 'a';
	Trie newNode = root.nodeArray[index];

	if (newNode == null) {
	newNode = new Trie();
	newNode.value = value;
	}
	newNode.countChildWordNode++;
	root.nodeArray[index] = newNode;

	root = newNode;
	}
	}
	public static int find(String name, Trie root) {
	for (int i = 0; i < name.length(); i++) {
	String value = name.substring(0, i+1);
	char[] charArray = value.toCharArray();

	int length = charArray.length;
	int index = charArray[length-1] - 'a';
	Trie newNode = root.nodeArray[index];

	if (newNode != null) {
	root = newNode;
	} else {
	return 0;
	}
	if (name.equals(root.value)) {
	return root.countChildWordNode;
	}
	}
	return 0;
	}
	}

view raw tries-contacts.java hosted with ❤ by GitHub

문제를 풀면서 꽤 애를 먹었다. 트라이 자체를 만들어 내는 것은 그렇게 어렵지 않았으나 자식노드의 수를 구하는 부분에서 어려움이 있었다. 처음엔 트리를 모두 순회하며 해당 문자열로 시작하는 노드의 수를 모두 세도록 만들었으나 몇몇 케이스에서 타임아웃에 걸렸다.

문제를 푸는 핵심 키는 문자열을 입력 할 때 마다 입력시 거쳐가는 노드의 자식 카운트를 하나씩 올려주는 것이다. 트라이 특성 상 자료 입력 시 글자 하나 마다 하나의 노드를 거쳐 가도록 되어있으므로 본인을 접두사로 포함하는 자식의 개수는 그냥 순회하는 노드마다 카운트를 1씩 올려주면 된다. 거쳐갔던 자료들의 수를 유지하고 있다면 “거쳐갔던 자료들의 수 = 노드의 값을 접두사로 포함하고 있는 노드의 개수” 가 된다.

예를들어 “abc”, “abcd”, “abcdefg” 는 공통적으로 “a” – “ab” – “abc”라는 노드를 거쳐서 저장되었다. 노드를 거쳐갈 때 마다 카운트를 1씩 올렸다면 “a”, “ab”, “abc” 노드는 세 번 거쳐갔을 것이므로 각각 3을 갖고있고(a와 ab는 실제로 입력된 자료가 아니지만 abc가 입력될때 abc가 거쳐가면서 생성됨) “abcd”는 2(abcd와 abcdefg가 거쳐감), “abcde”, “abcdef”, “abcdefg” 는 각각 1을 갖고 있을 것이다(a와 ab의 경우와 같이 abcdefg가 생성될 때 abcde, abcdef가 생성됨).

문제를 풀면서 새로운 자료구조를 배우고 또 고민고민끝에 해결책을 생각해 내 풀어내어서 굉장히 즐거웠던 문제였다!

[HackerRank] 이진탐색트리가 맞나요?

4월 13, 20184월 13, 2018 animato댓글 남기기

이진트리가 주어지면, 그것이 이진탐색트리인지 감별하는 메소드를 만든다.

이진트리와 이진탐색트리를 구별해야 한다. 이진트리와 이진탐색트리를 간단히 정리하자면..

이진트리:

트리의 각 노드가 최대 두 개의 자식을 갖는 트리

이진탐색트리:

이진트리이면서..
모든 노드의 값은 해당 노드의 모든 왼쪽 자식들의 값보다 커야 함
모든 노드의 값은 해당 노드의 모든 오른쪽 자식들의 값보다 작아야 함
같은 값을 허용하는가는 정의 하기 나름 (본 문제에서는 같은 값은 없다고 정의했다)
이진트리지만 이진탐색트리는 아님 (이미지 출처: 위키피디아)

200px-binary_search_tree-svg — 이진탐색트리(이미지 출처: 위키피디아)

다음과 같이 이진탐색트리를 판정하는 코드를 만들었다.

	/* Hidden stub code will pass a root argument to the function below. Complete the function to solve the challenge. Hint: you may want to write one or more helper functions.

	The Node class is defined as follows:
	class Node {
	int data;
	Node left;
	Node right;
	}
	*/
	boolean checkBST(Node root) {
	if (root.left == null && root.right == null) {
	return true;
	} else {
	if (checkBST(root.left) && checkBST(root.right)) {
	int leftTreeMaxValue = treeMaxValue(root.left);
	int rightTreeMinValue = treeMinValue(root.right);
	if (leftTreeMaxValue < root.data && root.data < rightTreeMinValue) {
	return true;
	} else {
	return false;
	}
	} else {
	return false;
	}
	}
	}
	int treeMaxValue(Node root) {
	if (root.left == null && root.right == null) {
	return root.data;
	} else {
	int leftValue = treeMinValue(root.left);
	int value = root.data;
	int rightValue = treeMinValue(root.right);

	if (leftValue < value) {
	if (value < rightValue) {
	return rightValue;
	} else {
	return value;
	}
	} else {
	if (leftValue < rightValue) {
	return rightValue;
	} else {
	return leftValue;
	}
	}
	}
	}
	int treeMinValue(Node root) {
	if (root.left == null && root.right == null) {
	return root.data;
	} else {
	int leftValue = treeMinValue(root.left);
	int value = root.data;
	int rightValue = treeMinValue(root.right);

	if (leftValue > value) {
	if (value > rightValue) {
	return rightValue;
	} else {
	return value;
	}
	} else {
	if (leftValue > rightValue) {
	return rightValue;
	} else {
	return leftValue;
	}
	}
	}
	}

view raw check-BST.java hosted with ❤ by GitHub

이진트리를 구별하는 코드는 별로 어렵지 않았지만 그 안에 이진탐색트리 조건을 같이 담는 과정이 조금 까다로웠다.

[HackerRank] 두 스택 이야기

4월 8, 20184월 8, 2018 animato댓글 남기기

Queues: A Tale of Two Stacks

두 개의 스택을 이용해 큐를 만드는 문제. 인풋값을 다루는 메인함수는 주어져 있고 큐만 만들면 된다. 큐에 필요한 스택 변수와 함수도 얼개는 만들어져있는 상태에서 구현만 하면 된다.

제약조건은 인풋값과 관련된 것 외에는 특별히 신경써야 할 것은 없는 것 같다.

스택과 큐를 간단히 정리하면,

스택(Stack):

Last-In-First-Out(LIFO) 후입선출
push: 스택에 값을 넣는다.
pop: 스택의 맨 앞에서 값을 하나 가져온다. 가져온 값은 스택에서 제거된다. (꺼낸다)
peek: 스택의 맨 앞에서 값을 하나 가져온다. 가져온 값은 스택에서 제거되지 않는다.

큐(Queue):

First-In-First-Out(FIFO) 선입선출
enqueue: 큐의 끝에 값을 넣는다.
dequeue: 큐의 맨 앞에서 값을 하나 가져온다. 가져온 값은 큐에서 제거된다. (꺼낸다)
peek: 큐의 맨 앞에서 값을 하나 가져온다. 가져온 값은 큐에서 제거되지 않는다.

다음과 같이 스택 두개를 이용해 하나의 큐를 만들었다.

	import java.io.*;
	import java.util.*;
	import java.text.*;
	import java.math.*;
	import java.util.regex.*;

	public class Solution {
	public static class MyQueue<T> {
	Stack<T> stackNewestOnTop = new Stack<T>();
	Stack<T> stackOldestOnTop = new Stack<T>();

	public void enqueue(T value) { // Push onto newest stack
	stackNewestOnTop.push(value);
	}

	public T peek() {
	if(stackOldestOnTop.empty()) {
	while (!stackNewestOnTop.empty()) {
	stackOldestOnTop.push(stackNewestOnTop.pop());
	}
	}
	return stackOldestOnTop.peek();
	}

	public T dequeue() {
	if(stackOldestOnTop.empty()) {
	while (!stackNewestOnTop.empty()) {
	stackOldestOnTop.push(stackNewestOnTop.pop());
	}
	}
	return stackOldestOnTop.pop();
	}
	}


	public static void main(String[] args) {
	MyQueue<Integer> queue = new MyQueue<Integer>();

	Scanner scan = new Scanner(System.in);
	int n = scan.nextInt();

	for (int i = 0; i < n; i++) {
	int operation = scan.nextInt();
	if (operation == 1) { // enqueue
	queue.enqueue(scan.nextInt());
	} else if (operation == 2) { // dequeue
	queue.dequeue();
	} else if (operation == 3) { // print/peek
	System.out.println(queue.peek());
	}
	}
	scan.close();
	}
	}

view raw two-stacks-queue.java hosted with ❤ by GitHub

스택 두 개 중 하나는 선입된 값이 가장 위(stackOldestOnTop, 출구스택)에 있도록 하고 다른 하나는 후입된 값이 가장 위(stackNewestOnTop, 입구스택)에 있도록 한다. enqueue시에는 입구스택에 스택의 push를 활용하여 값을 쌓고 dequeue시에는 출구스택에서 값을 빼 낸다. 출구스택에 값이 없을 땐 입구스택에서 값을 모두 가져와서 출구스택에 push한 뒤 출구스택의 맨 앞에서 값을 빼낸다. peek도 dequeue와 같은 방식으로 만들되 출구스택에서 값을 빼지(pop)않고 peek 한다.

예를들어, 큐에 1, 2, 3 을 순서대로 넣는다고 가정하면, 1-2-3 이 enqueue 될 때는 입구스택에 값을 쌓기 때문에 입구스택에 3|2|1] 이런 식으로 쌓이게 된다. 여기서 dequeue를 하려면 (1부터 빼내려면) 입구스택에 있는 모든 값을 출구스택으로 옮겨야 한다. 옮기는 과정에서 입구스택에서 값을 빼낼 땐 3-2-1의 순서대로 값이 빠지게 되고 빠지는 순서 그대로 다시 출구스택에 push하면 1|2|3] 이런식으로 값이 쌓이게 될 것이다. 이렇게 모두 옮기고 난 후 출구스택의 맨 앞 값을 빼내면 1이 빠진다. (dequeue)

한번 풀게 되면 스택과 큐의 특성을 둘 다 자연스럽게 익히게 되는 괜찮은 문제인 것 같다.