4Legs_Archives

SQL 실습 사이트 SQL Tryit Editor v1.6 WebSQL stores a Database locally, on the user's computer. Each user gets their own Database object. WebSQL is supported in Chrome, Safari, Opera, and Edge(79). If you use another browser you will still be able to use our Try SQL Editor, but a different ver www.w3schools.com 이 카테고리의 게시글들은 위 사이트의 테이블을 기준으로 작성되었다. SELECT, UPDATE, DELETE SELECT 모든 고객의 정보를 조회 SELECT *..

문제 링크 : www.acmicpc.net/problem/1849 1849번: 순열 1부터 N까지의 수들이 한 번씩 쓰인 수열이 있다. 그 수열에서 i 앞에 있는 수 들 중, i보다 큰 수들의 개수를 A[i]라고 정의하자. A[i]가 주어져 있을 때, 원래 수열을 구하는 프로그램을 작성하여라 www.acmicpc.net 문제 유형 Segment Tree, 누적 합 문제에서 제시된 예제를 풀어보자. 이러한 과정을 통해 모든 수의 빈칸을 채우면 원하는 수열을 구할 수 있다. 하지만 이를 선형 탐색의 형태로 구현한다면 시간복잡도는 O(N^2)가 되므로, 주어진 시간 제한을 만족할 수 없다. 따라서, 각 수가 들어갈 인덱스를 찾는 데 적어도 O(logN) 의 시간복잡도를 가지도록 구현해야 한다. 전체 시간복잡도..

문제 링크 : www.acmicpc.net/problem/1289 1289번: 트리의 가중치 첫째 줄에 트리의 정점의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N-1개의 줄에 대해 각 줄에는 세 개의 정수 A, B, W(1 ≤ A, B ≤ N, 0 ≤ W ≤ 1,000)가 입력되는데 이는 A점과 B점이 연결되어 있고 이 www.acmicpc.net 문제 유형 Tree DP, Math 어떤 한 서브트리에서 나올 수 있는 모든 경로를 구해 보자. 우선 root를 경유하지 않는 경로, 즉 root노드가 경로의 한쪽 끝인 경우이다. 이는 일반적인 재귀를 통해 모두 구할 수 있다. 문제는 root를 경유하는 경로이다. 이를 구하기 위해서는 root로부터 이어진 각 자식들의 서브트리 가중치를 서로 ..

문제 링크 : programmers.co.kr/learn/courses/30/lessons/60062 코딩테스트 연습 - 외벽 점검 레스토랑을 운영하고 있는 스카피는 레스토랑 내부가 너무 낡아 친구들과 함께 직접 리모델링 하기로 했습니다. 레스토랑이 있는 곳은 스노우타운으로 매우 추운 지역이어서 내부 공사를 하는 programmers.co.kr 문제 유형 Brute Force, DFS, 순열 [2020 카카오 블라인드 코딩 테스트] weak의 크기가 15, dist의 크기가 8로 매우 작기 때문에 완전 탐색으로 접근할 수 있는 문제이다. 우선 각 친구들은 반드시 취약 지점에서 출발하는 것이 유리함은 자명하다. 같은 거리를 이동하더라도 반드시 최대의 취약 지점을 지나기 때문이다. (따라서 문제의 4.5 ~..

문제 링크 : programmers.co.kr/learn/courses/30/lessons/60059 코딩테스트 연습 - 자물쇠와 열쇠 [[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true programmers.co.kr 문제 유형 Brute Force, 구현 [2020 카카오 블라인드 코딩 테스트] key와 lock의 크기가 작으므로, 모든 경우를 탐색함으로써 자물쇠를 열 수 있는 경우를 찾아내는 문제이다. key의 일부분만으로 lock을 맞춰도 관계없으므로, key의 가능한 모든 위치를 계산하기 위해 lock을 3배의 크기로 확장하여 구현한다. (코드의 extend_lock) key를 회전하는 함수와, key와 lock의 돌..

문제 링크 : www.acmicpc.net/problem/16225 16225번: 제271회 웰노운컵 첫 줄에 짝수 N(2 ≤ N ≤ 200,000)이 주어진다. 다음 줄에 A[1], ..., A[N], 그 다음 줄에 B[1], ..., B[N]이 (1 ≤ A[i], B[i] ≤ 109) 주어진다. 모든 A[i]는 서로 다르고, 모든 B[i]도 서로 다르다. www.acmicpc.net 문제 유형 Greedy 문제 두 개를 선택했을 때, 항상 상대는 B값이 더 큰 문제를 가져간다 했으므로, 주어진 문제들을 B값의 오름차순으로 정렬해 보자. 정렬 후 알 수 있는 사실은 다음과 같다. 즉, 2k + 1 번까지의 문제 중에서 k + 1 개의 문제를 가져갈 수 있고, 이 때 문제를 어떤 조합으로 고르던 항상 배..

문제 링크 : programmers.co.kr/learn/courses/30/lessons/72416 코딩테스트 연습 - 매출 하락 최소화 CEO를 포함하여 모든 직원은 팀장 또는 팀원이라는 직위를 가지고 있으며 그림에서는 팀장과 팀원의 관계를 화살표로 표시하고 있습니다. 화살표가 시작되는 쪽의 직원은 팀장, 화살표를 받는 programmers.co.kr 문제 유형 Tree DP, Greedy 2021 카카오 블라인드 코딩 테스트의 7번 문제이다. 문제의 '팀장'이 곧 서브트리의 root 노드임을 캐치했다면, 이 문제가 각 서브트리에서 최소 하나의 노드를 선택한 경우의 최소 가중치를 묻는 문제임을 알 수 있다. 단, 이 서브트리는 root와 그 자식 노드로만 이루어져 있다. 백준 2213 트리의 독립집합..

문제 링크 : programmers.co.kr/learn/courses/30/lessons/72415 코딩테스트 연습 - 카드 짝 맞추기 [[1,0,0,3],[2,0,0,0],[0,0,0,2],[3,0,1,0]] 1 0 14 [[3,0,0,2],[0,0,1,0],[0,1,0,0],[2,0,0,3]] 0 1 16 programmers.co.kr 문제 유형 BFS, DFS, Brute Force, 구현 2021 카카오 블라인드 코딩 테스트의 6번 문제이다. 게임판의 크기가 4x4로 매우 작고, 카드의 종류도 6가지이므로 각 카드를 찾는 모든 순서에 대해(완전 탐색) 이동 횟수를 구한 후 이들 중 최솟값을 구하면 된다. 이 풀이에서는 이동 횟수를 구하는 데 BFS를, 카드를 맞추는 순서에 대한 순열을 DFS로..

문제 링크 : programmers.co.kr/learn/courses/30/lessons/72412

문제 링크 : programmers.co.kr/learn/courses/30/lessons/72414 코딩테스트 연습 - 광고 삽입 시간을 나타내는 HH, H1, H2의 범위는 00~99, 분을 나타내는 MM, M1, M2의 범위는 00~59, 초를 나타내는 SS, S1, S2의 범위는 00~59까지 사용됩니다. 잘못된 시각은 입력으로 주어지지 않습니다. (예: 04:60:24, 11 programmers.co.kr 문제 유형 Lazy Propagation ※ 이 풀이에서는 공식 해답과 다르게 Lazy Propagation을 사용하였다. 공식 해답의 풀이는 추후 추가 예정 세그먼트 트리(Segment Tree) : Lazy Propagation [선행 개념 : 세그먼트 트리] 세그먼트 트리(Segment..