전체 카테고리

해당 문제는 K개의 수를 받아서 해당 수들이 M개의 카드 목록에 몇개 존재하는지를 확인해야하는 문제이다. 신경써야 할 부분은 첫 번째로 K번 만큼의 루프를 돌아야 한다는 점, 이분 탐색을 이용하면서 어떻게 특정 수가 몇 개 있는지를 확인하느냐이다. 특정 수가 몇 개인지 확인하고자 할 때, 우리는 이분 탐색의 특징을 이용할 수 있다. 이분 탐색은 반드시 탐색하는 배열이 정렬되어 있어야 한다. 이를 이용하면 내가 찾고자 하는 값이 탐색하는 배열에 복수개가 있다면, 이들은 연속해서 존재할 것이라는 점이 중요하다. 때문에 연속해서 있는, 이 같은 수들로 이루어진 블럭의 시작과 끝 인덱스를 안다면 해당 요소가 몇 개 있는지 알 수 있다. 이를 위해 UpperBound, LowerBound 개념을 이용한다. cf...

문제 자체는 어렵지 않다. 이전 글인 '나무 자르기' 글을 참고하면 쉽게 풀 수 있는 문제다. 문제의 조건 중 'N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이 때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오'는 중간값(mid, 자르는 길이)로 잘랐을 때의 랜선 길이의 수(cnt)가 N보다 크더라도 조건에 일치하는 것으로 본다는 의미를 가진다. 또한, 해당 조건(N개 이상의 랜선을 만들 수 있도록 랜선 길이를 정하는 방법)에 일치하는 경우의 수가 여러 가지이며, 이 경우들 중에서 자르는 랜선의 최대 길이(여기서는 이를 확인하기 위한 값으로 mid 사용)가 최댓값인 경우를 찾는 문제이다. 즉, cnt가 M과 같은 경우에는 lt를 mid + 1 로 변경시켜서 두 범위 중 더 큰..

이분 탐색을 통해 최소한 M미터 이상의 나무를 가져갈 수 있는 상황을 모두 체크해야 한다. 단순 이분 탐색과 다른 점은 이분 탐색에서는 확인하고자 하는 배열을 정렬해서 모든 처리가 끝나지만, 이 문제처럼 배열의 순서가 지켜져야 하는 상황에서는 아래와 같이 Java Stream을 사용해 rt 값을 최댓값으로 정의할 수 있다. (lt 역시 최솟값으로 설정해야 한다.) 유의할 점은 조건에 일치하는 경우에 lt, rt를 어떻게 움직이냐는 것인데, 높이(mid)를 높게 잡을 수록 가지고 갈 수 있는 나무가 적어진다. 문제에서는 자르는 높이의 최댓값(가져갈 수 있는 양은 최솟값이 됨)을 구하기 때문에, sum이 M과 일치하거나 더 높은 경우에는 자르는 높이를 올려야 한다. 즉, 두 범위 중 뒷 범위에서 탐색이 다시..

이분 탐색(Binary Search) 탐색(search) 기법 중 하나로, 정렬된 배열에서 찾고자하는 값을 탐색할 때 그 범위를 두 부분으로 나누어(=이분) 탐색하는 방법이다. 탐색하고자 하는 범위를 계속해서 줄여감으로써 시간 효율성을 O(logN)까지 올릴 수 있다. 탐색 범위를 줄이는 방법은 다음과 같다. 범위의 가장 중앙 인덱스(mid)의 값과 찾고자 하는 값을 비교한다. 찾고자 하는 값이 해당 인덱스(mid) 값보다 클 경우 범위는 해당 인덱스(mid)의 바로 뒤(mid + 1)부터 탐색 범위의 마지막 인덱스(처음에는 끝 인덱스)까지이다. 다시 정의된 범위에서 가장 중앙 인덱스의 값과 비교한다. (mid 값 변경) 찾고자 하는 값이 중앙 인덱스 값보다 작을 경우 범위는 탐색 범위의 시작 인덱스부터..

팝업에 보여질 html, js의 파일명이 아래와 같을 때, 다음과 같이 다이얼로그를 실행시킬 수 있다. sample.html resources/js/sample.js Open jQuery의 load() 함수를 통해 html을 로드해와서 이것을 dialog() 함수를 통해 다이얼로그로 열 수 있다. 이 때 관련 js 파일이 함께 로드되도록 하기 위해 해당 함수(openDial)가 실행될 때마다 requireJS의 undef() 함수로 js 파일을 초기화시켜준다. 팝업을 닫을 때 해당 js 파일을 초기화시켜주기 위해 jQuery Dialog에서 제공하는 beforeClose() 함수 내부에 초기화시켜주는 코드를 추가한다.

문제(백준 캡쳐) 초기 작성 코드 import java.util.Scanner; public class Main { private int solution(String str) { int answer = 0, idx = 0; char[] stack = new char[str.length()]; stack[idx++] = '('; for (int i = 1; i < str.length(); i++) { char c = str.charAt(i); if (c == '(') stack[idx++] = c; else { if (c == str.charAt(i - 1)) { stack[--idx] = ' '; answer++; } else { stack[--idx] = ' '; answer += idx; } } } ..

문자열 S와 T가 주어지고, S에서 문자열 T와 아나그램이 되는 부분문자열의 개수를 출력하는 문제이다. 첫 줄에 S가, 다음 줄에 T가 입력된다. 주어지는 문자열의 각 문자를 해싱해서 문자의 개수를 value로 삼는 것이 기본이 된다. 여기에 문자 T는 항상 S보다 짧은 문자열이고, S 내에서 T와 아나그램인 연속되는 문자를 찾는 것이기 때문에, T의 길이만큼 sliding-window 알고리즘 기법을 사용하면 된다. 사실 처음에 two-pointer 알고리즘 기법도 함께 적용하려 했으나 다른 문제로 실패하면서 보류하게 되었다. 이후에 코드를 개선할 때 추가할 예정이다. 많은 시간이 소요된 부분 two-pointer, sliding-window 알고리즘을 사용하기 위해 문자열 T를 해싱할 때 S 문자열의..

0과 1로 구성된 길이가 N인 수열이 주어지면, 이 수열에서 최대 k번 0을 1로 변경할 수 있습니다. 최대 k번의 변경을 통해 이 수열에서 1로만 구성된 최대 길이의 연속부분수열을 찾는 프로그램을 작성하는 문제이다. 첫 줄에 수열의 길이인 자연수 N(5

N개의 수로 이루어진 수열이 주어지면, 이 수열에서 연속부분수열의 합이 특정숫자 M이 되는 경우가 몇 번 있는지 구하는 문제이다. 초기 작성 코드 import java.util.Scanner; public class Main { private int solution(int n, int m, int[] arr) { int answer = 0; for (int i = 0; i m) break; } } return answer; } public static void main(String[] args..

N일 동안의 매출 중 연속 K일 동안의 최대 매출액을 출력하는 문제다. 첫 줄에 N(5