전체 글
[프로그래머스 C++] 튜플
문제 : 2019 카카오 개발자 겨울 인턴십 - 튜플 문제 설명 셀 수 있는 수량의 순서 있는 열거 또는 어떤 순서를 따르는 요소들의 모음을 튜플(tuple)이라고 합니다. n개의 요소를 가진 튜플을 n-튜플(n-tuple)이라고 하며, 다음과 같이 표현할 수 있습니다. (a1, a2, a3, ..., an) 튜플은 다음과 같은 성질을 가지고 있습니다. 중복된 원소가 있을 수 있습니다. ex : (2, 3, 1, 2) 원소에 정해진 순서가 있으며, 원소의 순서가 다르면 서로 다른 튜플입니다. ex : (1, 2, 3) ≠ (1, 3, 2) 튜플의 원소 개수는 유한합니다. 원소의 개수가 n개이고, 중복되는 원소가 없는 튜플 (a1, a2, a3, ..., an)이 주어질 때(단, a1, a2, ..., a..
[프로그래머스 C++] 가장 큰 정사각형
문제 : 가장 큰 정사각형 문제 설명 1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.) 예를 들어 0 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 가 있다면 가장 큰 정사각형은 0 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 가 되며 넓이는 9가 되므로 9를 반환해 주면 됩니다. 제한사항 표(board)는 2차원 배열로 주어집니다. 표(board)의 행(row)의 크기 : 1,000 이하의 자연수 표(board)의 열(column)의 크기 : 1,000 이하의 자연수 표..
[프로그래머스 C++] 쿼드압축 후 개수 세기
문제 : 쿼드압축 후 개수 세기 문제 설명 0과 1로 이루어진 2n x 2n 크기의 2차원 정수 배열 arr이 있습니다. 당신은 이 arr을 쿼드 트리와 같은 방식으로 압축하고자 합니다. 구체적인 방식은 다음과 같습니다. 당신이 압축하고자 하는 특정 영역을 S라고 정의합니다. 만약 S 내부에 있는 모든 수가 같은 값이라면, S를 해당 수 하나로 압축시킵니다. 그렇지 않다면, S를 정확히 4개의 균일한 정사각형 영역(입출력 예를 참고해주시기 바랍니다.)으로 쪼갠 뒤, 각 정사각형 영역에 대해 같은 방식의 압축을 시도합니다. arr이 매개변수로 주어집니다. 위와 같은 방식으로 arr을 압축했을 때, 배열에 최종적으로 남는 0의 개수와 1의 개수를 배열에 담아서 return 하도록 solution 함수를 완성..
[프로그래머스 C++] - 타겟 넘버
문제 : 타겟 넘버 문제 설명 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요. 제한사항 주어지는 숫자의 개수는 2개 이상 20개 이하입니다. 각 숫자는 1 이상 50 이하인 자연수입니다. 타겟 넘버는 1 이상 1000 이..
[C++] 이진 트리 + 힙, 트립
트립 (treap) 보통 STL에서 제공하는 이진 검색 트리는 대부분 X보다 작은 원소의 수를 계산하거나, k번쩨 원소를 찾는 연산을 지원하지 않는다. 따라서 필요할 때는 직접 군형 잡힌 이진 트리를 구현해야 하는데, 이게 쉽지 않은 작업이다. (속도나 효율도 별로다..) 그렇기에 필요한 경우 간단하게 구현이 가능한 treap을 사용한다. 정의 트립은 입력이 특정 순서로 주어질 때 성능이 떨어진다는 이진 검색 트리의 단점을 해결하기 위해 고안된 이진 검색 트리이다. 원리는 트리의 형태가 원소들의 추가 순서에 따라 결정되지 않고, 난수에 의해 임의대로 결정된다. 그렇기에 노드가 추가되거나 삭제되더라도 트리 높이의 기대치는 항상 일정하다. 이와 같은 속성을 만족시키려면 두가지 조건이 성립돼야 한다. 1. 이..
[프로그래머스 C++] - 카펫
문제 : 카펫 문제 설명 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다. Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요. 제한사항 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다. 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다. 카펫의 가로 길이는 세로 길이와 같거나, ..
[프로그래머스 C++] - 위장
문제 : 위장 문제 설명 스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다. 예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다. 종류 이름 얼굴 동그란 안경, 검정 선글라스 상의 파란색 티셔츠 하의 청바지 겉옷 긴 코트 스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요. 제한사항 clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다. 스파이가 가진 의상의 수는 1개 이상 30개 이하입니다. 같은 이름을 가진 의상은 존재하지 않습니..
[C++ openCV 도형 인식] 게임 매직 타일 매크로 [2] (완)
[파이썬 openCV 도형 인식] 게임 매직타일 매크로(1) 매직타일 매크로 openCV로 뭘 만들까 고민하다가 옛날에 했던 게임 중 하나인 '매직 타일' 생각이 나서 매크로를 만들어 봤다. 매직 타일은 간단한 리듬 게임이다. 매직 타일 소개 영상 보다시피, return-value.tistory.com 윗글을 읽고 오시면 이해가 빠릅니다. 결과 영상 전의 파이썬과 비교했을 때, 확실히 검출해네는 속도가 빨라졌다! 심지어 C++은 의도적으로 딜레이를 30ms정도 준 상태인데도 말이다. 확실히 이런 실시간 싱크 맟추는 것이 중요하다면, C++이 강력한 것 같다. 하지만 C++로 코딩하기는 참 너무 귀찮다.. 해줄게 너무 많다! 그래도 속도만큼은 진짜 탁월한 것 같다. C++ 소스 화면 녹화 부분 참고 코드 ..