랍스터 (요르고스 란티모스, 2015) 영화

사회규범 반 사회규범
감각과 교감


binary search 2018-8-5 코딩문제

이진 탐색 문제만 만나면 매번 실수한다.
이번엔 확실히 정리한다.

이진 탐색은 sorting되어있는 리스트에서 특정 값을 찾는 함수다.
시간 효율성은 O(logn) 수준이다. 

리스트에 중복된 값이 있을 때, 중복된 수 중 처음 값의 인덱스 혹은 마지막 값의 인덱스를 찾는다.
각각의 방식을 lower binary search와 upper binary search로 부른다.

*lower binary search

*upper binary search



찾는 과정은 리스트의 처음과 끝을 기준으로 계속해서 내가 찾는 값이 있는 범위를 좁혀 나가는 것 이다.
예를 들어서 upper binary search를 이용해서 위 그림과 같이 5라는 수가 나오는 마지막 index를 구한다.

사용 변수: left, right, mid, target
1. left = 0 , right = 23 으로 초기화

2. while( left <= right) // left 와 right의 순서가 뒤바뀌지 않는 상태에선 계속 진행
mid = (left + right) / 2; // 중간 index를 찾는다. 
if(list[mid] > target) // 만약 list[mid] 가 target 보다 크면 mid 왼쪽만 탐색한다.
right = mid - 1; 
else // 만약 list[mid] 가 target 보다 작으면 mid 오른쪽만 탐색한다.
left = mid + 1; // 여기서, list[mid]가 target 과 같으면 마찬가지로 오른쪽만 탐색한다.

3. retrun right; // right가 정답을 지시하고 있다.

본 알고리즘에서 주목할 점은 list[mid]가 target 과 같을 경우 left = mid + 1을 한다는 점이다.
이유는 upper 값을 찾기 때문이다. 현재 내가 찾는 값이 나왔어도 더 오른쪽 index에도 내가 찾는 값이 있을 수 있다. 
만약 있다면 left는 제대로 옮겼다.
만약 없다면, list[mid]가 마지막 target을 지시하고 있다면 어떨까?
문제없다. 왜냐하면 left = mid + 1 이 된 이후에는 항상 list[mid] > target 일 것이다. 그러면 항상 right = mid -1이 돼서 언젠간 left == right가 된다. left == right 인 상태에서도 list[mid] > target일 것이므로 right = mid -1이 된다. 결국 right 값이 내가 찾는 target의 upper index를 지시한다.
아래 그림은 이 과정을 묘사한다.



lower 값을 찾는 과정도 마찬가지이다.

아래는 코드이다.

test.c
______________________________________________________________
#include <stdio.h>

int search_upper(int arr[], int n, int target)
{
int left, right, mid;
left = 0; right = n - 1;
while (left <= right) 
{
mid = (left + right) / 2;
if (arr[mid] > target)
right = mid - 1;
else
left = mid + 1;
}
return right;
}

int search_lower(int arr[], int n, int target)
{
int left, right, mid;
left = 0; right = n - 1;
while (left <= right)
{
mid = (left + right) / 2;
if (arr[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return left;
}

int main(void)
{
int arr[] = {1,1,2,3,4,4,5,5,5,5,5,5,5,5,5,6,6,7,8,9,10,11,12};
int n = sizeof(arr) / sizeof(arr[0]);

printf("lower idx = %d\n", search_lower(arr, n, 5));
printf("upper idx = %d\n", search_upper(arr, n, 5));

return 0;
}
_________________________________________________________________

스마트 디바이스 쇼 2018 전시회

스마트 디바이스 쇼 2018에 다녀왔다.
폰버드w: 무선 네트워크 접속 hotspot 기능을 제공하는 제품이다. 유사 제품에는 도시락이 있다. 
특장점으로는 90개국에서 별도 설정 없이 구매한 데이터 사용이 가능하다.
또한 특정 프록시 서버로 라우팅이 되는지, 특정 국가에서 접속이 불가한 웹 사이트도 폰버드w를 사용하면 접속 가능하다.
가격은 17만원으로 저렴하지는 않다. 타겟이 개인 사용자인 것 같은데, 17만원의 비용을 1년에 한 두번 해외를 가는 사용자가 지불할지는 의문이다. 이런 제품은 여행사에서 대여 서비스를 하기에 좋을 것 같다. 이렇게 되면 개개인 여행자들이 도시락과 같은 제품을 대여할 필요가 없다. 과금은 패키지에 폰버드 w 대여료를 포함 시키는 방식이 가능하다. 이를 위해서는 먼저 여행사에 제품 홍보를 하는 것이 좋겠다.
Dr.Music3: (주) 스마트메디칼디바이스 에서 만든 제품이다. 의료기기로서 저주파 마사지 기능을 가지고 있다. 가격은 타 제품들에 비해 2-3배 가량 비싸지만 노래 리듬에 따라 마사지를 하는 기능이 포함되어 있다. 디자인은 훌륭한 편이다.
CZUR ET16 Plus Smart Scanner: 본 스캐너는 책을 1.5초 만에 사진으로 찍어서 스캔을 해 주는 기기이다. 곡면이 보정되고 활자 인식을 통해 문서 파일로 변환 또한 가능하다. 
POUT: 사무용품을 판매한다. 무선 충전 기능을 통해서 깔끔한 사무용품에 휴대폰 충전이 가능하게 만들었다. 디자인이 주력인 제품들이다.

전반적으로 판매되는 상품을 다음과 같은 카테고리로 나누어 볼 수 있었다: 헬스케어 (개인용 의료기기), 무선충전 사무용품, 특수용도 프린터 (3D, 식각) 등.. 본 전시회는 대부분 개인 소비자를 대상으로 제품 홍보를 하고 있었다. 


극장과 민주주의 oskar eusis

극장은 대화의 장 이다.
극 내 주인공 간에 관점의 충돌이 일어난다.
관객은 극중 인물 관점에 공감할 수 있다.
극장은 접근성을 올려서 모두에게 열려 있어야 한다.

관객은 극장에서 공동체 구성원으로서 경험을 원한다.

극장은 극을 통해 관객에게 의견 형성의 기반이 되는 사실적 정보를 제공한다.

관객은 극의 주체가 되어 의견을 표출하기도 하는데 극장은 이에 조력한다.

이상주의 적인 의견일 수 있다. 극장은 체제 교육의 장소이고 관객은 자유로부터 도피한 개인이다. 극의 설계자는 관객의 소속추구의지를 빌미로 체제 유지를 위한 의견을 형성하고 교육한다.

12

p1
세미나 내용은 저전력 딥러닝 가속기인 NVLDA NVIDIA DEEP Learning Accelerator의 디자인 원칙 입니다.

p2
들어가기에 앞서 NVDLA는 완전 오픈 소스로 RTL 부터 시뮬레이터까지 제공되고 있습니다.
제가 만약 SoC 벤더라면 NVDLA 라이센스를 부착하고 로열티 없이 제 칩에 통합을 할 수 있는 것입니다.

그냥 IP만 덩그러니 제공하는 것이 아니라, 모듈화된 코드에 시뮬레이션 환경이 제공되어 있습니다.
NVIDIA는 커뮤니티에 NVDLA의 변용과 그 보고를 장려합니다.

또 소형 기기에 많이 사용되는 ARM 프로세서와 호환이 되도록 AMBA (ARM Microcontroller Bus Architecture) 인터페이스가 사용됩니다.

왜 이런 일을 NVIDIA가 할까요?

먼저 상당히 scalability가 좋습니다. 모듈화되어 있는 설계 방식이 그렇고, 디바이스 내부 버퍼 사이즈를 제가 정할 수 있냐 라던가 혹은 device 내부에 firmware를 운용할 코어를 만들 것인가가 그렇습니다. 결과적으로 application-specific한 모델을 빌드하기에 좋습니다.
또 ARM bus 인터페이스에 디바이스를 붙힐 수 있습니다. 디바이스 제어를 위해서는 APB에 붙이고 디램의 경우 AHB 인터페이스로 되어 있습니다. 당연 ARM-FPGA 디바이스에서 시뮬레이션을 하기에도 편리합니다. Xilinx Zynq 디바이스 기반 보드에서 시뮬레이션을 하고있는 커뮤니티 사람들이 있습니다.
NVDLA라는 것은 저전력 환경을 타게팅 합니다. 전력 절감을 위한 여러 설계 방식을 뒤에서 리뷰 하겠습니다.

제가 생각하기에 결국 NVDLA는 소형 SoC에 Application-specific 저전력 가속기를 통합하려는 사람을 타게팅 했고 그 사람이 입맛 따라 적극적으로 가속기를 수정하고 시뮬레이션하고 디버깅해서 자신의 SoC를 디자인 할 수 있게 하려는 의도에서 개발된 프로젝트 입니다. 물론 royalty-free 라이센스 입니다.

p3

p4



1 2 3 4 5 6 7 8 9 10