devbelly

문제 www.acmicpc.net/problem/20295 알고리즘 HLD 풀이 $N$개의 가게가 트리 형태로 주어집니다. 가게마다 사탕을 5종류 중 1가지를 팔고 $Q$명의 친구들에게 사탕을 갖다 줄 수 있는지 묻는 문제입니다. 이 문제와 비슷합니다. Milk visits에서는 가게마다 사탕을 2가지 종류 중 1가지를 팔고 있는 것과 마찬가지라고 할 수 있습니다. 이 때는 인접한 노드가 같은 종류의 사탕을 판다면 하나의 집합으로 유니온하는 식으로 풀었습니다. 하지만 현재 문제에서는 5가지 종류가 주어지므로 유니온 파인드 만으로는 구분하기 힘듭니다. 문제를 간단히 하자면 트리 위에 두 정점이 주어졌을 때, 두 정점을 잇는 경로중에서 특정 사탕을 포함하는지를 찾아야 합니다. 비트마스크로 구간마다 어떠한 사..

문제 www.acmicpc.net/problem/15586 알고리즘 union find 풀이 $N$개의 정점으로 이루어진 트리 위에서 쿼리마다 가중치가 $k$이상인 인접한 노드들의 수를 구하는 문제입니다. 이 문제에서는 정점의 수와 쿼리가 5000이어서 각 쿼리마다 dfs를 돌려 수행이 가능했지만 이 문제는 둘 다 10만이므로 각 쿼리마다 dfs를 수행하면 시간 초과가 발생합니다. 경로의 최솟값이 $k$이상인 정점의 갯수는 가중치가 $k$이상인 간선들을 이어 만든 포레스트에서 자신이 속한 포레스트의 크기를 찾는 것과 동일합니다. 자신의 속한 포레스트의 크기를 구하기 위해선 유니온 파인드를 사용해야 하는데, 유니온 한 정점끼리 일관성을 갖기 위해서는 쿼리를 $k$를 기준으로 내림차순 정렬을 해야 합니다. ..

문제 www.acmicpc.net/problem/15591 알고리즘 DFS 풀이 $N$개의 정점이 트리를 이루고 각 엣지마다 가중치가 있을 때, 가중치가 $k$이상으로 이어져 있는 노드의 수를 구하는 문제입니다. $N$과 $Q$의 수가 최대 5000이므로 각 쿼리마다 $dfs$를 수행해도 시간초과가 나지 않습니다. $dfs(here, parent, weight)$를 호출하여 인접한 노드가 가중치 $k$이상으로 이어져 있는지 확인하면 됩니다. 코드 #include #define rep(i, n) for (int i = 0; i < n; ++i) #define REP(i, n) for (int i = 1; i = k && there != prv) { ret += 1; ret += dfs(there, here..

문제 www.acmicpc.net/problem/2613 알고리즘 이분탐색 풀이 $N$개의 구슬을 $M$개로 나눌 때, 각 그룹마다의 합이 가장 큰 것이 최소가 되게 하는 문제입니다. 최대의 최소화. 익숙한 이분탐색의 주제입니다. $solve$함수에서 입력값을 기준으로 $M$개 이하의 그룹을 만들 수 있는지 확인합니다. 딱 $M$개가 아닌 이하도 포함을 하는 이유는 그룹을 새로이 쪼개어 $M$개의 그룹을 만들 수 있기 때문입니다. 코드 #include #define rep(i, n) for (int i = 0; i p) { psum = 0; group += 1;..

데이터를 베이스화 해서 사용하면 효율적으로 정보를 저장하기 위해 여러 개의 테이블로 나누어 정보들을 저장하게 됩니다. 나뉜 테이블을 조합하여 정보를 조회하기 위해 JOIN을 사용합니다. ✔ INNER JOIN 두 테이블에서 ON을 통한 조건절을 통해 특정 RECORD만 조회를 합니다. MEMBER 와 NOTICE 테이블을 예로 들면 아래와 같이 작성가능합니다. SELECT * FROM MEMBER INNER JOIN NOTICE ON MEMBER.ID=NOTICE.WRITER_ID; MEMBER.ID 와 NOTICE.WRIDER_ID 가 같은 정보를 가리키므로 양쪽에 동일한 ID가 있을 때 조회를 합니다. ✔ OUTER JOIN INNER 와 달리 OUTER은 두 집합이 가리키는 벤다이어그램이 있을 때,..

SELECT 절은 다음과 같은 순서로 작성되어야 합니다. SELECT, FROM, WHERE, GROUP BY, HAVING, ORDER BY 작성되는 순서와 다르게 명령을 처리하는 순서는 SELECT가 맨 뒤로 간 순서대로 처리 됩니다. FROM, WHERE, GROUP BY, HAVING, ORDER BY, SELECT 만약 회원별 조회수를 조회하면서 조회수가 2 미만인 레코드만 확인하는 쿼리는 다음과 같이 작성할 수 있습니다. SELECT SUM(HIT) FROM NOTICE WHERE SUM(HIT)

문제 www.acmicpc.net/problem/17026 알고리즘 스택, 정렬 풀이 직각이등변삼각형으로 된 산의 꼭짓점이 주어집니다. 산의 색깔이 같을 때, 구분되는 산의 갯수를 구하는 문제입니다. 산 자체를 관찰하면 조금은 헷갈릴 수 있는 문제입니다. 산을 산의 시작 좌표와 산의 끝 좌표로 치환하여 문제를 풀어 나가야 합니다. 즉 산을 선분으로 치환하면 문제는 $N$개의 선분이 주어질 때, 완전히 겹치는 선분을 제외하고 세는 문제로 바뀌게 됩니다. 바뀌게 된 문제는 시작좌표를 오름차순으로 정렬하되, 시작좌표가 같다면 끝좌표는 내림차순으로 정렬하여 풀면 됩니다. 코드 #include #define rep(i, n) for (int i = 0; i < n; ++i) #define REP(i, n) for..

SELECT를 사용하여 결과집합을 조회하게 되면 만들지 않은 ROWNUM이 자동으로 생기게 됩니다. 왼쪽에 있는 빨간색 사각형이 ROWNUM에 해당하는 부분입니다. SELECT * FROM NOTICE; 상위 5개의 결과만 보기 위해서 다음과 같은 SQL을 사용할 수 있습니다. SELECT * FROM NOTICE WHERE ROWNUM BETWEEN 1 AND 5; 6번째부터 10번째를 조회하려면 위 내용을 응용해 다음과 같이 작성하면 된다고 생각할 수 있습니다. SELECT * FROM NOTICE WHERE ROWNUM BETWEEN 6 AND 10; 하지만 아무것도 출력되지 않았습니다. 왜 이런 현상이 발생할까요? ROWNUM은 결과집합을 만든 후 하나하나 넘버링 하는 것이 아니기 때문입니다. S..