전체 글

[Combinational Logic Circuit] 인코더(Encoder)

해당 강의노트는 S. Brown and Z. Vranesic, McGraw-Hill의 [Fundamentals of Digital Logic with VHDL Design, 3rd Edition] 책을 기반으로 작성되었습니다 Encoder - Encoder - $2^n$-to-n binary encoder - $2^n$-to-n priority encoder Encoder 인코더(Encoder)란? 인코더는 디코더의 역연산(reverse operation)을 수행하는 조합 논리 회로(combinational logic circuit)로, $2^n$-bit개의 입력 정보를 n-bit개 데이터로 출력한다. 이 과정을 입력에 대해 인코딩한다라고 함. 인코더 응용 사례 - 모든 디지털 시스템에 사용되는 매우 일..

[Combinational Logic Circuit] 디코더(Decoder)

해당 강의노트는 S. Brown and Z. Vranesic, McGraw-Hill의 [Fundamentals of Digital Logic with VHDL Design, 3rd Edition] 책을 기반으로 작성되었습니다 Decoder - Decoder - An n-to-$2^n$ binary decoder - Tri-state Buffer - Read-only Memory, ROM Decoder 디코더(Decoder)란? 디코더는 다중 입력에 다중 출력 조합 논리 회로(combinational logic circuit)로, n-bit 데이터 입력을 코드화된 $2^n$개의 출력으로 변환한다. (인코더에 의해 숨겨진 정보를 해독함) 디코더 응용 사례 - 디코더의 역할은 입력 이진수를 하나의 출력으로 연..

[Combinational Logic Circuit] 멀티플렉서(Multiplexer, MUX)

해당 강의노트는 S. Brown and Z. Vranesic, McGraw-Hill의 [Fundamentals of Digital Logic with VHDL Design, 3rd Edition] 책을 기반으로 작성되었습니다 Multiplexers - Multiplexer Circuit - Synthesis of a logic function using MUXs - Shannon's Expansion Theorem Multiplexer Circuit 멀티플렉서(Multiplexer, MUX)란? 복수 개의 입력 신호로부터 특정 조건에 의해 입력 신호를 한 개만 선택할 때 사용하는 것 디멀티플랙서(Demultiplexer, DeMUX)란? 멀티플렉서와 반대의 목적에 사용 됨 멀티플랙서 회로 - -to- M..

[SWEA] 그래프의 최소 비용 문제

본 글은 [SW Expert Academy]의 파이썬 SW문제 해결 응용-구현2 완전 검색 강의를 보고 정리한 글입니다 https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDYSqAAbw5UW6&subjectId=AWUYHO7a2JoDFAVT# SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 그래프의 최소 비용 문제 목차 01 최소 신장 트리 02 프림 알고리즘 03 크루스칼 알고리즘 04 최단 경로 05 다익스트라 알고리즘 01 최소 신장 트리 그래프에서 최소 비용 문제 유형 1. 최소 *신장 트리 문제 가중치 그래프에서 모든..

[Python] BOJ 9663. N-Queen

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net NxN 체스판에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력하는 문제로 N=4일때를 예시로 들면 다음과 같이 설명할 수 있다 4x4 체스판에 퀸 4개가 아래와 같이 있다 상태 공간 트리(State-Space Tree)로 1~4번 퀸의 위치를 표현할 수 있다 아래는 4개의 퀸들이 서로 공격할 수 없게 놓은 경우의 수 중 하나로, 상태 공간 트리로 표현했을 때는 다음과 같은 경로를 거치게 된다 - 퀸은 현..

이진 탐색(Binary Search)과 매개변수 탐색(Parametric Search)

이진탐색이란? 이진 탐색이란 정렬된 배열에서 타겟의 존재 여부와 존재한다면 해당 위치를 알려주는 알고리즘이다. 중요한 점은 정렬된 배열에서만 사용할 수 있다는 것이다 기존의 단순 비교를 통한 탐색을 한다면 최악의 경우 배열 안에 있는 N개의 데이터 모두와 비교해야하므로 시간복잡도가 O(N)인 반면, 이진탐색은 재귀적으로 탐색범위를 반으로 줄여나가서 시간복잡도가 O(logN)까지 줄일 수 있다 이진탐색과 매개변수 탐색 매개변수 탐색(parametric search)이란? *최적화 문제를 *결정 문제로 풀 수 있는 기술로 다음과 같은 상황에 이용할 수 있다. *최적화 문제(Optimization Problem): 가능한 해들 중 가장 좋은 해를 찾는 것 *결정 문제(Decision Problem): 답이 이..

파이썬으로 구현하는 퀵 정렬(Qucik Sort)

Concept 병합 정렬(Merge Sort)과 마찬가지로, 퀵 정렬은 분할 정복(Divide and Conquer) 기법과 재귀 알고리즘을 이용한 정렬 알고리즘으로, 시간복잡도는 $O(nlogn)$이다 하나의 리스트에서 피봇(pivot)이라고 불리는 임의의 기준값을 사용하여 pivot 값을 기준으로 pivot 보다 작은 값의 그룹과 큰값의 그룹으로 나눈다. 이 때 두 그룹의 각 요소들은 정렬된 상태는 아니지만, pivot은 정렬된 위치로 들어가게되며 이를 재귀호출을 통해 정렬하게 된다. 전체적인 동작 과정은 다음과 같다 구현 코드 (아래 코드는 pivot을 arr의 첫번째 요소로 잡은 코드입니다; pivot = arr[0]) 1) 정렬되지 않은 데이터 -> 리스트로 입력 받기 >>>3 2 4 6 9 1..

파이썬으로 구현하는 병합정렬(Merge Sort)

Concept 병합정렬은 분할 정복(Divide and Conquer) 기법과 재귀 알고리즘을 이용한 정렬 알고리즘으로, 시간복잡도는 O(nlogn)이다 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻는 정렬방법이다. 이때 병합 정렬은 아래와 같은 분할 정복 메커니즘을 따르게 된다 - 분할(Divide): 입력 리스트를 같은 크기의 2개의 부분 리스트로 분할한다 - 정복(Conquer): 부분 리스트를 정렬한다 - 결합(Combine): 정렬된 부분 리스트를 하나의 리스트에 통합한다 *이 때 그림에서 표현은 생략되었으나 부분 리스트의 크기가 1이 될 때까지 분할 후 정렬 후 합병과정을 거치게 된다 구현 코..