혼자 공부하는 공간

안녕하세요 GODZ입니다. 오늘은 문자열을 이용한 문제를 풀어볼 예정입니다. 1. 문제 2. 입출력 예제 3. 접근 [설명] N개의 문자열의 집합에서 특정 문자열이 어떤 문자열의 접두사가 되지 않을 때, 그 집합을 접두사 X 집합이라고 한다. 또한 접두사 X 집합을 만족하는 가장 큰 집합을 만드는 게 관건이다. 문자열의 수(N)가 최대 50, 문자열의 길이(M)가 최대 50이다. ---> 각 문자열을 이중 반복문으로 순회해도 O(N^2)이고, 문자열을 비교할 때 역시 O(M)이므로 결국 O(MN^2) = 125,000회 이내이다. [로직] 기준 문자열(origin)과 N-1개의 비교 문자열(comp)을 비교한다. origin의 길이가 comp의 길이보다 같거나 짧을 때만 비교한다. ---> origin의..

안녕하세요 GODZ입니다. 오늘은 동적 프로그래밍을 이용한 문제를 풀어볼 예정입니다. 1. 문제 2. 입출력 예제 3. 접근 동적 프로그래밍에서 가장 중요한 것은 해결했던 문제에 대해서 다시 문제를 풀지 않는 것이다. 이전에 풀었던 문제를 메모이제이션(Memoization)을 통해 다시 계산하지 않고 결과 값만 가져온다. * res[k] : k원을 만들 수 있는 경우의 수 * cArr[i] : i번 째 동전의 값 * res[k] += res[k - cArr[i]] : k원을 만들 수 있는 경우의 수에 k - cArr[i]원을 만들 수 있는 경우의 수의 합 [설명] * cArr[i]가 1원일 때, 10원을 만들기 위해서는 res[10] += res[9] ---> cArr[i]가 1원일 때의 res[10] ..

안녕하세요 GODZ입니다. 오늘은 이분 탐색을 이용한 문제를 풀어볼 예정입니다. 1. 문제 2. 입출력 예제 3. 접근 정렬한 뒤, 최대값에서 빼가면서 총 예산(M)을 맞추는 것은 각 예산 값들이 100,000 이하인 것을 감안하면 시간 제한(1초)를 맞출 수 없다. 따라서 이분 탐색을 통해 시간 복잡도를 log로 변환하여 작업을 줄이도록 한다. 예산의 값 중 최대값을 찾는다. 최소값과 최대값의 평균값(mid)을 구해 각 예산에 상한선을 적용한 뒤, 총 예산과 비교한다. 총 예산보다 작으면, mid값을 저장하고 mid값을 최소값으로 설정한 뒤 4번 작업 반복. 총 예산보다 크면, mid값을 최대값으로 설정한 뒤 4번 작업 반복. 최대값과 최소값이 같으면 반복을 종료하고, 저장된 mid값 중 가장 큰 값을..

안녕하세요 GODZ입니다. 오늘은 이분 탐색과 투 포인터를 이용한 문제를 풀어볼 예정입니다. 1. 문제 2. 입출력 예제 3. 접근 N개의 수를 하나씩 입력 받으면서 합 sum을 구한다. sum >= S 일 때, 길이 len을 저장하고 0번 인덱스부터 S보다 작아질 때까지 sum에서 뺀다. sum = S 일 때, 2번 작업 반복. 모든 수를 다 입력 받았으면 저장한 길이 len 중 최소값을 찾는다. 만약 저장한 길이 len이 존재하지 않는다면 0을 출력한다. 4. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36..

안녕하세요 GODZ입니다. 오늘은 문자열을 이용한 문제를 풀어볼 예정입니다. 1. 문제 2. 입출력 예제 3. 접근 원본 문자열의 길이 N(1이상 1백만 이하), 비교 문자열의 길이 M(1이상 36이하) 일 때, 원본 문자열을 한 번 순회하면서 비교 문자열을 지우는 작업은 O(NM)의 시간 복잡도를 가진다. O(NM)의 복잡도가 수없이 반복되기 때문에 제한시간을 맞출 수 없다. 따라서 문자열을 순회하면서 비교 문자열과 비교하는 작업을 병행한다. 원본 문자열을 저장할 자료구조는 StringBuilder나 Stack 그 외 List와 같은 mutable 구조를 사용하면 된다. 어떤 자료구조를 사용하든 간에 남은 원본 문자열을 출력해야 하므로 StringBuilder가 다른 자료구조에 비해 빠르다. 4. 코드..

안녕하세요 GODZ입니다. 오늘은 세그먼트 트리를 이용한 문제를 풀어볼 예정입니다. 1. 문제 2. 입출력 예제 3. 개념 세그먼트 트리(Segment Tree)는 연속적인 여러 개의 데이터가 존재할 때, 특정 범위 데이터만 처리하기 위해 사용하는 자료구조 입니다. 예를 들어, 배열(arr)에 {10, 9, 8, 7, 6, 5, 4, 3, 2, 1} 이라는 원소가 선형구조로 존재합니다. 여기서 인덱스는 1부터 시작이라고 가정하고 1부터 4, 5부터 8, 3부터 9, 7부터 9 에서의 최솟값을 구하는 기능을 하게끔 만들어야 한다고 합시다. 구현할 때 해당 인덱스(1, 4 // 5, 8 // 3, 9 // 7, 9)를 모두 순회하면서 구해야할 것입니다. 이때 배열 크기가 N, 최솟값을 구하는 횟수가 M 이라..

안녕하세요 GODZ입니다. 오늘은 문자열 처리를 이용한 문제를 풀어볼 예정입니다. 1. 문제 2. 입출력 예제 3. 로직 일단 입력 받은 문자열이 Java 특징에 해당하는지, C++ 특징에 해당하는지 검사합니다. - 특징 - Java - 첫 문자 소문자 // 단어를 구분하기 위해 앞 문자 대문자 사용 C++ - 소문자만 사용 가능 // 단어를 구분하기 위해 언더바(_) 사용 flag라는 변수를 두어 Error인 경우, Java인 경우, C++인 경우, 둘 다 해당되는 경우에 대해 값을 지정합니다. 그 후 각 값마다 해당하는 기능을 하게끔 로직을 만들면 되겠습니다. 처음 flag는 둘 다 포함으로 할당 입력받은 문자열의 첫 문자가 소문자인가? 소문자인 경우 arr[index] == '_' 인 경우 flag..

안녕하세요 GODZ입니다. 오늘은 문자열 처리를 이용한 문제를 풀어볼 예정입니다. 1. 문제 2. 입출력 예제 3. 접근 흔한 괄호 문제인데 생각보다 정답률이 많이 낮아서 가지고 온 문제입니다. 문자열 사이에 들어간 (, [ 와 ), ]가 제대로 짝이 맞게 들어갔는지 확인하는 문제입니다. 핵심은 닫히는 괄호에서 처리하는 로직입니다. 여는 괄호에서는 그냥 Stack에 push작업만 하면 되지만, 닫히는 괄호에서는 몇 가지 처리를 잘해주셔야 통과할 수 있습니다. 닫히는 괄호일 때, 아래와 같은 사항들을 체크해야 합니다. 더보기 1. Stack이 비어있는가? 2. 비어있지 않다면 짝이 맞는 괄호인가? 1에서 비어있는지 체크하지 않으면 런타임 에러가 뜰 수 있습니다. 2에서 짝이 맞지 않는 괄호라면 no를 출력..