분류 전체보기
-
[자료구조] 이진 탐색 트리 (Binary Search Tree)Study/자료구조,알고리즘 2022. 9. 22. 15:59
01. 이진 탐색 트리란? 이진 탐색 트리는 이진트리 기반의, 탐색을 용이하게 하기 위한 자료구조 탐색을 위한 키 값 기준으로 정렬된다. 이진 탐색 트리의 정의는 다음과 같다. 1. 모든 노드는 유일한 키를 갖는다. 2. 왼쪽 서브트리의 키는 루트의 키보다 작다. 3. 오른쪽 서브트리의 키는 루트의 키보다 크다. 4. 왼쪽과 오른쪽 서브트리도 이진트리이다. 02. 이진 탐색 트리의 연산 이진 탐색 트리는 삽입, 삭제 과정에서 이진트리의 특성을 유지해야 한다. 탐색 탐색 연산은 키 값 비교를 통해 왼쪽과 오른쪽 노드를 탐색할지 결정한다. 찾고자 하는 키 값과 현재 노드의 키 값이 일치한다면 탐색 성공 찾고자 하는 키가 현재 노드보다 작다면, 왼쪽 노드로 이동해 다시 탐색한다. 찾고자 하는 키가 현재 노드보..
-
ASCII와 Unicode, UTF-8Study/컴퓨터 구조 & 운영체제 2022. 9. 21. 21:36
01. 문자열 인코딩 (Character Set) 문자열을 n개의 byte로 이루어진 정수형으로 치환하여 프로그램에서 사용하는 것이다. 인코딩 방식으로 UTF-8, Multibyte, ASCII가 있다. 02. ASCII, Multibyte, WideChar, UTF-8 (그리고 UNICODE) 유니코드(UNICODE)는 ASCII Chracter Set에 포함되지 않은 문자(한국어 등) 을 표현하기 위한 방식이다 ASCII는 1Byte로 영어, 수학 기호 등이 표현되며, 1Byte인 만큼 최대 255개의 문자를 표현할 수 있다. 멀티바이트는 1바이트로도, 2Byte로도 문자가 표현될 수 있는 가변 인코딩 형식이다. 특정 문자 집합마다 (한국어, 중국어 등) 코드 페이지라는 것이 존재하며, 특정 코드 페..
-
[C++ 쉽게 풀어쓴 자료구조] 프로그래밍 프로젝트 8Study/자료구조,알고리즘 2022. 9. 20. 15:43
완전 이진트리 검사 함수 구현 완전 이진트리란 높이n 의 트리에서 n-1레벨까지는 포화상태, n레벨의 노드들은 왼쪽부터 채워져 있는 상태인 이진트리를 의미한다. 완전 이진트리 검사는 레벨 순회를 통해 구현했다. Left와 Right중 하나라도 null node일 경우, 그 이후 나타나는 노드들은 모든 노드가 단말노드여야 한다. bool CBinaryTree::IsFull() { std::queue bQueue; bQueue.push(m_Root); while (!bQueue.empty()) { bool meetNotFull = false; CBinaryNode* node = bQueue.front(); // full node라면 계속 탐색한다. if (node->GetLeft() && node->GetR..
-
[프로그래머스] Level1 - 완주하지 못한 선수코딩 테스트 2022. 9. 20. 10:42
1. 문제 설명 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요. 제한사항 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. completion의 길이는 participant의 길이보다 1 작습니다. 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다. 참가자 중에는 동명이인이 있을 수 있습니다. participant completion return ["leo, "kiki", ..
-
[열혈 TCP/IP 소켓 프로그래밍] Chapter2. 내용 확인문제Study/Network 2022. 9. 19. 19:50
01. 프로토콜이 무엇인가? 프로토콜이란, 데이터의 전송 방식을 결정하는 규약이다. 두 컴퓨터 간 프로토콜을 정의해야 데이터 전송 방식을 서로 알고 해석할 수 있다. 02. 연결지향 소켓 TCP의 전송 특성 3가지 데이터의 손실이 없음이 보장된다. 데이터의 경계가 없다 데이터의 전송 순서가 보장된다. 03. 비연결지향 소켓 UDP의 전송 특성 데이터의 손실이 있을 수 있다. 빠른 전송을 목표로 한다. 한 번의 전송에 데이터의 크기가 제한된다. 연결이라는 개념이 존재하지 않는다. 04. 유형별 적합한 타입의 소켓은? 실시간 스트리밍 : UDP 소켓. 빠른 전송이 목표가 되어야 하고, 데이터가 손실되더라도 최신의 데이터를 계속 받는 것이 더 중요하다. 텍스트 파일 전송 : TCP 소켓. 순서가 무조건 보장되..
-
[C++] 복사 생성자와 RVO, NRVOStudy/C & C++ 2022. 9. 19. 16:24
01. 복사 생성자란? 같은 타입의 인스턴스를 매개변수로 받는 생성자를 의미한다. class A { public: A() {}; A(const A& a){}; // Copy Constructor }; 02. 복사 생성자가 호출되는 경우 복사 생성자가 호출되는 경우는 세 가지이다. 기존 생성 객체를 사용해 새로운 객체를 초기화하는 경우 Call-By-Value 형식으로 함수의 매개변수를 전달할 때 Value 형태로 함수에서 return할 때 A origin; // 1. A copy(origin); A copy1 = origin; // 2. void Copy(A a) { // do something } // 3. A Copy2() { return A(); } 그렇다면, 아래 코드의 결과는 어떨까? #incl..
-
[뇌자극 시스템 프로그래밍] 01. 컴퓨터 구조에 대한 간략한 이해Study/컴퓨터 구조 & 운영체제 2022. 9. 17. 19:41
01. 시스템 프로그래밍이란? 좁게는 하드웨어를 사용할 수 있게 도와주는 프로그램을 만드는 것 (Operating System) 넓게는 운영체제에서 제공하는 라이브러리를 사용해 해당 운영체제의 컴퓨터에 일을 시키기 위한 프로그램을 만드는 것 02. 컴퓨터 하드웨어 구성 1. CPU의 구성 요소 ALU (Arithmetic Logic Unit) : 실제 연산 (산술, 논리)를 수행하는 장치이다. Control Unit : 명령어를 해석하고, 해석 결과에 따른 신호를 CPU의 다른 장치에 전송한다. Register Set : CPU내의 작은 메모리, 명령어 등을 임시 저장하고 ALU와 Control Unit이 가져다 쓰도록 한다. Bus Interface : I/O Bus의 통신방식과 프로토콜을 이해하고 있..
-
[자료구조] 스레드 이진트리 (Thread Binary Tree)Study/자료구조,알고리즘 2022. 9. 17. 17:46
01. What 이진트리의 순회를 위해 queue와 같은 다른 자료구조를 사용하거나, recursive function을 호출하지 않고 순회하기 위해 만들어진 트리 02. Idea 이진트리의 노드가 총 N개일 때, 연결(Link)는 총 2N개 존재할 수 있다. 이 중 루트를 제외한 N-1개의 링크가 존재하고, 나머지 N+1개는 NULL Link(연결이 없는 상태)이다. 스레드 이진트리는 이 NULL Link를 다음 순회 대상을 가리키는 용도로 사용해서 구현한다. 노드의 오른쪽 자식이 없는 경우, 다음 순회 대상을 가리키는 순회 후속자(succeedor)를 가리키도록 해서 구현한다. 단순한 이진트리와 달리 오른쪽 노드가 Thread인지 아닌지를 구분하기 위한 bool 변수가 Node 클래스에 추가된다. 0..