하다보면 늘겠지

📍 문제 설명 두 개의 문자열 A와 B가 주어졌을 때, 문자열 A를 편집하여 문자열 B로 만들고자 합니다. 문자열 A를 편집할 때는 다음의 세 연산 중에서 한 번에 하나씩 선택하여 이용할 수 있습니다. 삽입(Insert): 특정한 위치에 하나의 문자를 삽입합니다. 삭제(Remove): 특정한 위치에 있는 하나의 문자를 삭제합니다. 교체(Replace): 특정한 위치에 있는 하나의 문자를 다른 문자로 교체합니다. 이때 편집 거리란 문자열 A를 편집하여 문자열 B로 만들기 위해 사용한 연산의 수를 의미합니다. 문자열 A를 문자열 B로 만드는 최소 편집 거리를 계산하는 프로그램을 작성하세요. 예를 들어 "sunday"와 "saturday"의 최소 편집 거리는 3입니다. 입력 두 문자열 A와 B가 한줄에 하나씩..

📍 문제 설명 못생긴 수란 오직 2, 3, 5 만을 소인수로 가지는 수를 의미한다. 다시 말해 오직 2, 3, 5를 약수로 가지는 합성수를 의미한다. 1은 못생긴 수라고 가정한다. 따라서 못생긴 수들은 {1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ... } 순으로 이어지게 된다. 이 때, n번째 못생긴 수를 찾는 프로그램을 작성해라. 예를 들어 11번째 못생긴 수는 10이다. 입력조건 첫째 줄에 n이 입력된다.(1

📍 문제 설명 💡 접근 바로 뒤쪽이 아닌 모든 뒤쪽 병사들의 전투력보다 커야한다. 뒤집어서 LIS 알고리즘을 적용해서 최장 증가 부분 수열의 길이를 구하고 병사의 수 - 길이를 해주면 남아있는 병사의 최대 수가 나온다. 👩‍💻 코드 import java.util.*; public class Main { public static void main(String[] args) { Scanner kb = new Scanner(System.in); int n = kb.nextInt(); ArrayList v = new ArrayList(); int[] dp = new int[n]; for(int i = 1; i

📍 문제 설명 💡 접근 i번째 날부터 마지막 날까지 낼 수 있는 최대 이익을 담는 dp 테이블을 선언한다. 상담하는데 걸리는 시간이 기간안에 끝나는지에 따라 처리를 해준다. 기간안에 끝나면 현재의 이익을 과 현재 상담이 끝난 이후 날짜의 이익들을 더한값과 현재까지의 저장되어 있는 최대 이익을 비교하여 큰 값으로 갱신한다. 기간안에 끝나지 않으면 저장되어 있는 최대 이익을 dp 테이블에 담는다. 예를 들어 2일 째의 상담을 하게 되면 6일부터 상담진행이 가능(20+0)하기때문에 현재까지의 최대 이익인 3,4,5일(10+20+15) 상담으로 값을 갱신한다. 👩‍💻 코드 import java.util.*; public class Main { static int maxValue; public static voi..

📍 문제 설명 💡 접근 2번째 행부터 오른쪽 위에서 내려오거나 왼쪽 위에서 내려오는 거리를 기록한다. 마지막 행 중 최댓값 출력 👩‍💻 코드 import java.util.*; public class Main { public static void main(String[] args) { Scanner kb = new Scanner(System.in); int n = kb.nextInt(); int[][] arr = new int[500][500]; for(int i = 0; i < n; i++) { for(int j = 0; j

📍 문제 설명 [문제] n x m 크기의 금광이 있습니다. 금광은 1 x 1 크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어 있습니다. 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작합니다. 맨 처음에는 첫 번째 열의 어느 행에서든 출발할 수 있습니다. 이후에 m - 1번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 합니다. 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램을 작성하세요. [입력 조건] 1. 첫째 줄에 테스트 케이스 T가 입력됩니다. (1

📍 문제 설명 https://programmers.co.kr/learn/courses/30/lessons/60060 코딩테스트 연습 - 가사 검색 programmers.co.kr 💡 접근 ??로 해당하는 부분을 aa, zz로 변경시켜서 그 사이에 있는 문자열들을 더해주면 되는 문제였다. ?로 시작하는 경우도 있기 때문에 뒤집힌 문자열도 따로 리스트에 담아두어서 '?'의 위치에 따라 다른 리스트들을 사용하여 구했음 👩‍💻 코드 import java.util.*; public class Main { public static void main(String[] args) { Scanner kb = new Scanner(System.in); String[] words = {"frodo", "front", "fro..

📍 문제 설명 💡 접근 설치 거리를 중간점으로 지정해놓고 이분탐색 수행하면 된다. 👩‍💻 코드 import java.util.*; public class Main { static int c; public static void main(String[] args) { Scanner kb = new Scanner(System.in); int n = kb.nextInt(); c = kb.nextInt(); int[] arr = new int[n]; for(int i = 0; i < n; i++) { arr[i] = kb.nextInt(); } Arrays.sort(arr); //공유기 설치거리 int answer = 0; //공유기의 설치거리를 중간점으로 지정 int lt = 0; int rt = arr[n-1..

📍 문제 설명 고정점이란, 수열의 원소 중에서 그 값이 인덱스와 동일한 원소를 의미한다. 예를 들어 수열 a = [-15, -4, 2, 8, 13]이 있을 때, a[2] = 2이므로, 고정점은 2가 된다. 하나의 수열이 N개의 서로 다른 원소를 포함하고 있으며, 모든 원소가 오름차순으로 정렬되어 있다. 이 때 이 수열에서 고정점이 있다면, 고정점을 출력하는 프로그램을 작성해라. 고정점은 최대 1개만 존재한다. 만약 고정점이 없다면 -1을 출력한다. 단, 이 문제는 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 '시간 초과' 판정을 받는다. 입력조건 첫째 줄에 N이 입력된다.(1 −109109 109109) 출력조건 고정점을 출력한다. 고정점이 없다면 -1을 출력한다. 입력예시 5 -15 -6 ..

📍 문제 설명 N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 x가 등장하는 횟수를 계산하세요. 단, 이 문제의 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 '시간 초과' 판정을 받습니다. 입력예시 7 2 1 1 2 2 2 2 3 출력예시 4 💡 접근 이분탐색을 2번 사용해야한다. x가 처음으로 나오는 부분의 인덱스와 x가 마지막으로 나오는 부분의 인덱스를 구해야함 lt = 0 rt = 7 mid = 3 arr[mid] = 2 >= 2 이므로 rt = mid; lt = 0 rt = 3 mid = 1 arr[mid] = 1 = 2 이므로 rt = mid; 해당 rt가..