[코드 인터뷰 대비 시리즈 #8] 고급 문자열 알고리즘(Trie, 접미사 배열) 패턴 정리

여러분, 문자열(String) 문제는 코딩 인터뷰에서 자주 등장하며, 이전에 살펴본 KMP나 Rabin-Karp 같은 부분 문자열 검색 알고리즘뿐 아니라 더욱 고급스러운 자료구조와 알고리즘을 통해 대규모 문자열 처리 문제도 효율적으로 해결할 수 있습니다. 특히 트라이(Trie)를 이용하면 접두사(Prefix) 기반 쿼리를 효율적으로 처리할 수 있고, 접미사 배열(Suffix Array)나 접미사 트리(Suffix Tree), LCP(Longest Common Prefix) 배열, 문자열 해싱 등은 복잡한 문자열 패턴 분석, 다수 쿼리 처리, 문자열 집합 패턴 매칭 등을 O(N)~O(N log N) 안에 처리할 수 있는 강력한 도구입니다.이번 글에서는 Trie와 접미사 배열 등 고급 문자열 알고리즘을 만나..

• format_list_bulleted 미국 빅테크/코드 인터뷰
• · 2024. 12. 16.
• textsms

[모던 C++로 다시 쓰는 GoF 디자인 패턴 총정리 #19] 템플릿 메서드(Template Method) 패턴: 알고리즘 골격을 Concepts와 람다로 선언적으로 표현하기

이전 글에서는 메멘토(Memento) 패턴을 모던 C++ 관점에서 재해석하며, 상속 없이 값 기반 상태 스냅샷과 std::expected, coroutine, Ranges 등을 활용해 Undo/Redo, 비동기 복원, 로깅 등의 요구사항에 대응할 수 있음을 확인했습니다. 이번에는 행동(Behavioral) 패턴 중 템플릿 메서드(Template Method) 패턴을 다룹니다.템플릿 메서드 패턴은 상위 클래스에서 알고리즘의 골격(템플릿)을 정의하고, 하위 클래스에서 일부 단계를 오버라이드하여 구체화하는 패턴입니다. 그러나 전통적 접근은 상속 기반 구조로, 알고리즘 변형 시 하위 클래스 증가, 유지보수 어려움 등이 발생합니다. C++20 이상에서는 Concepts, 람다, std::expected, std:..

• format_list_bulleted 개발 이야기/C++
• · 2024. 12. 16.
• textsms

[모던 C++로 다시 쓰는 GoF 디자인 패턴 총정리 #18] 메멘토(Memento) 패턴: 상태 스냅샷을 값 기반으로 캡슐화하고 복원하기

이전 글에서는 미디에이터(Mediator) 패턴을 모던 C++ 관점에서 재해석하며, 상속 기반 구조 없이도 Concepts, std::function, std::expected, coroutine, Ranges 등을 활용해 객체 간 상호작용을 유연하고 타입 안전하게 구현할 수 있음을 확인했습니다. 이번에는 행동(Behavioral) 패턴 중 메멘토(Memento) 패턴을 다룹니다.메멘토 패턴은 객체 상태를 캡슐화(스냅샷)하여, 이후 필요할 때 원래 상태로 복원하는 기법을 제공합니다. 전통적으로는 Originator(원본 객체), Memento(상태 저장), Caretaker(메멘토 관리) 클래스를 정의하고, Memento 클래스로 상태를 저장/복원하는 상속 기반 구조를 사용했습니다. 그러나 모던 C++2..

• format_list_bulleted 개발 이야기/C++
• · 2024. 12. 16.
• textsms

[모던 C++로 다시 쓰는 GoF 디자인 패턴 총정리 #17] 미디에이터(Mediator) 패턴: 상호작용을 함수 합성과 Concepts로 집중 관리하기

이전 글에서는 이터레이터(Iterator) 패턴을 모던 C++ 관점에서 재해석하며, C++20 Ranges와 Concepts를 통해 상속 없이도 선언적이고 타입 안전한 순회 방식을 구현할 수 있음을 확인했습니다. 이번에는 행동(Behavioral) 패턴 중 미디에이터(Mediator) 패턴을 다룹니다.미디에이터 패턴은 객체들이 서로 직접 통신하는 대신, 미디에이터(중재자)를 통해 상호작용하도록 하여 객체 간 결합을 느슨하게 만드는 패턴입니다. 전통적으로는 미디에이터 인터페이스와 구체 미디에이터를 상속 기반으로 정의하고, 각 객체가 미디에이터를 참조해 메시지나 이벤트를 중개하는 구조를 사용했습니다. 그러나 모던 C++20 이상에서는 Concepts, 람다, std::function, std::expecte..

• format_list_bulleted 개발 이야기/C++
• · 2024. 12. 16.
• textsms

[코드 인터뷰 대비 시리즈 #7] 그리디(Greedy) 알고리즘 문제 접근 패턴 정리

여러분, 그리디(Greedy) 알고리즘은 많은 인터뷰 문제에서 자주 활용되는 패턴 중 하나입니다. 그리디 알고리즘은 매 순간 지역적으로 최선(최적)이라고 생각되는 선택을 함으로써 전체 문제의 최적해에 도달하려는 전략입니다. 물론 그리디 접근이 항상 전역 최적해를 보장하지는 않지만, 특정 조건(그리디 선택 정당성)이 성립하면 복잡한 문제도 단순하고 효율적으로 해결할 수 있어요. 이번 글에서는 그리디 알고리즘 문제에 직면했을 때 어떤 식으로 접근하고, 정당성을 어떻게 입증하며, 코너 케이스나 최적화 포인트, 면접에서의 커뮤니케이션 방법까지 단계별로 매우 구체적으로 다루어보겠습니다.그리디 문제에서 중요한 것은 "그리디 선택(Locally Optimal Choice)을 정당화할 수 있는가?" 입니다. 이를 위해..

• format_list_bulleted 미국 빅테크/코드 인터뷰
• · 2024. 12. 16.
• textsms

[모던 C++로 다시 쓰는 GoF 디자인 패턴 총정리 #16] 이터레이터(Iterator) 패턴: Ranges와 Concepts로 컬렉션 순회 재구성하기

이전 글에서는 인터프리터(Interpreter) 패턴을 모던 C++ 관점에서 재해석하며, 상속 기반 Expression 클래스 계층 없이도 std::variant, std::visit, Concepts, std::expected, Ranges, coroutine 등을 활용해 언어 해석 로직을 단순하고 확장성 높게 구현할 수 있음을 확인했습니다. 이번 글에서는 행동(Behavioral) 패턴 중 이터레이터(Iterator) 패턴을 다룹니다.이터레이터 패턴은 컬렉션의 내부 표현을 노출하지 않고, 요소에 접근하는 통일된 인터페이스를 제공하는 패턴입니다. 전통적으로는 컬렉션 별로 Iterator 인터페이스를 정의하고, begin()/end() 또는 next(), hasNext() 등의 메서드를 통해 요소 순회가..

• format_list_bulleted 개발 이야기/C++
• · 2024. 12. 16.
• textsms

[모던 C++로 다시 쓰는 GoF 디자인 패턴 총정리 #15] 인터프리터(Interpreter) 패턴: 파서와 해석 로직을 Ranges, Concepts로 선언적으로 구성하기

이전 글에서는 커맨드(Command) 패턴을 모던 C++20 이상 관점에서 재해석하며, 상속 기반 명령 클래스 대신 람다, Concepts, std::function, std::expected, coroutine, Ranges, std::format 등을 활용해 더 간결하고 확장성 높은 명령 시스템을 구현하는 방법을 살펴보았습니다. 이번 글에서는 행동(Behavioral) 패턴 중 인터프리터(Interpreter) 패턴을 다룹니다.인터프리터 패턴은 언어(DSL, 간단한 명령어 집합)나 표현(Expression)을 해석하는 로직을 객체로 캡슐화하는 패턴입니다. 전통적으로는 상속 기반 Expression 인터페이스, 각각의 구체 표현 클래스(NonterminalExpression, TerminalExpres..

• format_list_bulleted 개발 이야기/C++
• · 2024. 12. 16.
• textsms

[코드 인터뷰 대비 시리즈 #6] 동적 프로그래밍(DP) 문제 접근 패턴 정리

여러분, 알고리즘 인터뷰에서 동적 프로그래밍(DP) 문제를 접하면 많은 지원자가 “복잡하고 난해해”라며 당황하기 쉽습니다. DP는 문제를 작은 하위 문제(subproblem)로 나누고, 하위 문제의 해를 저장(memoization)하거나 테이블(tabulation)로 관리하여 중복 계산을 제거하는 기법입니다. 제대로 이해하고 패턴을 파악하면 DP 문제도 체계적으로 접근할 수 있으며, 면접 중에도 당황하지 않고 논리적으로 문제를 풀어나갈 수 있습니다.이번 글에서는 DP 문제를 만났을 때 어떤 접근 방법을 사용할지, 점화식(Recurrence Relation)을 어떻게 세우는지, 탑다운(Top-Down)과 바텀업(Bottom-Up) 접근 차이, 코너 케이스 처리, 복잡도 분석, 그리고 면접 상황에서 이 모든..

• format_list_bulleted 미국 빅테크/코드 인터뷰
• · 2024. 12. 16.
• textsms

[모던 C++로 다시 쓰는 GoF 디자인 패턴 총정리 #14] 커맨드(Command) 패턴: 함수 객체와 코루틴으로 실행 명령 캡슐화하기

커맨드(Command) 패턴은 실행할 작업(명령)을 객체로 캡슐화하여, 명령을 매개변수로 전달하거나 큐잉, Undo/Redo, 비동기 실행 등의 기능을 가능하게 하는 중요한 패턴입니다. 하지만 전통적 구현(특히 C++98/03, 심지어 C++11/14/17 시절)에서는 다음과 같은 단점이 있었습니다.전통적 방식:추상 커맨드 인터페이스(abstract Command) 정의이를 상속하는 구체 커맨드 클래스 다수 정의 → 클래스 수 증가, 유지보수성 저하Undo/Redo, 비동기 처리, 로깅 추가 시 복잡성 폭발명령 교체, 에러 처리 등 구현이 번거로움하지만, C++20 이상 모던 C++에서는 람다, std::function, Concepts, std::expected, std::format, coroutin..

• format_list_bulleted 개발 이야기/C++
• · 2024. 12. 16.
• textsms

[모던 C++로 다시 쓰는 GoF 디자인 패턴 총정리 #13] 책임 연쇄(Chain of Responsibility) 패턴: 함수 파이프라인과 Concepts로 동적 요청 처리하기

이전 글에서는 상태(State) 패턴을 모던 C++ 관점에서 재해석하며, 상속 기반 상태 클래스와 vtable에 의존하지 않고 std::variant, std::visit, Concepts, std::expected, std::format, Coroutines 등을 활용해 더 선언적이고 유지보수성 높은 상태 전이 로직을 구현할 수 있음을 확인했습니다. 이번에는 행동(Behavioral) 패턴 중 책임 연쇄(Chain of Responsibility) 패턴을 다룹니다.책임 연쇄 패턴은 요청(request)이 처리될 수 있는 핸들러(handler)들을 체인 형태로 연결하고, 각 핸들러가 요청을 처리하거나 다음 핸들러로 넘기는 구조를 제안합니다. 전통적으로는 상속 기반 핸들러 클래스 계층을 정의하고, setN..

• format_list_bulleted 개발 이야기/C++
• · 2024. 12. 16.
• textsms