공작소

>> 문제 바로가기 (https://www.acmicpc.net/problem/25181) 풀이 과정 특정 i번째 숫자 앞뒤로, 바꿨을 때 Ai != Bj && Aj != Bi 를 만족하는 j번째 숫자를 찾아 바꾸면 된다. import sys input = sys.stdin.readline n = int(input().rstrip()) arr = list(map(int, input().rstrip().split())) narr = [] for a in arr: narr.append(a) done = True for i in range(n): if arr[i] == narr[i]: idx = i + 1 while idx < n and narr[i] == narr[idx]: idx += 1 if idx ==..

>> 문제 바로가기 (https://www.acmicpc.net/problem/25595) 문제 기아데 연방 공화국은 '레기온'이라는 인공지능 무인 병기들과 전쟁 중이다. 공화국은 레기온에 대항할 수단으로 '레긴레이브'라는 보행 병기를 개발했다. 공화국 군인들 중 소수정예는 이 레긴레이브에 탑승해서 레기온에 맞서 싸운다. 신에이 노우젠은 제 86 전략기동전단 기갑전대의 전대장이자 근접전의 대가이다. 그는 레기온들의 위치를 전부 파악할 수 있는 이능력이 있다. 그의 전투 스타일은 직접 레기온이 있는 위치 근처로 가서 빠르게 해치우는 것이다. 레긴레이브는 화력이 다소 떨어지지만, 기동성이 뛰어나다는 장점이 있기 때문이다. 레긴레이브는 대각선 네 방향으로 이동할 수 있다. 현재 좌표가 (r, c) 라면 (r−..

>> 문제 바로가기 (https://www.acmicpc.net/problem/29196) 문제 이 대회의 운영진 중 한 명인 KSA 학생은 얼마 전 소수 공포증을 극복했으나 또 다른 소수를 구별할 수 없게 되어 버렸다. KSA의 명예를 지키기 위해 어떤 소수 k를 입력받아 k를 나타내는 분수 p/q를 아무거나 구해주자. p와 q는 10^9 이하인 양의 정수이며, k와 p/q의 절대오차 또는 상대오차가 10^(−6) 이하면 정답이다. 입력 첫 번째 줄에 소수 k가 주어진다. 출력 첫 번째 줄에 조건을 만족하는 분수가 존재한다면 YES, 아니라면 NO를 출력한다. 만약 그러한 분수가 존재한다면, 두 번째 줄에 두 정수 p, q를 공백을 사이에 두고 출력한다. 정답이 여러 개 존재한다면 그중 아무거나 출력해..

>> 문제 바로가기 (https://www.acmicpc.net/problem/14675) 문제 그래프 이론에서 단절점(cut vertex)과 단절선(bridge)은 다음과 같이 정의 된다. 단절점(cut vertex) : 해당 정점을 제거하였을 때, 그 정점이 포함된 그래프가 2개 이상으로 나뉘는 경우, 이 정점을 단절점이라 한다. 단절선(bridge) : 해당 간선을 제거하였을 때, 그 간선이 포함된 그래프가 2개 이상으로 나뉘는 경우, 이 간선을 단절선이라 한다. 이 단절점과 단절선을 우리는 트리(tree)에서 구하려고 한다. 그래프 이론에서 트리(tree)의 정의는 다음과 같다. 트리(tree) : 사이클이 존재하지 않으며, 모든 정점이 연결되어 있는 그래프 트리의 정보와 질의가 주어질 때, 질의..

>> 문제 바로가기 (https://www.acmicpc.net/problem/31229) 문제 다음 조건을 만족하는 길이 N의 수열 A = {A_1, A_2,…,A_N}를 출력하시오. 1≤ i < j ≤ N을 만족하는 모든 정수 i와 j에 대해서 다음 조건을 만족한다. A_i != A_j이고 수열 A의 모든 원소는 1 이상 10^9 이하의 정수이다. A_i + A_j는 A_i × A_j의 약수가 아니다. 입력 첫째 줄에 수열 A의 길이를 나타내는 정수 N이 주어진다. (2 ≤ N ≤ 5 000) 출력 첫째 줄에 조건을 만족하는 수열 A의 원소들을 공백으로 구분하여 출력한다. 위 조건을 만족하는 수열이 여러 개라면 그중 아무거나 출력한다. 풀이 과정 위 조건을 만족하는 수열은 홀수 수열이다. 홀수와 홀수..

>> 문제 바로가기 (https://www.acmicpc.net/problem/16956) 문제 크기가 R×C인 목장이 있고, 목장은 1×1 크기의 칸으로 나누어져 있다. 각각의 칸에는 비어있거나, 양 또는 늑대가 있다. 양은 이동하지 않고 위치를 지키고 있고, 늑대는 인접한 칸을 자유롭게 이동할 수 있다. 두 칸이 인접하다는 것은 두 칸이 변을 공유하는 경우이다. 목장에 울타리를 설치해 늑대가 양이 있는 칸으로 갈 수 없게 하려고 한다. 늑대는 울타리가 있는 칸으로는 이동할 수 없다. 울타리를 설치해보자. 입력 첫째 줄에 목장의 크기 R, C가 주어진다. 둘째 줄부터 R개의 줄에 목장의 상태가 주어진다. '.'는 빈 칸, 'S'는 양, 'W'는 늑대이다. 출력 늑대가 양이 있는 칸으로 갈 수 없게 할 ..

문제 N개의 정수로 이루어진 수열 a1, ... , aN이 있다. 택희는 해당 수열이 증가수열 혹은 감소수열이 되게 만들고 싶다. 증가수열은 모든 i(1 ≤ i arr[i]: up.append([]) up[-1].append(arr[i]) down = [[arr[0]]] for i in range(1, n): if arr[i-1] = up[0][0]: print(len(..

문제 팰린드롬이란 앞으로 읽으나 뒤로 읽으나 같은 문자열을 말한다. 팰린드롬의 예시로 POP, ABBA 등이 있고, 팰린드롬이 아닌 것의 예시로 ABCA, PALINDROME 등이 있다. 같은 의미를 가지는 여러 단어들을 보자. 회문 (한국어) palindrome (영어, 프랑스어, 노르웨이어, 그리스어, 라틴어) 回文 (일본어, 중국어) palindrom (독일어, 덴마크어) palindromi (핀란드어) palíndromo (스페인어, 포르투갈어) palindromo (이탈리아어, 에스페란토어) палиндром (러시아어) قلب مستو (아랍어) 뭔가 이상한 점이 보이지 않는가? 그 어떤 언어에서도 팰린드롬을 뜻하는 단어는 팰린드롬이 아니다! 많은 사람들이 추구하는 “대칭의 아름다움”은 그저 ..

문제 Wacław Sierpiński는 폴란드 수학자이다. 어느 날 그는 아래와 같은 방법으로 삼각형을 그리기로 했다. 정삼각형 T를 그린다. 삼각형 변의 중점을 서로 연결한다. 새롭게 생긴 정삼각형을 T1, T2, T3, T4라고 한다. 아래 그림 중 왼쪽 그림이 해당한다. 위의 단계를 삼각형 T1, T2, T3에 대해서 반복한다. 새로운 삼각형은 T11, T12, T13, T14, T21, T22, T23, T24, T31, T32, T33, T34가 된다. 1, 2, 3으로 끝나는 모든 삼각형에 대해서 이 방법을 반복한다. 이렇게 생긴 프랙탈을 Sierpinski 삼각형이라고 한다. 삼각형 B가 삼각형 A를 포함하지 않고, A의 한 변 전체가 B의 한 변의 일부일 때, A는 B에 기대고 있다고 한다..

문제 계산은 사람에게나 컴퓨터에게나 상당히 번거로운 일인 것 같다. 특히 n개의 행렬 M1,M2,⋯,Mn의 곱, 즉 M1M2⋯Mn같은 것은 정말이지 계산하기 귀찮다. 행렬과 그 곱셈이 익숙하지 않은 사람들을 위해 설명을 해 보자면, 먼저 행렬은 여러 수나 기호, 문자, 수식 같은 것을 직사각형 모양으로 적절히 배열한 후 이를 괄호로 묶은 것을 말한다. 편의상 이 문제에서는 행렬에 정수만 배열한다고 가정한다. 예를 들어 아래와 같은 것이 행렬의 한 예이다. 행렬에 배열된 수를 성분이라고 한다. 행렬의 가로줄은 행이라고 부르며, 위에서부터 차례로 제1행, 제2행, 제3행, … 식으로 이름을 붙인다. 또한 행렬의 세로줄은 열이라고 부르며, 왼쪽에서부터 차례로 제1열, 제2열, 제3열, … 식으로 이름을 붙인다..