https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 알고리즘 분석 해당 문제는 재귀함수(recursive function)를 사용하는 대표적인 문제이다. 예를 들어 아래와 같은 5x5 matrix 가 주어졌다고 해보자. 아래에서 화살표 표시가 된 곳이 로봇청소기가 처음으로 위치하는 자리가 된다. 그리고 초기에 청소기가 바라보는 방향은 북쪽이라고 가정하자. (빈칸을 0 벽을 1 청소가 된 칸을 2로 가정하자.) 첫 번째로 로봇은 현재위치를 청소할 ..
하드 디스크(HDD)는 비휘발성, 순차 접근이 가능한 컴퓨터의 보조 기억장치이다. 하드디스크에 존재하는 플래터를 회전시켜, 자기 패턴으로 정보를 기록한다. 아래 사진을 보면 HDD 가 어떤식으로 구성되어 있는지 알 수 있다. HDD에는 플래터가 여러 개 있는데, 이 플래터는 각각 따로 회전하는 것이 아니라 모두 함께 같이 회전한다. 다음 그림에서 보듯이 플래터 중심을 중점으로 하는 동심원을 트랙이라고 한다. 그리고 여러 플래터 상의 같은 위치의 트랙(같은 트랙 넘버)을 실린더라고 한다. 이 플래터에 자기 정보를 읽고 쓰는 것을 헤드라고 하는데 플래터 양면에 정보를 기록할 수 있기 때문에 각각의 플래터마다 두 개의 헤드가 있다. 그리고 헤드는 액츄에이터 암의 끝에 달려 있다. (1) Power Connec..
https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 해당 문제는 DFS(Depth-First Search)와 BFS(Breadth-First Search) 알고리즘을 한번에 사용하는 대표적인 문제이다. 해당 문제를 풀기에 앞서 어떤식으로 풀어야할지 계획을 자보자. 1. 벽을 3개 세워줘야함. 2. 벽이 세워진 상태에서 바이러스를 퍼뜨려야함 3. 바이러스가 다 퍼진 map 에서 안전영역을 구해야함. 4. 각 경우마다 안전영역이 최대일때 개수를 출력. 1. 벽을 ..
SQL 이란? SQL은 RDBMS에 저장된 데이터를 쿼리하고 관리할 목적으로 설계된, 관계형 모델을 기반으로 하는 ANSI및 ISO 표준 언어이다. SQL은 영어와 상당히 유사한 구조로 매우 논리적인 형태를 띄고 있다. 다른 많은 프로그램에서 명령 형식의 프로그래밍 다이어그램 방식을 사용하는 것과는 달리 SQL은 선언적 방식을 사용한다. 즉, SQL 에서 얻고자 하는 결과 형태만을 명시하며, 어떻게 이 결과를 얻어내는지에 대해서는 명시하지 않는다. 결과를 어떻게 얻어낼지 판단하는 것은 요구사항을 처리하기 위한 물리적인 방법을 결정하는 RDBMS 의 역할이다. SQL 은 데이터 정의언어 DDL(Data Definitin Language) , 데이터 조작언어 DML(Data Manipulation Langu..
https://www.hackerrank.com/challenges/what-type-of-triangle/problem?isFullScreen=false Type of Triangle | HackerRank Query a triangle's type based on its side lengths. www.hackerrank.com 위와 같이 삼각형의 각 변 A,B,C 와 각 변의 길이가 컬럼으로 존재하는 테이블이 있다. 결과는 Isosceles , Equilateral ,Scalene ,Not A Triangle 넷중 하나가 된다. 해당 단어가 뜻하는 바는 아래와 같다. 1) Not A Triangle : 세 변중 가장 긴 변의 길이가 나머지 두변의 합보다 크거나 같은 경우 2) Equilateral ..
https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 문제를 읽고 위의 예시 그림의 섬의 개수를 세어본다면, 총 3개의 영역으로 나뉘어져 섬의 개수는 3개인것을 알 수 있다. 즉 기준이되는 섬의영역(* 표시) 가 있을때 상하좌우 대각선까지 모두 포함해서 하나의 섬으로 이어질 수 있다는 것이다. (c,r) 순서쌍을 생각하자 c : 행 , r : 열 그럼 현재 (c,r) 을 기준으로 빨간색범위에 있으면 모두 하나의 섬으로 봐준다. 또한 이 문제는 ..
https://www.hackerrank.com/challenges/the-pads/problem The PADS | HackerRank Query the name and abbreviated occupation for each person in OCCUPATIONS. www.hackerrank.com 1) 첫번째 작업 OCCUPATIONS 라는 테이블이 주어져 있고 해당 테이블에는 이름과 직업 컬럼이 존재한다. 이 문제에서 도출해야 하는 결과는 "이름(직업 첫 글자 대문자)" 의 결과로 출력해야 하고 출력 행의 순서는 이름 오름차순이 되어야 한다. 2) 두번째 작업 또한, There are a total of x 직업명 을 출력해야하는데, 현재 테이블에 있는 직업명 자체를 집계화 시켜서 개수를 구한다음..
https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 가장 대표적인 미로탐색 문제의 정석이라고 할 수 있다. 보통 이러한 미로탐색류의 문제들은 BFS(Breadth-First Search) 알고리즘을 사용해서 문제를 해결하는 것이 보통이다. 어떤 식의 로직이 들어가는지 아래에서 살펴보자. 위와 같은 미로가 있을 때, 1행 1열부터 마지막행 마지막열까지 최소 몇번을 이동하는지 카운트하는 문제이다. 최소 경로는 아래의 경로와 같다. 그럼 위의 로직을 어떤 식으로 구현해야 할지 살펴보자..
문제 개요 https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 모든 문제가 다 그런건 아니지만 영역이 분할되어 해당 영역의 개수를 구하는 문제는 일반적으로 DFS(Depth-First Search) 또는 BFS(Breadth-First Search)알고리즘을 사용한다. 위와 같은 matrix 가 존재할 때, 높이들 중에 가장 작은 숫자는 2이고 가장 큰 숫자는 9이다. 숫자가 1~9 일때 물에 잠기는 지점들을 각각 카운트 해서 가장 최대값을 구하는 것이다..
B-TREE 구조 B-TREE 즉, 균형트리 (BALANCED TREE 줄여서 B-TREE)는 '자료구조'에 나오는 범용적으로 사용되는 데이터의 구조다. 이 구조는 주로 인덱스를 표현할 때와 그 외에서도 많이 사용된다. 이름에서 알 수 있듯이 B-TREE는 균형이 잡힌 트리다. NODE / PAGE 노드(NODE)는 트리 구조에서 데이터가 존재하는 공간이다. 즉, 갈라지는 부분의 '마디'를 뜻한다. 1) 루트노드(ROOT NODE) 가장 상위 노드로서 모든 출발은 해당 루트 노드에서 시작된다. 2) 브랜치 노드(BRANCH NODE) 중간노드라는 의미로 루트노드와 리프노드 사이에 징검다리 역할을 수행한다. 3) 리프노드(LEAP NODE) 제일 잎 노드 말단 노드라는 의미로 마지막에 있는 노드를 말한다...
