우노

문제 어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다. 이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다. 예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자. 이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다. 2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다. 입력 조건 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다..

문제 레스토랑을 운영하고 있는 스카피는 레스토랑 내부가 너무 낡아 친구들과 함게 직접 리모델링하기로 했습니다. 레스토랑이 있는 곳은 스노우타운으로 매운 추운 지역이어서 내부 공사를 하는 도중에 주기적으로 외벽의 상태를 점검해야 할 필요가 있습니다. 레스토랑의 구조는 완전히 동그란 모양이고 외벽의 총 둘레는 n미터이며, 외벽의 몇몇 지점은 추위가 심할 경우 손상될 수도 있는 취약한 지점들이 있습니다. 따라서 내부 공사 도중에도 외벽의 취약 지점들이 손상되지 않았는지, 주기적으로 친구들을 보내서 점검을 하기로 했습니다. 다만, 빠른 공사 진행을 위해 점검 시간을 1시간으로 제한했습니다. 친구들이 1시간 동안 이동할 수 있는 거리는 제각각이기 때문에, 최소한의 친구들을 투입해 취약 지점을 점검하고 나머지 친구..

문제 크기가 N x N인 도시가 있습니다. 도시는 1 x 1 크기의 칸으로 나누어져 있습니다. 도시의 각 칸은 빈칸, 치킨집, 집 중 하나입니다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미합니다. r과 c는 1부터 시작합니다. 이 도시에 사는 사람들은 치킨을 매우 좋아합니다. 따라서 사람들은 "치킨 거리"라는 말을 주로 사용합니다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리입니다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있습니다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합입니다. 임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2| 로 구합니..

itertools란? itertools는 파이썬에서 반복되는 데이터를 처리하는 기능을 포함하고 있는 라이브러리이다. 제공하는 클래스는 매우 다양하지만, 코딩 테스트에서 가장 유용하게 사용할 수 있는 클래스는 permutations, combinations이다. permutations(순열) ex) 4개의 서로 다른 공 중에서 2개를 골라 나열하는 경우의 수 순열은 순서가 중요하므로, A B 와 B A 는 다른 경우로 취급 nPr = n! / (n-r)! combinations(조합) ex) 4개의 공중에서 무작위로 2개의 공을 고르는 경우의 수 조합은 순서가 중요하지 않으므로, A B 와 B A 는 같은 경우로 취급 nCr = n! / ((n-r)! * r!) permutations permutation..

표준 라이브러리란? 특정한 프로그래밍 언어에서 자주 사용되는 표준 소스코드를 미리 구현해 놓은 라이브러리를 의미한다. 코딩 테스트에서는 대부분 표준 라이브러리를 사용할 수 있도록 허용하므로, 표준 라이브러리를 사용하면 소스코드 작성량에 대한 부담을 줄일 수 있다. 파이썬에서 지원하는 표준 라이브러리는 굉장히 다양하지만, 코딩 테스트를 준비하며 반드시 알아야하는 라이브러리는 6가지 정도이다. PS 주요 라이브러리 with Python 내장 함수 print(), input()과 같은 기본 입출력 기능부터 sorted()와 같은 정렬 기능을 포함하고 있는 기본 내장 라이브러리이다. itertools 파이썬에서 반복되는 형태의 데이터를 처리하는 기능을 제공하는 라이브러리이다. 순열과 조합 라이브러리를 제공한다...

문제 빙하가 깨지면서 스노우타운에 떠내려온 죠르디는 인생 2막을 위해 주택 건축사업에 뛰어들기로 결심하였습니다. 죠르디는 기둥과 보를 이용하여 벽면 구조물을 자동으로 세우는 로봇을 개발할 계획인데, 그에 앞서 로봇의 동작을 시뮬레이션 할 수 있는 프로그램을 만들고 있습니다. 프로그램은 2차원 가상 벽면에 기둥과 보를 이용한 구조물을 설치할 수 있는데, 기둥과 보는 길이가 1인 선분으로 표현되며 다음과 같은 규칙을 가지고 있습니다. 기둥은 바닥 위에 있거나 보의 한쪽 끝부분 위에 있거나, 또는 다른 기둥 위에 있어야 합니다. 보는 한쪽 끝부분이 기둥 위에 있거나, 또는 양쪽 끝부분이 다른 보와 동시에 연결되어 있어야 합니다. 단, 바닥은 벽면의 맨 아래 지면을 말합니다. 2차원 벽면은 n x n 크기 정사..

문제 'Dummy'라는 도스 게임이 있습니다. 이 게임에는 뱀이 나와서 기어 다니는데, 사과를 먹으면 뱀 길이가 늘어납니다. 뱀이 이리저리 기어 다니다가 벽 또는 자기 자신의 몸과 부딪히면 게임이 끝납니다. 게임은 N x N 정사각 보드 위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있습니다. 보드의 상하좌우 끝에는 벽이 있습니다. 게임을 시작할 때 뱀은 맨 위 맨 좌측에 위치하고 뱀의 길이는 1입니다. 뱀은 처음에 오른쪽을 향합니다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따릅니다. 먼저 뱀은 몸길이를 늘려 머리를 다음 칸에 위치시킵니다. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않습니다. 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 ..

문제 고고학자인 "튜브"는 고대 유적지에서 보물과 유적이 가득할 것으로 추정되는 비밀의 문을 발견하였습니다. 그런데 문을 열려고 살펴보니 특이한 형태의 자물쇠로 잠겨 있었고 문 앞에는 특이한 형태의 열쇠와 함께 자물쇠를 푸는 방법에 대해 다음과 같이 설명해 주는 종이가 발견되었습니다. 잠겨있는 자물쇠는 격자 한 칸의 크기가 1 x 1인 N x N 크기의 정사각 격자 형태이고 특이한 모양의 열쇠는 M x M 크기인 정사각 격자 형태로 되어 있습니다. 자물쇠에는 홈이 파여 있고 열쇠 또한 홈과 돌기 부분이 있습니다. 열쇠는 회전과 이동이 가능하며 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열리게 되는 구조입니다. 자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는 데 영..

들어가기 앞서 PS 시 유용하게 사용되는 함수들을 정리합니다. 2차원 리스트를 왼쪽으로 90도 회전하기 def rotate_the_matrix_90_degree_to_the_left(a): n = len(a) # 행 길이 계산 m = len(a[0]) # 열 길이 계산 result = [[0] * n for _ in range(m)] # 회전된 결과 리스트 # 모든 요소값을 90도 회전 for i in range(n): for j in range(m): result[m-j-1][i] = a[i][j] return result 2차원 리스트를 오른쪽으로 90도 회전하기 def rotate_the_matrix_90_degree_to_the_right(a): n = len(a) # 행 길이 계산 m = len..

문제 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다. 간단한 예로 "aabbaccc"의 경우 "2a2ba3c"(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, "abcabcdede"와 같은 문자열은 전혀 압축되지 않습니다. "어피치"는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 ..