phanre의 tistory

DB의 4가지 특징 1. 실시간 접근성 데이터베이스는 비정형적인 질의에 대해 실시간 처리에 의한 응답이 가능해야 합니다. 2. 지속적인 변화 데이터베이스의 상태는 동적으로, 즉 새로운 데이터의 삽입, 삭제, 갱신으로 항상 최신의 데이터를 유지해야 합니다. 3. 동시 공용 데이터베이스는 서로 다른 목적을 가진 여러 사용자들을 위한 것이므로, 다수의 사용자가 동시에 같은 내용의 데이터를 이용할 수 있어야 합니다. 4. 내용에 의한 참조 데이터베이스에 있는 데이터를 참조할 때, 데이터 레코드의 주소나 위치에 의해서가 아니라, 사용자가 요구하는 데이터 내용으로 찾아야 합니다. SQL 4가지 데이터 언어 1. DDL (Data Definition Language) 데이터베이스 구조를 정의, 수정, 삭제하는 언어입..

https://www.acmicpc.net/problem/3221 3221번: 개미의 이동 첫째 줄에 줄의 길이 L과 T가 주어진다. (2 ≤ L ≤ 200,000, 1 ≤ T ≤ 1,000,000) T의 단위는 초이다. 둘째 줄에는 개미의 수 N이 주어진다. (1 ≤ N ≤ 70,000, N < L) 다음 N개 줄에는 개미의 처음 위치 (줄의 www.acmicpc.net 개미 여러마리가 일직선상을 이동하는데 서로 부딪히거나 벽에 부딪히면 방향을 바꿉니다. 1초 마다 1씩 이동하는데 T초 후의 개미의 위치를 파악하는 문제입니다. 처음에는 개미끼리 부딪힐 때 어떻게 처리를 해야하나 고민했으나 생각해보니 개미끼리 부딪힐 경우 부딪힌 다른 개미가 이동하는 방향으로 움직였습니다. 여기까지는 금방 생각하였으나 개..

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 구현 문제입니다. 정사각형 네칸으로 만든 테트로미노의 모양으로 탐색을 하여 answer값을 max로 만드는 문제입니다. 우선 처음에 모든 테트로미노가 네칸이므로 dy, dx 배열을 만들어 만들어질 수 있는 경우의 수를 DFS로 탐색하였습니다. DFS로 네 방향 모두 탐색을 하며 탐색을 시작할 때 visit 배열의 값을 1로 만들어 중복을 피하고 탐색이 끝난 경우 visit을 다시 0으로 전환하여 ..

https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 간단한 BFS를 이용하는 문제입니다. arr 배열에 영역의 정보를 저장하고 이미 탐색한 지역인지를 확인하는 visit 배열을 만듭니다. 이후 arr 전체 탐색을 하며 arr[i][j] == 0인 경우 queue에 넣은 뒤 visit을 1로 하고 s값을 0으로 세팅합니다. BFS로 탐색하여 arr 정보가 0이고 visit 정보가 0인 경우 queue에 추가하고 visit을 1로 ..

https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 주어진 조건에 맞게 구현하는 문제입니다. 같은 색깔이 4개 이상 확인 하는 코드를 Check 함수로 만들었고 Check한 원소들을 '.'으로 바꿔주는 코드를 Pop 함수로 만들었고 빈칸을 채우는 코드를 Gravity로 만들었습니다. 우선 Check 함수에서는 DFS로 탐색하며 같은 색깔의 원소를 q라는 배열에 담아둡니다. 이후 함수가 종료되면 q 배열을 Puyo라는 dic..

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net DFS를 이용하여 4칸 탐색을 하면 T자 모양 테트로미노 제외한 모든 모양을 확인할 수 있다. DFS를 이용해 T자 제외 테트로미노의 최대합을 max함수를 이용하여 전역변수 answer에 저장해둔 후 T자 테트로미노를 탐색하여 answer의 최댓값을 조정한다. 이후에 answer값을 출력하면 된다. DFS를 이용할 때는 중복 체크를 위해 함수 시작부분에 visit[y][x] = 1을 하였고 다른 ..

https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 누적합을 이용하지 않으면 시간초과가 나는 문제이다. 처음에 1 2 3 4 5 를 받는다면 누적합을 구하여 1 3 6 10 15 를 배열에 저장한다 이후 포인터를 두개 생성하여 왼쪽 포인터는 0, 오른쪽 포인터는 1을 가리키게 한다. 그리고 오른쪽 포인터가 가리키는 누적합에서 왼쪽 포인터가 가리키는 누적합을 빼면 사이의 합이 구해진다. 이 방식으로 왼쪽 포인터가 배열의 크기를 넘어가지..

https://www.acmicpc.net/problem/17499 17499번: 수열과 시프트 쿼리 첫 번째 줄에 Q개의 연산을 차례대로 수행한 후 a1, a2, …, aN 을 공백을 사이에 두고 출력합니다. www.acmicpc.net 주어진 쿼리에 맞게 배열에 더하기를 하거나 시프트를 하는 문제이다. 단순 append, pop을 이용하면 시간초과가 나오므로 포인터를 활용해야 한다. 처음 p를 index 0으로 잡고 오른쪽으로 시프트하면 -, 왼쪽으로 시프트하면 + 하고 그 p값을 배열의 첫번째 인덱스라고 생각하고 더하고, 프린트하면 된다. 처음에 시간초과가 떠서 문제를 확인해보니 input에서 시간을 너무 잡아먹는 것 같아 sys 라이브러리의 sys.stdin.readline을 이용해서 input에..

https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 투 포인터를 이용하는 문제이다. 첫번째 인덱스와 마지막 인덱스를 가리키는 포인터를 두개 만들고 조건에 따라 포인터를 옮겨주면 된다. 오름차순으로 입력이 주어지기 때문에 포인터끼리의 합이 음수이면 왼쪽 포인터를 오른쪽으로 한칸 옮기고, 포인터값이 양수이면 오른쪽 포인터를 왼쪽으로 한칸 옮기면 된다. 그리고 포인터가 가리키는 값끼리의 합의 절대값을 min값과 비교하여 더 작다면 변경해준다. 이를..

https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net BFS로 (0,0)에서 시작하여 (n-1, m-1)에 도착할 때 까지 K개 이하의 벽을 부수고 진행하면 된다. vst, brk 배열을 생성하여 각각 이동 블록 개수와 부순 벽 개수를 저장하고 brk가 k를 넘으면 멈추게 한다. 시간을 줄이기 위해 이동할 블록이 현재 블록보다 부순 벽 개수가 적고 이동 거리도 적으면 탐색하지 않도록 하였다. import sys f..