Algorithm69

• 

  시소짝궁 문제 설명 무게 별 시소의 특정지점에 있을 때 평행을 유지할 수 있다. 짝궁을 이룰 수 있는 경우의 수를 구하시오. 시소는 중심으로 부터 2,3,4m 거리 지점에 좌석이 있고 해당 사람 무게 * 지점 == 다른 사람 무게 * 지점 이 같은 경우라면 짝궁을 이룰 수 있다. 생각한 아이디어 이분탐색 → x 최대공약수 → 어차피 n^2 풀이 [자료구조를 이용한 풀이] 맵 2개를 이용해 풀이함. 하나의 map은 [무게, 사람 수]로 구성 또 다른 map은 [2,3,4m 지점의 무게, 원천지] 로 구성 1번에서 중복으로 같은 무게를 가지고 있는 경우 pair를 자기들끼리 이룰 수 있으므로 계산해줌 2번에서는 원천지로 부터 2개 이상을 가지고 있으면 pair를 이룰 수 있으므로 계산 해줌 import java.ut.. Algorithm/프로그래머스 2023. 2. 26.

• 

  호텔 대실 문제 설명 호텔을 운영하는 주인은 최소 객실만을 이용하여 손님을 받으려 한다. 최소 몇개의 객실만을 가지고 운영할 수 있는가 생각한 아이디어 퇴실 시간 기준으로 오름 차순 정렬을 생각했지만 거의 다 틀렸다.. 왜 안돼는지 아시는 분 있으면 알려주세요 :) 풀이 (입실 시간 기준 정렬) public int solution(String[][] book_time) { int answer = 0; String[][] bt=book_time; int n=book_time.length; List times=new ArrayList(); for(int i=0; i Algorithm/프로그래머스 2023. 2. 26.

• 다이나믹 프로그래밍 - LCS, LIS 차이 LCS 가장 긴 공통 부분 수열 (공통적으로 일치하는 수열 중 가장 긴 부분) 유사문제(백준) 편집 거리 (서로 다른 두 단어의 변경 횟수) LIS 가장 긴 증가(또는 감소)하는 수열 어떠한 수열이 주어질 때, 그 수열에서 일부 원소를 뽑아내어 새로 만든 수열을 부분 수열이라고 하며, 이 수열이 오름차순(또는 내림차순)을 유지하면 증가(또는 감소)하는 부분 수열이 되는 것 유사문제(백준) 병사 배치 가장 긴 증가하는 부분 수열 문제 LIS를 n - log n에 구할 수 있지만, 요소를 확인할 수 있는 정확한 답은 아니라는 것을 알아야 한다. 단순한 길이는 n^2 이나 n-logn이랑 같다. Algorithm 2023. 2. 12.

• 백준 - 퇴사 문제 설명 나는 퇴사 전날 까지 많은 수익을 낼것이다. 하루 마다 벌어들일 수 있는 수익과 처리 기간이 주어진다. 이것들을 잘 분배하여 최대 수익을 낼 것이다. 생각한 아이디어 퇴사 n+1날은 일을 할 수 없으니 n일 까지만 일을 할 수 있다. dp[i] =: i 날 부터 시작해서 퇴사 전날까지 벌어들일 수 있는 수익으로 맨 뒤부터 데이터를 채워나갔다. 풀이 static class Node { private int day; private int profit; public Node(int day, int profit) { this.day = day; this.profit = profit; } } public static void main(String[] args) throws IOException { Bu.. Algorithm/백준 2023. 2. 12.

• 백준 - 치즈 문제 설명 공기면과 닿은 치즈는 녹는다. 치즈가 전부 사라지는 시간과 전부 사라지기전 치즈 개수를 구하라 생각한 아이디어 공기면과 맞닿는 치즈인 것을 어떻게 판별 할 수 있을까? 문제 첫줄에 힌트 있음 - > 가장자리는 무조건 적으로 치즈가 존재하지 않음을 의미 가장 자리 부터 탐색에 1이 맞닿는 곳이면 녹을 치즈인 것을 알 수 있다. 풀이 public static int[] solution() { int[] answer = new int[2]; int cheeseCnt = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (map[i][j] == CHEESE) { cheeseCnt++; } } } int hour = 0; int lef.. Algorithm/백준 2023. 2. 12.