본문 바로가기

전체 글262

[알고리즘 문제] 백준14719 - 빗물 www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치� www.acmicpc.net 예전에 모 회사 코딩테스트에 나왔던 문제인데 그떄 못풀었습니다. 어떻게풀까 고민만 하다가 끝난 문제... 해결방법은 각열에 빗방울을 떨어뜨려보면서 넘치지 않으면 정답에 더해주었습니다. 여기서 넘치지 않는것을 검사하는 방법은 각 열의 좌우로 빗방울의 높이보다 같거나 더 높은 벽이 있으면 됩니다. 그리고 빗방울을 하나씩 더해주는 것보다 각 열에서 높이가 넘치지 않을 정도의 최대높이부터 하나씩 빼.. 2020. 9. 9.
[알고리즘 문제] 백준3055 - 탈출 www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제�� www.acmicpc.net 물을 먼저 퍼뜨리고 이후에 고슴도치를 움직이는 방식으로 풀 수 있습니다. 그리고 고슴도치의 중복동선과 최단시간은 visited[][]로 관리할 수 있습니다. 전형적인 bfs문제입니다. #include #include using namespace std; int height, width; pair des, start; queue mole, water; int visited[50][50]; string map[50]; in.. 2020. 9. 8.
[알고리즘 문제] 백준15686 - 치킨 배달 www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 치킨 가게중 M개를 선정하고 모두 선정했다면 각 집에서 치킨집과의 최단 거리를 구합니다. 여기서 M개의 가게를 선정할 때는 재귀를 사용하였고 선정한 가게는 visited[]에 체크해 주었습니다. #include #include #include #include using namespace std; const int MAX = 51; vector ck; vector homes; vector c.. 2020. 9. 8.
[알고리즘 문제] 백준1034 - 램프 www.acmicpc.net/problem/1034 1034번: 램프 첫째 줄에 N과 M이 주어진다. N은 행의 개수이고, M은 열의 개수이다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 램프의 상태가 주어진다. 1이 켜져있는 상태이고, 0이 꺼져� www.acmicpc.net 처음에 재귀로 풀었다가 시간초과가 나왔습니다. 재귀를 이용해서 몇가지 방법으로 풀어봤는데 계속 시간초과가 나와서 다른 사람의 풀이를 참고하였습니다. 문제에서 구하는 값은 모든 열이 켜져있는 행의 최대개수를 구하는 문제입니다. 여기서 중요한 것은 모든 열이 켜져있어야 합니다. 대신에 키고/끄고할 수 있는 기준은 "열"입니다. 여기서 생각해볼 수 있는 점은 1행의 전구패턴과 2행의 전구패턴이 같다면 1행의.. 2020. 9. 6.
[데이터베이스] select문의 실행 순서 이번시간에는 select문이 내부적으로 어떤 순서로 실행되는지 알아보겠습니다. select - 5 from - 1where - 2group by - 3having - 4order by - 6 1. from여기 적혀있는 테이블이 정말 존재하는 테이블인지 확인하고 select권한이 있는지도 확인합니다. select 권한이 없는데 select문을 날린 경우 db가 뱉는 에러가 semantic error이며 syntax erro는 오타, 쉼표가 있어야 하는 곳에 쉼표가 없는 경우 내뱉는 에러입니다. 그래서 from절을 체크해서 어떤 테이블을 액세스를 해야되는지를 확인합니다. 2. where어떤 조건들이 있는지 확인하고 테이블에서 이 조건에 맞는 로우들을 가져옵니다. 3. group by내가 가져온 로우들을 어떤.. 2020. 9. 5.
[데이터베이스] 뷰(View) 뷰(View)는 select문을 저장한 객체라고 할 수 있습니다. 데이터베이스 존재하는 일종의 가상 테이블을 의미하며 실제 테이블처럼 행과 열을 가지고 있지만, 실제로 데이터를 저장하고 있지는 않습니다. 본래 데이터베이스 객체로 등록할 수 없는 SELECT 명령을 객체로서 이름을 붙여 관리할 수 있도록 한 것이 뷰 입니다. 따라서 뷰를 참조하면 그에 정의된 SELECT명령의 실행결과를 테이블처럼 사용할 수 있습니다. 나중에 사용자가 뷰를 사용하게 되면 마치 뷰가 기본 테이블인 것 같이 만들어 제공합니다. 따라서 뷰는 실행 시간에만 구체화되는 특수한 테이블 입니다. 1. 뷰의 생성 create view 뷰이름[원하는 속성] as select문 [with check option]; // []는 있어도 되고 .. 2020. 9. 5.
[알고리즘 문제] 백준14500 - 티트로미노 www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변� www.acmicpc.net 문제 해결의 핵심은, 각 map[y[x]를 돌면서 depth가 4만큼 dfs를 돌면 해결할 수 있습니다. 'ㅗ'모양을 제외하고는 dfs로 모양을 만들 수 있습니다. 이떄의 모양은 각 테트로미노가 회전/좌우반전의 모양을 모두 포함합니다. 그리고 'ㅗ'모양은 dfs로 나올 수 없는데 이 부분은 직접 구해주어야 합니다. #include #include using namespace std; const int MAX .. 2020. 9. 4.
[데이터베이스] 병행 제어(Concurrency Control) 병행제어란 여러개의 트랜잭션이 실행될 때 트랜잭션들이 데이터베이스의 일관성을 파괴하지 않고 다른 트랜잭션에 영향을 주지 않으면서 트랜잭션을 제어하는 것을 의미합니다. 병행제어의 목적은 데이터 베이스의 공유와 시스템 활용도의 최대화, 데이터 베이스의 일관성 유지, 사용자에 대한 응답시간을 최소화하는데 있습니다. 트랜잭션이 동시에 실행되면 ? Dirty Write 같은 데이터에 대해 동시에 두 개 이상의 트랜잭션이 값을 바꾸고자 할 때 발생되는 현상 Dirty Read 아직 종료(commit)되지 않은 트랜잭션의 쓰기 내용을 읽는 것으로 비정상적 상태의 데이터를 읽게 되는 현상 Non-repeatable Read 어떤 트랜잭션에서 동일한 데이터의 값을 매번 읽을 때 마다 틀려지는 현상 Phantom Read.. 2020. 9. 4.
[데이터베이스] 회복(Recovery) 데이터베이스의 회복이란 트랜잭션들을 수행하는 도중 장애로 인해 손상된 데이터베이스를 손상되기 이전의 정상적인 상태로 복구시키는 작업을 말합니다. 장애의 원인으로는 디스크 붕괴, 전원 고장으로 인한 하드웨어 결함, 소프트웨어의 논리 오류로 인한 소프트웨어 경함, 사람의 실수 등 여러가지가 있습니다. 이와 같은 원인으로 발생되는 장애는 다음과 같이 크게 3가지 유형으로 구분할 수 있으며 이러한 장애에 대한 회복을 위해 DBMS는 회복 관리(recovery manager)자를 두고 대비하고 있습니다. 1. 트랜잭션 장애트랜잭션 내의 논리적 오류나 내부 조건 즉, 입력 데이터의 불량, 데이터의 불명, 시스템 자원의 과다 사용 요구 등으로 정상적인 실행을 계속할 수 없는 상태 2. 시스템 장애하드웨어의 오동작으로.. 2020. 9. 3.

티스토리툴바