Dot Dot Line Dot

title: Programmers - 3 x n 타일링 date: 2022-07-10 tags: Algorithm DP https://school.programmers.co.kr/learn/courses/30/lessons/12902 문제 요약 1x2 사각형을 배치하는 문제이다. 세로가 3, 가로가 n인 공간에 사각형을 배치하는 경우의 수 % 1,000,000,007을 return한다. 문제 풀이 전형적인 DP 문제이다. 이전에 풀었던 2 x n 타일링보다 조금 어려우나, 여전히 DP 입문 수준의 문제이다. 세로가 3이므로 n이 홀수라면 3n은 홀수이다. 이는 사각형을 어떻게 배치해도 1이 남으므로, 절대 만들 수 없다. n이 짝수일 경우만 구하면 된다. 첫 배치는 3가지가 가능하다. 그 다음 배치의 경..

title: Programmers - 메뉴 리뉴얼 date: 2022-07-10 tags: Algorithm Permutation https://school.programmers.co.kr/learn/courses/30/lessons/72411 문제 요약 사람들이 주문한 메뉴들이 주어진다. course vector로 주어진 개수만큼 메뉴를 조합하여 새로운 세트를 만들 것이며, 2명 이상이며 가장 많은 손님이 주문한 메뉴 조합이 새로운 세트가 된다. 새로운 세트 메뉴들을 vector에 넣고, 정렬하여 return한다. 문제 풀이 오랜만에 재밌는 문제를 풀었다. 해당 문제는 permutation을 이용하는 것이 핵심인 문제이다. 각 손님이 주문한 메뉴들을 주어진 개수만큼 조합을 하고, 이를 unordered..

title: Programmers - 조이스틱 date: 2022-07-10 tags: Algorithm DFS https://school.programmers.co.kr/learn/courses/30/lessons/42860 문제 요약 문자열이 주어진다. A로만 이루어진 초기 문자열에서 조이스틱을 조종하여 주어진 문자열을 만들어야 한다. 조이스틱의 최소 조종 횟수를 return한다. 문제 풀이 우선 'A'를 주어진 문자로 바꿀 때, 정방향으로 바꾸는 것과 역방향으로 바꾸는 것 중 횟수가 더 적은 방법으로 count 한다. 가장 중요한 부분은 바꿀 문자를 선택하기 위하여 좌우로 움직이는 것이다. 좌, 우로 움직일 수 있으며, 'A' 문자가 주어지면 바꿀 필요가 없기에 방문하지..

title: Programmers - 순위 검색 date: 2022-07-09 tags: Algorithm Bitmasking https://school.programmers.co.kr/learn/courses/30/lessons/72412 문제 요약 지원자들은 5가지 정보를 가지고 있다. 조건 n개가 주어졌을 때, 각 조건을 통과하는 지원자가 몇명인지 vector에 넣어 return한다. 문제 풀이 이건 난이도 설정이 잘못되었다. 최소 Level 3 이상이다. 조건이 문자열들이며, 한두개가 아니었기에 바로 비트마스킹이 떠올랐다. OneHotEncoder와 비슷하게 각 비트가 조건에 해당하는지를 알려주었다. 문자열 조건은 총 9개로, 9비트를 이용하였다. 점수는 100k까지로, 17비트면 충분하였지만 이..

title: Programmers - 뉴스 클러스터링 date: 2022-07-09 tags: Algorithm https://school.programmers.co.kr/learn/courses/30/lessons/17677 문제 요약 제시된 두 문자열을 연속된 두 문자씩 중복을 허용하는 각각의 집합에 넣는다. 알파벳으로만 이루어져야 하며, 교집합과 합집합 연산이 가능한 집합이라고 생각한다. 유사도는 교집합의 개수 / 합집합의 개수 이며, 유사도 * 65536의 정수 부분을 return한다. 문제 풀이 집합을 구현하기에는 너무 귀찮다. 그러므로 편한 unordered_map을 이용하였다. 처음에는 하나의 unordered_map에 모든 것을 처리하였다. 연속한 두 문자 모두 알파벳이면 이를 string..

title: Programmers - 수식 최대화 date: 2022-07-09 tags: Algorithm https://school.programmers.co.kr/learn/courses/30/lessons/67257 문제 요약 +, -, *과 정수로만 이루어진 수식이 주어진다. 사칙연산의 우선순위를 바꾸었을 때, 수식의 절대값 중 가장 큰 값을 return한다. 문제 풀이 간단한 구현 문제이나, 개인적으로 많이 고민이 된 문제이다. 처음에는 queue를 이용하여 처리하려고 하였으나, 그럴 경우 queue 2개를 서로 바꿔가면서 사용하여야 한다. 또한 queue에 대한 포인터 처리가 제대로 되지 않았기에 이 방식을 사용하려면 또 하나의 함수를 추가하여야 하는 상황이었다. vector, erase 방..

title: Programmers - 교점에 별 만들기 date: 2022-07-08 tags: Algorithm https://school.programmers.co.kr/learn/courses/30/lessons/87377 문제 요약 2차원 평면의 서로 다른 직선들이 주어진다. 정수로만 이루어진 교점들을 이용하여 격자판을 문자열로 만들어 return한다. 문제 풀이 문제 요약이 더 길어지면 오히려 이해하기 어려울 수 있다. 문제가 이해가 되지 않을 가능성이 높고, 이는 문제를 직접 보는게 훨씬 좋다. 한 마디로 정리하면 그지같이 귀찮은 문제이다. 직선이 일치하여 무수히 많은 교점이 생기지 않으므로, 모든 직선의 교점을 구한다. 해당 교점이 정수로 이루어진 교점일 경우 vPoints vector에 p..

title: Programmers - 스킬트리 date: 2022-07-08 tags: Algorithm https://school.programmers.co.kr/learn/courses/30/lessons/49993 문제 요약 선행 스킬의 순서와 자유로운 스킬트리가 주어진다. 순서를 벗어난 스킬트리는 사용할 수 없으며, 사용 가능한 올바른 스킬트리의 개수를 return한다. 문제 풀이 선행 스킬의 순서는 최대 26개, 스킬트리는 최대 20개가 존재하며 각각 최대 26개의 순서로 구성되어 있다. 시간 복잡도는 문제가 없을 것이며, 구현만 하면 되는 문제이다. 처음에는 선행 스킬의 뒤부터 검사를 하는 프로그램을 작성하였으나, for문을 3번 중첩해야 하는 프로그램이 되었다. unordered_map을 도..

title: Programmers - 쿼드압축 후 개수 세기 date: 2022-07-08 tags: Algorithm Recursion https://school.programmers.co.kr/learn/courses/30/lessons/68936 문제 요약 0과 1로 이루어진 2차원 정수 배열을 쿼드 트리 방식으로 압축하고, 이 때 0과 1의 개수를 return한다. 문제 풀이 BOJ.1992 문제와 유사하다. BOJ 문제에서는 문자열로 압축한 반면, 이 문제에서는 압축 후 0과 1의 개수만 세면 된다. 압축 여부를 따로 저장하고 이를 해독하기는 매우 번거로우며 과한 투자이다. 주어진 구간이 0 혹은 1로만 이루어져있는지 확인하고, 그렇지 않을 경우 다시 4등분을 하여 recursion을 하여 해결..

title: Programmers - 하노이의 탑 date: 2022-07-07 tags: Algorithm Recursion https://school.programmers.co.kr/learn/courses/30/lessons/12946 문제 요약 하노이의 탑 문제이다. n개의 원판이 주어지며, 1번 기둥에 쌓여있다. 모든 원판을 3번 기둥에 최소 횟수로 옮겨야 하며, 과정을 vector에 넣어 return한다. 문제 풀이 최소 횟수는 바로 구할 수 있으나, 과정을 기록해야 한다는 것이 꽤 거슬렸다. 하노이의 탑은 원판의 움직임에 패턴이 존재하며, 원판의 개수와 위치에 따라 과정이 너무 동적으로 변화하여 DP는 사용하기 어렵다고 판단하였다. 결국 성능을 다소 포기하더라도 가장 구현하기 쉬운 재귀 함수..