728x90 정글 2기71 [C언어] 이진 탐색 트리(Binary Search Tree, BST) [C언어] 이진 탐색 트리(Binary Search Tree, BST) 이진 탐색 트리란 이진 탐색(Binary Search)과 연결리스트(Linked List)를 결합한 자료구조의 일종이다. 이진 탐색의 효율적인 탐색 능력(O(log n)은 유지하면서 자료 입력과 삭제가 효율적으로(O(1)) 가능하다. 이진 탐색 트리 특징 각 노드에 값이 있다. 값들은 전순서가 있다. 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다. 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이루어져 있다. 좌우 하위 트리는 각각이 다시 이진 탐색 트리여야 한다. 이진 탐색 트리 기능 검색, 추가, 삭제, 최솟값 찾기 코드 #include #include typedef i.. 2021. 9. 7. [C언어] 연결 리스트(Linked list) 구현 [C언어] 연결 리스트(Linked list) 구현 연결리스트는 복잡한 트리 구조를 구현하기 위해 사용되기 때문에 꼭 알고 넘어가야 한다. 이를 위해 구조체, 포인터, 동적 메모리 할당 등의 개념이 사용된다. 연결 리스트 연결 리스트란 데이터가 담긴 노드(메모리 공간)를 일렬로 연결하여 리스트화 한 것이다. 연결 리스트 특징 리스트의 중간 지점에서 노드를 손쉽게 추가하거나 삭제할 수 있다. 특정 노드를 찾으려면 노드를 모두 검색해야 한다.(최악의 경우) -> 하나씩 찾아봐야 하기 때문에 원하는 노드를 찾는데 오래 걸린다. 크기가 고정되어 있지 않다. 연결 리스트 기능 연결 리스트에서는 다음이 가능하다. 추가 삭제 찾기 노드 간 연결 새 노드 추가 노드 삭제 연결 리스트 코드 연결 리스트 코드 구현 #in.. 2021. 9. 5. [C언어] 구조체 포인터 사용하기 [C언어] 구조체 포인터 사용하기 다른 자료형과 마찬가지로 구조체도 포인터를 선언할 수 있으며, malloc 함수를 이용하여 동적 메모리를 할당할 수 있다. #define _CRT_SECURE_NO_WARNINGS // strcpy 보안 경고로 인한 컴파일 에러 방지 #include #include // strcpy 함수가 선언된 헤더 파일 #include // malloc, free 함수가 선언된 헤더 파일 struct Person { // 구조체 정의 char name[20]; // 구조체 멤버 1 int age; // 구조체 멤버 2 char address[100]; // 구조체 멤버 3 }; int main() { struct Person *p1 = malloc(sizeof(struct Perso.. 2021. 9. 4. [백준_11049] 다이나믹 프로그래밍(DP), 행렬 곱셈 순서 [백준_11049] 다이나믹 프로그래밍(DP), 행렬 곱셈 순서 행렬 곱셈 순서에 따라 곱셈의 횟수가 달라진다. 행렬이 주어졌을 때 다이나믹 프로그래밍(DP)를 이용하여 곱셈 횟수의 최솟값을 구하는 문제이다. 뭔가 어려운 포인트들이 많아 한 번 정리해두면 좋은 문제이다. https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 문제 풀이 생각 포인트 이 문제에서 중요한 포인트는 3가지 정도 있다. i 번 째 행렬의 행은 i-1 번 째 행렬의.. 2021. 9. 1. [Operating System 운영체제] Computer System Overview 02 [Operating System 운영체제] Computer System Overview 02 운영체제의 역할 1. 운영체제의 역할 1) User Interface(편리성) CUI(Character user interface) GUI(Graphical User interface) EUCI(End-User Comfortable Interface) - 특수목적. ex) MP3 플레이어용 UI 2) Resource management(효율성) HW resource(processor, memory, I/O devices, Etc.) SW resource(file, application, message, signal, Etc.) 3) Process(실행 주체) and Thread(가벼운 프로세스) managemen.. 2021. 8. 31. [Operating System 운영체제] Computer System Overview 01-1 Cache [Operating System 운영체제] Computer System Overview 01-1 Cache 1. 캐시(Cache) - 128KB 정도로 작음 1) 프로세서(CPU) 내부에 있는 메모리 (L1, L2 캐시 등) - 속도가 빠르고 가격이 비쌈, 레지스터보다 Core에서 멀리 떨어져있다. 멀리 떨어져 있을수록 사이즈는 커지고 속도는 느려진다고 생각하면 된다. 2) 메인 메모리의 입출력 병목현상 해소 - CPU와 메인메모리 간의 속도차가 여전히 존재. 2. 캐시의 동작 - 일반적으로 HW적으로 관리 됨 캐시 히트(Cache hit) : 필요한 데이터 블록이 캐시에 존재 캐시 미스(Cache miss) : 필요한 데이터 블록이 캐시에 없는 경우. 캐시가 메인 메모리까지 접근해 데이터를 캐시로 가져.. 2021. 8. 31. 이전 1 ··· 5 6 7 8 9 10 11 12 다음 728x90
