CS (26) 썸네일형 리스트형 [Programmers] JOIN > 있었는데요 없었습니다 핵심JOIN 각 동물에 대해 보호 시작일과 입양일을 포함한 테이블을 만든다.SELECT ANIMAL_ID, O.NAME FROM ANIMAL_INS IJOIN ANIMAL_OUTS OUSING (ANIMAL_ID)참고 입양이 되지 않은 경우에는 입양일이 NULL이고 이 경우 비교 연산은 NULL을 반환한다. WHERE 절에서 조건을 평가할 때 연산 결과가 NULL이면, 해당 조건은 false로 간주되어 결과 집합에서 해당 행이 제외된다. 입양 기록만있고 보호 시작일이 없는 상황은 비정상이기 때문에 포함되어야 하지만 이 문제에서는 이런 상황을 다루지 않기 때문에 어떤 JOIN을 사용할지 고려할 필요가 없다. 하지만 문제의 조건에 따라 고려해야할 수 있다. WHERE보호 시작일이 더 빠른지 확인한다. (두 .. [Baekjoon Online Judge] 14719. 빗물 (Java) https://www.acmicpc.net/problem/14719 핵심특정 지점을 기준으로 두 값을 찾는다.1. 해당 지점의 블록 높이2. 해당 지점을 기준으로 왼쪽의 땅에서 가장 높은 블록과 오른쪽 땅에서 가장 높은 블록 중에서 더 낮은 블록을 찾는다. 2번 값이 해당 지점에서 빗물이 최대로 쌓일 수 있는 높이이다.따라서 2번과 1번의 차가 해당 지점에서 쌓일 수 있는 빗물의 최대 높이(만약 이 차가 0 이하라면 빗물이 한 칸도 쌓일 수 없는 상태)+ 양 끝은 빗물이 쌓일 수 없다.구현나는 왼쪽을 기준으로 현재 인덱스까지 지점에서 가장 높은 블록의 높이를 배열에 저장했다. (누적합)e.g. highestFromLeft[10] : 0 ~ 10 지점 중에서 가장 높은 블록의 높이 오른쪽도 똑같이 구한 후.. [Baekjoon Online Judge] 1620. 나는야 포켓몬 마스터 이다솜 https://www.acmicpc.net/problem/1620 핵심N, M은 최대 100,000이다. 배열의 인덱스는 숫자이기 때문에포켓몬 번호가 주어졌을 때 포켓몬 이름을 찾는 것은 배열로 가능하지만포켓몬 이름이 주어졌을 때 포켓몬 번호를 찾는 것은 배열로 불가능하다.그렇다고 일일이 배열을 탐색하면 O(N)의 탐색을 N번 수행하므로 O(N^2)의 시간복잡도가 된다. (시간 초과) 따라서 String으로 O(1)에 탐색이 가능하면서 Key, Value 형태로 데이터를 저장하여 대응하는 포켓몬 번호까지 쉽게 가져올 수 있는 해시 맵을 사용할 것이다. Code (Java)import java.io.BufferedReader;import java.io.InputStreamReader;import java... [Programmers] JOIN > 조건에 맞는 도서와 저자 리스트 출력하기 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 핵심JOIN 문두 개 이상의 테이블을 결합하여 조회합니다. ON 이후의 조건에 맞는 행만 반환합니다.SELECT BOOK_ID, AUTHOR_NAME FROM BOOK BJOIN AUTHOR AON B.AUTHOR_ID = A.AUTHOR_ID BOOK에는 BOOK_ID 속성과 AUTHOR_ID 속성이 있지만 AUTHOR_NAME은 없다.BOOK의 각 행에 포함된 AUTHOR_ID에 대응하는 AUTHOR_NAME을 합치기 위한 쿼리이다. DATE_FORMAT 함수날짜를 지정된 형식으로 변환합니다.SELECT DA.. [Baekjoon Online Judge] 7785. 회사에 있는 사람 (C++, Java) https://www.acmicpc.net/problem/7785 핵심N은 최대 1,000,000이다.leave 로그마다 모든 enter 로그를 일일이 찾는 방법을 사용했을 때,만약 N/2개의 enter 로그가 연달아 나오고 그 다음 N/2개의 leave 로그가 연달아 나온다면N/2개의 enter 로그를 N/2개의 leave 로그에 대해 탐색해야 하므로 O(N^2)의 시간복잡도를 갖는다. (시간초과) 따라서 탐색 시간을 줄여야 한다. 여러 방법이 있는데 나는 해시 자료구조를 사용하는 방법을 사용했다.해시 자료구조의 탐색은 O(1)의 시간복잡도를 갖는다.이를 활용하면 앞선 상황에서 O(N)의 시간복잡도를 갖는다.Code (C++) with std::unordered_set#include #include u.. [Baekjoon Online Judge] 1806. 부분합 (C++, Java) 핵심가장 단순한 방법인 3중 반복문을 이용하는 방법은 O(N^3) (시간초과) 누적합과 투 포인터 알고리즘에 대해 알고 있다면 쉽게 떠올릴 수 있다.이 두 개념을 활용하면 시간복잡도가 O(N)으로 줄어든다. 두 포인터가 부분 수열의 양 끝을 가리키고 (부분 수열의 합이 S보다 커야한다는) 조건에 맞게 포인터를 조절한다. 앞 인덱스가 뒷 인덱스를 역전할 때까지 반복부분 수열의 합이 S보다 작다면, 크거나 같아질 때까지 뒷 인덱스를 1 증가시키고 해당 인덱스에 해당하는 원소를 추가한다.조건에 부합하는 최소 부분 수열의 길이를 갱신한다.부분 수열의 합이 S보다 크거나 같다면, 앞 인덱스에 해당하는 원소를 빼고 1 증가시킨다.Code (C++)#include using namespace std;#define M.. [Baekjoon Online Judge] 2230. 수 고르기 (C++, Java) https://www.acmicpc.net/problem/2230핵심N은 최대 100,000모든 두 원소의 차를 비교하려면 시간복잡도가 O(N^2)이다. (시간초과)한 원소에 대해 조건에 맞는(차가 M 이상이면서 가장 작은) 원소를 빠르게 찾을 수 있다면, 시간복잡도를 줄일 수 있다.방법 1. 이분 탐색A[i] + M에 대한 Lower Bound는 위 조건에 맞는 원소의 인덱스와 동일하다.이를 모든 i에 대해 찾고 차를 비교하면 된다.시간복잡도는 O(NlogN)방법 2. 투 포인터 알고리즘1. 정렬 후 두 개의 포인터를 시작 지점에 둔다. (i = 0, j = 0)2. 두 원소의 차가 M보다 커지는 지점까지 j를 옮긴다.3. 차가 지금까지의 차 중에서 가장 작다면, 갱신한다.4. i를 1증가 시키고 2~.. [Baekjoon Online Judge] 10815. 숫자 카드 (C++, Java) https://www.acmicpc.net/problem/10815핵심N과 M이 최대 500,000이다. 단순 탐색으로는 N개의 원소와 M개의 원소를 각각 대응시켜 봐야 하므로 시간복잡도 O(NM)이다. (시간초과)따라서 시간복잡도를 낮춰야 한다. 이분 탐색을 활용하면 M개의 각 원소에 대해 각각 O(logN)으로 탐색할 수 있다.전체 시간복잡도는 O(MlogN)으로 줄어든다. Code (C++)#include #include using namespace std;#define MAX_N 500000int arr[MAX_N];int main() { ios::sync_with_stdio(0); cin.tie(0); int N, M, x; cin >> N; for (int i = 0; i > arr[i]; .. 이전 1 2 3 4 다음
