노랑꼬리의 개발 블로그

목차 ※ 트리 #1 Tree ※ 트리 #2 DFS 1. 너비 우선 탐색이란? 2. BFS 구현 1. 너비 우선 탐색이란? (BFS : Breath First Search) - 그래프의 인접한 정점을 우선적으로 탐색 - queue를 이용하여 구현한다. - 장점 : 탐색된 경로가 항상 최단 경로이다, queue를 사용하여 다음 탐색 정점을 지정하므로 DFS 보다 메모리를 적게 사용한다. - 단점 : 목표 노드의 깊이가 깊은 경우 탐색이 오래 걸린다. 2. BFS 구현 (※ 입력 기준 : BFS 애니메이션) ※ 참조 위키 백과 너비 우선 탐색 : https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

목차 ※ 트리 #1 Tree 1. 깊이 우선 탐색이란? 2. DFS 구현 1. 깊이 우선 탐색이란? (DFS : Depth First Search) - 그래프에서 깊은 부분을 우선적으로 탐색 - 리프 노드에 도달 할 때 까지 목표 노드를 탐색, 발견 되지 않으면 현재 탐색 중인 노드의 부모 노드에서 탐색 되지 않은 자식 노드를 탐색한다. (백 트래킹 : backtracking) ㄴ 노드 방문 시 방문 여부를 검사해야 무한 루프를 방지할 수 있다 (탐색 된 노드 재탐색 방지) - 장점 : 현재 경로만 저장하며 탐색하므로 메모리를 적게 사용한다 (단순 탐색에 비해), 목표 노드가 깊이 있다면 빠르게 구할 수 있다. - 단점 : 탐색된 결과가 최단 경로가 아닐 수 있다. (목표 경로가 여럿일 경우), 목표 노..

목차 1. 트리의 구성요소 2. 트리 구현 1. 트리의 구성요소 Tree는 컴퓨터 친화적인 선형 자료구조가 아닌 사용자 친화적인 비선형 계층 자료 구조이다. 사용자가 원하는 데이터를 얻기 쉽도록 데이터를 구분하여 연결해 준다. ex) 컴퓨터 파일 경로, 회사 조직도 가. 노드(Node) - 트리의 각 요소 - 데이터를 저장하고 다음 노드로 연결 시켜줄 주소 값이 저장되어 있다. 1) 루트 노드 - 트리 구조에서 최상위 노드 (트리 예시 기준 A) - 부모 노드가 없음 2) 부모 노드 - 해당 노드와 연결 된 윗 노드 (트리 예시 기준 D와 E의 부모 노드 : B) 2-a) 조상 노드 - 해당 노드에서 루트 노드까지 경로 상의 윗 노드 들 (트리 노드 예시 기준 H의 조상 노드 : D, B, A) 3) 자..

목차 ※ STL #1 순차 컨테이너 ※ STL #2 연관 컨테이너 ※ STL #3 Stack & Queue 1. Heap 2. Priority_queue 1. Heap - 완전 이진 트리 (Complete Binary Tree) 기반 자료구조 ㄴ 이진 트리 : 자식 노드가 최대 두 개인 노드들로 구성된 트리 ㄴ 완전 이진 트리 : 마지막 레벨을 제외하고 모든 레벨이 완전히 채워진 이진 트리 ※ 마지막 레벨은 왼쪽 부터 순차적으로 채워져야한다. - 최대값 혹은 최소값을 빠르게 구하기 위한 자료구조 - 부모 자식 간의 관계만 중요하고 형제 노드와는 관계성이 없다. - Min Heap : 부모 노드가 자식 노드보다 항상 작다 (= 루트 노드가 최소값이다) - Max Heap : 부모 노드가 자식 노드보다 항상..

목차 ※ STL #1 순차 컨테이너 ※ STL #2 연관 컨테이너 1. stack 2. queue 1. std::stack - LIFO (Last In First Out : 후입선출) 데이터 구조 ㄴ 마지막에 삽입된 데이터가 가장 먼저 삭제된다. (사용처 예시 : ctrl + z, DFS(깊이 우선 탐색) ) - deque를 바탕으로 만들어져 있다. 가. 선언 및 초기화 template //template ≒ 자유 자료형 std::stack //T : 배열에 담길 자료형 - stack s1; // 빈 스택 생성 - stack s2( {'a', 'b', 'c'} ) // 생성과 동시에 초기화 - stack s3(s2); // s2의 값을 복사하여 s3 스택 생성 나. 멤버 함수 (※ 기준 : stack s..

목차 ※ STL #1 순차 컨테이너 1. set & multiset 2. map & multimap 가-B. 연관 컨테이너 (associate container) - key와 같은 특정 정렬 기준(연관)에 따라 원소를 정렬하는 컨테이너 - 정렬 기준에 따라 정렬이 되므로 특정 위치를 지정한 접근 및 참조가 불가능 하다. - 노드 기반 컨테이너이다. - 균형 이진트리로 구성되어 있다. - 찾기 연산이 매우 빠르다. (균형 이진트리 때문) 1. std::set & std::mulitset - set은 원소 자체가 key가 되어 분류된 균형 이진 트리이다. - key는 유일해야 하며 key == 원소 이므로 데이터의 중복이 허용되지 않는다. ㄴ mulitset에서는 키의 중복을 허용한다. (key의 중복허용을..

목차 1. STL 2. array 3. vector 4. deque 5. list 1. STL의 구성요소 STL는 표준 템플릿 라이브러리(Standard Template Library)의 약자이다. 컨테이너, 반복자, 알고리즘, 함수자 네 가지의 구성 요소를 제공한다. 가. 컨테이너(Container) - 데이터를 저장해주는 객체 나. 반복자(Iterator) - 컨테이너에서 보유하고 있는 내부 원소들을 순회할 수 있는 객체 - 포인터와 비슷한 역할을 한다. 다. 알고리즘(algorithm) - 컨테이너 내부 객체를 다루기 위해 검색, 비교, 정렬, 수정 등의 동작을 한다. - 컨테이너에 따라 사용가능한 알고리즘이 정해져있다. (효율성 때문에 적합하지 않은 컨테이너 미지원) 라. 함수자(functor) ..

※ 모듈화 : 소프트웨어를 성능 향상이나 수정, 재사용이 용이하도록 모듈 단위로 분해하여 나누는 것 - 모듈은 단독으로 컴파일이 가능한 최소 단위 - 각 모듈의 독립성이 높을 수록 좋은 모듈이다. - 결합도가 약할 수록, 응집도가 높을 수록 좋은 모듈이다. (결합도가 약하면 다른 모듈과 별개로 단독 사용가능) (응집도가 높으면 모듈 내부 요소가 서로 관련성이 높아 일처리가 효율적이다) 1. 결합도(Coupling) : 약할 수록 좋은 모듈 - 모듈간 상호 의존 정도, 두 모듈 사이의 연관 관계 - 결합도가 강하면 모듈 수정 및 유지보수가 어려워짐 결합도 약함 ↑ ↓ 결합도 강함 자료 결합도 (Data Coupling) 모듈 간 인터페이스가 자료 요소로만 구성되는 결합도, 다른 모듈 호출 시 매개변수나 인..

1. 개념 외부에서 인식할 수 있는 특성이 담긴 소프트웨어의 골격이 되는 기본 구조 시스템 전체에 대한 큰 밑그림 2. 특징 - 개발할 소프트웨어에 대한 전체적인 구조를 다룸 - 소프트웨어를 이루고 있는 여러 구성 요소 (서브 시스템, 컴포넌트)를 다룸 - 구성 요소들이 인터페이스를 통해서 어떻게 상호작용하는지를 정의 - 세부 내용 보다는 중요한 부분을 다룸 - 시스템 설계와 개발 시 적용되는 원칙과 지침이 있어야 함 3. 아키텍처 설계 시 고려사항 - 모든 이해관계자의 이해를 도울 수 있는 의사소통 도구로 활용할 수 있어야 함 - 개발 비용, 기간, 조직의 역량 등의 제약 사항을 정의해야 함 - 시스템 품질 속성(성능성, 사용성, 보안성, 안전성, 검증성, 변경성 등)의 우선순위를 결정해야 함 - 소프..

1. 개념 요구분석, 시스템 설계, 시스템 구현 등의 시스템 개발 과정에서, 개발자간의 의사소통을 원활하게 이루어지게 하기 위하여 표준화한 모델링 언어 소프트웨어 개발 시 산출물들을 비주얼하게 제공하여 개발자와 고객 또는 개발자 상호 간의 의사소통을 원활하게 할 수 있다. 2. 다이어그램의 구성 1) 액터 : 시스템 외부에서 시스템과 상호작용을 하는 사람이나 다른 시스템 (사용자) 2) 시스템 : 개발하고자 하는 어플리케이션 3) 유스케이스 : 시스템이 액터에게 제공해야 하는 기능 4) 관계 : 액터와 유스케이스들 사이의 의미있는 관계 3. 다이어그램의 종류 1) 구조 다이어그램 (정적 모델링) - 시스템의 정적 구조와 다양한 추상화 및 구현 수준에서 시스템의 구성 요소, 구성 요소들 간의 관계를 보여줌..