Brute Force (완전 탐색)문제의 해가 될 수 있는 모든 경우의 수를 탐색하는 방식문제를 푸는데 있어, 그 문제의 해가 될 수 있는 모든 경우의 수를 파악하는건 매우 중요하다. 필자는 문제를 풀 때 먼저 완전 탐색으로 풀 수 있는지 확인하고, 모든 경우의 수를 머릿속으로 생각하는 편이다. 만약 완전 탐색으로 시간 내에 풀지 못하면 문제의 조건에 따라서 DP, 그리디, 이진 탐색, 적절한 자료 구조를 사용해 최적화한다. 완전 탐색 시 재귀 호출을 사용하면 모든 경우의 수를 만드는 코드(순열, 조합··)를 쉽게 작성할 수 있기에 매우 유용하다. 경우의 수는 문제의 해 후보이며, 문제에 따라 다양한 상태를 가진다. (경로 문제의 경우 경로라는 상태를, 4x4 슬라이딩 퍼즐게임인 경우 퍼즐 맵을 상태로 ..
아래는 종만북의 DP의 메모이제이션 코드 패턴이다. //메모이제이션 사용 예 //전부 -1로 초기화 int cache[2500][2500] //a와 b는 각각 [0,2500) 구간 안의 정수 //반환 값은 항상 int형 안에 들어가는 양수 int someObscureFunction(int a, int b) { //기저 사례 처리 if(...) return ...; //답을 구한적이 있으면 곧장 반환 if(cache[a][b] != -1) return cache[a][b]; //답을 구한적이 없으면 여기서 답을 계산 cache[a][b] = ...; return cache[a][b]; } 외발뛰기 코드 import java.util.*; import java.io.*; public class Main { ..
순열 Brute Force시 경우의 수가 순열 또는 조합 형태로 나타날 수 있다. 아래는 N개의 수(1~N)에서 M개의 순열을 출력하는 코드이다. import java.util.*; import java.io.*; public class Main { static int N, M; static boolean[] select; static LinkedList numbers = new LinkedList(); public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringToken..
import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; int testCase = Integer.parseInt(br.readLine()); for(int t=0; t
Brute Force 시 같은 답을 중복으로 세는 상황이 발생할 수 있다 이를 해결하기 위해서는 항상 특정 형태를 갖는 답만을 세는 것이다. 흔히 사용하는 방법으로는 같은 답 중에서 사전 순으로 가장 먼저 오는 답 하나만을 센다. 예를 들어 (1,0),(2,3)이나 (2,3),(0,1)은 세지 않지만 (0,1),(2,3)은 센다. 이렇게 하기 위해서 각 단계에서 남아 있는 학생들 중 가장 번호가 빠른 학생의 짝을 찾아주면 같은 답 중 사전 순으로 먼저 오는 답만을 셀 수 있다. import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedRe..
SQL SQL(Structured Query Language)는 관계 DB의 표준 질의어이다. SQL에는 데이터 정의어, 조작어, 제어어를 모두 포함하며 사용자는 SQL로 RDB에 지시를 내린다. 모든 SQL문은 세미콜론(;)으로 문장 끝을 표시하며 INSERT, SELECT와 같은 키워드는 대소문자를 구분하지 않는다. 테이블 생성 SQL 테이블 생성문이다. [ ] 로 표시한 항목은 생략 가능하다. CREATE TABLE 테이블_이름 ( 1️⃣ 속성_이름 데이터_타입 [NOT NULL] [DEFAULT 기본값] 2️⃣ [PRIMARY KEY (속성_리스트)] 3️⃣ [UNIQUE (속성_리스트)] 4️⃣ [FOREIGN KEY (속성_리스트) REFERENCES 테이블_이름(속성_리스트)] [ON DEL..
관계 데이터 모델 관계 데이터 모델이란 RDB가 사용하는 논리 데이터 모델로 데이터를 릴레이션(테이블)에 저장, 관리하는 모델이다. 릴레이션 관련 용어 하나의 개체에 관한 데이터를 릴레이션에 저장한다. 릴레이션은 테이블과 같은 의미지만 관계의 의미를 강조하기 위해 릴레이션 용어로 사용된다. 속성 : 릴레이션의 열을 속성(attribute)이라 한다. 속성은 서로 다른 이름을 가져야한다. 도메인으로 값의 범위를 지정하며, 무결성 제약조건 등의 제약 조건이 붙기도 한다. 투플 : 릴레이션의 행을 투플(tuple)이라 한다. 투플은 개체의 모든 속성 값을 모아놓은 것으로 개체의 인스턴스가 된다. 도메인 : 속성 하나가 가질 수 있는 모든 값의 집합을 해당 속성의 도메인(domain)이라 한다. 속성이 가질 수..
데이터베이스 설계 데이터베이스 설계 과정을 요약하면 아래와 같다. 요구사항 분석 : 조직 내 사용자들의 요구 사항을 수집해 요구 사항 멩세서를 만든다. 개념적 설계 : 요구사항 명세서를 기반으로 DB의 개념적 구조를 만든다. 개념적 구조는 사용할 DBMS 종류에 독립적이며 데이터 요소와 요소 간의 관계를 표현한다. 일반적으로 E-R 모델(개념적 데이터 모델)을 사용해 만든다. 논리적 설계 : 개념적 구조를 기반으로 사용하는 DB의 논리적 구조를 만든다. 이때 논리적 구조는 사용할 DBMS에 따라 결정된다. RDB의 경우 테이블로 구성되는 관계 데이터 모델(논리적 데이터 모델)을 사용해 만든다. 물리적 설계 : 논리적 구조를 기반으로 DB의 물리적 구조를 만든다. 즉 데이터베이스의 데이터가 저장 장치에 저..
