학업 정리 (20) 썸네일형 리스트형 Planar Graph Planar Graph란, 평면 상에서 모든 Edge(또는 Vertice)가 서로 겹치지 않게 표현되는 Graph다. 노드 수가 4개 이하인 Complete Graph는 Planar Graph로 표현할 수 있지만, 노드 수가 5개 이상인 Complete Graph는 Planar Graph로 표현할 수 없다. 노드가 4개인 Complete Graph를 Planar Graph로 표현한 상태에서 노드 하나를 더 추가하면 Planar Graph를 만들 수 없음을 확인하라. 문제 다음 조건을 만족하는 그래프 G_n은 Planar Graph로 표현할 수 있을까? G_n의 노드는 노드 1, 노드 2, ..., 노드 n이다. (n은 자연수) 노드 x, 노드 y에 대해, x, y가 서로소이면 두 노드 사이에 Edge가 .. [C/C++/C#] 멀티스레드를 위한 Mutex, Interlocked, 그리고 ABA Problem 멀티스레드 프로그래밍에서 여러 스레드가 한 변수의 값을 동시에 변경하고자 하는 상태를 경쟁상태(Race Condition)라고 한다. 이때, 값을 읽고 새 값을 대입하는 과정을 원자적(atomic)으로 진행하지 못하면 충돌이 발생한다. 이를 해결하는 방법은 여러가지가 있다. 여기 C++과 C#으로 각각 구현한 코드를 알아보자. C/C++ 아래의 코드는 C/C++에서 Lock-free로 단일 연결 리스트(Linked List)를 구현한 예제의 일부다. #include #include #include #include using namespace std; #define NodeAddress unsigned long long #define NodeAddressMask 0x000FFFFFFFFFFFFF #defi.. 하노이 타워의 원판 이동 횟수 하노이 타워에 간단한 코드는 https://gunhoflash.tistory.com/41 참고. 일반적인 하노이 타워 문제에서, 한 기둥에 있는 n개의 원판을 다른 기둥으로 완전히 이동시키는 데 필요한 원판 이동 횟수를 F(n) 이라 할 때, F(n)을 n에 대한 식으로 나타내보자. 먼저, F(0) = 0, F(1) = 1 이다. 자연수 n에 대해, F(n) = F(n - 1) + 1 + F(n - 1) = 2F(n - 1) + 1 이다. 따라서, F(n) = 2F(n - 1) + 1 = 2(2F(n - 2) + 1) + 1 = 4F(n - 2) + 3 = 4(2F(n - 3) + 1) + 3 = 8F(n - 3) + 7 = ... = 2^((n - 1) - 1)(2F(n - (n - 1)) + 1) +.. Harvard Architecture, Von Neumann Architecture 컴퓨터에서 CPU는 메모리에서 명령과 데이터를 읽고 작업을 수행한다. 이때 컴퓨터의 구조는 크게 Havard Architecture와 Von Neumann Architecture로 구분된다. 둘의 차이는 메모리에서 명령과 데이터의 저장방식의 차이로부터 기인된다. Havard Architecture Havard Architecture는 명령과 데이터가 다른 메모리에 저장된다. 따라서 CPU는 명령과 메모리를 각각 버스를 통해 동시(1 clock)에 로드할 수 있기 때문에 처리속도가 빠르다고 할 수 있다. 하지만 회로가 복잡해지는 단점이 있다. Von Neumann Architecture Von Neumann Architecture는 명령과 데이터가 구분되지 않고 같은 메모리에 저장된다. 따라서 CPU는 명.. 인공지능 과제 - 단일 퍼셉트론 구현 코드 설명 3개의 perceptron을 만들어 각각 AND-gate, OR-gate, XOR-gate의 동작을 하도록 학습시킨다. main함수에서는 perceptron의 학습에 사용될 데이터를 정의하고 perceptron을 만들어 학습시킨다. Perceptron.h 헤더파일에서 Perceptron을 class로 정의했으며 Calculate, Train 등 여러 메소드가 구현되어있다. Perceptron의 weight와 threshold는 contructor에서 아래 범위의 랜덤한 실수(float)로 초기화된다. weight: -1이상 1이하 threshold: 0초과 1이하 코드 src.c /* 2019-2 인공지능 과제2 코드 2015920003 컴퓨터과학부 김건호 */ #include #i.. RAM, ROM에 대한 간단한 정리 DRAM과 SRAM의 차이, ROM의 종류에 대해 간단히 알아보자. RAM: Random-Access Memory 말 그대로 임의 접근 메모리이다. 접근할 데이터의 주소(위치)에 따라 접근시간이 다른 기억장치(Disk, Tape 등)와는 다르게, 임의의 데이터에 동일한 시간 내로 접근할 수 있다. 전원 공급이 중단되면 저장된 데이터가 손실(휘발)된다는 특징이 있으며, 데이터를 저장하는 소자에 따라 DRAM과 SRAM으로 나뉜다. DRAM: Dynamic Random-Access Memory Capacitor에 전하를 충전하는 방식으로 데이터를 저장한다. Capacitor는 시간이 지남에 따라 전자를 누전하므로 주기적인 재충전이 필요하며, 이 때문에 Dynamic Memory라고 한다. DRAM은 1비트 .. 시스템 버스와 중재, 인터럽트, DMA 시스템 버스는 컴퓨터 시스템의 구성요소(CPU, RAM, I/O 등)를 연결하는 중심 통로이다. 버스는 각종 정보를 전송하는 선으로 구성되어 있고, 이 선의 수에 따라 한 번에 전송되는 데이터의 양이 결정된다. 일반적인 컴퓨터 시스템에서 버스는 버스 클록의 주기에 의해 속도가 결정된다. 예를 들어 버스 클록의 주기가 50ns이고 버스의 폭이 64bit(=8byte)라면, 버스 대역폭은 160MB/s가 된다. 한편, 버스 사용의 주체가 되는 요소를 버스 마스터라고 하며, 다수의 버스 마스터가 동시에 버스를 사용하고자 할 때 이 순서를 제어하는 동작을 버스 중재라고 한다. 시스템 버스의 기능에 따른 분류 시스템 버스는 기능에 따라 다음과 같이 분류된다. 데이터 버스 시스템 요소 간 데이터를 전송하는데 사용되.. 25 Sliding Puzzle 이번 학기에 수강 중인 Computer Algorithm 강의에서 팀 프로젝트 과제가 2개 있었다. 이 글은 그 중 2번째 과제인 Sliding Puzzle에 관한 것이다. 문제 5*5 사이즈의 Sliding Puzzle이 있다. 24개의 퍼즐조각과 1개의 빈 칸이 있는데, 이 퍼즐을 완성하는 과정을 보여라. 완성된 퍼즐의 상태는 다음과 같다. 입력 퍼즐의 개수가 첫 줄에 주어지고, 이어서 각 퍼즐의 상태가 입력된다. 퍼즐의 상태는 25개의 수로 나열되는데, 이 중 1부터 24는 퍼즐조각을 나타내고, 25는 빈 칸을 나타낸다. 출력 각 줄에 퍼즐의 번호와, 빈 칸의 이동횟수, 이동과정(L, R, U, D)을 출력한다. 풀 수 없는 문제가 주어지면 -1을 출력한다. 입력 예시 15 1 2 3 4 5 6 7.. 이전 1 2 3 다음
