본문 바로가기

분류 전체보기

 (433)
브루트 포스(Brute Force) 브루트 포스의 의미는 모든 경우의 수를 다 구해서 문제를 해결하는 것이다. 이러한 브루트 포스의 핵심을 요약하자면 다음과 같다. • 브루트 포스로 문제를 풀기 위해서는 다음과 같은 3가지 단계를 생각해볼 수 있다. 1. 문제의 가능한 경우의 수를 계산해본다. • 직접 계산을 통해서 구한다. 대부분 손으로 계산해볼 수 있다. 2. 가능한 모든 방법을 다 만들어본다. • 하나도 빠짐 없이 만들어야 한다. • 대표적으로 그냥 다 해보는 방법, for문 사용, 순열 사용, 재귀 호출 사용, 비트마스크 사용이 있다. 3. 각각의 방법을 이용해 답을 구해본다. • 이 단계는 보통은 어렵지 않다. 문제에 나와있는 대로 답을 계산해본다. • 브루트 포스 문제의 시간 복잡도는 대부분 O(경우의 수 *방법 1개를 시도해보..
에라토스테네스의 체(소수 구하기) 소수(Prime)는 소수(素數, 발음: [소쑤], 문화어: 씨수, 영어: prime number)는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다. 예를 들어, 5는 1x5 또는 5x1로 수를 곱한 결과를 적는 유일한 방법이 그 수 자신을 포함하기 때문에 5는 소수이다. 그러나 6은 자신보다 작은 두 숫자(2×3)의 곱이므로 소수가 아닌데, 이렇듯 1보다 큰 자연수 중 소수가 아닌 것은 합성수라고 한다. 1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수로 정의하기도 한다. 합성수 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 합성수(合成數, Composite Number)는 1과 자기 자신이 아닌 다른 자연수의 곱으로 나타낼 수 있는 자연수를 의..
최대공약수(GCD) & 최소공배수(LCM) 구하기 최대공약수와 최소공배수는 수학의 기본적인 내용이다. 최대공약수는 말 뜻 그대로, 두 수의 공통적인 약수 중 최대로 큰 약수이다. 최소공배수 또한, 두 수의 공톡적인 배수는 최소로 작은 배수이다. 이러한 최대공약수와 최소공배수를 구하는 방식에 대해 살펴보자. 1. 최대공약수 먼저 최대공약수의 경우, 일일이 약수를 구해서 공통되는 약수 중 가장 큰 약수를 찾는 법이 있지만, 보다 효율적으로 유클리드 호제법을 사용하면 된다. 다음의 과정을 거치면 되는데, 이를 코드로 표현하면 다음과 같다. // 최대공약수 int gcd(int a, int b) { if (b == 0) return a; else { gcd(b, a%b); } } 생각보다 간단하다. 2. 최소공배수 최소공배수 또한 어렵지 않다. 최대공약수를 구..
Like 좋아요 모델 추가하기 좋아요를 구현하기에 앞서 모델 M:N 관계를 숙지해야 한다. 다수 대 다수의 관계를 맺고 있는 좋아요는 M:N의 관계 이다. 쉽게 말해, 글 하나에 여러 개의 댓글이 구성하던 1:N 의 관계와 달리 여러 유저와 여러 개의 좋아요의 관계가 구성되기에 M:N 다수의 관계이다. 구현에 앞서, Blog, Comment, User 3개의 모델이 구성되어 있어야 한다. 먼저 model에 Like 모델을 다대다(ManyToManyField)를 활용한다 # project/blog/models.py # M:N을 위한 속성 class User(models.Model): ... likes = models.ManyToManyField( User, # User 모델과 Blog 모델을 M:N 관계로 두겠다. through = '..
Chap 10. File System - File 개념(array of byte) - File System(disk block과 실제 file을 맵핑, 관리) - File System 구조(boot, super, inode, data) - FCB(file control block, INODE) 정보들(file type, file size, owner/group, # of blocks, timestamp, ptr to blocks) - INODE 구조(direct blocks, single indirect, double indirect, tirpple indirect) - directory in file system - virtual file system(vnode)
Chap 9. Virtual Memory Management - demand paging(Process에서 페이지 요구시 Os에서 처리) - Page fault(요구 - 부재 - Trap Os - Disk(page) - Page 갱신 후 - Table 갱신) - Pure Demand Paging(장 메모리 시간 절약, 연속 할당 / 단 반응성(속도 느림)) - Memory Perfomance 계산( (1-p)*m + p *f ) , slowdown(EAT/m) - COW(write가 이루어지는 순간에 copy) - Page replacement(Frame과의 관계, modify bit) - FIFO, OPT, LRU - LRU(HW 보조 counter, stack) - LRU ref bit, additional ref bit - LRU second chance A..
기말 정리 Chap 4. • Greedy Approach vs Dynamic Programming • Scheduling(GA로 해결 가능) 정렬 후 넣기 • Knapsack PB(GA는 fractional 만 가능), (DP를 써야 01 문제 해결가능)O(nW, 2^n) Chap 5. Backtracking • DFS 활용(promising 통해 안되는 곳 안들어가기) • N Queens (함수 들어올때 promising 일단 넣고 같은 행, 같은 열, 대각선 체크 후 통과하면 true) • Monte Carlo Alg 난수로 들어가기 • Sum of Subset(knapsack 동일) • Graph Coloring(연결 되어있고 색깔같으면 false) • Hamilton circuit(노드 한번만 방문), 하나..
Chap 7. 메모리와 프로그래머블 논리 - Memory PLD - 메모리(램 롬, rw ro) PLD 의미 - RAM Random access / Sequential accesss - memory 구성 (rw addr, io) enable + rw - RAM 개념 (순차 임의, 휘발, SRAM DRAM) - Memory Decoding circuits (동시, MUX) - 에러 정정(해밍코드) 2의 지수승 위치에 P 비트 추가해주고 2진수 나열해서 집합 구성후 XOR 연산 - 각 패리티비트 전부 XOR 연산 한 값으로 에렃위치 정정 가능 , 추가 패리티 비트 활용 - ROM 개념(읽을 수 만 있다) 회로 - PROM 회로와 ROM 종류 - PLD(AND OR 게이트 프로그래밍 가능하냐에 따라서 , PROM(01) PAL(10) PLA(11) ..

티스토리툴바