전체 글
백준 1451번 직사각형으로 나누기 // JAVA
문제 직사각형으로 나누기 세준이는 N*M크기로 직사각형에 수를 N*M개 써놓았다. 세준이는 이 직사각형을 겹치지 않는 3개의 작은 직사각형으로 나누려고 한다. 각각의 칸은 단 하나의 작은 직사각형에 포함되어야 하고, 각각의 작은 직사각형은 적어도 하나의 숫자를 포함해야 한다. 어떤 작은 직사각형의 합은 그 속에 있는 수의 합이다. 입력으로 주어진 직사각형을 3개의 작은 직사각형으로 나누었을 때, 각각의 작은 직사각형의 합의 곱을 최대로 하는 프로그램을 작성하시오. 입력 첫째 줄에 직사각형의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 직사각형에 들어가는 수가 가장 윗 줄부터 한 줄에 하나씩 M개의 수가 주어진다. N과 M은 100보다 작거나 같은 자연수이고, 직사각형엔 적어도 3개의 수가 있다..
백준 17135번 캐슬 디펜스 // JAVA
문제 캐슬 디펜스 캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 N×M인 격자판으로 나타낼 수 있다. 격자판은 1×1 크기의 칸으로 나누어져 있고, 각 칸에 포함된 적의 수는 최대 하나이다. 격자판의 N번행의 바로 아래(N+1번 행)의 모든 칸에는 성이 있다. 성을 적에게서 지키기 위해 궁수 3명을 배치하려고 한다. 궁수는 성이 있는 칸에 배치할 수 있고, 하나의 칸에는 최대 1명의 궁수만 있을 수 있다. 각각의 턴마다 궁수는 적 하나를 공격할 수 있고, 모든 궁수는 동시에 공격한다. 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다. 같은 적이 여러 궁수에게 공격당할 수 있다..
LeetCode - 997. Find the Town Judge
문제 In a town, there are N people labelled from 1 to N. There is a rumor that one of these people is secretly the town judge. If the town judge exists, then: The town judge trusts nobody. Everybody (except for the town judge) trusts the town judge. There is exactly one person that satisfies properties 1 and 2. You are given trust, an array of pairs trust[i] = [a, b] representing that the person l..
LeetCode - 746. Min Cost Climbing Stairs
문제 On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed). Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1. 풀이 기초적인 DP 문제이다. 한번에 올라갈 수 있는 계단의 수는 한칸 또는 두칸이며, 해당 칸을 밟을 경우 그만큼의 코스트를 사용한다. 이 때, 최소 코스트를 사용하여 가장 윗 칸까지 이동..
LeetCode - 303. Range Sum Query
문제 풀이 가장 기초적인 DP 문제이다. 0부터 배열의 끝까지의 합을 구한 배열을 하나 선언하여, sumRange 함수가 호출 될 때 사용하면 된다. sum 배열은 0 ~ num.length + 1 값이 존재하며, sum[i]는 num[0]~num[i-1]까지의 합을 의미한다. 따라서 sumRange(i,j)는 sum[j + 1] - sum[i]를 반환하면 원하는 결과를 얻을 수 있다. 코드 더보기 class NumArray { int []nums; int []sum; public NumArray(int[] nums) { this.nums = nums; sum = new int[nums.length + 1]; for(int i=1;i
6kyu - Find the unique number // Python
문제 There is an array with some numbers. All numbers are equal except for one. Try to find it! find_uniq([ 1, 1, 1, 2, 1, 1 ]) == 2 find_uniq([ 0, 0, 0.55, 0, 0]) == 0.55 It’s guaranteed that array contains at least 3 numbers. The tests contain some very huge arrays, so think about performance. 풀이 문제 조건에서 배열에 데이터가 많다고 했기 때문에 중복 값을 제거하는 것을 우선 순위로 생각했다. Python에서는 배열을 Set(중복된 값이 없는 자료형)으로 만드는 Method..
백준 18119번 단어 암기 // C++
문제 단어 암기 준석이는 영어 단어를 외우려고 한다. 사전에는 N가지 단어가 적혀 있다. 모든 단어는 소문자이다. 단어 안에 있는 모든 알파벳을 알 때, 그 단어를 완전히 안다고 한다. 다음과 같은 쿼리들이 주어진다. 1 x : 알파벳 x를 잊는다. 2 x : 알파벳 x를 기억해 낸다. 처음에 모든 알파벳을 기억하는 상태고, 모음은 완벽하게 외웠기 때문에 절대 잊지 않는다. 각 쿼리마다 완전히 알고 있는 단어의 개수를 출력하여라. 입력 첫 번째 줄에는 정수 N (1 ≤ N ≤ 104)과 M (1 ≤ M ≤ 5×104)이 주어진다. 다음 N개의 줄에는 문자열이 하나씩 주어진다. 문자열의 길이는 103을 넘지 않는다. 다음 M개의 줄에는 정수 o와 문자 x가 한 줄씩 주어진다. o는 1, 2중 하나이고, x..