골랜디 20250412 #1 Virtual 후기
골랜디를 진행해보았습니다.
오늘 느낀점은, 아직 g3 이상의 DP, Greedy 문제를 다루기에는 역부족하다는 것 입니다.
그래도 g5, g4 수준의 단순 구현이나 DP 는 해결할 수 있어 다행입니다.
SQL의 경우, easy 난이도는 말그대로 단순 문법이고, medium은 2문제 중 1문제만 해결할 수 있었습니다
.나머지 1문제의 경우도 조금 더 학습하면 해결할 수 있을 것 같습니다.
업솔빙한 문제로는
알고리즘 : 7570 줄세우기, 1781 컵라면
SQL : 1934 Confirmation Rate를 Upsolving했습니다.
줄 세우기
https://www.acmicpc.net/problem/7570
보자마자 어떻게 이걸 시간초과 안나게 구할 수 있을까? 라는 생각이 들었습니다.
완전탐색의 경우 어린이 수가(10*6)이기에 완탐 시 지수승으로 수렴하여 시간초과가 발생합니다.
그렇기에, DP나 그리디 스럽게 풀어야만 함을 인지는 했으나, 떠오르지 않아 포기했습니다.
------
업솔빙하며, 숫자를 맨 뒤나 맨 앞으로만 이동시킬 수 있기에 LIS인데, + 1 간격인 LIS를 구하는 것임을 이해했습니다.
처음에 LIS 코드를 작성하였습니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int N;
static int answer = 0;
static int[] arr;
static int[] cache = new int[1000001];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
arr = new int[N];
for(int i=0; i<N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.fill(cache, -1);
for(int i=0; i<N; i++) {
answer = Math.max(answer, solve(i));
}
System.out.println(N - answer);
}
static int solve(int idx) {
if(idx == N-1) {
return 1;
}
if(cache[idx] != -1) return cache[idx];
int ret = 1;
for(int i=idx + 1; i<N; i++) {
if(arr[idx] + 1 == arr[i]) {
ret = Math.max(ret, solve(i) + 1);
}
}
return cache[idx] = ret;
}
}하지만 시간초과가 발생합니다. 분명 메모이제이션을 활용했다고 생각했지만, 이 문제의 경우 오직 +1 인 값만 메모이제이션이 작동하기에, 실제적으로는 거의 모든 구간을 O(N^2)으로 탐색하는 것을 깨달았습니다.
더 이상 풀이가 떠오르지 않아, 다른 분들의 코드를 확인했고,
아래와 같이 직접 Position이 뒤 Index에 존재하는지 확인하는 방식이 있습니다.
이때, position[] 배열 : 인덱스에 해당하는 숫자가 위치한 인덱스를 저장 하는 것을 통해 문제를 해결함을 알 수 있습니다.
package Main;
import java.io.*;
import java.util.*;
public class Main {
static int N;
static int[] arr;
static int answer = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
arr = new int[N];
st = new StringTokenizer(br.readLine());
int[] position = new int[N + 2];
Arrays.fill(position, -1);
for(int i=0; i<N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
position[arr[i]] = i;
}
for(int i=0; i<N; i++) {
int currentNumber = arr[i];
int currentPos = i;
int length = 1;
while(currentNumber + 1 <= N && position[currentNumber + 1] > currentPos) {
currentPos = position[currentNumber +1];
currentNumber++;
length++;
}
answer = Math.max(answer, length);
}
System.out.println(N - answer);
}
}
이런 풀이도 존재하지만, DP 풀이도 존재했습니다.
사실, 탑다운 방식으로 DP 풀이를 재해석 해보려했으나, 도저히 풀리지 않아 상향식으로 재작성했습니다.
(상향식은 저에게 아직 어렵습니다. 앞으로 상향식 연습계획)
상향식으로 푼 방식입니다.
여기서 dp[i] 배열을 정의하면, i번호일떄까지 증가한 연속증가부분 수열의 개수 라고 정의합니다.
점화식은
dp[i] = dp[i-1] + 1; 이 됩니다.
package Main;
import java.io.*;
import java.util.*;
public class Main {
static int N;
static int[] arr;
static int[] dp;
static int answer = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
arr = new int[N];
st = new StringTokenizer(br.readLine());
dp = new int[N+1];
for(int i=0; i<N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
dp[arr[i]] = dp[arr[i] - 1] + 1;
answer = Math.max(answer, dp[arr[i]]);
}
System.out.println(N - answer);
}
}
바둑알 점프
https://www.acmicpc.net/problem/17492
일반적인 구현문제입니다.
한번에 문제를 해결했고, dxdr 과 같이 방향을 정의하는 부분에서, 2차원 배열안에서 (,) 콤마를 작성하지 않는 바람에 약간의 시간소요가 있었습니다.
자바의 가변배열에 대하여 다시금 조심해야 함을 느꼈습니다.
import java.io.*;
import java.util.*;
public class Main {
static int N;
static int[][] map;
static int[][] dir = {{-1,-1}, {-1,0}, {-1,1}, {0,1}, {1,1}, {1,0}, {1,-1}, {0,-1}};
static boolean answer = false;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
map = new int[10][10];
for(int i=0; i<N; i++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
solve();
System.out.println(answer == true ? "Possible" : "Impossible");
}
static void solve() {
if(answer == true) return ;
int cnt = 0;
for(int i=1; i<map.length-1; i++) {
for(int j=1; j<map.length-1; j++) {
if(map[i][j] == 2) {
cnt += 1;
}
if(cnt > 1) break;
}
if(cnt > 1) break;
}
if(cnt == 1) answer = true;
int[][] storeMap = new int[N][N];
for(int i=1; i<N-1; i++) {
for(int j=1; j<N-1; j++) {
//만약 바둑알이 존재하는 곳이라면, 8가지 방향을 살펴보며 확인합니다.
if(map[i][j] == 2) {
int r = i;
int c = j;
for(int[] dxdy : dir) {
int nr = r + dxdy[0];
int nc = c + dxdy[1];
if(nr < 1 && nc < 1 && nr >= N && nc >= N) continue;
//점프할 공간이 넘치지 않는지 확인합니다.
int jumpNr = nr + dxdy[0];
int jumpNc = nc + dxdy[1];
if(jumpNr < 1 && jumpNc < 1 && jumpNr >= N && jumpNc >= N) continue;
//만약 점프할 사이 공간에 바둑알이 존재한다면, 점프는 가능하다.
if(map[nr][nc] == 2 && map[jumpNr][jumpNc] == 0) {
for(int q=0; q<N; q++) {
for(int w=0; w<N; w++) {
storeMap[q][w] = map[q][w];
}
}
map[r][c] = 0;
map[nr][nc] = 0;
map[jumpNr][jumpNc] = 2;
solve();
for(int q=0; q<N; q++) {
for(int w=0; w<N; w++) {
map[q][w] = storeMap[q][w];
}
}
}
}
}
}
}
}
}
병약한 윤호
https://www.acmicpc.net/problem/14677
이 문제 N이 500 이기에 1500개의 약 조합이 주어집니다.
그렇기에 당연히 시간복잡도 초과가 우려되어 DP나 그리디로 문제의 범위가 줄어들었고, 문제에서 최적부분구조 형태가 보여 다이나믹 프로그래밍을 적용했습니다.
이 문제 또한 바로 해결완료했습니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int N;
static int answer = 0;
static int[] arr = new int[1501];
static int[][] cache = new int[1502][1502];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
String str = st.nextToken();
for(int i=0; i<str.length(); i++) {
arr[i] = str.charAt(i) == 'B' ? 0 : str.charAt(i) == 'L' ? 1 : 2;
}
for(int i=0; i<cache.length; i++) {
Arrays.fill(cache[i], -1);
}
answer = solve(-1, N*3, 0);
System.out.println(answer);
}
public static int solve(int left, int right, int turn) {
if(left + 1 == right) {
return 0;
}
if(cache[left + 1][right + 1] != -1) {
return cache[left + 1][right + 1];
}
int ret = 0;
if(arr[left + 1] == turn) {
ret = Math.max(ret, solve(left + 1, right, ( (turn + 1) % 3)) + 1);
}
if(arr[right - 1] == turn) {
ret = Math.max(ret, solve(left, right - 1, ( (turn + 1) % 3)) + 1);
}
return cache[left + 1][right + 1] = ret;
}
}
컵라면
https://www.acmicpc.net/problem/1781
보자마자, 냅색이 떠올랐으나, 문제의 예시가 이해가 가지않아 구체적인 풀이가 떠오르지 않았습니다.
2, 6, 3, 1, 7, 5, 4 순으로 숙제를 하는데 갑자기 2, 6, 3, 7 번 문제를 시간 내에 풀었다라고 합니다.
그러면 1번 문제는 데드라인이 1인데 왜 7번 문제를 갑자기 먼저 푼것인가? 하는 이해가 안가는 점에 의해서 문제를 포기했습니다.
업솔빙 한 과정입니다.
1. 주어진 데드라인 컵라면을, 데드라인 오름차순, 컵라면 내림차순으로 정렬합니다.
2. pq에 내가 받은 컵라면을 저장합니다. 이떄 오름차순으로 저장합니다.
3. 만약, 데드라인 이내의 과제라면 먼저 처리합니다.
4. 만약 데드라인 이후의 과제인데, 내가 받았던 컵라면 보다 더 많은 컵라면을 준다면, 이 과제를 진행하고, 이전에 진행했던 과제를 하지 않습니다. 이 과정이 가장 "그리디"스러운 방식입니다.
이 4번 과정의 사고방식이 가장 중요합니다. (우리는 이미 미래의 컵라면을 알고 있고, 과거의 컵라면을 언제든지 사용하지 않아도 된다는점을 알아야 합니다.)
package Main;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
static int N;
static int[] arr;
static int[] dp;
static int answer = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
int[][] arr = new int[N][2];
for(int i=0; i<N; i++) {
st = new StringTokenizer(br.readLine());
arr[i][0] = Integer.parseInt(st.nextToken()); //데드라인
arr[i][1] = Integer.parseInt(st.nextToken()); //컵라면 수
}
Arrays.sort(arr, new Comparator<int[]>() {
@Override
public int compare(int[] a, int[] b) {
if(a[0] == b[0]) {
return b[1] - a[1];
}
return a[0] - b[0];
}
});
//내가 지금까지 받은 컵라면
PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer a, Integer b) {
return a - b;
}
});
for(int i=0; i<arr.length; i++) {
if(pq.size() < arr[i][0]) {
pq.add(arr[i][1]);
}else if(pq.size() == arr[i][0] && pq.peek() < arr[i][1]){
pq.poll();
pq.add(arr[i][1]);
}
}
while(!pq.isEmpty()) {
answer += pq.poll();
}
System.out.println(answer);
}
}
570. Managers with at Least 5 Direct Reports
문제가 계층구조를 알고 있느냐 라고 물어보는 듯합니다.
이 계층구조를 이해하고 있다면, 문제를 곧바로 이해하고 코딩이 가능합니다.
/* Write your PL/SQL query statement below */
select e1.name
from employee e1
inner join employee e2 on e1.id = e2.managerid
group by e1.id, e1.name
having count(*) >= 5;
1934. Confirmation Rate
https://leetcode.com/problems/confirmation-rate/description/?envType=study-plan-v2&envId=top-sql-50
사실 처음에 left outer join을 한뒤 user_id로 grouping 하여 이후 timeout과 confirmed의 개수를 select절에서 센뒤 그값을 분수로 표현하면 된다고 생각했습니다.
하지만, 문제점은 select절에서 case when을 사용하려고 했지만, 그것의 개수를 어떻게 표현하는것에서 막혔습니다.
실패한 쿼리입니다.
select s.user_id
from signups s
left outer join confirmations c on s.user_id = c.user_id
group by user_id;
업솔빙 과정입니다.
예상대로 CASE WHEN을 사용하였고, group by 에 의해 자동으로 c.action일 경우 1.00, 아닐경우 0.00 으로 더해진뒤 AVG 집계함수로 평균값이 구해집니다.
select s.user_id,
ROUND(
AVG(
CASE
WHEN c.action = 'confirmed' then 1.00
else 0
END
),
2) as confirmation_rate
from signups s
left outer join confirmations c on s.user_id = c.user_id
group by user_id;
620. Not Boring Movies
https://leetcode.com/problems/not-boring-movies/description/?envType=study-plan-v2&envId=top-sql-50
easy합니다.
오랜만에 쿼리를 작성해서 그런지 id % 2 == 1 로 작성하는 실수를 저질렀습니다.
또한, descritpion의 경우에도 sql에서 not description = 'boring' 처럼 not 연산자가 떠올라서 어떻게 할지 고민했으나, 심플하게 != 로 작성했습니다.
select *
from cinema
where id % 2 = 1 and description != 'boring'
order by rating desc
'알고리즘 > 랜덤디펜스' 카테고리의 다른 글
| [백준][랜덤디펜스] 골랜디 Virtual #4 (0) | 2025.04.16 |
|---|---|
| [백준][랜덤디펜스] 골랜디 Virtual #3 (0) | 2025.04.15 |
| [백준][랜덤디펜스] 골랜디 Virtual #2 (0) | 2025.04.13 |