전체 글
-
[백준] 16929번 two dots문제 풀이 2020. 3. 20. 19:23
16929 Two Dots 문제 Two dots는 Playdots, Inc.에서 만든 게임이다. 게임의 기초 단계는 크기가 N×M인 게임판 위에서 진행된다.각각의 칸은 색이 칠해진 공이 하나씩 있다. 이 게임의 핵심은 같은 색으로 이루어진 사이클을 찾는 것이다.다음은 위의 게임판에서 만들 수 있는 사이클의 예시이다. 점 k개 d1, d2, ..., dk로 이루어진 사이클의 정의는 아래와 같다.모든 k개의 점은 서로 다르다. k는 4보다 크거나 같다.모든 점의 색은 같다.모든 1 ≤ i ≤ k-1에 대해서, di와 di+1은 인접하다. 또, dk와 d1도 인접해야 한다. 두 점이 인접하다는 것은 각각의 점이 들어있는 칸이 변을 공유한다는 의미이다.게임판의 상태가 주어졌을 때, 사이클이 존재하는지 아닌지 구..
-
[백준] 16954번문제 풀이 2020. 3. 20. 16:58
16954 움직이는 미로 탈출 문제욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 윗 칸으로 이동해야 한다.이 게임의 특징은 벽이 움직인다는 점이다. 1초마다 모든 벽이 아래에 있는 행으로 한 칸씩 내려가고, 가장 아래에 있어서 아래에 행이 없다면 벽이 사라지게 된다. 욱제의 캐릭터는 1초에 인접한 한 칸 또는 대각선 방향으로 인접한 한 칸으로 이동하거나, 현재 위치에 서 있을 수 있다. 이동할 때는 빈 칸으로만 이동할 수 있다.1초 동안 욱제의 캐릭터가 먼저 이동하고, 그 다음 벽이 이동한다. 벽이 캐릭터가 있는 칸으로 이동하면 더 이상 캐릭터는 이동할 수 없..
-
OpenCV학교 수업/프로젝트 2020. 3. 19. 20:13
수어 손동작을 카메라를 통해 인식, 검출하는 과정이 필요했기에 이미지 프로세싱에 좋은 opencv도 사용했었다.opencv에 대한 설명도 기록한다. OpenCV (Open Source Computer vision) 개념 : 실시간 컴퓨터 비전*을 목적으로 한 프로그래밍 라이브러리, 단일 이미지나 동영상의 이미지를 분석 및 추출하기 위한 API C/C++ 언어로 개발되었고, 이 API를 사용할 수 있는 언어는 C/C++, Java, Python 등이 있다. * 컴퓨터 비전(Computer Vision) : 기계의 시각에 해당하는 부분을 연구하는 컴퓨터 과학의 최신 연구 분야 중 하나. 응용 기술 : 물체인식, 안면 인식, 제스처 인식
-
Deep Leaning학교 수업/프로젝트 2020. 3. 19. 19:02
프로젝트에서 딥러닝 기술을 이용했었는데, 딥러닝이 무엇인지를 정리해 두도록 하겠다. Deep Learning 딥러닝개념 : 딥러닝 ⊂ 머신러닝여러 층을 가진 인공신경망*(Artificial Neural Network, ANN)을 사용하여 머신러닝 학습을 수행하는 것. 머신러닝의 한 종류라고 할 수 있다. 차이점머신러닝은 학습하려는 데이터들에서 어떤 특징을 추출할 것인지 사람이 직접 분석하고, 판단한다. (사람 개입)그러나, 딥러닝은 기계가 스스로 학습하려는 데이터에서 특징을 추출하고 학습한다. (사람 개입x) *인공신경망 ? 인간의 뇌가 가진 신경세포 즉 뉴런을 본떠 만든 네트워크 구조. 입력층(input layer), 은닉층(hidden layer), 출력층(output layer)로 구성되어 있다. ..
-
next_permutaion 함수잡다한 지식 2020. 3. 18. 20:10
이전 포스팅에서 순열을 재귀적 방법을 통해 구현해보는 걸 올린적이 있는데.순열을 c++ 헤더에서 next_permutation이라는 함수를 통해 쉽게 구현하는 방식이 있어서 정리해보자 한다. 헤더를 추가한 후, next_permutation()함수에 백터의 iterator 혹은 주소를 넣으면 벡터에 다음 순열이 적용된다. bool next_permutation(수열의 시작, 수열의 끝) : 현재 나와 있는 수열에서 다음 순열을 구하고 true를 반환. 다음 순열이 없다면(다음에 나온 순열이 순서상 이전 순열보다 작다면) false를 반환. 코드를 통해서 자세히 알아보자. ([1,2,3,4,5] 수열에서 나올 수 있는 순열은?) 1234567891011121314151617181920212223242526..
-
순열과 조합잡다한 지식 2020. 3. 18. 19:49
백준 문제를 풀면서 stl을 사용하지 않고, 재귀적 방법으로 순열과 조합을 구현해서 문제를 풀어야하는 경우가 많았기에 정리해서 올려본다. 순열개념 : 서로 다른 n개의 원소에서 r개를 중복없이 골라 순서에 상관있게 나열하는 것 (nPr)예시 : [1, 2, 3, 4, 5] 5개의 원소 중에서 3개를 고르시요. 답) 맨 앞자리가 1일 경우 : [1,2,3], [1,2,4], [1,2,5], [1,3,2], [1,3,4], [1,3,5], [1,4,2], [1,4,3], [1,4,5], [1,5,2], [1,5,3], [1,5,4]맨 앞자리가 2일 경우 : [2,1,3], [2,1,4], [2,1,5], [2,3,1], [2,3,4], [2,3,5], [2,4,1], [2,4,3], [2,4,5], [2,5..
-
Lazy propagation알고리즘 2020. 3. 17. 18:30
사전 지식segment tree에서 하나의 값을 업데이트하는 연산의 시간복잡도는 O(logN) (N : 배열의 길이)인데, 나머지 수들도 변경해줘야하므로총 걸리는 시간복잡도은 O(NlogN)이다. 그런데, 이전에서 다룬 것 처럼 한번에 하나의 수를 업데이트 하는것이 아닐 경우의 시간 복잡도는 어떨까? 10개의 수 1, 10, 3, 6, 5, 6, 4, 2, 9, 7에 대해 3번째 수부터 6번째 수까지 5씩 더하는 업데이트해야 하는 경우을 생각해보자.이전 포스팅에서 사용한 업데이트 방식을 사용하면 업데이트 함수를 3,4,5,6번째 숫자에 대해 각각 호출해야한다. 즉, 길이 N인 배열에 질의가 K번 들어올 때 (for문과 같은 반복문을 사용할 경우) 전체 업데이트에 O(NKlogN)의 시간복잡도 필요하다. ..
-
Segment Tree알고리즘 2020. 3. 17. 17:20
Segment Tree 세그먼트 트리개념 : 배열의 특정 구간의 합, 혹은 특정 구간에서 최대값·최솟값 등을 효율적으로 구하기 위한 자료구조기본 구조 : 완전 이진 트리 구조 가장 최상단인 루트 노드 - 전체 구간의 정보 가장 최하단의 리프 노드 - 배열의 그 수 자체 즉 배열의 각 요소 배열의 크기가 N = 10개 일때의 세그먼트 트리를 그리면, 세그먼트 트리는 1차원 배열로 구현한다. 크기 : 입력 배열의 크기가 N일때, 리프 노드의 개수가 N이 된다. 따라서 세그먼트 트리의 높이는 [logN]이 되고, 세그먼트 트리 배열의 크기는 2^(H+1) 이 된다. 이를 코드로 나타내면12int h = (int)ceil(log2(n));int tree_size = (1