전체 글 썸네일형 리스트형 백준 11438 LCA 2 트리를 입력받은 뒤, 공통 조상 중 가장 가까운(높이가 낮은) 노드를 찾는 문제이다. LCA 1이 있고 LCA 2가 있는데, LCA 1은 나이브하게 공통 조상을 밑에서부터 같이 찾아 올라가도 정답 처리가 되지 않을까 싶다. 그 문제는 골드3이고 이 문제는 플레 5이므로 난이도 차이가 꽤 난다. 문제의 접근은 DP-Like 하다. DP도 제대로 본건 아니지만, 연산 과정을 배열에 저장한다는 관점에선 비슷하다고 볼 수 있지 않을까? DP를 좀 더 많이 해보고 차이점을 더 잘 알게 된다면 이 글을 수정해야겠다. 그럼 여기서 DP-Like 하게 연산과정을 저장한다고 했는데, 무엇을 저장하는가? 바로 어떤 노드의 2^K번째 조상을 저장한다. 100000개의 노드가 있을 때, Worst Case일 경우 높이는 10.. 더보기 [나만 몰랐던 알고리즘] MST 구하기 - Kruskal's Algorithm Minimun Spanning Tree는 모든 노드를 잇는 사이클이 없는 그래프 중 간선(edge)의 가중치 합이 최소가 되는 트리(그래프)이다. 글로 봤을땐 저게 뭔가 싶은데 그림으로 한번 보자 위 사진과 같은 그래프에서, 모든 노드를 포함하는 부분 그래프를 신장 부분 그래프라고 한다. 여기서 간선이 어떻게 연결되는지에 따라 여러개의 신장 부분 그래프를 만들 수 있는데, 이 중 간선의 합이 최소가 되는 신장 부분 그래프를 MST라고 하고, 오늘 정리할 알고리즘은 이 MST를 찾는 Kruskal 알고리즘이다. 알고리즘을 크게 정리하면, 모든 에지를 Cost 순으로 정렬되는 Priority Queue에 넣는다. PQ에서 하나를 뽑는다 -> 이 에지의 출발점과 도착점이 연결되어 있지 않다면 트리에 추가한다... 더보기 [나만 몰랐던 알고리즘] Union-Find Union-Find 는 알고리즘이라고 하기에는 다른 알고리즘에서 많이 쓰이는 부품같은 존재다. 원소 N개가 있을때, 이 원소들을 합집합하는 연산(union)과 특정 원소가 어디 속했는지 구하는 연산(find) 이 두개로 이루어져서 이름도 Union-find 이다. 초기화 원소가 N개 있다고 했을때, size = N인 int array parents를 만든다. 이 배열은 해당 인덱스 원소의 부모를 내용으로 가진다. 초기에는 각 원소가 각각의 집합에 속해있다고 가정하므로, parents[i] = i 로 초기화 한다. int parent[10]; for (int i = 0;i 더보기 [나만 몰랐던 알고리즘] 최소 공통 조상, LCA 트리 구조에서 조상은 현재 노드 위에 있는 노드들이다. LCA(최소 공통 조상)은 말 그대로 공통 조상 중에서 가장 낮은(높이가 최소인) 조상을 말한다. 트리를 보면, 루트 노트 1은 깊이 0을 가지고, 9번 노드는 깊이 3을 가지는 것을 볼 수 있다. 여기서 10과 5의 공통 조상은 1, 3이 있고 최소 공통 조상은 3이다. LCA를 구하는 방법은, 나이브하게 접근하면 매번 트리를 타고 올라가면서 확인하는 방법이 있다. 가장 확실하지만 시간이 아주 오래 걸릴 수도 있다. 트리가 꼭 균형이 맞는다는 보장이 없으므로 심한 경우에는 노드 갯수만큼의 비교와 count가 필요하다. 따라서 많은 문제에서 LCA는 다른 방법으로 구하게 된다. LCA에서 가장 핵심이 되는 것은 배열 하나의 추가이다. DP와 비슷하다.. 더보기 백준 2042 구간 합 구하기 진짜 제곧내 문제 이다. 입력받은 N개의 수에서 두 인덱스 사이의 부분합을 구하거나, 특정 인덱스의 수를 변경하는 두 가지의 연산을 하면 된다. 엄청 나이브하게 접근해서 작동만 하는것을 짰을때는 진짜 말그대로 배열에서 하나씩 탐색하며 부분합을 더했고, 변경도 배열에서 직접 변경하도록 했다. 시간초과인걸로 기억한다. 이런 구간 합 문제에서 투 포인터 알고리즘을 사용할 수도 있었다. 하지만 검색을 해보니 세그먼트 트리로 접근해야 한다고 해서 관련된 내용을 찾아보고 작성했다. 세그먼트 트리에 대한 내용은 따로 작성한 포스팅이 있다. 세그먼트 트리는 각 노드가 자신이 포함하고 있는 노드들의 합을 저장하는 트리라고 할 수 있다. 코드 전에 각 함수의 로직을 간략히 보면, init() leaf node나오기 전까지.. 더보기 [나만 몰랐던 알고리즘] 세그먼트 트리 트리 구조를 띄는 자료 구조인 세그먼트 트리는, 일렬로 나열되어 있는 자료 중에 어느 부분(세그먼트)의 연산(합, 최소, 최대, 곱 등)을 구하는데 많이 쓰인다. 크게 다음과 같은 문제 조건인지 확인해 보면 된다. 1. 구간 l, r (l end || right 첫 번째 if 구문. 범위가 어떤지에 따라 다르지만, 대부분의 흐름에선 두번째 경우의 함수로 시작해서, 각 노드나 검색 범위의 중심부 노드들을 첫번째 경우로가지는 함수에서 값을 뱉고, 가장자리나 범위 바깥은 세번째 경우로 0을 리턴해 올라온것을 두번째 경.. 더보기 Home IoT 설레발 치다가 라즈베리파이 태워먹은.SULL 할 수 있으니까 한다. 아 요즘 아침에 일어날 때마다 너무 건조하다. 그렇다고 가습기를 틀어놓고 자면 아침에 너무 습하고 정작 목도 여전히 건조한 상태 그대로다. 가습기를 바꾸고 싶은데 일단 지금 상황이 어떤지부터 확인해야겠다. 가습기가 특정 기준에 따라 켜지고 꺼지고 하는 방식이 아니라 분무 세기만 조절하는 무식한(...) 녀석이라 스마트 플러그랑 연동해서 써도 나쁘지 않을것 같았다. 하지만 여기서 중요한것은 지금 습도 상태를 얻어야 하는것... 쿠팡에서 보니 온습도계가 만오천원선이다. 하지만 뭐 다른것하고 연동도 못하고 그냥 디스플레이만 하는거라 살까하다가 말았다. 생각해보니 저번에 키트로 샀던 아두이노에 온습도센서가 있던것 같다. 여기에 라즈베리파이를 얹고 항상 돌아가는 나스에서 값 받아다가 기록해.. 더보기 YOLO Object Detector 쓰기 (3) 컴파일 삽질 시작 - Darknet 본격적으로 Darknet을 Build해본다. Github에서 Darknet repo를 clone해온다. git clone https://github.com/AlexeyAB/darknet.git Opencv\build\bin\Release의 opencv_ffmpeg, opencv_world dll을 darknet\build\darknet\x64로 복사한다. Cuda Dir(CUDNN 복사한 dir)\bin 에서 cuDNN64_7.dll을 darknet\build\darknet\x64로 복사한다. darknet\build\darknet 의 darknet.vcxproj 을 text editor로 연다 CUDA_10으로 find 후 버전을 10.2로 전부 수정한다. darkn.. 더보기 이전 1 ··· 5 6 7 8 9 다음
