티스토리

cs-learn

검색하기

블로그 홈

cs-learn

humilde.tistory.com/m

computer science, machine learning, mathematics

구독자: 0

방명록 방문하기

주요 글 목록

알고리즘의 효율 분석 알고리즘 수행 시간 측정 방법 알고리즘의 시간 측정은 '절대 시간'을 측정하는 방법과 '시간 복잡도'를 측정하는 방법이 존재한다. '절대 시간'은 말 그대로 프로그램과 프로그램 사이의 걸리는 시간을 측정하는 방법이다. '시간 복잡도'는 알고리즘이 시작한 순간부터 결과 값이 나올 때까지 연산 횟수를 의미한다. 코딩 테스트를 위한 알고리즘에서는 거의 대부분 시간 복잡도로 평가한다. 시간 복잡도시간 복잡도(Time Complexity)란, 알고리즘의 성능을 나타내는 지표로, 입력 크기에 대한 연산 횟수의 상한을 의미한다. 시간 복잡도는 주로 점근적 표기법을 사용하여 나타낸다. 시간 복잡도 측정 1차원 배열의 맨 앞부터 하나씩 검사하는 알고리즘이라고 가정해보자. 이런 경우, 입력이 1일 때는 시간복잡도가 1이.. 공감수 4 댓글수 1 2024. 9. 25.
연결 리스트 (Linked List) 5 - 양방향 연결 리스트 (Doubly Linked List) 양방향 연결 리스트양방향 연결 리스트는 각 노드가 앞뒤 방향으로 링크된다. 각 노드가 다음 노드 뿐 아니라 직전 노드에 대한 링크도 가져서, 한 노드만 알면 앞뒤로 자유롭게 이동이 가능하다. 양방향 연결 리스트의 삽입 먼저 삽입할 노드의 바로 앞자리 노드를 prev로 레퍼런스하고, prev 다음 자리에 노드를 삽입한다. 양방향 연결 리스트의 삭제삭제할 노드를 curr로 레퍼런스로 설정하고 양쪽 노드를 바로 연결시킨다. 양방향 연결 리스트의 구현class BidirectNode: def __init__(self, x, prevNode:'BidirectNode', nextNode: 'BidirectNode'): self.item = x self.prev = prevNode .. 공감수 0 댓글수 0 2024. 9. 18.
연결 리스트 (Linked List) 4 - 원형 연결 리스트 (Circular Linked List) 원형 연결 리스트(Circular Linked List)연결 리스트에서는 첫 노드와 마지막 노드에 접근성이 극적으로 차이난다. 첫 노드에는 단번에 연결 가능하고, 두번째 노드에는 링크를 끝까지 따라가야 접근할 수 있다. 그 결과 원소를 삽입/삭제할 때, 맨 앞, 맨 끝에 따라서 차이가 난다. 따라서, 이 차이는 마지막 노드가 첫 번째 노드를 링크하도록 바꾸면 해소될 수 있고, 이런 구조의 연결 리스트를 원형 연결 리스트라 한다. 레퍼런스 __head 대신 마지막 노드에 대한 레퍼런스 __tail을 두고, 마지막 노드가 맨 앞의 더미 헤드 노드를 링크하게 만든다. 빈 원형 연결 리스트는 더미 헤드 노드가 자신을 링크한다. __tail을 마지막 노드를 가리키게 만들었을 때, 맨 뒤와맨 앞에 대한 접근성의 차.. 공감수 0 댓글수 0 2024. 9. 18.
연결 리스트 (Linked List) 3 - 연결 리스트의 구현 원소 삽입원소 x를 i번째 자리에 삽입하는 메서드# i번째 연결리스트의 원소 x 삽입하기def insert(self, i:int, newItem): if i >=0 and i ListNode: curr = self.__head for index in range(i+1): curr = curr.next return curr # 연결 리스트의 끝에 원소 x 추가하기 def append(self, newItem): prev = self.__append(self.__numItems-1) newNode = ListNode(newItem, prev.Next) prev.next = newNode self.__numItems +=1 원소 삭제i번째 노드를 삭제하는 메서드 # i.. 공감수 0 댓글수 0 2024. 9. 17.
연결 리스트 (Linked List) 2 - 각 작업 설명 원소 삽입 맨 앞에 원소 삽입__head : 첫 번째 노드를 가리키는 레퍼런스newNode.item = xnewNode.next = __head__head = newNode__numItems += 1... 중간, 맨 뒤에 원소 삽입prev: 삽입 노드의 직전 노드를 가리키는 레퍼런스newNode: 새로 삽입하려는 노드newNode.item = xnewnode.next = prev.nextprev.next = newNode__numItems += 1 .. 연결 리스트에 원소 삽입 알고리즘if i == 0: newNode.item = x newNode.next = __head __head = newNode __numItems +=1else: newNode.item = x newNode... 공감수 0 댓글수 0 2024. 9. 13.
연결 리스트 (Linked List) 1 - 객체 구조 연결 리스트의 객체 구조앞서 언급했듯이, 리스트의 하부 구조는 배열로 이루어져 있어서, 다음 두 가지와 같은 단점이 존재한다. 1. 배열의 크기는 고정되어 있어서 배열이 크기 이상으로 삽입될 경우, 더 큰 배열을 할당받아 원소를 모두 옮겨주는 작업을 진행해야함2. 원소를 삽입 또는 삭제하려면 일부 또는 원소 전부를 한 칸씩 시프트하는 불편함이 존재한다.' 연결 리스트(Linked List)는 배열의 공간 낭비를 피할 수 있는 자료구조이다. 원소가 추가 될 때마다 공간을 할당받아 추가하는 동적 할당 방식을 따른다. 연결 리스트의 노드 구성 item : 정수나 실수 같은 숫자 타입이나 복잡한 객체가 저장 필드next : 다음 노드를 가리키는 링크 연결 리스트의 일반적인 형태__head : 첫 번째 노드를 .. 공감수 1 댓글수 1 2024. 9. 13.
리스트(List) 리스트(list)는 '줄 세워진 데이터' 또는 '늘어선 데이터'를 의미한다. 리스트의 작업 리스트 ADT 예시i번 자리에 원소 x 삽입i번째 원소 삭제원소 x 삭제i번째 원소 확인원소 x의 index리스트 사이즈 etc 리스트 구현 파이썬의 리스트는 하부가 배열로 구현되어 있다중간에 원소 삽입하면, 삽입한 원소 이후의 원소들이 모두 한칸씩 shift 하게됨확보해놓은 배열 공간이 다 찼을 때, 새로운 배열을 할당받아 기존 배열 내용 복사 etc하부 작업을 직접하진 않지만, 배열 기반 리스트의 단점은 분명히 존재함리스트의 객체 구조파이썬에서는 리스트 자료구조가 기본적으로 제공된다. 아래 선언한 리스트 a, b는 각각 하나씩의 객체다.a = []b = [1, 3, 5] 리스트 객체에서는 다음과 같이 11개의.. 공감수 0 댓글수 0 2024. 9. 13.
재귀와 귀납적 사고 어떤 문제나 함수 등이 자신과 성격이 똑같지만 크기가 더 작은 문제를 하나 이상 포함하고 있을 때 재귀적 구조를 갖고 있다고 말한다. 재귀 구조 예시 수열 등차 수열 seq(n): if n = 1: return 1 else: return seq(n-1) + 5 ※반복해서 호출하는 재귀 알고리즘은 끝나기 위해서 반드시 경계 조건을 가지고 있어야한다. 위 알고리즘에서는 if n = 1이 경계조건이다. 피보나치 수열 fib(n): if n=1 or n=2: return 1 else: return fib(n-1) + fib(n-2) ※재귀 알고리즘의 사용은 문제를 해결하는데 유용할 수 있지만, 잘못 쓰면 치명적일 수 있다. 위에 예시에서 n이 커질수록 걸리는 시간이 매우 증가하게 된다. 이는 한번 계산했던 결과.. 공감수 0 댓글수 0 2024. 2. 13.
자료구조 소개 자료구조 간략 소개 선형 자료구조 : 데이터가 한줄로 배치된 자료구조 색인 자료구조 : 데이터를 효율적으로 찾기 위한 자료구조 추상 자료형 (Abstract Data Type) 추상 데이터 타입(ADT : Abstract Data Type)은 어떤 데이터 타입이 어떤 작업으로 이루어지는지만 표현한 것으로, 구현 방법을 명시하지 않는다는 점에서 자료구조와는 다르다. 어떤 대상이 '지원하는 작업을 나열해 표현'하는 것을 '추상적으로 표현'한다라고 하며, 대상을 그렇게 표현한 것을 추상적 데이터 타입이라고 한다. ex) 리스트의 ADT 표현 ADT '리스트' 작업: i번째 자리에 새 원소 넣기 원소 x 찾기 i번째 자리의 원소 삭제하기 비어 있는지 확인하기 청소하기 위처럼 특정 대상에 대한 ADT는 유동적이다.. 공감수 0 댓글수 0 2024. 1. 23.
CPU 스케쥴링 알고리즘 CPU 스케쥴링 알고리즘의 종류는 매우 다양하고 운영체제 저마다 서로 다른 스케쥴링 알고리즘을 사용하고 있다. 스케쥴링 알고리즘의 종류 선입 선처리 스케쥴링 선입 선처리 스케쥴링은 FCFS(First Come First Served Scheduling)이라고 부르며, 단순히 준비 큐에삽입된 순서대로 프로세스를 처리하는 비선점형 스케쥴링 방식이다. 프로세스들이 기다리는 시간이 매우 길어질 수 있다. CPU를 오래 사용하는 프로세스가 먼저 도착하면, 다른 프로세스들은 그 프로세스가 CPU를 사용하는 동안 무작정 기다릴 수 밖에 없게 된다. 이를 호위 효과(convoy effect)라고 한다. 최단 작업 우선 스케쥴링 최단 작업 스케쥴링은 SJF 스케쥴링 (Shortest Job First Scheduling.. 공감수 0 댓글수 0 2023. 5. 26.
CPU 스케쥴링 운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것을 CPU 스케쥴링(CPU scheduling)이라고 한다. 프로세스 우선순위 CPU 할당을 기다리는 프로세스 순서대로 CPU를 사용하는 것은 합리적인 것처럼 보이지만, 합리적인 방법이 아니다. 프로세스마다 우선순위가 다르고, 우선순위가 높은 프로세스는 빠르게 처리해야 하는 프로세스를 의미한다. 우선순위가 높은 프로세스는 대표적으로 입출력 작업이 많은 프로세스이다. 그리고 입출력 작업이 많은 프로세스를 먼저 실행시키는 것이 효율적인 이유는 아래 예시를 통해 알 수 있다. 먼저, 일반적인 프로세스가 어떤 과정을 거치며 실행되는지를 봐야한다. 대부분의 프로세스들은 다음과 같이 CPU와 입출력장치를 모두 사용하며 실행된다. 위의 그림과 같이.. 공감수 0 댓글수 0 2023. 5. 26.
캐시 메모리 CPU는 프로그램 실행 과정에서 메모리의 저장된 데이터를 빈번하게 사용한다. 하지만 CPU가 메모리에 접근하는 시간은 CPU가 연산하는 시간보다 느리기 때문에, 이를 극복하기 위한 저장 장치가 캐시 메모리이다. 저장 장치 계층 구조 (memory hierarchy) 컴퓨터가 사용하는 저장 장치들은 CPU에 얼마나 가까운가를 기준으로 계층적으로 나타낼 수 있다. CPU에 가까운 저장 장치는 빠르고, 멀리 있는 저장 장치는 느리다. 속도가 빠른 장치는 저장 용량이 작고, 가격이 비싸다. 캐시 메모리 (cache memory) 캐시 메모리는 CPU와 메모리 사이에 위치하고, 레지스터보다 용량이 크고 메모리보다 빠른 SRAM 기반의 저장 장치이다. CPU의 연산 속도와 메모리 접근 속도의 차이를 줄기이 위해 만.. 공감수 0 댓글수 0 2023. 4. 28.
메모리 RAM의 특징과 종류 RAM의 특징 주기억장치의 종류에는 크게 RAM과 ROM이 있고, RAM에는 실행할 프로그램의 명령어와 데이터가 저장된다. 휘발성 저장 장치(volatile memory) 전원을 끄면 저장된 내용이 사라지는 저장장치 RAM 비휘발성 저장 장치(non-volatile memory) 전원이 꺼져도 저장된 내용이 유지되는 저장장치 ex) 하드 디스크, SSD, CD-ROM, USB 메모리 보조기억장치는 전원을 꺼도 내용을 유지하지만, CPU는 보조기억장치에 직접 접근하지 못하기 때문에, 비휘발성 저장 장치에는 보관할 대상을 저장하고, 휘발성 저장 장치에는 실행할 대상을 저장한다. RAM의 용량과 성능 RAM 용량이 크면 많은 프로그램들을 동시에 빠르게 실행시킬 수 있다. RAM의 종류 D.. 공감수 0 댓글수 0 2023. 4. 27.
CISC와 RISC 세상에는 수 많은 CPU 제조사들이 있고, CPU마다 규격과 기능, 만듦새가 다 다르다. 따라서, CPU가 이해하고 실행할 수 있는 명령어는 조금씩 차이가 있다. 이렇듯 CPU가 이해할 수 있는 명령어들의 모음을 명령어 집합 혹은 명령어 집합 구조 (Instruction Set Architecture)라고 한다. 예를 들어, 인텔 노트북 속 CPU는 x86혹은 x86-64 ISA를 이해하고, 애플의 아이폰 속 CPU는 ARM ISA를 이해한다. 따라서, x86과 ARM은 다른 ISA이기 때문에, 인텔 cpu를 사용하는 컴퓨터와 아이폰은 서로의 명령어를 이해할 수 없다. 정리하면, 같은 소스 코드로 만들어진 같은 프로그램이라 해도 ISA가 다르면, 어셈블리어도 같이 달라진다. 따라서, 명령어 병렬 처리 기.. 공감수 0 댓글수 0 2023. 4. 27.
명령어 병렬 처리 기법 명령어 파이프라인 명령어 처리 과정을 클럭 단위로 나누어 보면 일반적으로 다음과 같이 나눌 수 있다. 1. 명령어 인출 (Instruction Fetch) 2. 명령어 해석 (Instruction Decode) 3. 명령어 실행 (Execute Instruction) 4. 결과 저장 (Write Back) 명령어들을 동시에 처리하여 작동하기 위해서는, 각 단계를 동시에 실행할 수 있어야한다. 위와 같이 명령어들을 명령어 파이프라인에 넣고 동시에 처리하는 기법을 명령어 파이프라이닝(Instruction pipelining)이라고 한다. 파이프라이닝 자체는 높은 성능을 가져오지만, 특정 상황에서는 성능 향상에 실패하는 경우가 있다. 이러한 상황을 파이프라인 위험(pipeline hazard)라고 한다. 데이.. 공감수 0 댓글수 0 2023. 4. 27.
빠른 CPU를 위한 설계 기법 클럭 컴퓨터 부품들은 '클럭 신호'에 맞춰 작동되고, CPU는 '명령어 사이클'이라는 정해진 흐름의 맞춰서 명령어들을 실행한다. 따라서 클럭 속도가 높아지면 CPU는 명령어 사이클을 더 빠르게 반복하기 때문에, 일반적으로 클럭 속도가 높은 CPU는 성능이 좋다. 클럭 속도는 헤르츠(Hz) 단위로 측정하며, 이는 1초에 클럭이 몇 번 반복되는지를 나타낸다. 클럭 속도는 매번 일정하게 유지하지 않고, 고성능을 요하는 순간에는 순간적으로 클럭 속도를 높이고, 그렇지 않을 때는 유연하게 클럭 속도를 낮춘다. 최대 클럭 속도를 강제로 끌어 올리는 것을 오버클럭킹(over clocking)이라고 한다. 클럭 속도를 높이는 것은 CPU를 빠르게 만들지만, 클럭 속도만으로 CPU의 성능을 올리는 것은 한계가있다. 코어.. 공감수 0 댓글수 0 2023. 4. 27.
CPU의 작동 원리 - 명령어 사이클과 인터럽트 CPU가 하나의 명령어를 처리하는 과정에서 어떤 정형화된 흐름이 존재하는데, 이를 명령어 사이클이라고 한다. 또한 이 흐름이 끊어지는 상황도 발생하는데 이를 인터럽트라고 한다. 명령어 사이클 (Instruction Cycle) 인출 사이클(fetch cycle) 메모리에서 명령어를 CPU로 가져오는 단계 실행 사이클(execution cycle) CPU로 가져온 명령어를 실행하는 단계 간접 사이클 (indirect cycle) 어떤 명령어는 인출과 실행 사이클 만으로도 가능하지만, 어떤 명령어를 실행하기 위해서는 메모리 접근이 필요하다. 이때, 메모리 접근하는 단계를 간접 사이클이다. 인터럽트 CPU가 어떤 일을 수행중 방해를 받아서 중단될 수 있는데, 이러한 신호를 인터럽트라고 한다. 인터럽트는 크게 .. 공감수 0 댓글수 0 2023. 4. 7.
CPU의 작동 원리 - 제어장치, ALU, 레지스터 CPU는 메모리에 저장한 명령어를 읽고 해석하는 제어장치, 계산을 담당하는 ALU, 작은 임시 저장 장치인 레지스터로 이루어져 있다. 1. ALU와 제어장치 ALU ALU가 받아들이는 정보 ALU는 레지스터를 통해 피연산자를 받아들이고, 제어장치로부터 수행할 연산을 알려주는 제어 신호를 받아들인다. ALU가 내보내는 정보 연산을 수행한 결과는 특정 숫자나 문자, 메모리 주소가 될 수도 있다. 결과 값은 바로 메모리에 저장되지 않고 일시적으로 레지스터에 저장된다. -> CPU는 레지스터에 임시로 저장하는 것을 통해서 실행 속도를 빠르게 할 수 있다. ALU는 계산 결과와 함께 플래그를 내보낼 수 있다. 플래그는 CPU가 프로그램 실행 도중 반드시 기억해야 하는 참고 정보이다. 플래그는 플래그 레지스터에 저.. 공감수 0 댓글수 0 2023. 4. 7.
명령어 2 - 명령어의 구조 이 장에서는 기계어나 어셈블리어를 이루는 명령어를 자세히 살펴본다. 연산 코드와 오퍼랜드 명령어는 연산 코드와 오퍼랜드로 구성되어 있다. 명령어가 수행할 연산을 연산코드라 하고, 연산에 사용할 데이터나 연산에 사용할 데이터가 저장될 위치를 오퍼랜드라고 한다. 연산 코드가 담기는 영역을 연산 코드 필드라고 하고, 오퍼랜드가 담기는 영역을 오퍼랜드 필드라고 한다. 오퍼랜드 오퍼랜드 필드는 연산에 사용할 데이터 또는 연산에 사용할 데이터가 저장된 위치를 의미한다. 다만, 오퍼랜드 필드에는 연산에 사용할 데이터를 직접 명시하기 보다는 연산에 사용할 데이터가 저장된 메모리 주소나 레지스터 이름이 담긴다. 따라서 오퍼랜드 필드를 주소 필드라고 부른다. 명령어에 따라서 없을 수도 있고, 여러 개가 있을 수 있고 위 .. 공감수 0 댓글수 0 2023. 3. 31.
명령어 1 - 소스 코드와 명령어 이 장에서는 프로그래밍 언어로 작성한 소스 코드가 컴퓨터 내부에서 명령어가 되고 실행되는 과정을 학습한다. 고급 언어와 저급 언어 컴퓨터가 이해하는 언어가 아닌 사람이 이해하고 작성하기 쉽게 만들어진 언어를 고급 언어(high-level programming language)라고 한다. 대부분의 프로그램이 언어는 고급 언어에 포함된다. 컴퓨터가 직접 이해하고 실행할 수 있는 언어를 저급 언어(low-level programming language)라고 한다. 컴퓨터가 프로그램을 실행할 수 있기 위해서는, 고급 언어로 작성된 소스 코드가 저급 언어인 명령어로 변환되어야한다. 저급언어 기계어 기계어는 0과 1의 명령어 비트로 이루어진 언어이다. 기계어는 컴퓨터만을 위해 만들어진 언어로, 사람이 의미를 이해하.. 공감수 0 댓글수 0 2023. 3. 31.
데이터 이번 장에서는 컴퓨터가 0과 1로 데이터를 표현하고 학습하는 방법에 대해 알아본다. 0과 1로 숫자를 표현하는 방법 정보 단위 컴퓨터가 개발된 초기에 '전기 신호가 들어오고, 들어오지 않고'를 하나의 의미로 받아들였다. 따라서, 전기 신호가 들어온 상태(on) / 들어오지 않은 상태(off)를 각각 1,0으로 표현하였다. 이처럼 0과 1을 표현할 수 있는 가장 작은 정보 단위를 비트라고 한다. 1 비트는 (꺼짐), (켜짐)으로 2가지 정보를 표현할 수 있다. 2 비트는 (꺼짐, 꺼짐), (꺼짐, 켜짐), (켜짐, 꺼짐), (켜짐, 켜짐)으로 4가지 정보를 표현할 수 있다. 즉, n 비트는 2의 n제곱개의 정보를 표현할 수 있게된다. 우리가 사용하는 파일이나 프로그램은 수백만 개의 비트로 이루어져 있다. .. 공감수 0 댓글수 0 2023. 3. 31.
컴퓨터 구조 시작 컴퓨터 구조를 알아야 하는 이유 1. 문제 해결 프로그래밍 언어의 문법만 알고 있는 사람은 제대로 된 디버깅을 하기가 어렵다. ex) 실습이나 실무 상황에서, 같은 코드를 작성하여 실행시켰을 때 어떤 컴퓨터에서는 실행이 되고, 어떤 컴퓨터는 실행되지 않는 현상을 종종 마주할 수 있다. 컴퓨터 구조를 이해하고 있다면, 더욱더 심층적인 문제 상황 판단과 문제 해결의 실마리를 찾을 수 있다. 2. 성능, 용량, 비용 컴퓨터를 필요로 하는 상황에서, 어떤 특징의 CPU를 사용해야하고, 어떤 메모리를 사용해야 되는지를 현명하게 선택할 수 있고, 이는 성능, 용량, 비용을 고려하는 개발하는 개발자가 될 수 있다. 컴퓨터 구조를 제대로 알면, 프로그램을 위한 최적의 컴퓨터 환경을 스스로 판단할 수 있다. 컴퓨터 구조.. 공감수 0 댓글수 0 2023. 3. 28.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.