문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (1 ≤ N < 15) 출력 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. 풀이 퀸은 직선과 대각선으로 이동할수있기때문에 한행에 한개만 존재가능하다. 아래처럼 말이다. 따라서 첫행부터 한행씩 내려가면서 찾는 DFS를 생각을 했다. 따라서 visted[N][N]을 통해 공격가능한곳과 이미 퀸이 놓인자리를 방문 처리할려고 한다. 시간복잡도 상으로는 한행이 진행될때마 한열씩 접근을 못하기때문에 15! 시간복잡도라고 생각을했다. 근데 추가적으로 대각선도 생각을 하면 15!(13..
문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 고른 수열은 오름차순이어야 한다. 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 풀이 문제를 보면 백트래킹 문제인것을 알 수 있다. 시간복잡도를 계산하자면 N까지의 수를 M의 값만큼 반복해서 구해야 하기때문에 O(N^M) 이 된다. 예시를 들자면 1~4까지의 수로 3길이의 수열을 만든다고 생각하면 4x4x4가 ..
관계형 데이터베이스 정규화를 통해 이상 현상을 제거하고 데이터 중복을 피함으로써 데이터 불일치성 문제를 해결한다. 동시성 관리와 병행 제어를 통해 여러 사용자가 동시에 데이터를 공유하고 조작할 수 있다. 메타 데이터를 통해 데이터의 성격, 속성, 표현 방법을 체계화하고 데이터 표준화를 지원한다. 보안 기능을 제공하여 인증된 사용자만이 참조할 수 있도록 한다. 다양한 제약조건을 이용하여 데이터 무결성을 보장하고 오류를 방지합니다. 1970년에 E.F.Codd 박사가 논문에 처음 소개했다. 기존의 파일시스템, 망형(네트워크형 데이터베이스), 계층형 데이터베이스를 대체하는 장점이있다.(데이터 중복제거, 동시성 관리와 병행 제어, 합리적인 테이블 모델링, 보안 기능 제공 등등) DML, DDL, DCL, TCL..
JPA란 ORM(객체 - 관계 자동매핑)중 하나이자 Java Persistence API의 약자로 자바 플랫폼에서 객체와 관계형 데이터베이스를 매핑하고, 객체 지향적인 방식으로 데이터를 영속화 하는 기술이다. 보통 JPA 프레임워크로는 Hibernate를 사용해서 구현한다. ※Hibernate: 자바 언어를 위한 ORM 프레임워크이다. 자바 객체를 통해 데이터베이스가 Oracle, MySql, MSSQL등에 상관없이 다룰수있게 해준다. 이를 통해 개발자는 SQL을 사용하지 않고 메서드 호출만으로 쿼리가 수행된다. JPA구동방식 먼저 persistenc.xml 파일을 조회해서 설정에 맞게 DB를 구상한다. DB에 접근할때 매번 커넥션을 생성해주는 EntityManagerFactory를 생성합니다. Fact..
연산자(Operator) - 연산을 수행하는 기호이다. - 연산을 수행하기 위해선 대상, 바로 '피연산자'가 필요하다. 산술 연산자 산술연산자는 +, -, *, /, %로 이루어져있다. 정수끼리 연산을 하면, 피연산자 중에 long이 있을경우에는 long으로 변환 후 수행, 그 외의 정수는 int로 변환된후 실행된다. 산술 연산자의 오버플로우 오버플로우(Overflow)는 변수가 자신이 표현할 수 있는 범위를 벗어나는 값을 가지게 되는 상항을 말한다. 연산자의 부분에서는 더하기나 곱하기등을 통해 표현할수있는 최대값을 벗어나면 오버플로우가 발생한다. public class Main { public static void main(String[] args) { int a = 1000000; // 1,000,0..
문제 입력 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연결하는 두 노드 중 부모 노드의 번호를 나타내고, 두 번째 정수는 자식 노드를, 세 번째 정수는 간선의 가중치를 나타낸다. 간선에 대한 정보는 부모 노드의 번호가 작은 것이 먼저 입력되고, 부모 노드의 번호가 같으면 자식 노드의 번호가 작은 것이 먼저 입력된다. 루트 노드의 번호는 항상 1이라고 가정하며, 간선의 가중치는 100보다 크지 않은 양의 정수이다. 출력 첫째 줄에 트리의 지름을 출력한다. 풀이 시간복잡도 면에서 주어진 값은 최대 만이고 이중반복문을 돌려도 1억번이라 2초안에 ..
문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 입력 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다. 출력 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. 풀이 시간복잡도 면에서 주어진 수는 10만이다. 따라서 이중for문을..
목표 데이터 모델링 각 성능에 대해 이해하고 학습하기 학습할 것 성능 데이터 모델링의 개요 정규화의 성능 반정규화의 성능 대량 데이터에 따른 성능 데이터베이스 구조와 성능 분산 데이터베이스와 성능 성능 데이터 모델링의 개요 성능 데이터 모델링 DB 성능향상을 위해서 설계단계의 데이터 모델링때부터 정규화, 반정규화, 테이블 통합, 테이블 분할, 조인구조, PK, FK등 여러가지 성능과 관련된 사항이 데이터 모델링에 반영되도록 한다. 데이터 모델은 성능을 튜닝하면서 변경 될 수 있는 특징이 있다. 데이터의 증가가 빠를수록, 성능저하에 따른 성능 개선비용은 증가한다. 분석/ 설계 단계에서 고려한 데이터 모델링을 수행할 경우 성능 저하에 따른 Rework 비용을 최소화 할 수 있는 기회를 갖게된다. 성능을 고려..
목표 자바의 프리미티브 타입 종류와 변수와 배열 선언하는 방법 이해하기 학습할 것 프리미티브 타입 종류와 값의 범위 그리고 기본 값 프리미티브 타입과 레퍼런스 타입 리터럴 변수 선언 및 초기화하는 방법 변수의 스코프와 라이프타임 타입 변환, 캐스팅 그리고 타입 프로모션 1차 및 2차 배열 선언하기 타입 추론, var 프리미티브 타입 자바에는 총 8가지의 프리미티브 타입이있다. 이 표를 보자니 문득 궁금한 점이 있다. 왜 음수가 하나 더 많을까? 사실 양수와 음수 메모리는 동등하고 그렇기에 표현할수 있는 수는 동일하다. 하지만 0을 음수또는 양수 둘중 하나가 처리해야되는과정에서 양수가 담당을 하였다. 따라서 음수가 0을 제외한 수를 하나 더가짐으로써 많아 보일뿐이다. 메모리크기와 값의 범위는 어떤 관계가 ..
문제 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다. X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다. 예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다. ‘()’ 인 괄호열의 값은 2이다. ‘[]’ 인 괄호열의 값은 3이다. ‘(X)’ 의 괄호값은 2×값..
