Meluu_의 코딩 공부 일지

🧫 문제 분석 ✔️ 출처사전 순 최대 공통 부분 수열 골드 4 📖 문제 삽질을 많이 한 문제그리디 알고리즘인데  처음에는 문자열로 만들어서 하다가 생각해보니 100 같은 건 더 큰 수인데 사전순으로는 매우 낮다.  두번째로 A  수열의 각각의 위치에서 시작해서 LDS 탐색을 해서 여러 LDS를 얻어B  수열에서 또 LDS각각 원소에 대해 맞는지 확인하는 식이였는데 그냥 엉터리였고, 이상한 접근법을 해서 틀렸다. A 수열에서 큰값순으로 값을 저장한다음 단순히 B 수열에서 순차적으로 찾아도 안된다.51 90 100 85 5 5100 90 5 1 2//answer2100 5// wrong3100 90 5 A수열에서 큰 값 순으로 저장했다면100 90 85 5 1이렇게 저장되어있을 것이다.  제일 큰 100..

🧫 문제 분석 ✔️ 출처램프 골드 4 📖 문제  예전에 못풀었다가 정말 잊혀질때 쯤, 바로 오늘 풀게되었다.알고리즘 분류는 브루트 포스지만 나는 그리디 알고리즘이라고 생각한다.  처음 시도때 생각없이 브루트 포스로 모든 경우의 수를 해봤었는데 당연히 시간초과났다. 이번에는 예제를 유심히 보다가 램프 행을 전체적으로 봤을때 똑같은 패턴인 램프 행들이 있었다. 그 패턴들 마다 개수를 저장하고, 개수를 내림차순으로 정렬해서 k번 스위치를 눌렀을 때 가능한지 불가능한지 판별하는 방식으로 짜서 성공했다. 스위치 누름 처리방법가장 많이 나온 패턴이 0001 이라고 하자. 개수는 3개1. 안켜진 상태 즉, 0의 개수를 센다.2. 한 열을 제외한 나머지 0은 다 킨다. (k - 0의 개수 + 1)  (여기서는 01..

🧫 문제 분석 ✔️ 출처햄버거 분배 실버 3 📖 문제 앞의 사람이 가장 왼쪽 즉,  거리가 먼 것 부터 먹어줘야 뒤에 사람이 선택지가 늘어난다. 따라서 앞의 사람이 현재 위치-k ~ 현재 위치 + k 까지 탐색해서  앞쪽에 있는 아직 안먹은 햄버거가 있다면 먹는다.  쉬운 문제인데 이런 유형을 까먹을까봐 기록함으로써 이해한다.  🔅 문제 풀이import java.io.*;import java.util.ArrayList;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedRead..

🧫 문제 분석 ✔️ 출처주유소 실버 3 📖 문제 그리드(탐욕법) 문제로 매우 간단하다. 근데 가끔식 주어진 입력의 크기를 제대로 안봐서 놓치는 경우가 허다하다.  항상 지금 쓰려는 자료형이 적합한지 생각해야한다. 여기서는 리터랑 가격이 최대 10억, 도시 거리가 최대 10억이므로 long 타입으로 계산해주는것이 좋다.  주유소 가격의 최솟값을 도시를 지날때마다 갱신하면서구한 최솟값 * 거리 로 비용을 구한다.  예제 1번을 보면 처음 도시에서는 무조건 충전해야하므로 다음 도시까지 이동하는 최소한의 기름만 충전한다.2L충전 (5 * 2원) 다음 도시에서 이전 도시와 기름값을 비교해서 더 작다면 최솟값을 바꾸고 다음 거리만큼 주유한다.3L(2 * 3) 그 다음 도시에서는 이전 도시보다 비싸므로 이전 도시..

🧫 문제 분석 ✔️ 출처20207번 달력 골드 5 📖 문제 열 : 365 + 2 (1부터 365까지, 그리고 마지막에 값이 남은채로 계산되는 거 방지용)행 : 중복 일정 가능성 1000개높이 배열 하나 생성 입력 값은 시작 날짜가 빠른 순, 같다면 길이가 긴 순으로 오름차 정렬→ 근데 시작 날짜가 빠른 순으로 해도 된다. 일정에 각 날짜 기간 저장, 중복이라면 현재 행 + 1에 날짜 기간 저장0 행에는 중첩 날짜를 이어서 저장높이 배열에는 각 날짜의 높이 최댓값을 저장 그리고 0행의 일정을 쭉 탐색해서 길이를 구하고 최대 높이를 구한다음 길이 * 높이를 더해 코팅지 면적을 구한다. 🔅 문제 풀이import java.io.*;import java.util.*;public class Main { ..

🧫 문제 분석 ✔️ 출처잃어버린 괄호 실버 2 📖 문제 이 문제같은 경우첫번째 수를 저장한 뒤 +가 나오면 더해준다. 그런데 한 번이라도 -가 나오면 그 뒤에 아무리 많은 +가 나와도 처음 나온 - 때문에 이들은 전부 합한 후 -로 빼게 된다. 따라서 한 번이라도 - 가 나오면 저장 한 수에 계속해서 -로 빼주면 된다.  예를 들어 아래의 입력이 주어진다고 하자1+2-4-5+2+3처음 1 +2까지는 더하고 -가 나왔으므로 괄호를 쳐서 최솟값을 만들어야 하기에 - 뒤에 나오는 +로 더해지는 모든 수들을 빼주면 된다.(1 + 2) - 4 - 5 - 2 - 3 = -11(1+2)  -4 - (5 + 2 + 3) =   -11  🔅 문제 풀이import java.io.*;public class Main {..

🧫 문제 분석✔️ 출처회의실 배정 실버 1 📖 문제 정렬 문제로 회의가 끝나는 시간을 기준으로 정렬하되 같다면 시작시간을 오름차순으로 정렬해야한다.주의할 점은 끝나는 시간에 바로 다른 회의가 시작할 수 있다는 것이다.  정렬 후 마지막 회의 시간 보다 다음 회의의 시작시간이 크거나 같으면 이는 가능한 회의이므로 마지막 회의시간을 다음 회의가 끝나는 시간으로 바꾼다.   종료시간이 같다면 시작시간을 오름차순 정렬을 해야하는 이유예를 들어보면41 22 24 42 4 이것을 끝나는 시간으로만 정렬했을 경우입력 순서대로 1 22 24 42 4 이대로 들어왔을 것이고 마지막 회의시간은 2 -> 2-> 4로 되고 2 4 일때 마지막 회의시간 = 4 이기에 이 회의는 무시된다. 따라서 잘못된 답을 내놓게 ..

백준 11047번 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 문제 풀이 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw..