[알고리즘] Greedy Algorithm - Interval Scheduling
·
컴퓨터 과학/알고리즘
Interval scheduling Job j starts 𝑠𝑗 and finishes at 𝑓 𝑗.Two jobs are compatible if they don’t overlapGoal: find maximum subset of mutually compatible jobs일을 가장 많이 사용하는 방법을 찾는 경우를 찾는다고 했을 때 문제입니다.직관적으로 봤을 때 b, e, h를 고를 시 가장 많은 경우의 수를 고려하지만 직관적으로 해결 하는 것이 아닌 다양한 접근법을 이용해서 해결 해보겠습니다.Approach 1) Earliest start time: Consider jobs in ascending order of 𝑠 𝑗일이 시작되는 시간 중에서 가장 먼저 시작되는 일을 기준으로 시작한다...
[알고리즘] 비트마스크(BitMask)
·
컴퓨터 과학/알고리즘
비트마스크란?비트마스크(Bitmask)는 이진수의 비트를 사용해 여러 상태나 조합을 효율적으로 표현하는 기법입니다. 각 비트는 특정한 상태를 나타내며, 비트 연산을 통해 다양한 조합을 처리할 수 있습니다. 비트마스크는 조합 문제나 상태 추적 문제에서 특히 유용하게 사용됩니다. 장점메모리 효율성: 비트를 사용해 여러 상태를 간단하게 저장할 수 있어, 메모리 공간을 절약할 수 있습니다.속도: 비트 연산은 빠르기 때문에, 대량의 데이터를 신속하게 처리할 수 있습니다.조합 관리: 비트마스크를 사용하면 여러 상태를 조합하는 문제를 쉽게 해결할 수 있습니다.코드의 간결성: 비트 연산을 사용하면 코드가 간결해지고 가독성이 좋아질 수 있습니다.단점이해의 어려움: 비트마스크의 개념이 초보자에게는 다소 복잡하게 느껴질 수..
[운영체제] CPU(중앙처리장치)의 여러 구성 요소
·
컴퓨터 과학/운영체제
이번에는 CPU의 여러 구성요소에 대해 설명하도록 하겠습니다.CPU는 크게 PC, ALU, AC, MAR, 제어 유니트, IR, MBR의 요소를 가지고 있습니다. 1. PC (Program Counter) - 프로그램 카운터역할: 현재 실행 중인 명령어의 주소를 가리키는 레지스터입니다.다음에 실행될 명령어의 메모리 주소를 저장합니다.명령어를 읽을 때마다 증가하며, 프로그램 흐름을 제어합니다. 2. ALU (Arithmetic Logic Unit) - 산술 논리 장치역할: 산술 연산(덧셈, 뺄셈 등)과 논리 연산(AND, OR, XOR 등)을 수행하는 장치입니다.CPU의 연산 능력을 담당하며, 데이터를 처리하는 가장 핵심적인 장치입니다. 3. AC (Accumulator) - 누산기역할: ALU에서 연산된..
[운영체제] 운영체제(Operating System)란?
·
컴퓨터 과학/운영체제
운영체제(Operating System)란?컴퓨터 응용 소프트웨어와 하드웨어를 안전하게 인터페이스 하기 위해 필요한 서비스의 모음입니다.운영체제는 컴퓨터의 모든 자원을 효율적으로 관리하는 시스템으로, 하드웨어, 소프트웨어, 데이터 자원에 대한 독점적인 권한을 소유하며, 자원 할당, 공유, 액세스 등을 제어합니다.하드웨어 자원: CPU, 메모리, 키보드, 마우스, 디스플레이, 하드디스크, 프린터 등소프트웨어 자원: 응용 프로그램데이터 자원: 신호, 세마포어, 뮤텍스, 파일, 데이터베이스 등운영체제는 컴퓨터 시스템 관리자 역할을 하며, 프로그램 관리, 메모리 관리, 파일과 디스크 장치 관리, 입출력 장치 관리, 사용자 계정 관리를 수행합니다. 운영체제는 소프트웨어(software)입니다.GUI를 비롯한 도구..
[컴퓨터 네트워크] 프로토콜이란 무엇인가?
·
컴퓨터 과학/컴퓨터 네트워크
프로토콜이란?프로토콜(Protocol)은 컴퓨터 네트워크에서 데이터 통신을 위해 정의된 규칙과 절차의 집합을 말합니다. 네트워크 상의 장치들이 서로 데이터를 주고받기 위해 따라야 하는 표준화된 규칙입니다. 프로토콜은 어떤 데이터가 전송될지, 어떻게 전송될지, 오류가 발생했을 때 어떻게 처리할지 등을 규정하여, 서로 다른 시스템들이 문제없이 통신할 수 있도록 해줍니다. 그리고 프로토콜은 네트워크 상에서 서로 다른 기기들이 원활하게 통신할 수 있도록 만들어주는 규칙의 집합입니다. 이러한 규칙 덕분에 네트워크는 복잡한 환경에서도 데이터를 안정적으로 주고받을 수 있습니다. 주요 프로토콜의 역할데이터 포맷 지정: 프로토콜은 데이터가 어떤 형태로 포맷되어야 하는지 정의합니다. 예를 들어, 이메일을 전송할 때 사용하..
[컴퓨터 네트워크] 헤더란 무엇인가?
·
컴퓨터 과학/컴퓨터 네트워크
헤더란 무엇인가?헤더(Header)는 네트워크에서 전송되는 각 데이터 패킷의 앞부분에 위치한 정보 블록입니다. 이 헤더는 패킷이 전달되는 동안 경로를 따라 올바르게 처리될 수 있도록 도와주는 다양한 메타데이터를 포함합니다. 소스에서 데이터가 전송될 때, 전송 계층이나 네트워크 계층에서 해당 데이터 앞부분에 특정 정보가 추가되어 패킷을 구성하게 됩니다. 소스 헤더의 주요 역할1) 주소 지정헤더에는 패킷이 어디서 왔고, 어디로 가야 하는지에 대한 정보가 포함됩니다. 이는 소스 IP 주소와 목적지 IP 주소를 통해 이루어집니다. 이 정보는 패킷이 네트워크 상에서 적절한 경로를 따라 이동하도록 도와줍니다. 예를 들어, 인터넷에서 패킷은 여러 라우터를 거쳐 목적지에 도달합니다. 이때, 라우터는 헤더에 있는 주소 ..
[알고리즘] 투 포인터(Two Pointer)
·
컴퓨터 과학/알고리즘
투 포인터 기법은 배열이나 리스트를 탐색하는 데 매우 효율적인 알고리즘 기법입니다. 두 개의 포인터를 사용하여 문제를 해결하는 이 기법은 주로 정렬된 데이터에서 특정 조건을 만족하는 쌍을 찾는 데 유용합니다. 이 기법은 많은 경우에 O(N) 또는 O(N^2)의 시간 복잡도를 가지며, 최적화된 솔루션을 제공합니다. 투 포인터(Two Pointer) 기본 개념투 포인터 기법은 다음 두 가지 주요 방식으로 사용됩니다:양 끝에서 시작하기적용 예: 정렬된 배열에서 두 수의 합이 목표 값과 일치하는 쌍을 찾는 문제방법: 배열의 시작과 끝에 각각 포인터를 두고, 두 포인터가 가리키는 값의 합을 계산합니다. 합이 목표 값과 같으면 쌍을 찾은 것이고, 그렇지 않으면 포인터를 조정합니다.같은 방향으로 이동하기적용 예: 특..
[알고리즘] 이분 탐색(Binary Search)
·
컴퓨터 과학/알고리즘
이분 탐색(Binary Search)은 정렬된 배열에서 특정 값을 빠르게 찾기 위한 효율적인 알고리즘입니다. 이 알고리즘은 배열을 반복적으로 반으로 나누면서 원하는 값을 찾는 방식으로 동작하며, 시간 복잡도가 O(logn)입니다. 이는 선형 탐색(Linear Search)의 O(n)과 비교할 때 훨씬 더 효율적입니다. 이분 탐색 알고리즘의 동작 원리시작과 끝 설정: 배열의 시작점(low)과 끝점(high)을 설정합니다.중간점 계산: 시작점과 끝점의 중간 인덱스(mid)를 계산합니다.중간값 비교: 배열의 중간 값(arr[mid])과 찾고자 하는 값(target)을 비교합니다.만약 arr[mid]가 target과 같으면, 해당 인덱스를 반환합니다.만약 arr[mid]가 target보다 크면, target은 ..
피사노 주기(Pisano Period)
·
컴퓨터 과학/수학
피사노 주기란 피보나치 수열을 어떤 수 m으로 나눈 나머지들의 수열이 반복되는 주기를 말합니다. 피보나치 수열의 각 항을 m으로 나눈 나머지들을 구하다 보면, 이 나머지들이 주기적으로 반복되는 패턴을 갖게 됩니다. 이 패턴이 반복되기 시작하는 주기의 길이를 피사노 주기라고 합니다. 예시예를 들어, 피보나치 수열을 3으로 나눈 나머지의 피사노 주기를 살펴보겠습니다:피보나치 수열: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...피보나치 수열을 3으로 나눈 나머지: 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, ...여기서 나머지의 수열을 보면 0, 1, 1, 2, 0, 2, 2, 1 이후부터 다시 0, 1, 1, 2, 0, 2, 2, 1이 반복되기 시작합니다. 이 주기는..
[알고리즘] 최소 공배수(LCM, Least Common Multiple)
·
컴퓨터 과학/알고리즘
최소공배수(LCM, Least Common Multiple)를 구하는 여러 가지 방법이 존재하며, 이 중에서도 유클리드 호제법을 활용한 방법이 가장 효율적입니다. 아래에서는 여러 방법을 비교하고, 각 방법의 특징과 효율성을 설명하겠습니다. 1. 완전 탐색 기반 방법 (Brute Force)이 방법은 두 수의 배수를 계산하고, 가장 작은 공통 배수를 찾는 매우 직관적인 방법입니다. 알고리즘a와 b의 배수를 각각 계산합니다.두 수의 배수 중에서 가장 작은 공통 배수를 찾습니다.def lcm_brute_force(a, b): max_ab = max(a, b) lcm_value = max_ab while lcm_value % a != 0 or lcm_value % b != 0: lc..
[알고리즘] 최대 공약수(GCD, Greatest Common Divisor)
·
컴퓨터 과학/알고리즘
이번에는 최대공약수(GCD, Greatest Common Divisor)를 구하는 여러 알고리즘을 소개하겠습니다. 각 방법은 효율성이나 구현 방식에 차이가 있습니다. 1. 완전 탐색 방법 (Brute Force)첫 번째는 완전 탐색 방법을 이용한 최대 공약수를 구하는 방법 입니다.가장 직관적인 방법으로, 두 수의 공통된 약수 중에서 가장 큰 값을 찾는 방법입니다. 알고리즘두 수 중 작은 수를 선택합니다.그 수로부터 1까지 모든 수에 대해 두 수 모두를 나눌 수 있는지 확인합니다.두 수를 모두 나눌 수 있는 가장 큰 수가 최대공약수입니다.def gcd_brute_force(a, b): min_num = min(a, b) for i in range(min_num, 0, -1): if ..
[자료구조] 힙(Heap)
·
컴퓨터 과학/자료구조
힙(Heap)은 완전 이진 트리(Complete Binary Tree) 형태를 가지는 자료구조로, 각 노드의 값이 특정한 조건을 만족하도록 정렬된 트리입니다. 힙은 주로 우선순위 큐(Priority Queue)를 구현할 때 사용되며, 그 특성 때문에 빠른 삽입과 삭제 연산이 가능합니다.힙의 특성힙은 다음 두 가지 특성을 가집니다.완전 이진 트리(Complete Binary Tree):트리가 완전히 채워져 있으며, 마지막 레벨을 제외한 모든 레벨이 꽉 차 있습니다.마지막 레벨에서는 노드들이 왼쪽부터 오른쪽으로 채워져 있습니다.힙 특성(Heap Property):최대 힙(Max Heap): 부모 노드의 값이 자식 노드의 값보다 크거나 같아야 합니다. 즉, 트리의 루트(root) 노드는 항상 최대값입니다.최소..
김치바보
'컴퓨터 과학' 카테고리의 글 목록 (2 Page)
상단으로

티스토리툴바