전체 글

[CS - 자료구조] 이진 탐색 트리 (BST, Binary Search Tree), Red-Black Tree

이진 탐색 트리 (Binary Search Tree) 배경 이진 트리에서 데이터를 효과적으로 찾는 방법을 고민함 데이터를 효과적으로 찾기 위해 데이터를 효과적으로 저장하는 것이 더욱 효율적이다는 아이디어를 고안해냄 개념 이진 트리 기반의 데이터 탐색을 위한 자료구조 (이진 트리 + 데이터 저장 규칙) 데이터 저장과 동시에 정렬을 하는 자료구조 이진 트리의 효율적인 탐색 능력을 가지며, 삽입과 삭제 가능 조건 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드 모든 노드에서 위의 조건을 충족 모든 노드는 유일한 키를 가짐 (노드 중복값 없음) operation 시간복잡도 (검색, 저장, 삭제 등) O(logn) worst case : 편향 트리 (skewed tree) → 한쪽으로만 노드가 추가되는 것 이..

[CS - 자료구조] 트리 (Tree), 이진 트리 (Binary Tree)

트리 (Tree) 개념 선형 구조인 큐, 스택과 달리, 비선형 구조로 계층적 관계(Hierarchiral Relationship)를 표현하며 데이터를 저장하는 자료구조 그래프의 한 종류이며, 사이클이 허용되지 않는 그래프 (자기 자신으로 돌아오지 않는) 용어 노드 (Node) : 트리를 구성하는 각각의 요소 간선 (Edge) : 노드를 연결하는 선 루트 노드 (Root Node) : 트리 구조에서 최상위에 있는 노드 단말 노드 (Leaf Node 또는 Terminal Node) : 하위에 다른 노드가 없는 노드 (맨 끝에 있는 노드) 내부 노드 or 비단말 노드 (Internal Node) : 단말 노드를 제외한 모든 노드 (루트 노드도 포함) 레벨 (Level) : 노드가 몇 층인지 나타냄 (루트 노드..

[CS - 자료구조] 그래프 (Graph)

그래프 (Graph) 개념 요소들이 서로 복잡하게 얽혀있는 연결 관계를 정점(vertex)과 간선(edge)으로 표현한 자료구조 스택, 큐처럼 CS의 대표적인 자료구조 중 하나 현실 세계의 많은 것들을 그래프로 나타낼 수 있어서 알고리즘 문제에 그래프 유형이 많음 cf) 트리 또한 그래프의 한 종류이며, 사이클이 허용되지 않는 그래프를 의미함 용어 정점 (Vertex, Node) 데이터가 저장되는 기본 원소 간선 (Edge, Link) 정점간의 관계를 나타내는 선 인접 정점 (Adjacent Vertex) 하나의 정점에서 간선으로 직접적으로 연결된 정점 차수 (degree) 각 정점에 연결되어 있는 간선의 수 진입 차수 (in-degree) : 방향 그래프에서 해당 정점으로 외부에서 오는 간선의 수 진출..

[CS - 자료구조] 해시 테이블 (Hash Table)

해시 테이블 (Hash Table) 배경 직접 주소화 테이블 (Directed Address Table) 의 단점을 보완하기 위해 직접 주소화 테이블 (Directed Address Table) key, value를 저장할 때 key값으로 k를 갖는 원소는 index k에 저장하는 방식 (key를 그대로 인덱스로 쓰는 테이블) key가 적절(배열의 인덱스로 쓰기 적절)하면 상관이 없음 ex) (2,”노정호”), (1,”배준석”), (4,”정재헌”) 만약 (학번, 이름)이나 (아이디, 닉네임) 등의 key, value를 저장하는 상황에 문제가 발생 (201622528, 박강욱) → 배열의 201622528 번째 공간에 value 저장 → 메모리 공간 낭비 발생 (syunxttm, 박강욱) → 배열의 syu..

[iOS - Swift] Networking 테스트 코드 작성하기 (feat. URLSession)

배경 및 원리 오늘은 Network 환경에서 테스트 코드를 작성하는 방법을 알아보려고 함. iOS 환경에서 가장 기본적인 Networking 기술은 URLSession이고, 나 또한 지금 URLSession을 사용하기 때문에 URLSession 환경에서의 테스트 코드를 작성해보려고 함. 여기에 필요한 건 Test Double 개념이고, 그중에서도 Stub 또는 Mock 개념이 필요함. (*현업에서는 상태와 행위를 동시에 검증하는 경우가 많아서 ‘Mock’으로 퉁쳐서 사용한다고 함) 이게 뭐임? Unit Test로 URLSession의 통신 자체를 테스트할 수도 있지만(status code가 200인지), 통신으로 받은 데이터를 잘 가공하는지 테스트해야 함. (통신이 잘 된 후 그 다음 과정을 검증하는 것..

[iOS - Swift] 의존 관계 역전 원칙 (DIP, Dependency Inversion Principle)

안녕하세요 K입니다. 오늘은 의존 관계 역전 원칙(DIP,Dependency Inversion Principle)에 대해 알아보겠습니다. DIP에 대해 많이 들어보셨나요? 저는 이번에 Unit Test 코드를 작성 중 MockURLSession 테스트 코드를 작성하면서 이 개념을 만났는데요, 쉽게 이해가 안되기도 하고, 굉장히 중요한 개념이기도 해서 이번 기회에 제대로 공부해보았습니다. 의존 관계 역전 원칙(DIP,Dependency Inversion Principle)이 필요한 이유 우선, 의존 관계 역전 원칙(이하 DIP)을 공부하기 전에 제 성향상 이 개념이 필요한 이유와 상황부터 알아야 하는 지라 이것부터 알아보겠습니다. (특정 개념을 공부하면서 그 이유와 목적을 모른다는 것은 말이 안되겠죠?) ..

[iOS - Swift] TDD를 위한 Unit Test 코드 작성하기 (Feat. XCTest)

안녕하세요, 이번에는 Unit Test 코드를 작성하는 방법에 대해 알아보겠습니다. 이전부터 워낙 테스트 코드에 대해 많이 들었어서 중요성은 알고 있었지만, 얼핏 들은 세션에서 너무 어렵게 느껴지는 바람에 지레 겁을 먹은 적도 있습니다. (첫인상이 안좋았습니다.) 하지만 테스트 코드를 넘어 TDD와 CI/CD를 위해서라면 꼭 짚고 넘어가야 하는 개념이기 때문에 꼼꼼히 살펴보도록 하겠습니다. 틀린 부분은 댓글로 언제든지 알려주시면 감사하겠습니다! 왜 테스트 코드를 짜야 하는가? 저는 무언갈 공부하기 전에 그것의 쓰임이나 용도, 필요성을 확실히 느껴야 하는 스타일입니다. 도대체 우리는 왜 테스트 코드를 짜야 하고 저는 이걸 왜 배워야 할까요? '테스트' 코드는 말 그대로 무언갈 시험해보기 위한 코드입니다. ..

[iOS] 의존성 주입(Dependency Injection, DI)이 객체의 결합도를 낮춰주는 이유 (Feat. Car)

의존성 주입(DI)은 의존성 생성 및 관리를 종속되는 객체와 분리하기 때문에 객체의 결합을 줄여줍니다. 즉, 객체는 의존성이 어떻게 생성되거나 관리되는지 알 필요가 없으므로 의존성은 줄어들고 더 모듈화되고 유지 관리가 쉬워집니다. 이를 더 잘 이해하기 위해 예를 들어 보겠습니다. 자동차를 만들고 있다고 상상해 보세요. 자동차에는 엔진, 변속기, 바퀴와 같은 여러 구성 요소가 있습니다. 각 구성 요소에는 엔진용 연료, 변속기용 오일, 타이어용 공기 등 고유한 의존성 집합이 있습니다. 이제 자동차의 엔진을 교체하고 싶다고 가정해 보겠습니다. 긴밀하게 연결된 시스템에서는 엔진에 종속된 모든 구성 요소를 새 엔진에 맞게 수정해야 할 수 있습니다. 예를 들어, 새 엔진의 출력에 맞게 변속기를 변경하거나 새 엔진의..