개발 지식/CS5 시간 복잡도 - 대표적인 빅오(Big-O) 표기법 알고리즘 문제를 풀다 보면 시간 복잡도, 공간 복잡도를 계산할 줄 알아야 어떤 알고리즘이 더 효율적인지 판단할 수 있다. 빅오 표기법은 알고리즘 실행시간이 최악일 때를 표기하는 방법으로, 신뢰성이 떨어지는 오메가 표기법(실행시간 평균일 때를 표기하는 방법), 평가하기 어려운 세타 표기법(실행시간이 최상일 때 표기하는 방법)에 비해 성능을 예측하기 용이하여 주로 사용된다. ✏️ 복잡도란 ? 시스템이나 시스템 구성 요소 또는 소프트웨어의 복잡한 정도를 나타내는 말로, 시스템 또는 소프트웨어를 어느 정도의 수준까지 테스트해야 하는지 또는 개발하는데 어느 정도의 자원이 소요되는지 예측하는 데 사용. ✏️ 시간 복잡도란? 알고리즘의 실행시간, 즉 알고리즘을 수행하기 위해 프로세스가 수행하는 연산 횟수를 수치화한 .. 2023. 2. 18. [CS]컴퓨터 주요 구성 요소(CPU, Memory, IO Devices, System Bus), 메모리 계층과 각 메모리 특징 📌 메모리 계층(Memory Hierarchy)이란? = 메모리를 필요에 따라 여러 가지 종류로 나누어 둠을 의미한다. 이때 필요한 대부분의 경우 CPU가 메모리에 더 빨리 접근하기 위함이다. 위 그림처럼 계층 구조에서 상위의 기억장치일수록 접근 속도와 접근 시간이 빠르지만, 기억 용량이 적고 고가이다. 아래로 내려갈수록 상대적으로 비용은 내려가고 접근 속도는 느리지만 기억 용량이 크다. 📌 기억 장치(Memory Unit)? 컴퓨터에서 사용하는 프로그램과 처리할 데이터 및 처리한 결과 등을 저장하는 장치. 컴퓨터에서 사용하는 모든 프로그램과 데이터를 저장해 두고 필요할 때 이용할 수 있도록 해준다. 기억 장치는 처리 속도와 사용 용도, 기억 용량의 크기에 따라 아래와 같이 4가지로 구분된다. 레지스터(.. 2023. 1. 14. [cs50 모두를 위한 컴퓨터 과학] 자료구조(Data Structure) 📝 연결 리스트(Linked list) 배열에서는 각 인덱스의 값이 메모리상에서 연이어 저장되어 있다. 하지만 각 값이 메모리상의 여러 군데 나뉘어져 있다고 하더라도 바로 다음 값의 메모리 주소만 기억하고 있다면 여전히 값을 연이어서 읽어들일 수 있다. ⇒ 이를 ‘연결 리스트’라고 한다. 3은 다음 값이 없기 때문에 NULL(\n, 즉 0)을 다음 값의 주소로 저장한다. typedef struct node { int number; struct node *next; } node; - 연결리스트를 구조체로 정의한 것 배열과 비교해 연결 리스트는 새로운 값을 추가할 때 다시 메모리를 할당하지 않아도 되는 장점이 있다. But, 연결 리스트에 값을 추가하거나 검색하는 경우 이를 위해 해당 위치까지 연결 리스트의.. 2022. 10. 2. [cs50 모두를 위한 컴퓨터 과학] 메모리(Memory) 메모리 주소, 포인터 C에서는 변수의 메모리상 주소를 받기 위해 '&’이라는 연산자를 사용. #include int main(void) { int n = 50; printf("%p\\n", &n); } 예를 들어, 위와 같은 코드를 실행하면 ‘0x7ffe00b3adbc’와 같은 값을 얻을 수 있고, 이는 변수 n의 16진법으로 표현된 메모리의 주소이다.(보안상 실행시 위치가 매번 바뀜) 반대로 '*'를 사용하면 그 메모리 주소에 있는 실제 값을 얻을 수 있다. 16진수의 유용성 16진수(Hexadecimal)로 표현하면 2진수로 표현했을 때 보다 훨씬 간단해지고 컴퓨터는 8개의 비트가 모인 바이트 단위로 정보를 표현하므로 2개의 16진수는 2진수로 변환되기 때문에 정보를 표현하기 매우 유용하다. 64bi.. 2022. 9. 22. [cs50 모두를 위한 컴퓨터 과학] 알고리즘(Algorithm) 네이버 boostcourse의 모두를 위한 컴퓨터 과학 (CS50 2019) 4. 알고리즘을 들으며 정리한 내용입니다. 더 자세한 강의의 예시는 https://www.boostcourse.org/cs112/lecture/119019?isDesc=false 참조하세요. 1. 검색 알고리즘 선형 검색 - 처음부터 끝까지 하나씩 증가시키며 그 값이 맞는지 검사 ex) 전화번호부 위에서 아래로 맞는 이름이 나올 때까지 검색 이진 검색 - 만약 배열이 정렬되어 있다면, 배열 중간 인덱스부터 시작하여 찾고자 하는 값과 비교하며 그보다 작은 값이 저장되어 있는 인덱스 또는 큰 값이 저장되어 있는 인덱스로 이동을 반복. ex) 전화번호부가 정렬되어 있다면, 중간부터 시작해 a-z 알파벳순의 가까운쪽(왼쪽 or 오른쪽).. 2022. 8. 4. 이전 1 다음
