화요밍의 개발로그

맵 Map 자료구조란? 저장된 데이터가 키 key와 값 value로 하나의 쌍을 이루는 자료구조를 말합니다. 키가 존재하지 않는 값은 저장할 수 없으며, 모든 키는 중복되지 않습니다. 키를 통해 값을 바로 구할 수 있으므로 데이터를 검색하는데 O(1)의 시간복잡도가 소요됩니다. 배열을 기반으로 하는 Map 배열을 기반으로 맵을 구현하면 index 값으로 데이터를 저장 및 검색이 가능하므로 O(1)이 소요됩니다. 그러나 배열은 컴파일 이전에 크기를 정해줘야 하므로 배열 사이즈를 넘어가는 key 값은 사용할 수 없는 문제가 있습니다. 즉, key값의 범위가 배열 사이즈를 초과하는 경우 수용할 수 없습니다. 이러한 문제를 해결하기 위해 나온 자료구조가 해쉬 테이블 Hash Table입니다. 해시 테이블 Has..

그래프 Graph란? 간선 Edge과 정점 Vertex으로 이루어진 자료구조이며, 정점 간의 관계를 표현하는 조직도입니다. 정점에는 데이터가 저장되며, 간선을 통해 정점과 정점 사이의 관계를 알 수 있습니다. 그래프 용어 정점(Vertex, 노드 Node): 데이터가 저장됨 간선(Edge, 링크 Link): 정점들을 연결하는 선, 정점과 정점 사이의 관계를 표현 인접 정점(Adjacent Vertex): 간선에 의해 연결된 정점(6과 4는 서로 인접 정점임) 차수(Degree): 무방향 그래프에서 각 정점에 연결된 Edge의 개수(5의 차수는 3) 진출 차수(Out-degree): 방향 그래프에서 각 정점으로부터 나가는 간선의 개수 진입 차수(In-degree): 방향 그래프에서 각 정점으로 들어오는 간..

트리 Tree란? 계층적 관계(Hierarchical Relationship), 부모-자식 관계를 표현하는 비선형 자료구조입니다. 트리는 사이클이 없고, 서로 다른 두 노드를 잇는 길이 하나인 그래프의 일종입니다. 컴퓨터의 Directory 구조, 조직도, 족보 등이 트리의 대표적인 예입니다. 트리 구성요소 노드 Node: 트리를 구성하고 있는 각각의 요소 간선 Edge: 트리를 구성하기 위해 노드와 노드를 연결하는 선, 노드가 N개이면 간선은 N-1개를 가짐 루트 노드 Root Node: 트리 구조에서 최상위에 있는 노드 단말 노드 Terminal Node(외부 노드 External Node, Leaf Node): 자식 노드가 없는 노드 내부 노드 Internal Node(비단말 노드): 하나 이상의 ..

스택 Stack 나중에 들어간 원소가 먼저 나오는 후입선출, Last In First Out(LIFO)의 선형 자료구조입니다. 접시처럼 차곡차곡 쌓이는 구조로 데이터를 삽입하면 Top에 위치하며, Pop 연산을 할 때 Top에 위치한 데이터가 빠져 나옵니다. 데이터의 삽입/삭제는 O(1)의 시간복잡도가 소요됩니다. 스택의 활용 웹 브라우저 방문기록(뒤로가기): 가장 나중에 열린 페이지부터 다시 보여줌 연산자 후위 표기법 계산 수식의 괄호 검사: 연산자 우선순위 표현을 위한 괄호 검사 프로그램에서의 시스템 스택 실행 취소(Undo): 가장 나중에 실행된 것부터 실행을 취소함 역순 문자열 만들기: 가장 나중에 입력된 문자부터 출력 안드로이드의 액티비티: 사용자의 동작으로 인해 새로운 화면이 띄워지면 Push..

1. 프로세스와 쓰레드의 정의 프로세스 Process 프로세스는 실행 중인 프로그램을 말하며, 운영체제 입장에서의 작업 단위입니다. 디스크로부터 메모리에 적재되어 CPU의 할당을 받을 수 있는 것을 말합니다. 운영체제는 프로세스에 스택, 힙, 데이터 영역, 코드 영역을 할당합니다. * 프로세스의 생성 프로그램이 CPU에 의해 실행된다. 프로세스가 생성되고 메모리에 프로세스 주소 공간(코드, 데이터, 스택 영역)이 할당된다. 이 프로세스의 메타데이터가 PCB에 저장된다. * 프로그램과 프로세스 프로그램은 어떤 데이터를 사용하여 어떤 작업을 할지 그 절차를 적어놓은 것으로, 하드디스크 같은 저장장치에 저장되어 있는 정적의 상태입니다. 프로세스는 프로그램 실행을 위해 메모리에 적재한 동적인 상태로 운영체제로부..

리스트란? 추상적 자료형으로 순서를 가지고 일렬로 항목들을 나열한 구조를 말합니다. 데이터가 순차적으로 저장되어 한 줄로 연결된 형태를 띄기 때문에 선형 구조라고 합니다. 중복된 데이터의 저장이 가능합니다. 리스트는 구현 방법에 따라 배열을 기반으로 구현된 순차 리스트와 메모리의 동적 할당을 기반으로 구현된 연결 리스트로 나뉩니다. 또한, 연결 리스트는 연결 방식에 따라 단일 연결 리스트, 원형 연결 리스트, 이중 연결 리스트로 구현할 수 있습니다. 리스트와 집합 집합은 특정한 값들을 저장하는 추상 자료형입니다. 하지만 집합에서는 데이터들의 순서가 존재하지 않고 중복되지 않는다는 점에서 리스트와 다릅니다. 리스트와 배열 어떻게 보면 배열을 리스트의 일종이라고 할 수 있지만, 배열과 리스트는 다릅니다. 먼..

자료구조란? - 데이터를 표현하고 저장하는 방법이다. 자료구조는 컴퓨터에서 자료를 효율적으로 관리하고 구조화시키는 방법으로 한 마디로 말하자면 '데이터의 표현 및 저장 방법'이라고 할 수 있다. 자료구조는 정수, 실수, 문자, 문자열과 같은 단순구조 뿐만 아니라 리스트, 스택, 큐와 같은 선형구조, 트리, 그래프와 같은 비선형 구조, 순차파일,색인파일, 직접파일과 같은 파일 구조로 크게 분류된다. 따라서 int형 변수도 데이터를 표현하고 저장하는 하나의 방법이므로 넓은 의미에서 자료구조에 속한다고 볼 수 있다. 자료구조와 알고리즘 자료구조와 알고리즘은 연관성이 높다. 각각의 과목을 공부하기 위해 도서관에 가서 책을 고르면서 보니, 두 내용을 한 번에 다루는 책이 많았다. 알고리즘 책에서 자료구조에 대한 ..

동적 프로그래밍(동적 계획법, Dynamic Programming)은 하나의 문제를 풀기 위해서 해당 문제를 여러 개의 Subproblem으로 나누어 푸는 방식이고, Subproblem은 반복되며 답은 항상 같은 특성을 이용하여 Memoization을 통해 최종적으로 문제를 해결하는 것을 말한다. 설명 간략하게 정리된 위의 문장을 쪼개서 설명하면 다음과 같다. 1. 하나의 문제를 풀기 위해서 해당 문제를 여러 개의 Subproblem으로 나누어 푸는 방식이다. 하나의 문제를 풀기 위해서는 그보다 더 작은 Subproblem으로, 그리고 해당 subproblem에서 그보다 더 작은 Subproblem을 더이상 나눌 수 없을 때까지 나누어 작은 Subproblem의 결과 값으로 부터 최종 답을 구할 수 있는..

Summary BFS와 DFS는 그래프의 모든 정점을 탐색하는(그래프의 순회) 완전 탐색 알고리즘이다. BFS는 Breadth-First Search로 너비 우선 탐색을 의미하고 자료구조는 Queue를 사용한다. DFS는 Depth-First Search로 깊이 우선 탐색을 의미하고 자료구조는 Stack을 사용한다. 설명 쉽게 설명하기 위해서 아래와 같은 그래프가 있다고 가정해보자. (만약, Queue와 Stack에 대해 잘 모른다면 먼저 아래 참고를 통해 공부하고 돌아오자!) 그래프의 모든 노드를 BFS와 DFS 방법으로 탐색하여 탐색 순서가 어떻게 되는지 살펴보며 공부해보자. - BFS (Breadth-First Search, 너비 우선 탐색) BFS는 방문 노드와 가장 가깝게 인접한 노드들을 먼저 ..