jjuya

n단 논법 15723번 [16일차]시간제한메모리 제한2초128MB문제모든 중앙대 컴퓨터공학부(소프트웨어학부) 학생들은 미인이다.지무근은 중앙대 컴퓨터공학부 학생이다.그러므로 지무근은 미인이다.위 연역 논증은 대표적인 삼단논법의 예시이다. 삼단논법이란 전제 두 개와 결론 하나로 이루어진 연역 논증이다. 이것을 응용하면, n개의 전제가 있을 때 m개의 결론을 도출할 수 있을 것이다. 이때의 n과 m은 모든 의미에서 적절한 수라고 가정하자. 자세한 것은 입출력 예시를 확인하자. 입력첫째 줄에 정수 n(2 ≤ n ≤ 26)이 주어진다.둘째 줄부터 n개의 줄에 걸쳐 각 줄에 전제가 하나씩 주어진다. 전제는 모두 a is b의 형식으로 주어지며 a와 b는 서로 다른 임의의 알파벳 소문자이다. 특별한 명시는 없지만 ..

헌내기는 친구가 필요해 21736번 [16일차]시간제한메모리 제한1초1024MB문제2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 싶다. 도연이가 다니는 대학의 캠퍼스는 N×M 크기이며 캠퍼스에서 이동하는 방법은 벽이 아닌 상하좌우로 이동하는 것이다. 예를 들어, 도연이가 (x, y)에 있다면 이동할 수 있는 곳은 (x+1, y), (x, y+1), (x−1, y), (x, y−1)이다. 단, 캠퍼스의 밖으로 이동할 수는 없다.불쌍한 도연이를 위하여 캠퍼스에서 도연이가 만날 수 있는 사람의 수를 출력하는 프로그램을 작성해보자. 입력첫째 줄에는 캠퍼스의 크기를 나타..

스피카 21316번 [15일차]시간제한메모리 제한1초1024MB문제위 그림은 처녀자리 중 12개의 별을 12개의 선분으로 이어 만든 그림이다.시은이는 임의로 각 별에 1부터 12까지의 서로 다른 정수 번호를 부여하고, 12개의 정수 쌍으로 각 선분이 어떤 두 별을 잇는지 기록하였다. 하지만 어떤 별에 어떤 번호를 부여했는지 잊어버렸다고 한다.선분들의 정보가 주어질 때, 가장 밝은 별인 Spica가 몇 번 별이였는지 알려주자. 입력입력은 12개의 줄로 주어진다.각 줄에는 서로 다른 두 개의 정수 x, y가 주어지며, 두 별 x와 y를 잇는 선분이 있음을 의미한다.반드시 그림과 같은 모습임이 보장된다. 출력 입력으로 주어진 그래프에서 Spica는 몇 번 별인지 출력하여라.번호에 해당하는 정수 하나를 출력하면..

유사 라임 게임 24431번 [15일차]시간제한메모리 제한1초512MB문제Alice는 영어 단어를 조합하여 라임(Rhyme)을 만드는 단어 게임을 즐겨한다. Bob도 라임을 만들고 싶지만, 아직 어려서 단어를 잘 모르기 때문에 Alice가 "유사 라임 게임"을 제안했다.먼저, 영문 대문자로만 구성된 길이가 L인 서로 다른 단어 n개를 종이에 적는다: 편의상 W1,W2,…Wn을 n개의 단어라 하자.어떤 한 쌍의 단어 Wi와 Wj를 비교했을 때 최대 공통 접미사의 길이가 F이상이면 두 단어는 "유사 라임"을 이룬다고 정의한다. 이러한 단어 쌍을 "유사 라임 쌍"이라 부르자."유사 라임 게임"은 주어진 단어들을 이용하여 최대한 많은 "유사 라임 쌍"을 만드는 게임이다. 단, 한 단어는 최대 하나의 유사 라임 ..

그녀를 찾아서  16502번 [15일차]시간제한메모리 제한2초512MB문제 그녀와 백화점을 가면 우리는 각자 따로따로 매장을 돌아다닌다. 중간에 그녀를 만나려면 어느 매장으로 가봐야 할까? 그녀는 백화점 쇼핑 중에는 전화벨로 방해받고 싶지 않아서 핸드폰을 꺼놓고 있다.우리는 주어진 시간에 각 매장별로 그녀가 그 곳에 있을만한 확률을 보여주는 프로그램을 만들려고 한다.입력은 유한한 그래프와 양의 정수이다. 그래프는 그녀의 움직임을 모델한 것이고, 움직임은 10분 단위로 일어난다고 하자. 양의 정수는 백화점에서 헤어진지 몇 10분 째인지를 나타낸다. 그래프의 노드는 매장을 의미하고, 노드 사이의 화살표는 한 매장에서 다른 매장으로 이동하는 관계이고, 화살표에는 그 이동의 확률이 표현되어 있다. 한 노드에서 ..

상근이의 여행  9372번 [14일차]시간제한메모리 제한1초256MB문제상근이는 겨울방학을 맞아 N개국을 여행하면서 자아를 찾기로 마음먹었다. 하지만 상근이는 새로운 비행기를 무서워하기 때문에, 최대한 적은 종류의 비행기를 타고 국가들을 이동하려고 한다.이번 방학 동안의 비행 스케줄이 주어졌을 때, 상근이가 가장 적은 종류의 비행기를 타고 모든 국가들을 여행할 수 있도록 도와주자.상근이가 한 국가에서 다른 국가로 이동할 때 다른 국가를 거쳐 가도(심지어 이미 방문한 국가라도) 된다. 입력첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고,각 테스트 케이스마다 다음과 같은 정보가 주어진다.첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000)..

점프왕 쩰리 (Small) 16173번 [14일차]시간제한메모리 제한2초128MB문제‘쩰리’는 점프하는 것을 좋아하는 젤리다. 단순히 점프하는 것에 지루함을 느낀 ‘쩰리’는 새로운 점프 게임을 해보고 싶어 한다. 새로운 점프 게임의 조건은 다음과 같다.‘쩰리’는 가로와 세로의 칸 수가 같은 정사각형의 구역 내부에서만 움직일 수 있다. ‘쩰리’가 정사각형 구역의 외부로 나가는 경우엔 바닥으로 떨어져 즉시 게임에서 패배하게 된다.‘쩰리’의 출발점은 항상 정사각형의 가장 왼쪽, 가장 위의 칸이다. 다른 출발점에서는 출발하지 않는다.‘쩰리’가 이동 가능한 방향은 오른쪽과 아래 뿐이다. 위쪽과 왼쪽으로는 이동할 수 없다.‘쩰리’가 가장 오른쪽, 가장 아래 칸에 도달하는 순간, 그 즉시 ‘쩰리’의 승리로 게임은 종..

바닥 장식 1388번 [14일차]시간제한메모리 제한2초128MB문제형택이는 건축가이다. 지금 막 형택이는 형택이의 남자 친구 기훈이의 집을 막 완성시켰다. 형택이는 기훈이 방의 바닥 장식을 디자인했고, 이제 몇 개의 나무 판자가 필요한지 궁금해졌다. 나무 판자는 크기 1의 너비를 가졌고, 양수의 길이를 가지고 있다. 기훈이 방은 직사각형 모양이고, 방 안에는 벽과 평행한 모양의 정사각형으로 나누어져 있다.이제 ‘-’와 ‘|’로 이루어진 바닥 장식 모양이 주어진다. 만약 두 개의 ‘-’가 인접해 있고, 같은 행에 있다면, 두 개는 같은 나무 판자이고, 두 개의 ‘|’가 인접해 있고, 같은 열에 있다면, 두 개는 같은 나무 판자이다.기훈이의 방 바닥을 장식하는데 필요한 나무 판자의 개수를 출력하는 프로그램을..

Best Grass 6186번 [14일차]시간제한메모리 제한1초128MB문제 베시는 부드러운 봄 풀을 씹는 하루를 계획하고 있으며, 농부 존이 R(1

그래프(Graph)정점(Vertex)과 간선(Edge)으로 이루어진 자료구조 G = (V, E)정점 : 데이터 / 간선 (데이터 간의 관계, 방향성)   그래프의 종류방향그래프 : 간선의 방향 O무방향 그래프 : 간선의 방향 X가중치 방향 그래프 : 간선의 가중치-> 지도상의 위치... 그래프 표현인접행렬2차원 배열을 사용, 그래프의 장점들 간의 연결 관계 표현행렬( i , j ) 위치에 간선의 유무를 나타냄무방향 - 간선존재 1 / 간선 없음 0방향그래프 - ( i -> j ) 일 때 간선이 존재하면 1 / 없으면 0가중치 그래프 - 간선이 존재하면 가중치값 / 없으면 0장점O(1)의 시간복잡도 / 단순한 구조단점O(N^2)의 높은 공간복잡도=> 정점의 개수가 정해 저 있을 경우 유리함!class Gr..