백엔드 개발자로 가는길

백준 15681 / 트리와 쿼리골드5구현 방법구현 방법은 루트 노드에서 시작해서 dfs를 이용해 자식노드들을 모두 방문하면서 노드 수를 지속적으로 더하면서 구현했습니다.이렇게 하면 모든 노드 방문이 끝남과 동시에 각 노드를 루트로 하는 서브 트리의 정점 수를 알 수 있게 됩니다.따라서 현재 문제의 노드 수(N), 쿼리 수(Q)의 범위가(2 ≤ N ≤ 10^5, 1 ≤ Q ≤ 10^5) 커도 O(N + Q)의 시간복잡도로 해결 가능합니다.구현 방법은 쉬운편인데 이 아이디어를 생각하는게 꽤 어려웠습니다. 아마 트리 특징에 익숙하지 않아서 그런것 같습니다.트리 특징사이클이 존재 하지 않습니다.(임의의 두 정점 U와 V에 대해, U에서 V로 가는 최단경로는 유일)간선수 = 노드수 - 1아무 정점이나 잡고 부모와..

백준 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; // 자기보다 큰수의 개수 ..

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

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

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

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

https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 골드2 구현 방법 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이므로 DP로 풀 경우 O(n^2)의 시간복잡도를 가지므로 런타임 에러가 발생한다. 따라서 이 문제의 경우, 이분 탐색으로 구현해야 한다. 하지만 여기서 이해가 안되는 부분이 생겼다. 예를 들어서 5 6 2 7이라는 수열이 있다고 하자. 이 경우 이분 탐색으로 구현 하면 순서는 다음과 같다. 1. 5 2. 5 6 3. 2 6 ..

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 실버 2 구현 방법 처음에 보고 재귀로 풀어야 겠다는 생각이 들어서 바로 풀었지만 시간 초과가 났다. 생각해보니 문제는 조합을 의도한거였는데 순열로 풀어서 시간 초과가 난거였다. 구현 자체는 간단하다. 1. n명의 사람들 중 반을 조합으로 선택한다. 2. 조합으로 선택된 사람들의 능력치를 구한다 3. 차이값을 계산하여 최소값인 경우 저장한다. 코드 import java.io.BufferedReader; import j..

https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 골드 4 구현 방법 구현 문제라서 문제부터 간단하게 요약했다. plate -> r * c 공기청정기 = 1번열(c) 설치, 두행(r) 차지한다 미세먼지 양 = A(r, c) a. 미세먼지 모든칸 동시에 확산, 네방향으로 인접한 방향에 공기청정기 있거나 칸없으면 확산 x 확산 양 : a(r,c) / 5 소수점 버리기 (r,c)에 남은 양 : a(r, c) - a(r,c)/5 * (확산 방향 개수)..