Dot Dot Line Dot

title: Programmers - 2 x n 타일링 date: 2022-06-21 tags: Algorithm DP https://programmers.co.kr/learn/courses/30/lessons/12900 문제 요약 1x2 타일을 2xn 공간에 배치하는 모든 경우의 수를 구한다. 문제 풀이 전형적인 DP 입문 문제이다. n >= 3 일때, n번째 경우의 수는 n-2번째의 배치에서 가로로 배치하는 경우의 수와 n-1번째의 배치에서 세로로 배치하는 경우의 수의 합이다. 이전 두 단계의 값만 참조하기 때문에 과한 메모리를 할당할 필요 없이 길이 3의 배열만 있으면 된다. n 3 일 때 (n-3)번 DP 계산을 해준다. 계산 이후 배열의 마지막 element의 값이 정답이다. 프로그램 #incl..

title: Programmers - 짝지어 제거하기 date: 2022-06-20 tags: Algorithm https://programmers.co.kr/learn/courses/30/lessons/12973 문제 요약 데이터로 들어온 문자열에서 같은 문자가 서로 붙어있다면 붙어있는 2개의 문자를 제거한다. 모든 문자가 제거가 되면 1을, 안 되면 0을 return한다. 문제 풀이 문자열의 길이는 최대 1M이므로 1s라 가정하면 O(nlogn)이 한계이다. 앞에서부터 탐색하며 제거가 되면 바로 앞의 문자부터 체크를 시작하여야 불필요한 탐색을 하지 않는다. 처음에는 string.erase 함수를 이용하였으나, 시간이 너무 오래 걸려 효율성 테스트를 하나도 통과하지 못하였다. 스택 방식으로 수정하였다...

title: Programmers - 가장 큰 수 date: 2022-06-20 tags: Algorithm https://programmers.co.kr/learn/courses/30/lessons/42746 문제 요약 데이터로 들어온 숫자들을 이어 붙여 가장 큰 수를 만들어야 한다. 매우 큰 수가 될 수 있으므로 문자열로 바꾸어 return한다. 문제 풀이 문자열로 return하라는 의미는 모든 수를 비교하는 것이 아닌, 올바른 방식으로 수를 정렬한 후 그대로 이어 붙이라는 뜻이다. algorithm의 sort 함수를 사용, 비교 함수인 bCompare 함수를 만들어 정렬한다. 정렬시 두 숫자를 붙인 문자열로 바꾸어 비교하여 더 큰 수가 만들어지는 순서대로 정렬한다. 추가적으로 프로그래머스는 itoa..

title: Programmers - 단체사진 찍기 date: 2022-06-20 tags: Algorithm DFS https://programmers.co.kr/learn/courses/30/lessons/1835 문제 요약 카카오 프렌즈를 조건에 맞게 배치하여야 한다. 가능한 경우의 수를 return한다. 문제 풀이 8마리가 확정이므로 약 40k를 검사하여야 한다. 조건은 최대 100개이므로 최대 4M의 순열 조합 생성과 조건 확인이 이루어진다. 조건 확인시 주어진 vector를 계속 확인해야 하므로 .data () 함수를 이용하여 시간을 줄일 수 있을 것으로 보인다. 이전에는 이러한 문제를 DFS로 풀었으나, next_permutation이라는 좋은 함수를 알게 되어 이를 활용하면 프로그램의 길이..

title: Programmers - 더 맵게 date: 2022-06-20 tags: Algorithm https://programmers.co.kr/learn/courses/30/lessons/42626 문제 요약 데이터로 들어온 값을 전부 K 이상으로 만들어야 한다. 가장 작은 두 데이터간의 연산을 통해 하나의 큰 데이터로 바꿀 수 있다. 변환 횟수를 count하며, 만들 수 없다면 -1을 return한다. 문제 풀이 데이터의 개수는 최대 1M, minimum indicator인 K는 0~1B 사이이다. int 타입으로 충분하나, signed의 경우 overflow가 발생할 수 있다. 테스트 케이스가 부족하여 overflow는 잡아내지 않는다. 1s 기준으로 O(nlogn) 까지가 한계이며, 값이 ..