seulcoding

3.1. Sequential Logic Combinational Logic 지금까지는 시간에 대한 문제는 생각하지 않았음 input이 있고, output은 그냥 intput의 function 계산 이전에 다른 일들이 발생할 일이 없음 "즉시" 계산됨 -> 이를 "Combinational Logic" 이라고 함 하지만, 실제 세상에서는 "time"을 고려해야함 Hello, Time 크게 두가지를 고려해야됨 같은 hardware를 사용함 input은 변하고 output은 따라와야됨 ex. for loop State를 기억해야함 memory counters ex. for loop에서 sum을 계속 더할때 The Clock Physical time 실제 세상에서의 시간 컴퓨터 세상에서는 이런 복잡한 physic..

Binary search 순차탐색: 특정 데이터를 찾기 위해서 앞에서부터 확인하는 방법 이진탐색: 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 시작점, 끝점, 중간점 ex. 이미 정렬된 10개의 데이터 중 값이 4인 원소를 찾는 예시 시작접: 0, 끝점: 9, 중간점 4 (index) 중간점을 기준으로 다시 끝점, 중간점을 옮김 시간복잡도: logN (단계마다 탐색범위를 2로 나누는 것) 이진탐색 소스: 재귀적 구현 def binary_search(array, target, start, end): if start > end: return None mid = (start + end) // 2 # 찾은 경우 중간점 인덱스 반환 if array[mid] == target: return mid # 중간점..

Greedy algorithm 현재 상황에서 지금 당장 좋은것만 고르는 방법 문제를 풀기 위한 최소한의 아이디어 정당성 분석: 이 방법으로도 문제가 제공하는 최적의 해를 구할 수 있는지 일반적인 상황에서 그리디 알고리즘으로는 최적의 해를 보장하지 못할 때가 많음 문제 거스름돈 문제 (500, 100, 50, 10) 정당성 분석 큰 단위가 항상 작은 단위의 배수이기 때문에 작은 단위의 배수가 아니라면 최적의 해를 보장해주지 못함 (i.e. 500, 400, 100...) 시간복잡도 화폐의 개수에 따라 증가하므로 O(K) (화폐가 K개일때) n = 1260 count = 0 coins = [500, 100, 50, 10] for coin in coins: count += n // coin n = n % co..

2.1. Binary numbers 2진법에 대한 간단한 설명. 자세한 내용은 생략 2.2. Binary addition 이진법을 더하는 법. 10진수처럼 더하면 된다. 다만 할당된 비트 (ex. 8bit + 8bit)를 넘어서는 carry는 overflow로 처리된다. 3가지 형태의 adder를 만들어볼 예정 Half adder 두 bit를 더함. a, b를 더해서 sum(값)과 carry가 나옴 | a | b | sum | carry | | 0 | 0 | 0 | 0 | | 0 | 1 | 1 | 0 | | 1 | 0 | 1 | 0 | | 1 | 1 | 0 | 0 |Full adder 위의 half adder에서 이전 계산에서 나온 carry도 받는 adder a, b, c(이전 carry)를 받아서 s..

1.1 boolean logic 불 대수: true/false, yes/no, on/off, 1/0 같은 2진수(bool) 값을 다루는 대수학. bool function: 2진수를 입력받아 2진수를 출력하는 함수 컴퓨터는 2진수를 표현하고 처리하는 하드웨어이기 때문에 불 함수는 하드웨어 아키텍처의 중심. Boolean Operation AND, OR, NOT Boolean expression NOT(0 OR (1 AND 1)) = NOT(0 OR 1) = NOT(1) = 0general expression을 만들 수 있음 f(x, y, z) = (x AND y) OR (NOT(x) AND z)이 함수가 어떤 함수인지 알기 위해서는 모든 x, y, z을 truth table로 만들어보면 된다. 1.2 Bo..