본문 바로가기

Algorithm98

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.
2020 Kakao internship 67259 - 경주로 건설(다익스트라, 0-1 bfs) c++ - N by N의 벽이 중간중간 존재하는 경주로에서 상하좌우로 도로가 놓이는데 N, N까지 도달할 수 있는 최소비용의 도로를 놓아야된다. - 출발지와 도착지가 정해져있는 구간의 최소비용을 구하는 로직으로는 다익스트라 알고리즘이 있어서 바로 그 알고리즘으로 접근하였다. (개인적으로 하는 알고리즘 스터디에서 어떤 분이 0-1 bfs 라는 로직을 사용한 것을 보았는데 이를 이용하면 O(V + E)복잡도로 풀 수 있다. 다익스트라는 우선순위큐를 이용할 시에 O((V+E)logV)이다. - 주의할 점으로는 코너가 발생할시 건설비용이 100이 아니라 600이 되는데, 그 것을 모든 칸의 건설비용을 계산 할 때 이전에 있었던 칸의 방향정보를 가져와서 지금 방향과 비교해서 수평이면 100, 수직이면 600으로 계산하는.. 2021. 9. 6.
2020 Kakao internship 67258 - 보석 쇼핑(슬라이딩 윈도우) c++ - 특정 범위의 보석을 모두 챙기는데 모든 종류의 보석을 챙기는 가장 짧은 범위를 찾는 문제이다. - 문제에서 보석 배열 길이가 10만이므로 10만^2 = 100억이므로 nlogn 이하 로직을 사용해야한다. 그렇기 때문에 어떤 범위가 이동하면서 그 범위 안의 구간합 등이 조건에 성립하는지를 O(N)으로 구할 수 있는 슬라이딩 윈도우 방식으로 접근하였다. - 전체 보석 종류 갯수를 구한다. 그 종류 갯수는 어떤 범위가 모든 보석종류를 모두 포함하는 최소길이의 범위가 될 것이다. 인덱스 0부터 모든 보석종류를 포함하는지를 map을 통해서 체크한다. map을 사용하는 이유는 2개 이상의 같은 종류보석이 들어있을 수 있기 때문이다. 모든 종류 보석이 있는 범위가 구해지면 거기서 1칸씩 전진하면서 전진하는 방향 .. 2021. 9. 6.

티스토리툴바