Computer Science

이전 포스팅을 참고https://jinhos-devlog.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%99%84%EC%A0%84-%ED%83%90%EC%83%89-Exhaustive-Search ✒️ 1. BFS / DFS- 너비우선탐색(Breadth-First Search, BFS)는 하나의 요소를 방문하고 그 요소에 인접한 모든 요소를 우선 방문하는 방식- 깊이우선탐색(Depth-First Search, DFS)는 트리의 한 요소(노드)와 다음 수준(level)의 자식 노드를 따라가는 방향으로 탐색하는 방식- 길 찾기 등에 주로 쓰이는 알고리즘이다. (미로 등) ✒️ 2. BFS (너비 우선 탐색)BFS는 그래프나 트리 구조에서 노드를 탐색..

✒️ 1. 완전 탐색 이란?간단히 말해서, 모든 경우의 수를 시도하는 방법이다.구현에 있어서는 비교적 간단할 수 있다.하지만, 어찌보면 무식한 방법...Brute Force 라고도 불린다. 즉, 무식하게 가능한 거 다 해보겠다는 방법을 의미한다.그러나 직관적이어서 이해하기 쉽고 문제의 정확한 결과값을 얻어낼 수 있는 가장 확실하며 기초적인 방법이다. 우리는 CS적으로 어떠한 알고리즘을 쓸 것인가 고민할 때 2가지를 생각한다.어렵게 생각할 필요 없이 우리가 코딩테스트 문제를 풀다보면 맞이하는 2가지 과제이다. 1. 정확성: 문제를 정확히 해결할 수 있는가?2. 효율성: 주어진 시간 내에 해결할 수 있는가? (시간 복잡도) 완전탐색의 가장 중요한 핵심은 "가능한 모든 방법을 모두 고려한다"는 점인데,어떻게 ..

✒️ 0. 들어가기 전힙과 우선순위 큐는 데이터의 우선순위를 관리하는 데 필수적인 자료구조로, 주로 최댓값이나 최솟값을 빠르게 찾기 위해 사용된다.아래에서 힙의 구조, 힙 정렬, 그리고 우선순위 큐의 구현 방법을 배워보자. ✒️ 1. 힙(Heap)힙은 완전 이진 트리(Complete Binary Tree) 구조로, 노드 간의 특정 관계를 유지하여 데이터 중 가장 크거나 작은 값을 빠르게 찾아내는 자료구조이다. 힙은 크게 최대 힙과 최소 힙으로 나뉜다.💡 최대힙과 최소힙최대 힙(Max Heap): 부모 노드의 값이 자식 노드의 값보다 항상 크거나 같은 구조를 가진다.                                  최댓값은 항상 루트 노드에 위치하므로, O(1) 시간 복잡도로 최댓값을 찾을 수..

✒️ 0. 들어가기 전이 글에서는 주로 키-값 쌍을 저장하거나 고유한 값을 저장하는 데 사용되는 자료구조들에 대해 설명한다.해시테이블의 구현 방식과 맵, 셋의 활용 사례를 포함하여 배워보자! ✒️ 1. Map (맵)Map은 고유한 키를 기반으로 값(Value)을 저장하는 키-값(Key-Value) 쌍의 자료구조이다.삽입 시 자동으로 정렬되며, 이는 레드-블랙 트리(Red-Black Tree)를 사용해 구현된다.Map의 주요 특징은 고유한 키를 기반으로 하며, 중복 키를 허용하지 않는다는 점이다.💡 시간복잡도- 참조(Access): O(log n)- 탐색(Search): O(log n)- 삽입/삭제(Insertion/Deletion): O(log n) 💡 특징Map은 키를 기준으로 자동 정렬되기 때문에..

✒️ 0. 들어가기 전트리와 그래프는 비선형 자료구조의 대표적인 예시이다.이 글에서는 트리와 그래프의 기본 개념부터 시작해, 다양한 종류의 트리, 그래프의 표현 방법(인접행렬과 인접리스트)에 대해 다뤄보자. ✒️ 1. 그래프 이론의 기초 (Graph, Vertex, Edge, Weight)정점(Vertex)와 간선(Edge)으로 이루어진 집합을 그래프(Graph)라고 부른다.정점은 노드(Node)라고도 불리며, 특정 객체, 위치, 사람 등을 나타낼 수 있다.간선은 이 정점들을 잇는 선으로, 관계나 경로를 표현한다.- 노드/정점(Node, Vertex): 그래프를 구성하는 기본 단위로, 점 또는 노드로 표현된다.- 간선(Edge): 두 정점을 연결하는 선으로, 그래프 내의 관계나 경로를 나타낸다.- 가중치..

✒️ 0. 들어가기 전이번 글에서는 연결리스트, 스택, 큐와 같은 기본적인 자료구조에 대해 깊이 있게 탐구해보겠다.각 자료구조의 개념, 구조, 시간 복잡도, 그리고 실전 코드 예제까지 다루면서 그 원리를 이해하고, 어떻게 구현되고 사용하는지를 배워보자. ✒️ 1. 연결리스트(Linked List)연결리스트는 메모리에서 연속되지 않은 위치에 노드를 저장하며, 각 노드는 다음 노드로의 포인터를 가지고 있다.이는 배열과 같은 순차적인 자료구조와는 다르게, 삽입과 삭제가 빠르게 이루어질 수 있는 장점을 제공한다.노드는 데이터와 다음 노드를 가리키는 포인터로 구성되며, 이 포인터를 통해 노드들이 연결된다.각 노드는 next 또는 next, prev라는 포인터로 서로 연결된 선형적인 자료구조!! 연결리스트는 주로 ..

✒️ 0. 들어가기 전포인터는 C와 C++와 같은 저수준 프로그래밍 언어에서 메모리를 직접 다루는 강력한 도구이다.이 글에서는 C++ 언어로 포인터의 개념, 메모리와의 관계, 그리고 실제 사용에 살펴보자. ✒️ 1. 메모리와 주소컴퓨터의 메모리는 1바이트 크기의 셀들이 연속적으로 나열된 구조이다.각 셀은 고유한 주소를 가지며, 이 주소를 통해 메모리에 접근한다.예를 들어, 'int i;'라는 선언은 4바이트(일반적인 int 크기)의 메모리 영역을 예약한다.이때 변수 i의 주소는 이 4바이트 중 첫 번째 바이트의 주소를 가르킨다. 그럼 값이 아닌, 이 주소를 직접 출력해보려면 어떻게 해야할까?C++에서는 '&' 연산자를 사용하여 변수의 메모리 주소를 얻을 수 있다.int i = 0;cout * 0x0000..

✒️ 0. 들어가기 전정적 배열과 동적 배열에 대해 다뤄보자.메모리 관리와 성능의 균형에 관한 이야기이다. 일반적으로 "배열"이라고하면 정적 배열을 의미한다.그렇기에 보통 "동적 배열"은 명확히 "동적 배열"이라고 이야기한다. 배열은 프로그래밍에서 가장 기본적이면서도 강력한 자료구조 중 하나이다.앞서 말했듯 크게 정적 배열과 동적 배열로 나눌 수 있는데,이 두 가지 형태는 각각 고유한 특성과 용도를 가지고 있다. 이 글에서는 정적 배열과 동적 배열의 특징, 장단점, 그리고 실제 사용 사례를 깊이 있게 살펴보겠다 ✒️ 1. 정적 배열 (Static Array)정적 배열은 컴파일 시점에 크기가 결정되는 배열이다.C++에서는 주로 C 스타일의 배열 선언(int arr[10])이나 std::array를 사용하여..