늘로그

보호되어 있는 글입니다.

보호되어 있는 글입니다.

보호되어 있는 글입니다.

문제 난이도 유형 🥇골드 4티어 데이크스트라, 최단 경로, 우선순위 큐 문제 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 128 MB 7417 3813 3063 50.271% 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 하는 게임이다. 서강그라운드에서 1등을 하면 보상으로 치킨을 주는데, 예은이는 단 한번도 치킨을 먹을 수가 없었다. 자신이 치킨을 못 먹는 이유는 실력 때문이 아니라 아이템 운이 없어서라고 생각한 예은이는 낙하산에서 떨어질 때 각 지역에 아이템 들이 몇 개 있는지 알려주는 프로그램을 개발을 하였지만 어디로 낙하해야 자신의 수색 범위 ..

데이터베이스 관리 시스템 아키텍처 쿼리 평가 엔진 쿼리 평가 엔진은 사용자로부터 입력받은 SQL 구문을 분석하여 어떤 순서로 기억장치의 데이터에 접근할지 결정한다. 이때 결정되는 계획을 '실행 계획'이라고 한다. 이러한 실행 계획에 기반을 둬 데이터에 접근하는 방법을 '접근 메서드'라 한다. 쿼리 평가 엔진은 계획을 세우고 실행하는 DBMS의 핵심 기능을 담당하는 모듈이다. 디스크 공간 매니저 DBMS에서 가장 낮은 Layer에서 디스크의 공간을 관리한다. 상위 컴포넌트에서 페이지를 할당하거나 할당 해제, 페이지를 읽거나 쓰는 요청을 받아서 처리한다. 디스크 공간 매니저는 성능을 위해서 페이지들을 최대한 순차적으로 배치한다. 왜냐하면 seek time이나 rotation 지연을 최대한 줄이기 위함이다. ..

문제 난이도 유형 🥇골드 3티어 소수판별, 에라토스테네스의 체, 투 포인터 알고리즘 문제 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 128 MB 29230 12431 8657 41.498% 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다. 3 : 3 (한 가지) 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지) 53 : 5+7+11+13+17 = 53 (두 가지) 하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문..

문제 난이도 유형 🥇골드 4티어 투 포인터 알고리즘 문제 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 0.5 초 128 MB 59814 15970 11186 25.388% 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. 출력 첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다..

일반적인 데이터베이스 개론에서 트랜잭션 개념과 회복 다음 내용이므로 순서대로 공부하는 것을 선호하신다면 데이터베이스 트랜잭션 개념과 회복까지 학습하시면 도움이 될 수 있습니다. 잘못된 부분이 있다면 피드백 부탁드립니다. 들어가기 앞서 이 글을 읽기 전에 이전에 다룬 견고하게 트랜잭션 스케줄(Transaction Schedules) 개념 잡기 를 먼저 읽는 다면 도움이 될 것이다. 일반적으로는 트랜잭션의 병행 수행에 의한 문제를 다루고, 스케줄링을 공부한 이후 병행 제어를 배운다. 하지만 반대로 나는 문제가 생기지 않는 병행 수행을 이해하기 위한 스케줄링에 대한 개념을 먼저 다루었다. 비직렬 스케줄에 따라 여러 트랜잭션을 인터리빙 방식으로 병행 수행한다면 갱신 분실, 모순성, 연쇄 복귀 등의 문제가 일어날..

문제 난이도 유형 🥇골드 5티어 데이크스트라, 최단 경로, 우선 순위 큐 문제 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 0.5 초 128 MB 59634 18383 12030 32.072% N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다. 입력 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 ..

문제 난이도 유형 🥇골드 5티어 BFS, 그래프 탐색 문제 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 256 MB 135198 50338 31779 35.199% 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 ..

문제 난이도 유형 🥇골드 4티어 시뮬레이션, 구현 문제 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 512 MB 26125 14224 9548 53.674% 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1 ×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다. 공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 Ar,c이다. 1초 동안 아래..

문제 난이도 유형 🏅 플래티넘 5티어 큐, BFS, 시뮬레이션 문제 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 256 MB 21220 4462 2703 19.271% 두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다. 호수는 행이 R개, 열이 C개인 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다. 호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다. 아래에는 세 가지 예가 있다. ...XXXXXX..XX.XXX ....XXXX.......XX .....XX.......... ....XXXXXXXXX.XXX .....X..

일반적인 데이터베이스 개론에서 트랜잭션 개념 다음 내용이므로 순서대로 공부하는 것을 선호하신다면 데이터베이스 트랜잭션 개념까지 학습하시면 도움이 될 수 있습니다. 잘못된 부분이 있다면 피드백 부탁드립니다. 들어가기 앞서 트랜잭션의 ACID를 보장하고, 데이터베이스를 모순이 없는 일관된 상태로 유지하기 위해서 DBMS는 회복 기능을 제공한다. 회복이란 장애가 발생했을 때, 데이터베이스를 장애 발생하기 전 일관된 상태로 복구하는 것이다. 장애(failure)의 유형 시스템이 제대로 동작하지 않은 상태를 장애(failure)라고 한다. 가볍게 표만 보고 넘어가 보자. 유형 설명 트랜잭션 장애 의미 트랜잭션 수행 중 오류가 발생하여 정상적으로 수행을 계속 할 수 없는 상태 원인 트랜잭션의 논리적 오류. 잘못된 ..

일반적인 데이터베이스 개론에서 트랜잭션 개념과 회복 다음 내용이므로 순서대로 공부하는 것을 선호하신다면 데이터베이스 트랜잭션 개념과 회복까지 학습하시면 도움이 될 수 있습니다. 잘못된 부분이 있다면 피드백 부탁드립니다. 스케줄이 없는 세상 만약 컴퓨터과학에서 스케줄링이 없었다면 세상은 위와 같을 것이다. 운영체제를 배울 때도 스케줄링은 소중하구나 느꼈는데, 트랜잭션 스케줄링을 공부할 때도 다시 한번 소중함을 느낄 수 있었다. 트랜잭션 스케줄(Transaction Schedules) 이란? 데이터베이스의 일관적인 상태를 유지하기 위해서 동시에 실행되는 트랜잭션(병행 수행)들의 연산 순서를 정하는 것을 의미한다. 연산 순서에 따라서 결과가 달라지기 때문에 병행 수행을 하기 위해서는 스케줄이 중요하다. 병행 ..

문제 난이도 유형 🥇골드 4티어 그래프, 최소 신장 트리, 유니온 파인드 알고리즘 문제 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 128 MB 54980 23231 13075 40.511% 그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오. 최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. 입력 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음..