CS

유클리드 호제법 - 최대공약수(GCD) 구하기

유클리드 알고리즘(Euclidean algorithm)은 2개의 자연수의 최대공약수를 구하는 알고리즘이다. 비교대상의 두 개의 자연수 a와 b에서(단 a>b) a를 b로 나눈 나머지를 r이라고 했을때 GCD(a, b) = GCD(b, r)과 같고 "r이 0이면 그때 b가 최대공약수이다."라는 원리를 활용한 알고리즘이다. ex) GCD(24,16) -> GCD(16,8) -> GCD(8,0) : 최대공약수 = 8 구현 재귀 함수 활용 int GCD(int a, int b) { if(b==0)return a; else return GCD(b,a%b); } 반복문 활용 int GCD(int a,int b){ while(1){ int r = a%b; if(r==0) return b; a = b; b = r; }..

에라토스테네스의 체

소수를 판별하는 알고리즘이다. 소수들을 대량으로 빠르고 정확하게 구하는 방법이다. 단일 숫자 소수 여부 확인 어떤 수의 소수의 여부를 확인 할 때는, 특정한 숫자의 제곱근 까지만 약수의 여부를 검증하면 O(N^1/2)의 시간 복잡도로 빠르게 구할 수 있다. 수가 수(N이라고 가정)를 나누면 몫이 생기는데, 몫과 나누는 수 둘 중 하나는 N 제곱근 이하이기 때문이다. 만약, 대량의 소수를 한꺼번에 판별해야할 경우는 '에라토스테네스의 체'를 이용한다. 에라토스테네스의 체 원리 에라토스테네스의 체는 가장 먼저 소수를 판별할 범위만큼 배열을 할당하여, 해당하는 값을 넣어주고, 이후에 하나씩 지워나가는 방법을 이용한다. 배열을 생성하여 초기화한다. 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다.(지..

C++ 다익스트라(Dijkstra) 알고리즘 개념 및 구현 (무방향 그래프)

다익스트라 알고리즘 다익스트라(dijkstra) 알고리즘은 그래프에서 한 정점(노드)에서 다른 정점까지의 최단 경로를 구하는 알고리즘 중 하나이다. 이 과정에서 도착 정점 뿐만 아니라 모든 다른 정점까지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두 찾게 된다. 매번 최단 경로의 정점을 선택해 탐색을 반복하는 것이다. 참고로 그래프 알고리즘 중 최소 비용을 구하는 데는 다익스트라 알고리즘 외에도 벨만-포드 알고리즘, 프로이드 워샬 알고리즘 등이 있다. 동작 단계 ① 출발 노드와 도착 노드를 설정한다. ② '최단 거리 테이블'을 초기화한다. ③ 현재 위치한 노드의 인접 노드 중 방문하지 않은 노드를 구별하고, 방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택한다. 그 노드를 방문 처리한다. ④ ..

[C#] 연결 리스트(Linked List)란?

1. 연결 리스트(Linked List)란? * 연결 리스트(Linked List) : 데이터를 저장하는 자료구조. 각 노드가 데이터와 포인터를 가지고 있으면서 노드들이 한 줄로 쭉 연결되어 있는 방식. 2. 단일 연결 리스트(Singly Linked List) : 단방향으로 노드들을 연결한 간단한 자료 구조. (ex) 아래는 4개의 노드를 갖는 단일 연결 리스트를 그림으로 표현한 것. using System; public class LinkedList_Study { public T Data { get; set; } public LinkedList_Study Next { get; set; } public LinkedList_Study(T data) { this.Data = data; this.Next =..

[C#] .NET의 연결 리스트 : LinkedList<T>

LinkedList : 이중 연결 리스트로 되어 있으며, 리스트 노드는 LinkedListNode 클래스를 사용. 노드를 추가하기 위한 AddFirst(처음), AddLast(끝), AddBefore(특정 노드 앞), AddAfter(특정 노드 뒤) 등 다양한 메서드가 있음. LinkedList의 메서드 종류 코드 예시) LinkedList list = new LinkedList(); list.AddLast(1); list.AddLast(2); list.AddLast(3); list.AddLast(4); var node = list.Find(2); var newNode = new LinkedListNode(3); list.AddAfter(node, newNode); //2가 들어있는 노드 다음에 3을 집..

[C#] 힙 (Heap)

1. 힙이란? : 완전 이진 트리(Complete Binary Tree)의 일종. 여러 값의 데이터들 중 최대값과 최소값을 빠르게 찾아낼 수 있는 자료구조입니다. (시간복잡도로 따지면 O(logn)이 걸림) * 힙의 특징 - 중복 값을 허용 - 루트가 최대값(새로운 데이터가 추가될 때 부모노드와 크기를 비교해 크기가 더 큰 값을 부모노드로 올리기 때문) - 새로운 데이터를 추가할 때 작은 레벨 순서대로 채움(왼쪽부터) 2. 이진 탐색 트리와 힙의 차이 * 공통점 : 둘 다 이진 트리. * 차이점 - 힙은 이진 탐색 트리와 달리 중복 값을 허용. - 힙은 각 노드들이 부모노드의 데이터 값보다 작거나 같음. - 이진 탐색 트리는 말 그대로 탐색을 위한 자료구조이고, 힙은 최대값과 최소값 검색을 위한 자료구조..

메모리 (RAM) 구조

RAM과 ROM RAM은 자유롭게 읽고 쓸 수 있는 기억장치로, RWM(Read Write Memory)라고 부르기도 한다. 또한 RAM에는 현재 사용 중인 프로그램이나 데이터가 저장되어 있다. 시스템의 전원이 꺼지면 기억된 내용이 모두 사라지는 휘발성 메모리의 특징을 가진다. 일반적으로 주기억장치 또는 메모리라고 불린다. ROM은 기억된 내용을 읽을 수만 있는 기억장치로서 일반적으로 쓰기가 불가능하다. 또한 시스템의 전원이 꺼져도 기억된 내용이 지워지지 않는 비휘발성 메모리다. 실제로 ROM은 주기억장치로 사용되기보단 주로 변경 가능성이 없는 시스템 소프트웨어를 기억시키는데 이용된다. (ex. 기본 입출력 시스템, 자가 진단 시스템) 프로그램 실행 순서 프로그램이 실행되는 과정을 도식화하면 다음과 같다..

Virtual Memory - 가상 메모리 ( 필요한 이유 )

간단하게 말해서 프로세스의 논리 메모리와 물리 메모리를 분리하기 위해 생긴 개념이다. 왜 분리를 해야 하냐면, 물리 메모리의 한계를 극복하기 위해서이다. 무슨 말이냐면 여러 프로그램을 돌리면 메모리 부족의 문제가 생긴다. 이는 메모리 침범의 문제로 이어지기 때문에 이를 해결하고자 한 방법이다. 이런 이유 때문에 가상 메모리와 물리 메모리를 분리한다는 의미다. 논리 메모리가 가상 메모리다. 왜 가상 주소가 필요한지 예를 들어보자, 3개의 프로그램을 일정 시간에 따라 반복적(time에 따라)으로 돌리고 메인 메모리의 크기는 64KB라고 가정해보자. 그러면 먼저 taks1 (32KB), task2(16KB), task3(48KB)의 정보는 Hard disk에 다 들어있을 것이다. 그러다가 task1이 실행되면..

Memory Allocation (논리 메모리, 물리 메모리, Dynamic Loading, Paging이 나온 이유 )

memory를 나눌 때 어떻게 눌지 정해야 한다. 모든 프로세스는 메모리에 올라와서 실행되는데 각각의 프로세스는 자신만의 할당 메모리가 있다. 이때 하나의 프로세스가 다른 프로세스 메모리에 침범하면 문제가 생긴다. 이런 이유 때문에 메모리의 구분이 필수적이다. 예방하는 방법으로 가장 단순하게는 시작 주소와 끝 주소를 지정하는 것이다. base 주소로부터 limit 주소를 하나의 프로세스에게 할당한다. (+아래서 보이지만, 운영체제 또한 메모리 상에 존재한다.) 어떤 프로세스를 할당할 때, base 주소보다 크고 base + limit 주소보다 작은 공간이 비어 있다면 할당하는 순서를 가질 수 있다. 메모리 주소 메모리에는 Logical address와 Physical address가 존재한다. 이 차이를..

Swapping 스와핑 ( page in, page out )

여러 프로그램을 메모리상에서 돌리다 보면 메모리가 부족할 수밖에 없다. 이런 메모리 부족을 해결하기 위해서 나온 방법이 Swapping이다. 더 많은 프로세스가 메모리에 존재할 수 있도록 하는 것이다. swapping을 사용하면 프로세스를 다시 실행할 때 처음부터 메모리에 올리는 것이 아니라 더 빨리 할 수 있기 때문이다. Swapped은 backing store를 만들어서 프로세스 단위로 swap in, swap out을 동작한다. ( backing store는 임시저장소로 하드디스크나 NVM처럼 여러 하드웨어가 될 수 있다. 즉 Secondary Storage다.) 프로그램이 실행되면 Bakcing store에 있는 필요한 page 정보를 메모리에 올린다. 이렇게 프로세스 단위로 왔다 갔다 하는 걸,..