728x90 공부167 너비 우선 탐색(BFS) ※이 포스팅은 나동빈님 강의를 듣고 정리한 것 입니다.※ https://www.youtube.com/watch?v=66ZKz-FktXo&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=16 너비 우선 탐색 (Breath-First-Search, BFS)입니다. 너비 우선 탐색은 탐색을 할 때 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘입니다. 특히나 '맹목적인 탐색' 을 하고자 할때 사용하는 탐색 기법이고 미로찾기와 같은 곳에서 많이 활용이 됩니다. 이는 '최단 경로'를 찾아준다는 점에서 최단 길이를 보장해야 할 때 많이 사용됩니다. 큐를 이용합니다. 'BFS는 가까운 거를 먼저 탐색한다'라는 개념입니다. 큐와 그래프가 준비가 되었습니다. BFS는 맨 처음에 시작.. 2020. 6. 3. 알고리즘 스택, 큐 알고리즘에서 가장 많이 활용이 되는 자료구조가 스택과 큐가 아닐까 싶습니다. 그냥 다른 수업을 들을 때도(메모리의 스택구조라던가, 데이터통신에서 큐잉이론이라던가) 정말 자주 나오는 주제인데요. 오늘은 알고리즘 측면에서 stack 라이브러리에 사용에 대해 이야기 해보겠습니다. 일단 stack 은 접시 쌓기라고 생각하시면 됩니다. 접시를 쌓는다고 생각할때 위로 쌓이잖아요? 그리고 접시가 필요해서 하나 들고갈때는 가장 아래거를 들고 가나요? 아니죠. 가장 위에 있는 접시, 즉 가장 최근에 놔둔 접시를 가져갑니다. 이처럼 스택은 가장 최근에 들어온 게 가장 먼저 나가는 구조입니다. 아래 그림을 보면 조금 더 쉽게 이해가 되실 겁니다. 스택을 삽입(Push) 하는 과정입니다. 4를 먼저 넣었기 때문에 4가 제일 .. 2020. 6. 3. 데이터통신-Signal Encoding/Modulation(2) Digtal 신호를 Digtal 신호로 사용되는 기법은 6가지가 있습니다. 그중에 두인 NRZ-L과 NRZ-I 에 대해 먼저 이야기해보도록 하겠습니다. Nonreturn to Zero-Level(NRZ-L) - 0 -> 1 / 1 -> 0 Nonreturn to Zero-Inverted(NRZ-I) - differential encoding 사용 아래 그래프를 보면 NRZ-L 의 규칙은 빠르게 알 수 있습니다. 하지만 NRZI는 ... 잘 모르겠죠. differential encoding 을 사용하기 때문입니다. differential encoding 이 뭐냐하면은 0,1 의 값을 표현하는게 아니라 변화를 파악하는 겁니다. '0이 들어왔네? ' 가 아니라 '1이 0으로 바뀌었네?' 하는 겁니다. 이는 신.. 2020. 6. 3. 논리회로설계 스펙에서부터 상태천이도를 구하는 과정을 알아봅시다. FSM(Finite State Machine) 상태유한기는 상태가 유한한 회로인데 즉 순차회로라는 뜻입니다. 다음 순차회로는 Binary String에서 특별한 패턴 "1011" 찾는 회로입니다. 1011을 찾으면 출력이 1이 되어야합니다. ex)01101101100 가 들어옵니다. 01101101100 이 부분과 01101101100 에서 출력 1이 나옵니다. 출력 : 00000100100 이런 식이 되겠죠. 그럼 이러한 동작을 하는 상태천이도를 그려보겠습니다. 순차회로는 두가지 타입이 존재 합니다. 밀리머신(Mealy Machine)과 무어머신(Moore Machine)인데요. 밀리머신 : 출력이 현재상태와 입력에 의해서 결정 무어머신 : 출력이 현.. 2020. 6. 2. 이전 1 ··· 34 35 36 37 38 39 40 ··· 42 다음 728x90
