적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.
크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)
예를 들어, 그림이 아래와 같은 경우에
RRRBB GGBBB BBBRR BBRRR RRRRR
적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)
그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)
둘째 줄부터 N개 줄에는 그림이 주어진다.
출력
적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.
예제 입력 1복사
5 RRRBB GGBBB BBBRR BBRRR RRRRR
예제 출력 1복사
4 3
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static int N;
static int x, y;
static ArrayList<int[]>[] graph;
static boolean[][] visit; // 이미 방문한 정점의 정보를 담을 배열
static Queue<int[]> Q;
static char[][] map;
static int[][] deltas = { { 1, 0 }, { -1, 0 }, { 0, -1 }, { 0, 1 } };
static int c = 0;
static int RG_c = 0;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
N = Integer.parseInt(br.readLine());
map = new char[N][N];
visit = new boolean[N][N];
for (int n = 0; n < N; n++) {
map[n] = br.readLine().toCharArray();
}
graph = new ArrayList[N * N];
for (int i = 0; i < N * N; i++) {
graph[i] = new ArrayList<int[]>();
}
// 인접 그래프 만들기 (=ok)
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
for (int k = 0; k < 4; k++) {
int nr = deltas[k][0] + i;
int nc = deltas[k][1] + j;
int[] n = { nr, nc };
if (nr < 0 || nc < 0 || nr >= N || nc >= N)
continue;
graph[i * N + j].add(n);
}
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (!visit[i][j]) {
int[] p = { i, j };
bfssol(p, true);
c++;
}
}
}
sb.append(c + " ");
visit = new boolean[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (!visit[i][j]) {
int[] p = { i, j };
bfssol(p, false);
RG_c++;
}
}
}
sb.append(RG_c);
System.out.println(sb);
}
private static void bfssol(int[] p, boolean b) {
Q = new LinkedList<int[]>();
// 시작정점을 큐에 넣어줌
Q.add(p);
// 시작정점을 방문했다는 정보 저장
visit[p[0]][p[1]] = true;
// 큐에 정점이 없어질 때까지 반복
while (!Q.isEmpty()) {
// 큐에서 정점을 poll해서 이동함
int[] q = Q.poll();
// 이동한 정점에서 연결된 정점들을 큐에 넣어주고 visit배열에 체크
for (int[] i : graph[q[0] * N + q[1]]) {
if (b) {
if (!visit[i[0]][i[1]] && map[q[0]][q[1]] == map[i[0]][i[1]]) {
Q.add(i);
visit[i[0]][i[1]] = true;
}
} else {
if (!visit[i[0]][i[1]] && ((map[q[0]][q[1]] == 'R' && map[i[0]][i[1]] == 'G')
|| (map[q[0]][q[1]] == 'G' && map[i[0]][i[1]] == 'R')
|| map[q[0]][q[1]] == map[i[0]][i[1]])) {
Q.add(i);
visit[i[0]][i[1]] = true;
}
}
}
}
}
}
시스템으로 구축하고자 하는 업무에 대해 key, 속성, 관계 등을 정확하게 표현, 재사용성이 높음
[] 물리적 데이터 모델링
실제로 데이터베이스에 이식할 수 있도록 성능, 저장 등 물리적인 성격을 고려하여 설계
[] 데이터베이스 스키마 구조 3단계
외부 스키마
개념 스키마
내부 스키마
[] ERD 작성 순서
엔티티를 그린다
엔티티를 적절하게 배치한다
엔티티간 관계를 설정한다
관계명을 기술한다
관계의 참여도를 기술한다
관계의 필수여부를 기술한다
[] 엔티티의 특징
반드시 해당 업무에서 필요하고 관리하고자 하는 정보이어야 한다.
유일한 식별자에 의해 식별이 가능해야 한다.
영속적으로 존재하는 인스턴스의 집합이어야 한다.
엔티티는 업무 프로세스에 의해 이용되어야 한다.
엔티티는 반드시 속성이 있어야 한다.
엔티티는 다른 엔티티와 최소 한 개 이상의 관계가 있어야 한다.
[] 엔티티, 인스턴스, 속성, 속성 값의 관계
한 개의 엔티티는 두 개 이상의 인스턴스의 집합이어야 한다.
한 개의 엔티티는 두 개 이상의 속성을 갖는다.
한 개의 속성은 한 개의 속성 값을 갖는다.
[]속성의 특성에 따른 분류
기본 속성
설계 속성
파생 속성
[] 도메인
각 속성은 가질 수 있는 값의 범위가 있는데 이를 그 속성의 도메인이라하며, 엔티티 내에서 속성에 대한 데이터타입과 크기 그리고 제약사항을 지정하는 것이다.
[] 속성의 명칭 부여
해당 업무에서 사용하는 이름을 부여한다
서술식 속성명은 사용하지 않는다
약어 사용은 가급적 제한한다
전체 데이터모델에서 유일성 확보하는 것이 좋다
ERD에서는 존재적 관계와 행위에 의한 관계를 구분하지 않지만 클래스 다이어그램에서는 이것을 구분하여 연관관계와 의존관계로 표현한다.
[] 관계의 표기법
관계명: 관계의 이름
관계차수: 1:1, 1:M, M:N
관계선택사양: 필수관계, 선택관계
[] 관계 읽기
기준 엔티티를 한 개 또는 각(each)으로 읽는다.
대상 엔티티의 관계참여도 즉 개수를 읽는다.
관계선택사양과 관계명을 읽는다.
[] 식별자의 종류
엔티티 내에서 대표성을 가지는가에따라 주식별자와 보조 식별자로 구분
엔티티 내에서 스스로 생성되었는지 여부에 따라 내부식별자와 외부식별자로 구분
단일 속성으로 식별이 되는가에 따라 단일 식별자와 복합 식별자로 구분
원래 업무적으로 의미가 있던 식별자 속성을 대체하여 일련번호와 같이 새롭게 만든 식별자를 구분하기 위해 본질 식별자와 인조 식별자로 구분
[] 주식별자의 특징
유일성: 주식별자에 의해 엔티티내에 모든 인스턴스들을 유일하게 구분함
최소성: 주식별자를 구성하는 속성의 수는 유일성을 만족하는 최소의 수가 되어야 함
불변성: 주식별자가 한 번 특정 엔티티에 지정되면 그 식별자의 값은 변하지 않아야 함
존재성: 주식별자가 지정되면 반드시 데이터 값이 존재
[] 성능데이터모델링이란
데이터베이스 성능 향상을 목적으로 설계단계의 데이터 모델링 때부터 성능과 관련된 사항이 데이터 모델링에 반영될 수 있도록 하는 것이다.
중복속성에 대한 분리가 1차 정규화의 대상이 되며, 로우단위의 중복도 1차 정규화의 대상이 되지만 칼럼 단위로 중복이 되는 경우도 1차 정규화의 대상이다.
[] 반정규화
정규화된 엔티티, 속성, 관계에 대해 시스템의 성능향상과 개발과 운영의 단순화를 위해 중복, 통합, 분리 등을 수행하는 데이터 모델링의 기법을 의미한다. 반정규화는 데이터를 중복하여 성능을 향상시키기 위한 기법이라고 정의할 수 있고, 좀 더 넓은 의미의 반 정규화는 성능을 향상시키기위해 정규화된 데이터 모델에서 중복, 통합, 분리 등을 수행하는 모든 과정을 의미한다. 데이터 무결성이 깨질 수 있는 위험을 무릅쓰고 데이터를 중복하여 반정규화를 적용하는 이유는 데이터를 조회할 때 디스크 I/O량이 많아서 성능이 저하되거나 경로가 너무 멀어 조인으로 인한 성능 저하가 예상되거나 칼럼을 계산하여 읽을 때 성능이 저하될 것이 예상되는 경우 반정규화를 수행하게 된다.
[] 반정규화 절차
1. 반 정규화 대상조사
범위처리빈도수 조사
대량의 범위 처리 조사
통계성 프로세스 조사
테이블 조인 개수
2. 다른 방법 유도 검토
뷰 테이블
클러스터링 적용
인덱스의 조정
응용애플리케이션
3. 반정규화 적용
테이블 반정규화
속성의 반정규화
관계의 반정규화
[] 반정규화의 대상에 대해 다른 방법으로 처리
지나치게 많은 조인이 걸려 데이터를 조회하는 작업이 기술적으로 어려울 경우 뷰를 사용하면 이를 해결할 수도 있다.
대량의 데이터처리나 부분처리에 의해 성능이 저하되는 경우에 클러스터링을 적용하거나 인덱스를 조정함으로써 성능을 향상시킬 수 있다.
대량의 데이터는 primary key의 성격에 따라 부분적인 테이블로 분리할 수 있다. 즉 파티셔닝 기법이 적용되어 성능 저하를 방지할 수 있다.
응용 애플리케이션에서 로직을 구사하는 방법을 변경함으로써 성능을 향상시킬 수 있다.
[] 슈퍼/서브 타입 데이터 모델의 변환기술
개별로 발생되는 트랜잭션에 대해서는 개별 테이블로 구성
슈퍼타입+서브타입에 대해 발생되는 트랜잭션에 대해서는 슈퍼타입+서브타입 테이블로 구성
전체를 하나로 묶어 트랜잭션이 발생할 때는 하나의 테이블로 구성
[] PK 순서
PK 순서를 결정하는 기준은 인덱스 정렬구조를 이해한 상태에서 인덱스를 효율적으로 이용할 수 있도록 PK 순서를 지정해야 한다. 즉 인덱스의 특징은 여러개의 속성이 하나의 인덱스로 구성되어 있을 때 앞쪽에 위치한 속성의 값이 비교자로 있어야 인덱스가 좋은 효율을 나타낼 수 있다. 앞쪽에 위치한 속성 값이 가급적 '=' 아니면 최소한 범위 'BETWEEN' '<>'가 들어와야 인덱스를 이용할 수 있는 것이다.
int fibo_iter(int n)
{
if( n < 2) return n;
else {
int i, tmp, current = 1, last = 0;
for(i =2; i <= n; i++){
tmp = current;
current += last;
last = tmp;
}
return current;
}
}
사람들이 사물을 정리하는 것과 마찬가지로 프로그램에서도 자료들을 정리하는 여러 가지 구조들이 있는데, 이를 자료 구조라 부른다.
물건을 쌓아 놓는 것
스택
영화관 매표소의 줄
큐
할일 리스트
리스트
영어사전
사전, 탐색구조
지도
그래프
조직도
트리
알고리즘
컴퓨터 프로그램은 자료구조로 표현되고 저장되어있는 자료(data)와 주어진 문제를 처리하는 절차가 필요하다.
이러한 절차는 알고리즘이라고 불린다.
예를 들어 트리의 어떤 노드를 탐색하는 문제가 있을 때, 트리는 자료구조이고, 이 트리 상에서 어떤 노드를 탐색하는 절차를 기술한 것이 알고리즘이다.
알고리즘은 장치가 이해할 수 있는 언어로 기술된 명령어들의 집합으로,
알고리즘을 기술하는 데는 다음과 같은 방법이 있다.
자연어
흐름도(flowchart)
유사 코드(pseudo-code)
프로그래밍 언어
알고리즘이 되기 위한 조건은 다음과 같다.
입력: 0개 이상의 입력이 존재해야 한다.
출력: 1개 이상의 출력이 존재해야 한다.
명백성: 각 명령어의 의미는 모호하지 않고 명확해야 한다.
유한성: 한정된 수의 단계 후에는 반드시 종료되어야 한다.
유효성: 각 명령어들은 실행 가능한 연산이어야 한다.
[1.2] 추상 데이터 타입
데이터: 처리의 대상이 되는 모든 것
데이터 타입: 데이터의 집합과 이러한 데이터에 적용할 수 있는 연산의 집합
추상 데이터 타입: 새로운 데이터 타입을 추상적으로 정의한 것
자료 구조: 추상 데이터 타입을 프로그래밍 언어로 구현한 것
추상 데이터 타입
데이터 타입의 정의가 그 데이터 타입의 구현으로부터 분리된 데이터 타입
즉 데이터 타입을 추상적으로 정의함을 의미
데이터나 연산이 무엇(what)인지는 정의되지만, 데이터나 연산을 어떻게(how) 컴퓨터 상에서 구현할 것인지는 정의되지 않는다.
프로그램에서 추상 데이터 타입이 구현될 때 구현 세부사항은 외부에 알리지 않고 외부와의 인터페이스만을 공개하게 된다. 즉 인터페이스만 정확하게 지켜진다면 추상 데이터 타입이 여러 가지 방법으로 구현될 수 있음을 뜻한다. 이를 통해 전체 프로그램을 변경 가능성이 있는 구현의 세부사항으로부터 보호하는 것이다.
[1.3] 알고리즘의 성능 분석
점점 더 처리해야 할 자료의 양이 많아지므로 효율성의 차이가 더 커지게 되고 사용자들은 빠른 프로그램을 선호하므로 경쟁력을 갖기 위해서는 최선의 효율성을 가져야 한다.
알고리즘의 복잡도 분석 방법
공간 복잡도 : 알고리즘이 사용하는 기억 공간 분석
시간 복잡도 : 알고리즘의 실행 시간 분석
시간 복잡도 : 알고리즘의 절대적인 실행 시간을 나타내는 것이 아니라 알고리즘을 이루고 있는 연산들이 몇 번이나 실행되는 지를 숫자로 표시한다.
시간 복잡도 함수: 입력 갯수 n에 따라 변하는 T(n)으로 표기
빅오 표기법
자료의 개수가 많은 경우 차수가 가장 큰 항이 가장 영향을 크게 미치고 다른 항들은 상대적으로 무시될 수 있다. 따라서 불필요한 정보를 제거해 알고리즘 분석을 쉽게 할 목적으로 시간 복잡도를 표시하는 방법을 빅오(big-oh notation) 표기법이라고 한다.
[ 정의 ]
두개의 함수 f(n)과 g(n)이 주어졌을 때 모든 n>=n(0)에 대하여 |f(n)|<=c|g(n)|을 만족하는 2개의 상수 c와 n(0)가 존재하면 f(n)=O(g(n))이다.
N 개의 막대 기둥이 일렬로 세워져 있다. 기둥들의 폭은 모두 1 m이며 높이는 다를 수 있다. 이 기둥들을 이용하여 양철로 된 창고를 제작하려고 한다. 창고에는 모든 기둥이 들어간다. 이 창고의 지붕을 다음과 같이 만든다.
지붕은 수평 부분과 수직 부분으로 구성되며, 모두 연결되어야 한다.
지붕의 수평 부분은 반드시 어떤 기둥의 윗면과 닿아야 한다.
지붕의 수직 부분은 반드시 어떤 기둥의 옆면과 닿아야 한다.
지붕의 가장자리는 땅에 닿아야 한다.
비가 올 때 물이 고이지 않도록 지붕의 어떤 부분도 오목하게 들어간 부분이 없어야 한다.
그림 1은 창고를 옆에서 본 모습을 그린 것이다. 이 그림에서 굵은 선으로 표시된 부분이 지붕에 해당되고, 지붕과 땅으로 둘러싸인 다각형이 창고를 옆에서 본 모습이다. 이 다각형을 창고 다각형이라고 하자.
그림1 . 기둥과 지붕(굵은 선)의 예
창고 주인은 창고 다각형의 면적이 가장 작은 창고를 만들기를 원한다. 그림 1에서 창고 다각형의 면적은 98 ㎡이고, 이 경우가 가장 작은 창고 다각형이다.
기둥들의 위치와 높이가 주어질 때, 가장 작은 창고 다각형의 면적을 구하는 프로그램을 작성하시오.
입력
첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 빈 칸을 사이에 두고 주어진다. L과 H는 둘 다 1 이상 1,000 이하이다.
출력
첫 줄에 창고 다각형의 면적을 나타내는 정수를 출력한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class BJ_02304 {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int TC = Integer.parseInt(br.readLine());
int result = 0;
int[][] polls = new int[TC][2];
int tallest = Integer.MIN_VALUE;
for (int t = 0; t < TC; t++) {
st = new StringTokenizer(br.readLine(), " ");
polls[t][0] = Integer.parseInt(st.nextToken());
polls[t][1] = Integer.parseInt(st.nextToken());
}
// 기둥을 x 좌표 순서로 정렬
Arrays.sort(polls, (s1, s2) -> Integer.compare(s1[0], s2[0]));
// 기둥의 시작부터 끝까지 탐색하며 높은 기둥이 나올 때마다 높은 기둥수로 tallest 갱신해 result에 +=tallest
for (int i = polls[0][0], k = 0; i <= polls[TC - 1][0]; i++) {
if (polls[k][0] == i) {
if (tallest < polls[k][1]) {
tallest = polls[k][1];
}
k++;
}
result += tallest;
}
if (TC <= 1) {
System.out.println(result);
return;
}
// 뒷부분 처리
//가장 높은 기둥과, 뒤에서부터 탐색한 가장 높은 기둥과의 차이를 빼주기
//차이-> tallest-backtallest
int backtallest = Integer.MIN_VALUE;
int difference = 0;
for (int i = polls[TC - 1][0], k = TC -1 ; i >= polls[0][0]; i--) {
//i갸 기둥을 만났을 때
if (polls[k][0] == i) {
//앞에서부터 체크한 가장 높은 기둥 tallest와 만나면 break
if(tallest == polls[k][1] && polls[k][0] == i) break;
//뒤에서부터 체크한 tallest보다 현재 만난 기둥이 더 높으면 backtallest와 difference 갱신
if (backtallest < polls[k][1]) {
backtallest = polls[k][1];
difference = tallest-backtallest ;
}
//다음 기둥
k--;
}
//차이 빼주기
result -= difference;
}
System.out.println(result);
}
}
높은 기둥이 갱신될 때마다 tallest 변수를 갱신해 poll[0]의 x좌표부터 poll[TC-1] x좌표까지 방문하며 누적 합하고
(line 23~32)
가장 높은 기둥이 tallest를 만날 때까지 뒤에서부터 차이를 갱신하며 누적합에서 차이를 빼주는 방식으로 풀이하였습니다.
