본문 바로가기
728x90

전체 글427

난수 생성 algorithm Psuedo Random 우선 컴퓨터가 난수를 생성하기 어렵다는 것을 알아야한다. 컴퓨터는 사람과 달리 무의식적인 선택, 또는 우연에 의한 선택을 할 수 없기에 기본적으로 정해진 입력에 따라 정해진 값을 낼 수 밖에 없기 때문이다. 이를 결정적 유한 오토마타(Deterministic Finite Automata)라고 한다. 이는 컴퓨터가 하나의 입력에 대해 무조건 하나의 전이만 가능하기 때문이다. 따라서 컴퓨터는 특정한 방법으로 계산하거나 계속해서 변하는 값을 초기값으로 잡고 계산과정을 거쳐서 사람이 보기에 난수처럼 보이도록 하는 의사 난수(psuedo random)을 이용한다. 흔히 난수표를 만들어두고 그를 이용하여 의사 난수를 생성한다. 그러나 난수표가 정해진 순간 같은 수로 다시 돌아온다는 것이 확.. 2022. 11. 17.
C++ 난수 생성 rand함수 #include #include #include int main() { srand(time(NULL)); for (int i = 0; i < 5; i++) { printf("Random Num : %d \n", rand() % 100); } return 0; } rand함수를 이용한 위 코드를 보면 srand, time, rand와 같은 함수들을 볼 수 있다. 우선 위의 코드는 실제 난수를 생성하는 코드가 아니라 난수처럼 보이도록 하는 의사 난수(pseudo random number)를 생성하는 코드이다. srand 함수로 무작위로 정해지는 첫 숫자인 seed를 설정할 수 있다. 위 코드의 경우 time(NULL)을 통해 프로그램을 실행했던 시간 초를 시드값으로 지정햇다. 그리고 rand().. 2022. 11. 17.
OS (pthread) fork의 return값은 child에서 0이고 parent는 pid이다. 0인경우와 그렇지 않은 경우로 조건문을 나누었으나 child와 parent 모두 40000000이 나온것으로 보아 fork를 진행하면 child와 parent에서 모두 process가 진행됨을 알 수 있다. deadlock 상태가 되어 아무것도 출력이 되지 않았다. 코드를 수정해보았다. foo2 함수에서 pthread_mutex_lock 함수를 통해 뮤텍스 잠금을 요청하고 임계영역에 접근을 해야하는데 lock1과 lock2의 순서가 바뀌어서 lock1과 lock2가 얽혀서 dedlock상태가 된것으로 추정되어 그 순서를 바꾸었더니 제대로 출력이되었다. 2022. 11. 13.
OS (fork) Fork Fork의 과정을 5ex1.c에서 실행하였다. Fork는 다음과 같은 과정을 통해 실행이 된다. 5ex1 running -> fork -> mov eax,2 , INT 128 -> system call: -> sys_fork -> do_fork 이를 정리하면 다음과 같다. 1. body를 복사합니다. 2. 프로세스 디스크립터를 복사합니다. 3. child에 대한 정보를 조정합니다. 4. child에게는 NULL값을 return하고 parent에게는 child의 pid를 return합니다. 따라서 위의 코드를 보면 먼저 child가 실행되어서 x:0이 먼저 출력되고 그 다음에 부모가 실행되어 x의 값에 4770를 return합니다. 이것으로 child의 pid는 4770번임을 알 수 있습니다. 과.. 2022. 11. 10.
Baekjoon Training #24499 #24499 누적합을 이용하여 풀이를 진행하고자 하였다. 누적합은 itertools module에서 accumulate 함수를 import해와서 사용할 수 있다. accumulate 함수의 작동원리를 살펴보면 다음과 같다. from itertools import accumulate arr = [1, 2, 3, 4, 5] result = accumulate(arr) for sum in result: print(sum) """ output: 1 = 1 3 = 1 + 2 6 = 3 + 3 10 = 6 + 4 15 = 10 + 5 """ 위와 같은 return갑을 내놓는 accumulate 함수를 이용하여 24499번을 풀이하였다. import sys from itertools import accumulate .. 2022. 11. 9.
Bubble sort, Insertion sort, Selection sort Bubble Sorting Algorithm 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다. 알고리즘의 흐름을 보면 이중 반복문을 통해 안쪽 반복문을 이용하여 0번 인덱스와 1번 인덱스를 비교하고 1번 인덱스와 2번 인덱스를 비교하는 방식으로 i번째 인덱스와 i+1번째 인덱스를 비교한다. 다음으로 바깥 반복문을 수행하려고 보면 마지막 인덱스에는 가장 큰 자료가 도달해있다. 그러면 마지막 인덱스를 제외하고 n-1번째까지 반복문을 진행하면 n-1번째 인덱스에 두번째로 큰 자료가 도착을한다. 따라서 바깥반복문은 j data[j+1]) { temp = data[j+1]; data[j+1] = data[j]; data[j] = temp; } } } } Time complexity Tn = (n-1)+(n-.. 2022. 11. 8.
Coursera-Supervised Machine Learning: Regression and Classification (8) Chapter 1 fin. Gradient descent algorithm 교수님이 식에 대한 자세한 이해보다는 아 그렇구나 하고 넘어가도 아무 상관이 없다고 하셨다. 그래도 어떤 연산이길래 그냥 넘어가라고 하시나 궁금해서 한번 봤더니 역시 교수님의 말씀에는 다 이유가 있었다. 이전에도 공부했던 내용인 gradient descent algorithm에 대해 다시보면 최소값을 찾아가는 과정이지만 Global Minimum을 찾는 과정이 아니라 Local Minimum을 찾아가는 과정으로 아래와 같이 여러개의 Local Minimum에 도달하여 결과를 도출할 수 있다. 그러나 convex function꼴로 표현을 하면 아래와 같이 bowl-shape로 global minimum 하나만 존재하여 절대 multiple local min.. 2022. 11. 6.
Signal and System approximate computing 1번 문제 소스코드 import math #삼각함수와 pi를 이용하기 위해 math 모듈 import import matplotlib.pyplot as plt #pip install matplotlib을 통하여 미리 module install N = int(input()) #예삿값을 구하기 위한 N을 입력 t = 0 graph = [] #빈 리스트 생성 def sigma(t): #x_hat_n(t)의 결과를 구하는 sigma 함수 정의 n = 1 #n -> 1~N sum = 0.0 while n < N: #n이 N보다 작은 경우에 sum += (4.0 / math.pi) * (1 / n) * math.sin(n * math.pi * float(t)) #x(t)식 계산 n += 2 #n에 홀수값 대입 re.. 2022. 11. 6.
OS(process id) task_struct is defined in include/linux/sched.h (search for "task_struct {"). Which fields of the task_struct contain information for process id, parent process id, user id, process status, children processes, the memory location of the process, the files opened, the priority of the process, program name? ---process id: pid_t pid ---parent process id: struct task_struct *parent ---user id: uid_t.. 2022. 11. 5.
OS(interrupt) 함수의 첫줄에 내용을 추가하였습니다. Reboot 해보니 login화면에서부터 타이핑 자체가 진행이 되지 않았습니다. 이는 원래 interrupt가 발생 후, 키보드 입력과정을 처리한 뒤 IRQ_HANDLED를 리턴하는데, 이과정들을 거치지 않고 바로 IRQ_HANDLED를 리턴하도록 했기 때문에, 어떤 문자를 입력해도 실행이 되지 않는 것입니다. Login 자체가 불가능하여 다시 타이핑이 가능하게 하려면 linux2로 접속하여 함수를 다시 바꿔주고 리부팅을 해야했습니다. Printk를 통해 x pressed를 구현했다. 이와 같이 입력하면 x pressed가 출력이되는 것을 확인했습니다. Code의 값을 하나 증가 시키도록 하여 입력한 키의 오른쪽 버튼이 입력되도록 하였습니다. 다음과 같이 입력됨을 확.. 2022. 11. 5.
Baekjoon Training #2805 #2805 import sys input = sys.stdin.readline #시간초과 방지 N, M = map(int,input().split()) #나무 수 N, 원하는 나무 길이 M 입력 trees = [int(n) for n in input().split()] #나무들의 길이 입력 def tree_cut(): #기준 길이를 정하는 함수 define standard_len = 0 #기준 길이 0으로 초기화 while True: # 기준 길이를 1씩 늘려주며 반복 standard_len += 1 sum = 0 for i, tree in enumerate(trees): #trees 리스트의 원소를 integer type으로 그대로 입력받기 위해 이용 if tree > standard_len: #tre.. 2022. 11. 5.
Baekjoon Training #1753 #1753 문제를 풀기앞서 이번 문제에서는 코드를 작성하기 전에 공부해야하는 내용이 많았다. 우선 이문제는 정점에서 정점으로의 최단거리를 계산하는 문제중 다익스트라 알고리즘을 이용하는 문제였다. 다익스트라 알고리즘은 graph 자료구조에서 우선순위큐를 사용하여 방문하지 않은 노드를 방문하는 방식으로 최단 거리를 계산하는 알고리즘이다. 이에 대한것은 Dijkstra Algorithm 게시물에서 자세하게 다뤘다. import sys import heapq input = sys.stdin.readline #시간초과 방지 INF = 10000000000 #무한을 상징 V,E = map(int, input().split()) #정점, 간선 개수 입력 K = int(input()) #시작 정점 입력 graph = .. 2022. 11. 1.
728x90

티스토리툴바