본문 바로가기

자료구조15

[Java] Graph (Adjacency Matrix, Adjacency List) 정점(Vertex)과 간선(Edge)로 구성된 것, Graph(G) = (Vertex(V), Edge(E)) Graph 용어 정점(Vertex) - 노드, 특정할 수 있는 실체간선(Edge) - 정점 간 이어져 있는 선가중치(Weight) - 정점 간에 거리, 비용 (간선의 길이라고 생각해도 좋음)경로(Path) - 출발 정점에서 도착 정점까지의 거쳐 간 순서순환(Cycle) - 경로의 출발 정점과 도착 정점이 같은 경우차수(Degree) - 정점에 붙은 간선 수진입 차수(In-Degree) - 정점으로 들어오는 간선 수진출 차수(Out-Degree) - 정점에서 나가는 간선 수Graph 종류 유향 그래프(Directed Graph) - 특정 정점에서 특정 정점으로 이동하는 그래프무향 그래프(UnDire.. 2024. 7. 9.

[Java] Binary Search Tree 앞 포스팅에서 작성한 Tree의 비효율적인 문제를 개선하기 위해 생긴 이진 탐색 트리다.트리는 여러 자식을 가질 수 있지만 이진 검색 트리에서는 Binary Tree의 개념을 사용하기 때문에자식이 Left, Right만 존재한다. 이를 통해 Log_2 (N) 번만에 모든 수행을 끝낼 수 있다. 또, inorder를 수행 시 오름차순 정렬된 결과를 얻을 수 있다. package com.study.datastructrue.nonlinear.binarysearchtree;public class Node { int value; Node left; Node right; public Node(int value) { this.value = value; left = null;.. 2024. 7. 8.

[Java] Tree 트리 자료구조의 종류 : Tree, Binary Tree, Binary Serach Tree, Balanced Binary Serach Tree, Heap, Trie이번 포스트에서는 기본적인 Tree에 대해서만 작성해보자. Tree란 ? Node와 Edge로 구성된 방향이 존재하는 비순환 Graph의 한 종류이다. 그래서 DAG(Directed Acyclic Graphs)라고도 한다.그럼 Graph로 분류하면 되지 왜 Tree냐는 의심을 하게 된다.Tree는 Graph에서 몇가지 특성을 더 가진다. 1. 루트 노드가 하나 존재한다.2. 부모 노드는 하나밖에 존재하지 않는다.3. 노드는 0개 이상의 자식을 가지고 있다.4. 자식이 0개인 경우 단말노드(Leaf Node)라고 한다.5.. 위 특성을 지키는 .. 2024. 7. 7.

8. 프로세스 제어 블록 (PCB, Process Control Block) PCB란? 프로세스 제어 블록은 프로세스 정보를 담고 있는 하나의 단위이다. PCB 하나에는 프로세스 정보(PID, PPID, Process Status, ... )를 가지고 있다. 해당 내용은 외우고 있을 필요는 없다. 실제 시스템 프로그래밍을 하게 될 때, 이 정보를 컨트롤하게 된다. PCB가 왜 필요할까? 다중 프로그래밍 기법을 생각해보자. 중간에 인터럽트가 발생해서 CPU가 처리하고 있던 프로세스를 잠시 인터럽트 처리하고 다른 프로세스를 발생해야한다. 그 이유는 CPU Idle Time을 줄이기 위해서이다. 이 때, 다른 프로세스를 실행하고 interrupt가 종료되면 기존의 프로세스를 이어서 처리해야한다. 여기서 기존의 프로세스로 전환하는 과정을 컨텍스트 스위칭(Context Switching).. 2024. 4. 21.

7. 프로세스 (Process) 본격적인 운영체제 개념 이전까지는 운영체제를 알기 위한 전반적인 흐름이나 기본적인 지식을 설명하는 내용이었다. 운영체제의 시작을 알리는 프로세스란 도대체 무엇일까? 우리는 Chrome, Kakao Talk와 같은 Application을 프로그램이라고 부른다. 이 녀석들은 HDD나 SSD에 저장되어있다. 바로가기 icon에 대해 '우클릭 - 속성 - 파일위치열기'를 눌러보면 정확한 프로그램을 찾을 수 있다. windows에서는 Chrome.exe와 같은 *.exe 확장자가 붙는데 이것을 프로그램이라고 한다. 앞에서 프로세스도 *.exe라고 다룬적이 있다. 맞지만 조금 다르다. exe 파일에는 코드, 데이터, 스택, 힙 공간이 목적 코드로 작성되어있는데 이 실행파일을 실행했을 경우 메모리에 적재되는데 실행 .. 2024. 4. 21.

백준 - [BOJ 3085] 사탕게임 백준 온라인 져지(BOJ)에서 제공 되는 3085번 문제는 브루트 포스(Brute-Froce, 완전 탐색) 유형이다. 해당 문제는 code.plus 기초 2/2, 브루트포스에 게시된 문제이다. 문제 상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다. 가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다. 사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 보드의 크기 N이 .. 2024. 3. 1.

백준 - [BOJ 12094] A와 B 백준 온라인 져지(BOJ)에서 제공 되는 12094번 문제는 그리디(Greedy, 탐욕법) 유형이다. 해당 문제는 code.plus 중급 1/3, 그리디 알고리즘에 게시된 문제이다. 문제 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈이는 간단한 게임을 만들기로 했다. 두 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게임이다. 문자열을 바꿀 때는 다음과 같은 두 가지 연산만 가능하다. 문자열의 뒤에 A를 추가한다. 문자열을 뒤집고 뒤에 B를 추가한다. 주어진 조건을 이용해서 S를 T로 만들 수 있는지 없는지 알아내는 .. 2024. 2. 29.

6. STL 사용하기 - std::list STL 이란? C++ 에서 제공하는 STandard Library를 STL이라고 한다. 자바에서는 자바에서 제공하는 API라고 볼 수 있다. 지금까지 list에 대해 직접 설계해보았고 list에 대한 설명이 충분했다. 이번에는 STL을 직접 사용하면서 어떤 기능이 있고 언제, 어떻게 사용할 지 생각해보도록 하자. ※ 시간이 오래 걸리는 Method는 제외한다. (효율적 사용) std::list Construct Method Description (constuctor) 리스트 생성시 입력 값 operator= = 기호에 대한 연산 방법 Iterators Method Description begin() 리스트 Head에 속한 데이터 위치 end() 리스트 마지막 위치 != Tail, null 값 rbegin.. 2024. 2. 11.

5. 원형 연결 리스트 (Circular Linked List) 원형 연결 리스트란? 단순 연결 리스트에서 끝이 처음과 연결되어 있는 형태를 원형 연결 리스트라고 합니다. STL에도 구현되어있지 않고 아직 학생 수준이지만, 실제로 사용되는 경우도 본 적이 많이 없습니다. 그래서 단순하게만 만들어보도록 할 것인데, 이중 연결 리스트 형태로 만들려고 합니다. (실제로 순환적인 요소는 큐 또는 재귀를 많이 사용하는듯) 원형 연결 리스트(Circular Linked List) 구현하기 많은 기능을 추가하지는 않겠습니다. 노드 #pragma once template class Node { public: Node(T data); T getData() const; Node* getNext() const; Node* getPrev() const; void setNext(Node* .. 2024. 2. 10.

이전 1 2 다음

티스토리툴바