Gonna be my Best part

www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 문제 흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다. 주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된..

www.acmicpc.net/problem/4779 4779번: 칸토어 집합 칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로, 구간 [0, 1]에서 시작해서 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만든다. 전체 집합이 유한이라고 가정하고, www.acmicpc.net 문제 칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로, 구간 [0, 1]에서 시작해서 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만든다. 전체 집합이 유한이라고 가정하고, 다음과 같은 과정을 통해서 칸토어 집합의 근사를 만들어보자. 1. -가 3N개 있는 문자열에서 시작한다. 2. 문자열을 3등분 한 뒤, 가운데 문자열을 공백으로 바꾼다. 이렇게 하면, 선(문자열) 2개가 남는다. 3..

분할 정복 알고리즘은 이름에서 부터 알 수 있듯, 그대로 해결할 수 없는 문제를 거의 같은 크기의 여러개의 작은 문제로 분할하여 해결하는 방법이다. 또한 분할 정복 알고리즘의 경우 보통 재귀함수를 통해서 구현되지만 거의 같은 크기의 문제로 나눠야 한다는 것에 차이가 있다. 분할 정복의 구성 1) 주어진 문제를 여러개의 부분 문제로 나눈다. (divide) 2) 재귀 함수를 통해서 각각의 부분 문제를 해결한다 (conquer) 3) 각 부분의 문제의 답으로 부터 전체 문제의 답을 계산한다. (merge) 문할 정복의 적용을 위해 요구되는 특성 1) 문제를 둘 이상으로 나누는 자연스러운 방법이 있어야한다. 2) 부분 문제의 답을 조합하여 원래 문제의 답을 계산하는 효율적인 방법이 있어야 한다. 문할 정복 문..

정규화가 등장하게 된 배경 하나의 릴레이션에서 여러 엔티티의 attribute를 혼합하면 데이터의 중복이 일어나 저장 공간이 낭비된다. 또한 이러한 중복으로 인해 하나의 릴레이션에서만 변경되고 다른 릴레이션들에선 변경되지않는 데이터의 불일치 문제도 일어나 어느것이 정확한지 알 수 없게 된다. 이러한 문제의 해결을 위해 정규화 과정을 거치는 것. 갱신 이상 삽입 이상: 원하지 않는 자료가 삽입되거나 삽입하는데 자료가 부족해 삽입되지 않아 발생 삭제 이상: 하나의 자료만 삭제하길 원하나 그 자료가 포함된 튜플이 모두 삭제되어 정보 손실이 발생 수정 이상: 일부 튜플만 갱신되어 정보가 모호해지거나 일관성이 없어져 정확한 정보 파악이 되지 않는 문제 정규화 데이터베이스의 설계를 재구성하는 테크닉으로, 이를 통해..

인덱스 인덱스란? 인덱스는 대부분의 책들의 처음이나 마지막에있는 색인과 같은 느낌이다. 데이터는 책의 내용이고그 데이터가 저장된 레코드의 위치가 인덱스 목록의 페이지 번호가 된다. 따라서 인덱스를 사용하는 경우 원하는 값을 가져오기 위해 DB의 모든 데이터를 검색할 필요가 없어 진다. DB에서의 인덱스는 column의 값과 해당 레코드가 저장된 주소를 키와 값의 쌍으로 만들어 두는 것이다. 이는 항상 정렬되어있어 탐색에 용이하다. 하지만 새로운 값을 추가하거나 수정, 삭제하는 경우 속도가 느려진다. 인덱스는 데이터 저장 성능을 낮추고 탐색 성능을 높이는 기능이라고 볼 수 있다. 또한 인덱스 관리를 위해 추가적으로 저장공간이 사용되고 이를 관리하기 위한 작업이 추가적으로 필요하다는 단점이 있다. Index..

데이터베이스가 필요한 이유는 무엇일까? 데이터베이스를 사용하기 이전에는 데이터 관리에 파일시스템 사용 -> 데이터를 각각의 파일 단위로 저장하게 됨. 이렇게 되면 독립적인 어플리케이션과 상호 연동이 되어야 하는데, 데이터의 종속성, 중복성, 무결성에 문제가 생긴다. 데이터베이스의 특징엔 무엇이 있는가? 독립성 데이터베이스의 starage상의 어떠한 물리적인 변화가 생기더라도 관련된 어플리케이션들을 수정해야할 필요가 없다. = 내부 스키마가 변하더라도 외부/개념 스키마에 영향X (물리적 독립성) 논리 스키마가 변하더라도 어플리케이션에 영향을 주지 않는다. = 논리스키마가 변해도 외부 스키마에는 영향X (논리적 독립성) 무결성 데이터의 정확성, 일관성, 유효성이 유지되는 것. 잘못된 데이터가 발생하는 경우를..

www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오. 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다. 입력 첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다. 출력 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. 예제 입력 1 20 2 예제 출력 1 21 풀이 위의 식처럼 N을 k개로 나타내는 방법의 수는 k-1개로 N~0을 나타내는 방법의 수를 모두 합..

www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net 문제 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망에서 사람들의 친구 관계는 그래프로 표현할 수 있는데, 이 그래프에서 사람은 정점으로 표현되고, 두 정점을 잇는 에지는 두 정점으로 표현되는 두 사람이 서로 친구 관계임을 표현한다. 예를 들어, 철수와 영희, 철수와 ..

www.acmicpc.net/problem/2011 2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net 문제 상근이와 선영이가 다른 사람들이 남매간의 대화를 듣는 것을 방지하기 위해서 대화를 서로 암호화 하기로 했다. 그래서 다음과 같은 대화를 했다. 상근: 그냥 간단히 암호화 하자. A를 1이라고 하고, B는 2로, 그리고 Z는 26으로 하는거야. 선영: 그럼 안돼. 만약, "BEAN"을 암호화하면 25114가 나오는데, 이걸 다시 글자로 바꾸는 방법은 여러 가지가 있어. 상근: 그렇네. 25114를 다시 영어로 바꾸면, "BE..

www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 입력 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어..