해나의 컴공생존기

https://www.acmicpc.net/problem/10989 문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 출력 이는 원래 하던 merge sort로 하면 메모리 초과가 난다. 여기서 힌트로 봐야할 것은 숫자의 중복이 있다는 것과 입력되는 수는 10,000이하라는 것이다. 이 문제의 풀이는 10,000짜리 배열을 만들어서 각 숫자가 몇개 들어왔는지 세고 출력하는 것이다. #include using namespa..

해당 게시글은 건국대학교 컴퓨터공학부 박능수 교수님의 강의와 교재를 참고하여 작성하였습니다. Perfomance 사용자의 목적에 따라 중요하다고 생각하는 컴퓨터의 성능이 다르다. 그래서 기기의 특성마다 다른 성능 척도를 사용한다. 그 중에서도 시간은 컴퓨터 성능의 가장 기본적인 척도이다. 같은 작업을 최단시간에 실행하는 컴퓨터가 가장 빠른 컴퓨터이다. 하지만 무작정 시작시간과 끝시간을 재서 구하면 OS의 오버헤드, 메모리접근 등의 시간이 같이 더해질 것이다. 순수하게 프로그램을 실행하기 위해 걸린 시간을 CPU time이라고 한다. 이는 우리가 실제 느끼는 시간과는 다르다. 성능측정을 위해 여러 용어를 알아보자. clock : 하드웨어 이벤트가 발생하는 시점. clock cycle : 이 클럭의 시간 간..

해당 게시물은 건국대학교 김욱희 교수님의 데이터베이스 강의와 DATABASE SYSTEM CONCEPTS 7th 원서를 참고하여 작성하였습니다. 1. Structure of Relational DB ralational database는 unique 한 이름을 가진 table의 모음으로 이루어져있다. 이는 instruct라는 relation이다. 나와있는대로 각 행을 attributes혹은 columns라고 부르고 각 열을 tuples혹은 rows라고 부른다. relation의 domain이란 attribute와 대응하는 열에 대한 데이터 타입(Data Type)과 길이를 의미한다. 이는 atomic 해야한다. 즉, 값을 둘로 나누거나 할 수 없다는 의미이다. 모든 도메인은 null값을 포함 하고 있다. ..

해당 게시물은 건국대학교 김욱희 교수님의 데이터베이스 강의와 DATABASE SYSTEM CONCEPTS 7th 원서를 참고하여 작성하였습니다. 1. Purpose of DB Systems Data reduncy and inconsistency DB 시스템은 데이터의 중복과 모순을 막아준다. 데이터를 다루다보면 데이터가 중복되는 경우가 있다. 하지만 이는 storage 낭비와 access cost를 증가 시킬수 있다. 또 이는 데이터 모순을 불러올 수 있다. 중복된 데이터들 중 하나의 데이터만 바꿨을 때 중복된 모든 데이터를 수정하기 힘들기 때문이다. Difficulty accessing data 기존 시스템으로는 효율적으로 데이터를 검색하고 분류하기 힘들다. 일반적인 사용을 위해서는 응답성이 높은 데이..

https://www.acmicpc.net/problem/11728 11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거 www.acmicpc.net 문제 정렬되어있는 두 배열 A와 B가 주어진다. 두 배열을 합친 다음 정렬해서 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거나 같은 정수이다. 출력..

문제 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다. 1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 수 있다. CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있다. 사무실에는 벽이 있는데, CCTV는 벽을 통과할 수 없다. CCTV가 감시할 수 없는 영역은 사각지대라고 한다. CCTV는 회전시킬 수 있는데, 회전은 항상 90도 방향으로 해야 하며..

https://www.acmicpc.net/problem/15651 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 풀이 #include using namespace std; int N, M; int check[10]; int num[10]; void NM(int n){ if(n==M){ ..

문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 고른 수열은 오름차순이어야 한다. 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다 풀이 백트래킹에 대한 감이 아직 없는건지 N과M(1)과 비슷한 문제인데 꽤 헤맸다. 하지만 그저 간단하게 for문을 이전 n 값부터 돌리면 되는 거였다. num[n-1]을 위해 num은 index 1부터 사용했다. 몇개 더 풀어봐야할..

문제 N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. 출력 첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다 풀이 백트래킹 문제 너무 어렵다…. 처음에는 연속되는 수열을의 합만 되는줄 알고 풀었다가 틀렸다. 이는 숫자 하나하나 보며 해당 숫자를 더했을때와 더하지 않았을때를 고려한다. 코드 자체는 N과 M 문제보다 쉬운 것 같은데.. 백트래킹 자체가 나한테 잘 안 와..

https://www.acmicpc.net/problem/1992 문제 흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다. 주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다 위 그림에서..