가장 먼 노드 문제 설명 n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다. 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요. 제한사항 노드의 개수 n은 2 이상 20,000 이하입니다. 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다. vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다. 풀이 다익..

정규화 왜? 한 릴레이션에 여러 엔티티의 어트리뷰트들을 혼합하게 되면 정보가 중복 저장되며, 저장 공간을 낭비하게 된다. 또 중복된 정보로 인해 갱신 이상이 발생하게 된다. 동일한 정보를 한 릴레이션에는 변경하고, 나머지 릴레이션에서는 변경하지 않은 경우 어느 것이 정확한지 알 수 없게 되는 것이다. 이러한 문제를 해결하기 위해 정규화 과정을 거친다. 이상(Anomaly)의 개념 및 종류 삽입 이상(Insetion Anomaly) : 릴레이션에 데이터를 삽입할 때 의도와는 상관 없이 원하지 않는 값들도 함께 삽입되는 현상 삭제 이상(Deletion Anomaly) : 릴레이션에서 한 튜플을 삭제할 때 의도와는 상관 없는 값들도 함께 삭제되는 연쇄가 일어나는 현상 갱신 이상(Update Anomaly) :..

관계형 데이터 베이스 개체(Entity)나 관계(Relationship)을 모두 릴레이션(Relation)이라는 표(Table)로 표현한다. 구조 튜플 = 레코드 릴레이션을 구성하는 각각의 행을 말한다. 튜플의 수를 카디널리티(Cardinality) 또는 기수, 대응수라고 한다. 속성의 모임으로 구성된다. 속성 (Attribute) = 데이터 필드 데이터베이스를 구성하는 가장 작은 논리적 단위이다. 속성의 수를 디그리 또는 차수라고 한다. 도메인(Domain) 하나의 속성이 취할 수 있는 같은 타입의 원자(Atomic) 값들의 집합이다. 주민번호 속성의 도메인은 숫자로 알파벳은 입력될 수 없다. 릴레이션의 특징 튜플은 중복되지 않는다. 튜플 사이에는 순서가 없다. 튜플의 삽입, 삭제로 인해 릴레이션은 시..

데이터 베이스를 사용하는 이유 기존의 파일 시스템을 이용한 데이터 관리에서 생기는 데이터 종속성 문제와 중복성, 데이터 무결성을 해결하기 위해 데이터 베이스가 필요하다. 특징 데이터의 독립성 물리적 독립성: 데이터 파일을 늘리거나 새롭게 추가하더라도 관련된 응용프로그램을 수정할 필요가 없다. 논리적 독립성: 데이터 베이스는 논리적 구조로 다양한 응용 프로그램의 논리적 요구를 만족시켜줄 수 있다. 데이터의 무결성 데이터의 정확성, 일관성, 유효성이 유지되는 것을 말한다. 개체 무결성 모든 테이블이 기본키로 선택된 필드를 가져야한다. 고유한 값이며 빈 값은 허용되지 않는다. 참조 무결성 두 테이블의 데이터가 항상 일관된 값을 갖도록 유지되어야한다. 만약 참조하는 데이터가 삭제된다면 참조하는 데이터도 삭제되어..

배달 문제 설명 N개의 마을로 이루어진 나라가 있습니다. 이 나라의 각 마을에는 1부터 N까지의 번호가 각각 하나씩 부여되어 있습니다. 각 마을은 양방향으로 통행할 수 있는 도로로 연결되어 있는데, 서로 다른 마을 간에 이동할 때는 이 도로를 지나야 합니다. 도로를 지날 때 걸리는 시간은 도로별로 다릅니다. 현재 1번 마을에 있는 음식점에서 각 마을로 음식 배달을 하려고 합니다. 각 마을로부터 음식 주문을 받으려고 하는데, N개의 마을 중에서 K 시간 이하로 배달이 가능한 마을에서만 주문을 받으려고 합니다. 다음은 N = 5, K = 3인 경우의 예시입니다. 위 그림에서 1번 마을에 있는 음식점은 [1, 2, 4, 5] 번 마을까지는 3 이하의 시간에 배달할 수 있습니다. 그러나 3번 마을까지는 3시간 ..

예상 대진표 문제 설명 △△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고, 1번↔2번, 3번↔4번, ... , N-1번↔N번의 참가자끼리 게임을 진행합니다. 각 게임에서 이긴 사람은 다음 라운드에 진출할 수 있습니다. 이때, 다음 라운드에 진출할 참가자의 번호는 다시 1번부터 N/2번을 차례대로 배정받습니다. 만약 1번↔2번 끼리 겨루는 게임에서 2번이 승리했다면 다음 라운드에서 1번을 부여받고, 3번↔4번에서 겨루는 게임에서 3번이 승리했다면 다음 라운드에서 2번을 부여받게 됩니다. 게임은 최종 한 명이 남을 때까지 진행됩니다. 이때, 처음 라운드에서 A번을 가진 참가자는 경쟁자로 생각하는 B번 ..

조이스틱 문제 설명 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다음 알파벳 ▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로) ◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서) ▶ - 커서를 오른쪽으로 이동 (마지막 위치에서 오른쪽으로 이동하면 첫 번째 문자에 커서) 예를 들어 아래의 방법으로 "JAZ"를 만들 수 있습니다. - 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다. - 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다. - 마지막 위치에서 조이스틱을 아래로..

소수 찾기 문제 설명 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요. 제한 사항 numbers는 길이 1 이상 7 이하인 문자열입니다. numbers는 0~9까지 숫자만으로 이루어져 있습니다. "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다. 풀이 1부터 len(numbers)까지 가능한 순열을 구한 후 해당 값이 소수인지 체크하고 소수일 경우 set에 넣는다. (중복 제거를 위해) from itertools import permut..