끈기 있는 개발 공간

https://school.programmers.co.kr/learn/courses/30/lessons/12983접근이 문제는 완전 탐색으로 해결할 수 없다.strs 배열의 길이가 $1\leq{…}\leq{100}$ 이기 때문에, 순열을 계산하면 시간이 초과될 것이기 때문이다.t의 길이 제한이 $1\leq{…}\leq{20,000}$ 이기 때문에 DP만 잘 정의하면,t의 어느 자릿수까지를 만드는 데 필요한 최소 조각수를 구할 수 있다.따라서, memoization을 위한 배열 dp를 i 길이의 문자열을 만드는 데 필요한 최소 조각 수로 정의한다.소스코드(Java)class Solution { public int solution(String[] strs, String t) { int[] ..

https://school.programmers.co.kr/learn/courses/30/lessons/60060접근이 문제를 보자마자 딱 들었던 생각이 Trie 자료구조를 사용해야겠다는 것이었다.마침 얼마 전 Trie 자료구조를 알게 된 문제가 있어 관련 포스팅을 작성했었다.Trie 자료구조에 대해 궁금하면 다음 글을 읽어보면 도움이 될 것이다.[Algorithm] 프로그래머스 - [3차] 자동완성words와 queries 배열의 길이 제한사항이 $2\leq{…}\leq{100,000 }$ 이기 때문에 완전 탐색으로는 이 문제를 풀 수 없다.그래서 words를 Trie 자료구조상 트리 형태로 저장시키고, queries 배열의 원소들을 Trie에서 하나씩 순차적으로 탐색해야 한다. 트리 자료구조에서 탐색..

https://school.programmers.co.kr/learn/courses/30/lessons/43236접근주어진 제한사항에서 rocks 배열의 길이가 50,000개 이하이므로 솔루션의 시간복잡도는 $O(N^2)$이 될 수 없다.$O(N\log{N})$, $O(N\log{M})$이나 $O(N)$의 시간복잡도를 가지는 알고리즘을 선택해야 한다.잘못된 초기 접근펼치기/접기나는 아쉽게도 $O(N)$의 시간복잡도로 문제를 해결하려고 시도했다. DP로 접근했다.일단 주어진 rocks 배열을 오름차순으로 정렬시킨다. 근데, 이미 이 부분에서 $O(N\log{N})$이 됐다…바위 사이의 거리를 담은 배열 d를 정의한다. 이 때, 시작지점과 도착지점도 포함하여 거리를 계산한다.예를 들어, rocks 배열을 오..

비트마스크는 비트(bit) 연산을 사용해 부분 집합을 표현하는 것이다.비트 연산비트 연산에는 대표적으로 다음과 같이 네 가지 연산이 있다.& ($AND$) : 두 조건이 참이면 참, 아니면 거짓으로 처리| ($OR$) : 두 조건 중 하나라도 참이면 참, 아니면 거짓으로 처리~ ($NOT$) : 주어진 조건이 참이면 거짓, 거짓이면 참으로 처리^ ($XOR$) : 두 조건이 서로 다르면 참, 아니면 거짓으로 처리다음은 비트 연산의 이해를 돕기 위한 표이다.십진수 $A$와 $B$의 비트 연산은 $A$와 $B$를 이진수로 변환하여 가장 뒤의 자리부터 하나씩 연산을 수행하면 된다.예를 들어, $A=27$, $B=83$인 경우 이를 이진수로 변환하면 $A = 11011_{(2)}$, $B=1010011_{(2)..

순열순열(Permutation)은 임의의 수열을 다른 순서로 섞는 연산이다.예를 들어, 수열 1 2 3 4가 있을 때, 1 2 3 4 | 1 2 4 3 | 1 3 2 4 | 1 3 4 2 | 1 4 2 3 | 1 4 3 2가 1 2 3 4의 순열이다.이는 서로 다른 순열의 개수가 $4!$이고 사전식 나열임을 알 수 있다.이를 통해 크기가 $N$인 수열의 서로 다른 순열의 개수는 $N!$라는 것을 알 수 있다.그리고 C++에서 순열을 나타낼 때는 사전식으로 나타내므로 일반적으로 위와 같이 순열을 사전식으로 나타낸다.다음 순열사전순으로 다음에 오는 순열과 이전에 오는 순열을 찾는 방법을 알아보자.C++ STL의 algorithm에는 이미 next_permutation과 prev_permutation이 존재하..

브루트 포스에서 방법을 만드는 방법은 크게 세 가지가 있다.재귀 호출순열비트마스크이 중 가장 중요한 방법이 재귀 호출이다.그 이유는 순열과 비트마스크 모두 재귀 호출을 이용하여 구현할 수 있기 때문이다.그러므로 재귀 호출에 대한 이해와 연습이 필요하다.N과 M 문제는 재귀 호출에 대한 이해와 연습을 하기에 적절하다.N과 M 문제는 크게 순서와 선택과 관련된 문제인데 이것이 무엇을 의미하는지 문제를 풀어가며 알아보자.백준 15649번 - N과 M (1)https://www.acmicpc.net/problem/15649소스코드(C++)#include using namespace std;int a[9];bool c[9];void go(int index, int n, int m) { if(index == ..

재귀브루트 포스에서 방법을 만드는 방법은 크게 세 가지로, 재귀 호출, 순열, 비트마스크가 있다고 하였다.이 때, 순열과 비트마스크는 재귀로 구현할 수 있기 때문에 재귀가 가장 중요한 방법이라고 하였다.아래는 이와 관련된 N과 M 포스팅이다.https://tenutz.tistory.com/58그렇다면 재귀는 어떻게 구현을 해야 할까?재귀를 구현할 때, 생각해야 할 것은 크게 세 가지다.불가능한 경우정답을 찾기 위한 조건을 만족하지 못하는 경우 즉, 재귀를 계속 진행해도 의미가 없는 경우를 뜻한다.정답을 찾은 경우정답을 찾은 경우에 적절한 처리가 이루어져야 재귀를 계속 진행할 수 있다.다음 경우 호출정답을 계속해서 찾아나가기 위해 다음 경우를 어떻게 호출할 것인지 생각해야 한다.대표적으로 N과 M 포스팅에..

건너 뛰며 해보기건너 뛰며 해보기는 모든 경우의 수를 다 안 해봐도 된다고 판단될 경우에 몇 가지를 생략하고 넘어가는 것을 말한다.백준 6064번 - 카잉 달력https://www.acmicpc.net/problem/6064$M$과 $N$보다 작거나 같은 자연수 $x$, $y$를 가지고 각 년도를 와 같은 형식으로 표현한다.의 다음 해를 이라고 할 때, $x\lt{M}$이면 $x^{\prime}=x+1$이고, 그렇지 않으면 $x^{\prime}=1$이다. $y$의 경우도 마찬가지다.네 개의 정수 $M$, $N(1\leq{M,N}\leq{40,000}), x(1\leq{x}\leq{M}), y(1\leq{y}\leq{N})$가 주어질 때,이 첫 번째 해이고, 이 카잉 달력의 마지막 해라고 하면 는 몇 번째..