백엔드 개발자로 가는길

https://school.programmers.co.kr/learn/courses/30/lessons/157340lv3구현 방법case when구문을 사용해서 대여중, 대여 가능 구분했습니다.BETWEEN을 사용해서 2022-10-16이 포함되어 있는지 확인했습니다.MAX 이용해서 해당 car id가 한번이라도 대여중인 경우 대여중만 나오도록 했습니다.(사전적으로 '중'이 '가' 보다 큼)코드SELECT CAR_ID, MAX (CASE WHEN '2022-10-16' BETWEEN START_DATE AND END_DATE THEN '대여중' ELSE '대여 가능' END) AS AVAILABILITYFROM CAR_RENTAL_COMPANY_RENTAL_..

https://www.acmicpc.net/problem/2758골드4구현 방법N = 뽑아야 하는 개수M = 최대 수 1. 완전 탐색 - 시간 초과처음에 현재 뽑은 수의 두배 이상의 수를 선택해야 하기 때문에 재귀를 이용하면 시간 복잡도가 O(n * log m)이라고 착각했다. 하지만 실제 시간 복잡도는 O(m * 2^n)를 가진다. 이분 탐색처럼 반틈만 탐색하는게 아니기 때문이다. 2. 삼중 포문을 사용한 DP1번의 문제점은 같은 계산이 반복적으로 이루어진다는 문제점이 있다.예를 들어서 1에서 재귀가 나누어지면 다음에는 두배인 2부터 2000까지의 재귀가 발생한다.다음 재귀인 2에서 재귀가 나누어지면 다음에는 두배인 4부터 2000까지의 재귀가 발생한다.이 두 경우를 보더라도 4 ~ 2000이 겹치게 ..

https://www.acmicpc.net/problem/1106골드4구현 방법전형적인 DP 유형이라고 생각이 들었습니다. knapsack 유형과 비슷하기도 했기 때문입니다.풀이 방법은 dp 배열을 만들고 채울 수 있는 인원의 비용과 현재 비용을 비교하면서 최소값을 업데이트 하는 방식으로 구현했습니다.점화식dp[현재 인원 + 채울 수 있는 인원] = Math.min(dp[현재 인원 + 채울 수 있는 인원] , dp[현재 인원] + 채울 수 있는 인원 cost) 이때 주의할 점은 목표 인원을 넘더라도 비용이 더 작은 경우를 고려해야 한다는 점 입니다.코드import java.io.*;import java.util.*;/*** 백준 1106* 호텔* 골드4* https://www.acmicpc.net/pro..

https://www.acmicpc.net/problem/16120골드4구현 방법백준 9935 문자열 폭발 문제와 동일하다.문자열 하나하나를 스택에 넣고 4개 이상이 들어오면 PPAP가 맞는지 확인하고 맞으면 P로 바꾸면 된다.코드import java.io.*;/*** 백준 16120* PPAP* 골드4* https://www.acmicpc.net/problem/16120*/public class Boj16120 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String s = b..

https://www.acmicpc.net/problem/2015골드4 구현 방법틀린 접근법1. 모든 누적합을 구해, 원하는 값이 나오면 카운트 => 시간 초과시간 복잡도가 O(n^2)이 되기 때문입니다. 올바른 접근법sum(i) - sum(j - 1) = sum[j ... i]특징을 이용해야 합니다.현재 저희는 목표값 K를 구해야 하기 때문에 sum[i] - sum[j - 1] = K인 값을 구하는게 목표입니다.이 식은 sum[i] - K = sum[j - 1]로 바꿀 수 있습니다.이를 통해 현재까지의 부분합에서 목표값 K를 뺏을 때의 값이 존재하는지 확인하면서 갱신해주는 방법으로 구현하면 O(n)으로 답을 낼 수 있습니다.코드import java.util.*;import java.io.*;/*** 백..

https://www.acmicpc.net/problem/14938골드4구현 방법1. bfs 구현 방법1. 갈수 있는 범위 내에서 bfs 돌면서 지나간 지역을 체크 한다.2. 지나간 지역의 아이템을 다 더한다.3. 최댓값 갱신한다.주의할 점은 bfs 돌 때 방문 체크를 하면 안된다. 이유는 이미 방문한 노드에서 다른 노드로 갈 수 있는 경우가 생기기 때문이다.하지만 이 방법은 노드까지의 최단 경로를 고려하지 않아서 중복된 노드 탐색이 발생하게 된다. 2. 다익스트라 구현 방법항상 최단 경로로 노드를 탐색한다면 노드 탐색의 중복이 발생하지 않게 된다. 코드1. bfsimport java.util.*;import java.io.*;/** * 백준 14938 * 서강그라운드 * 골드 4 * https://ww..

https://www.acmicpc.net/problem/1562골드1 구현 방법길이가 N인 계단수를 구하는 방법은 길이가 (N-1)인 계단수에서 하나의 숫자를 추가해 주면 된다.이때 (N-1)인 계단수의 마지막 수에서  + 1이거나 - 1인 수를 하나 추가하면 만들어진다.그럼 이제 계단수를 구하기 위해 필요한 정보를 알수 있다.계단수 길이, 현재 계단수의 마지막 자리수가 필요하게 된다.하지만 문제 조건에서 0~9 모든 수가 나와야 한다고 했으므로, 현재 만들어진 계단수도 필요하게 된다.또한 완전 탐색할 경우 9^N개의 경우의 수가 나오므로 시간초과 가능성이 매우 높다.따라서 전의 계단수로 현재 계단수를 구하기 때문에 "다이나믹 프로그래밍"을 이용하기로 했다.이때 현재 만들어진 계단수는 비트마스크를 이용..

https://school.programmers.co.kr/learn/courses/30/lessons/131123 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.krLV3구현 방법구해야 하는것이 두가지다.첫번째로 음식 종류별 즐겨찾기가 가장 많은 가게 찾기두번째로 즐겨 찾기가 가장 많은 가게의 정보 출력 첫번째는 group by로 해결하면 된다.두번째는 첫번째로 나온 정보인 food_type과 favorites를 바탕으로 두 정보와 일치하는 가게를 찾아서 출력하면 된다.(서브 쿼리, in 사용)코드-- 즐겨찾기가 가장 많은 식당 정보 출력하기-- https://..

https://www.acmicpc.net/problem/1509골드1구현 방법문자열에 대해 모든 팰린드롬을 구하는 방법은 dp[시작문자 위치][끝 문자 위치]를 사용해서 구했다. https://kdozlo.tistory.com/53이제 dp[시작 문자 위치][끝 문자 위치]를 이용하여 팰린드롬 수로 분할의 개수의 최솟값을 구해야 한다. 처음에 dfs로 하면 되겠다 싶어서 구현했는데 두가지 문제점이 있었다.첫번째로는 끝에서부터 팰린드롬 수인 경우 그 다음을 카운터 하는 방식으로 구현했는데, 이렇게 했을 때 항상 최적의 최소값이 나오지 않는다. 따라서 그리디하게 풀면 안되고 모든 경우를 따져야 한다.두번째 문제는 시간복잡도가 너무 높다. 문자열의 최대 길이가 2500인데 심지어 모든 경우를 따지면 2^25..

백준 2473 / 세 용액골드3구현 방법N개의 용액중에 3개를 선택하여 0에 가장 가까운 세 용액을 출력해야 한다.N의 범위는 최대 5000이기 때문에 완전 탐색하면 시간 초과가 난다.자연스럽게 시간복잡도를 줄일 방법을 찾을 텐데 떠오르는 알고리즘이 이분탐색과 투포인터 두개 였다. 이분탐색이분탐색으로 구현할 경우, 처음과 끝을 기준으로 가운데 탐색을 지속적으로 한다.이러면 두 용액을 고정시켜 놓고 나머지 한 용액을 이분탐색으로 정하는 방식으로 구현 해야한다.이러면 시간복잡도가 O(n^2 * longn)이 된다. 투포인터투포인터로 구현할 경우, 두 포인트가 움직이면서 범위를 조정한다. 자 그러면 한 용액만 고정시켜놓고 구현이 가능해진다이러면 시간복잡도가 O(n * n)으로 이분탐색보다 빠르다.코드impor..