분류 전체보기

백준 15686번 치킨 배달 (C++)

문제 설명 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제 해결 그리디가 아닌, 완전 탐색을 해야 풀리는 문제이다. 이 점만 알고 접근한다면 그리 어려운 문제는 아니다. 문제 조건을 보면 알 수 있듯이, M, N의 수가 그리 높지 않아 완전 제곱으로 충분히 문제를 해결할 수 있다. 과정은 다음과 같다. 1. M개 치킨집을 뽑는다. (조합의 원리를 생각하면 된다.) 2. M개에 대한 치킨 거리를 계산한다. 3. 최솟값을..

백준 9663 N-Queen (C++)

문제설명 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 해결 백트래킹(DFS)을 이용해서 푸는 문제이다. 한 step당 하나의 퀸을 일단 두고, 조건에 만족하면 다음 step으로 넘어가는 방식이다. 주의할 점은 두 가지이다. 1. visit 배열을 두어 현재 둔 위치를 체크해두되, DFS 재귀문 호출 뒤에 다시 풀어준다. 2. 대각선 인덱스 헷갈리지 않게 조심한다. 대각선 기준으로 찾을 때, 현재 step 이전에 y가 더 큰 경우도 고려해주어야 한다. ..

백준 1039번 교환 (C++)

문제설명 https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 문제 해결 완전 탐색으로 풀었고, DFS, BFS 둘다 가능할 것 같은데 나는 BFS로 풀었다. 하나의 스텝 안에서 중복을 체크하기 위해 visit이라는 이름의 set 자료구조를 선언했다. 이 중복 체크를 DFS에서 하려면 재귀에 대해 잘 이해하고 코드를 짜야할 것 같다. 인덱스로 관리하기 위해 입력은 string 형태로 받았으며, while 문 안에서는 총 3번의 반복문이 이루어진다. 1. 기존 q에 있었던 값들 (즉, 이전 스텝에서 q에 넣었던 수들)을 ..

백준 1062번 가르침 (C++)

문제설명 https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 문제해결 전체적인 코드 흐름은 다음과 같다. default_alpha에 항상 들어가는 5개의 알파벳을 넣어준다. 최적화를 하기 위해 백트래킹에서는 default_alpha에 해당하는 문자들은 탐색하지 않았다. 따라서 문장들을 탐색하면서 default_alpha에 해당하는지 검사한다. 만약 default_alpha에 속하면 이미 검사를 완료했다는 의미로 word_dup을 1로 바꿔주..

백준 1759번 (C++)

문제 설명 문제 해결 수의 크기가 크지 않으면서, 모든 경우의 수를 탐색해야 하므로 완전 탐색인 DFS 문제임을 알 수 있다. 크게 어려운 문제는 아닌데, 처음에 visit 배열을 만들고, for 문을 돌면서 DFS 함수에 들어가는 식으로 잘못 접근했다가 시간이 조금 걸렸다. 여기서는 그래프 탐색이 아니고 암호 선택의 문제이기 때문에, 해당 알파벳을 택한다 / 택하지 않는다의 두 가지 경우밖에 없다. 이 경우에 한해 재귀를 돌면 된다. 다시 방문할 일이 없으므로 visit 배열도 불필요하다. 나는 아직도 재귀의 개념이 직관적으로 와닿지가 않는다. 그게 다양한 dfs 문제를 풀었음에도 불구하고 잘 막히는 이유인 것 같다. 문제를 풀 때 먼저 손으로 들어가기 전에 DFS의 정의를 어떻게 해야하는지를 확실히 ..

[데이터베이스시스템] Chapter 4 : Intermediate SQL

챕터 4에서는 계속해서 SQL에 대해 더 살펴볼 것이다. Joined Relations Join operation은 두 개의 릴레이션을 하나의 릴레이션으로 만드는 것이다. from 안에서 subquery로 사용이 가능하다. Join operation은 다음 3가지 타입이 있다. 1. Natural join 2. Inner join 3. Outer join 하나씩 살펴보자. Natural Join in SQL 모든 튜플을 다 연결시켜서 의미없는 정보를 생산시키는 카티션 곱과 다르게, natural join은 join을 수행하는 릴레이션 중에서 공통 속성의 값이 같은 튜플만을 고려한다. 예를 들어 instructor과 teach 테이블로부터 정보를 결합할 때, 보통 일치 조건으로 instructor.ID =..

[데이터베이스시스템] Chapter 3: Introduction to SQL

SQL Parts SQL은 데이터베이스와 상호작용하기 위한 언어로, 기능에 따라 다음으로 나눌 수 있다. DDL(Data Definition Language) : 데이터베이스의 구조를 정의한다. 릴레이션의 스키마, 무결성 제약 조건(integrity), 관련 속성들의 타입, 뷰(View), 액세스 권한, 물리적 저장 구조 등을 정의한다. 릴레이션 삭제/수정하는 기능도 제공한다. DML : database에서 tuple을 수정, 삽입, 제거, 정보 검색이 가능하다. DCL : 데이터의 사용 권한을 관리하는 데에 사용된다. Embedded SQL, Dynamic SQL : SQL이 c++, 자바와 같은 일반 프로그래밍 언어에 내재될 수 있다. Domain Types in SQL 다음과 같은 특징들이 있다. ..

[데이터베이스시스템] Chapter 6: Database Design Using the E-RModel

이번 챕터에서는 데이터 모델링을 하는 방법을 배운다. 데이터 모델링은 건축에서 지반 설계를 하는 작업과 유사하다. 즉, 현실 세계의 복잡한 개념을 단순화하고 추상화시켜 데이터베이스화하는 과정을 의미한다. Design Alternatives database schema를 설계할 때, 두가지 오류를 피해야 한다. 1. Redundancy(중복성) : 좋지 못한 설계는 정보의 반복을 야기할 수 있다. 데이터 중복은 정보의 업데이트가 있을 때 data inconsistency를 초래할 수 있다. 2. Incompleteness (불완전성) : 좋지 못한 설계는 기업의 특정 측면을 수행하기 어렵거나 불가능하게 만들 수 있다. ER model -- Database Modeling ER model은 다음 세가지 개념..