백엔드 개발자로 가는길

백준 1477 휴게소 세우기골드4구현 방법처음에 그리디 방식으로 생각했다.가장 긴 구간대를 꺼내 반으로 나누는 것을 반복하면 될거라고 생각했으나, 이 경우 최댓값의 최소값 조건을 만족하 못하는 경우가 발생했다.예를 들어, 구간이 300 140이고 두번 나눌 수 있다고 했을 때 150, 150, 140 -> 75, 75, 150, 140으로 150이 된다.하지만 실제로 300을 두번 나누어 100, 100, 100, 140이 되기 때문에 140이 될 수 있다.세울 수 있는 휴게소의 범위 1 - 100, 도로 길이의 범위 100 - 1000으로 범위가 작다. 또한 만족하는 최댓값의 최소값을 구해라고 했다.정리하면 범위 내에서 가능한 모든 경우를 고려하여 최솟값을 구해야한다. 하지만 모든 범위를 하나하나 탐색..

자바 - 백준 2617 / 구슬 찾기골드4구현 방법중간값이 될 수 없는 조건은 자신보다 크거나 작은 수들이 (전체 수의 개수 / 2)보다 많은 경우가 된다.자신보다 큰 수들을 저장하고, dfs 돌리면서 자신보다 큰 수와 자신보다 작은 수를 저장해서 구하면 답이 나온다!코드import java.util.*;import java.io.*;/** * 백준 2617 * 구슬 찾기 * 골드4 * https://www.acmicpc.net/problem/2617 */public class Boj2617 { static int N; // 구슬 수 static int M; // 확인 수 static List[] l; // 자기보다 큰 수 static int[] big; // 자기보다 큰수의 개수 ..

mysql - 프로그래머스 131537 / 오프라인/온라인 판매 데이터 통합하기lv4구현 방법두 테이블의 데이터를 한번에 볼 수 있도록 묻는 문제였다. 문제를 보고 한쪽 테이블에는 없는 칼럼이 있는걸 보고 full outer join 사용하면 된다고 생각했다.하지만 mysql은 따로 full outer join 기능을 제공하지 않고 있어 union을 사용하여 풀기로 했다.OFFLINE_SALE에는 user_id 칼럼이 없으므로 이를 null로 줘서 칼럼수를 맞추고 union 하여 풀었다.코드 select DATE_FORMAT(SALES_DATE, "%Y-%m-%d") as SALES_DATE, PRODUCT_ID, USER_ID, SALES_AMOU..

자바 - 백준 7662 / 이중 우선순위 큐골드4구현 방법연산의 범위가 최대 1,000,000이내 이고, 이런 테스트 케이스가 여러개 나옵니다.따라서 최댓값과 최솟값을 항상 관리하면서 연산을 수행하는 것이 좋다고 판단했습니다.방법은 첫번째로 우선순위 큐 두개를 이용하여 최댓값 최소값을 값을 삽입할 때마다 최신 상태로 유지하는것 입니다. 이러면 삽입 때마다 O(log n)의 시간복잡도가 걸립니다.두번째로 두 우선순위큐를 동기화 시키며 일관성을 유지해야 합니다. 여기서 처음에 잘못 생각했습니다.잘못된 방법최댓값, 최솟값을 삭제할 때마다 min, max에 가장 최근에 삭제한 값을 저장해 놓았습니다.이렇게 한 뒤 최댓값이나 최솟값을 삭제할 때마다 min, max와 비교하여 값이 같거나 큰 경우 삭제를 못하도록 ..

프로그래머스 299310 / 연도별 대장균 크기의 편차 구하기lv2구현 방법2가지 방법으로 풀었습니다.서브 쿼리,left join 방법over, partition by 방법배운 점윈도우 함수레코드 간의 연산을 처리하기 위한 함수참고 : 집계함수 - 칼럼 단위 연산 처리(그룹화)over : 윈도우 함수를 정의할 때 사용하는 구문, 함수가 적용될 데이터의 범위를 지정partiton by : 특정 컬럼의 값에 따라 그룹으로 나누는 데 사용됩니다.SQL 쿼리의 실행 순서FROM, JOIN: 테이블과 조인을 결합.WHERE: 조건을 만족하는 행을 필터링.GROUP BY: 그룹화.HAVING: 그룹화된 데이터에 조건을 적용.SELECT: 필요한 컬럼을 선택하고 별칭을 적용.ORDER BY: 최종 결과 정렬.LIMI..

자바 - 백준 16928 / 뱀과 사다리 게임골드5구현 방법제가 초반에 많은 틀린 이유는 크게 두가지가 있었는데요.첫번째로 현재 위치에서 갈 수 있는 조건은 세가지 중 하나인데 여러 경우로 생각했습니다.예를 들어 현재 위치에 사다리나 뱀이 연결되어 있다면 그것만 가능한데. 그거 외로 그냥 주사위를 돌려 갈 수 있다고 착각을 했습니다. 두번째로 깊이우선 탐색으로 했습니다. 해당으로 구현하면 시간초과가 납니다. 이유는 간단합니다.깊이 우선으로 탐색할 경우 모든 경우를 전부 탐색해야 가장 최소값을 알 수 있기 때문입니다. 따라서 이 문제는 넓이 우선 탐색으로 구현해야 합니다. 이렇게 구현 한다면 최초로 나오는 100이 최솟값이 되기 때문입니다.왜냐하면 같은 주사위를 굴린 횟수(== 같은 깊이)에 대한 위치를 ..

프로그래머스 299308 / 분기별 분화된 대장균의 개체 수 구하기lv2구현 방법ceil을 이용해서 분기를 직접 계산하여 구했다.조건문(case when then else)을 통해 분기를 정해 구했다.quarter 함수를 이용해 분기를 정해 구했다.처음에 2번 방식을 떠올렸지만 코드가 너무 길어져 1번 방식으로 구했습니다.분기 자체를 구하는 내장 함수가 없을까 찾아보니 quarter가 있네요.3번이 가장 간단합니다.코드-- 직접 계산select concat(ceil(month(DIFFERENTIATION_DATE) / 3), 'Q') as 'QUARTER', count(id) as 'ECOLI_COUNT'from ECOLI_DATAgroup by QUARTERorder by ..

백준 15651 N과 M (3)실버3구현 방법1 범위임으로 한 횟수마다 뽑을 숫자를 모두 고려하면 7^7 정도 나옴으로 시간초과는 걱정안해도 됩니다.시간 복잡도 : O((선택 횟수) ^ (뽑을 수 있는 숫자 범위))선택 횟수를 행으로, 뽑을 수 있는 최대 숫자를 열로 하는 이차원 boolean 배열을 만듭니다.재귀를 이용하여 한 재귀당 한 숫자를 뽑아서 이차원 배열에 저장합니다.선택을 다 한 경우 이차원 배열을 통해 출력합니다.이렇게 구현했는데 시간이 좀 느려서 다른 코드를 참조했습니다.제 코드와 비교해 보니 굳이 이차원 배열까지 만들 필요 없었습니다.일차원 배열을 선택 횟수만큼 만들고 선택된 숫자를 넣어서 구현하면 출력시 도는 횟수가 줄어 시간이 좀 더 빨라 졌습니다.코드import java.io.*;..

특정 물고기를 잡은 총 수 구하기LV2구현 방법count, join, in을 이용하여 구현했습니다.join조인 순서를 고려했습니다. 현재 테이블에서 fish_name_info가 fish_info에 비해 작기 때문에 fish_name_info를 먼저 처리 했습니다.inor 이용하여 조건에 만족하는 값을 찾지 않고 in을 이용했습니다.이유는 크게 두가지가 있습니다.인덱스 : 인덱스를 설정한 경우 in을 통해 단일 인덱스 조회가 가능해집니다.간결한 표현코드SELECT COUNT(fi.fish_type) AS "fish_count"FROM fish_name_info fin JOIN fish_info fi ON fi.fish_type = fin.fish_typeWHERE fin..

https://www.acmicpc.net/problem/13397골드4 구현 방법처음에 dfs 이용한 완전탐색 생각했습니다.하지만 배열의 크기가 5000이고 나눌 수 있는 횟수가 5000이라서 최대 2^5000(구간 당 나눈다/안나눈다.)로 시간초과가 날게 뻔했습니다. => 시간복잡도 : O(2^(배열의 길이)) 매개변수 탐색해당 문제는 나눈 구간별 (최댓값 - 최솟값)의 최댓값의 최솟값을 구하는게 목표 입니다.또한 이 최대값의 최솟값 범위는 0 ~ 10000 사이입니다.(배열에 들어있는 수는 1보다 크거나 같고, 10,000보다 작거나 같은 자연수 조건 때문) 따라서 목표값을 기준으로 이분탐색을 진행하면서 해당 목표값을 구간을 나누어서 나올 수 있는 값인지를 판단하면 됩니다. 구간을 나누어서 목표값이..