본문 바로가기

Algorithm/programmers42

2020 Kakao blind 60061 - 기둥과 보 설치(배열) c++ - 기둥과 보를 설치,해체하는 조건들이 담긴 벡터가 주어졌을 때, 이를 순서대로 실행해서 설치되거나, 해체하거나, 혹은 설치해체가 이루어지지 않는 조건이던가 해서 모두 진행한 뒤 나온 결과값을 리턴하는 로직을 짜는 문제이다. - 건설되는 기둥과 보의 좌표값이 격자를 따라 간다고 되어 있으므로 이것을 조금 수정해서 격자의 가로세로변을 원소로 담는 새로운 배열을 기둥, 보 각각 새로 선언해서 읽어야한다. - 그런 뒤에 기둥을 건설할 수 있는지, 보를 건설할 수 있는지, 기둥과 보를 해체할 수 있는지에 대한 체크함수를 만들어줄 수 있다. 문제에서 나온 조건대로 그려줄 수 있다. #include #include #include using namespace std; bool col[101][101] = {0}; .. 2021. 9. 9.
2020 Kakao blind 60060 - 가사검색(이분탐색, 트라이 자료구조) c++ - 쿼리 벡터의 단어(와일드카드가 섞여있는)에 대해서 words벡터에서 일치할 수 있는 단어가 몇 개인지 리턴하는 로직을 만드는 문제이다. - 일단 words 벡터와 queries벡터의 길이가 각각 10만이므로 2중 for문으로 탐색하는 O(N^2) = 100억 로직으로 풀 수 없다. 따라서 검색로직의 파라미터가 되는 쿼리에 대한 접근은 줄일 수가 없으니까 words 벡터를 탐색시에 logn 이하의 로직을 써서 NlogN이하의 복잡도 알고리즘을 사용해야한다. 그러므로 이분탐색이 적절하다고 생각하고 접근하였다. (대신 연속된 문자열을 키로 사용해서 빠른 조회가 가능한 트라이 자료구조를 사용할 수 있다. 여기서 문자열이 시작되는 s[0]을 루트노드로 하여 조합가능한 모든 문자열에 대해서 트리구조로 노드를 만.. 2021. 9. 9.
2020 Kakao blind 60059 - 자물쇠와 열쇠(완전탐색, 배열) c++ - key와 lock의 사이즈 조건이 20이하이므로 모든 조건에 대해서 키를 돌려가면서 매칭시켜서 lock이 열리는 조건이 발견되면 1를 리턴해주는 로직을 짜면 된다. - lock의 row, col 범위를 2 * key 사이즈 + lock사이즈으로 늘린 다음에 가운데에 원래 lock의 값을 넣어주고 탐색을 하면 key와 lock이 겹치는 조건을 생각하기가 더 쉬워진다. 탐색시에 lock과 key가 겹쳐지지 않는 케이스가 생기지만 탐색범위가 20 by 20이기 때문에 크게 시간이 늘어나지 않는다. #include using namespace std; int m, n; vector Lock, Lock_cpy, Key; void rotate() { vector tmp(m, vector(m)); for(int .. 2021. 9. 9.
2020 Kakao blind 60058 - 괄호 변환(스택, 재귀 구현) c++ - 문제에서 지시하는 데로 구현해야 올바른 괄호 문자열이 만들어지는데, 재귀를 이용해야한다. - 괄호가 올바른지, 균형잡혔는지 카운트하기 위해서 스택을 이용하거나 혹은 직접 int변수로 카운트 할 수 있다. - 처음 시작 시에 균형잡힌 문자열이 주어지는 것을 이용해서 p를 2개의 균형잡힌 문자열 u,v로 나눈 뒤에 그 중 u를 옳바른 문자열로 만들어 주고, 남은 v를 재귀적으로 다시 같은 로직을 이용하여 결과적으로 옳바른 문자열 + 옳바른 문자열 + 옳 +옳... 을 리턴하도록 만들어주는 것이 포인트이다. #include #include #include using namespace std; bool isCorrect(string& s) { int open = 0; for (char& ch : s) { i.. 2021. 9. 9.

티스토리툴바