본문 바로가기
728x90

백준

 (129)
[백준] 6064번 IOIOI [Python] - 문자열 N+1 개의 I 사이에 N개의 O가 들어있는 문자열 $P_N$ : IOIOIOIO...IOI에 대해서 N이 주어질 때 I와 O로만 이루어진 길이가 M인 문자열에서 $P_N$이 몇 번 포함되는지 세는 문제 IOIOIOI에는 IOI가 3번 포함됨. 더보기 문제 N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 $P_N$이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI $($O가 N개$)$ I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다. 출력 S에 $P_N$이 몇 군..
[백준] 1009번 분산처리 [Python] 10대의 컴퓨터로 분산 처리를 진행한다. $a^b$개의 데이터를 처리할 때, 1번 데이터 > 1번 컴퓨터, 2번 데이터 > 2번 컴퓨터, ... , 10번 데이터 > 10번 컴퓨터, 11번 데이터 > 1번 컴퓨터, 12번 데이터 > 2번 컴퓨터, ... 위와 같은 방법으로 처리함 총 데이터 개수가 주어질 때, 마지막 데이터를 처리하는 컴퓨터 번호를 출력하는 문제 더보기 문제 재용이는 최신 컴퓨터 10대를 가지고 있다. 어느 날 재용이는 많은 데이터를 처리해야 될 일이 생겨서 각 컴퓨터에 1번부터 10번까지의 번호를 부여하고, 10대의 컴퓨터가 다음과 같은 방법으로 데이터들을 처리하기로 하였다. 1번 데이터는 1번 컴퓨터, 2번 데이터는 2번 컴퓨터, 3번 데이터는 3번 컴퓨터, ... , 10번 데이터는..
[백준] 1004번 어린 왕자 [Python] 출발점, 도착점이 주어질 때, 최소한의 행성을 거쳐서 가는 방법을 구하는 문제 행성들의 중심과 반지름이 주어지고, 행성의 이탈 및 진입 횟수를 합산해서 최소가 되는 값을 출력하면 된다. 더보기 문제 어린 왕자는 소혹성 B-664에서 자신이 사랑하는 한 송이 장미를 위해 살아간다. 어느 날 장미가 위험에 빠지게 된 것을 알게 된 어린 왕자는, 장미를 구하기 위해 은하수를 따라 긴 여행을 하기 시작했다. 하지만 어린 왕자의 우주선은 그렇게 좋지 않아서 행성계 간의 이동을 최대한 피해서 여행해야 한다. 아래의 그림은 어린 왕자가 펼쳐본 은하수 지도의 일부이다. 빨간 실선은 어린 왕자가 출발점에서 도착점까지 도달하는데 있어서 필요한 행성계 진입/이탈 횟수를 최소화하는 경로이며, 원은 행성계의 경계를 의미한다. ..
[백준] 2178번 미로 탐색 [Python] - BFS NxM 크기의 미로에서 $($1,1$)$ 에서 $($N,M$)$로 가는데 지나야하는 최소 칸 수를 구하는 문제 1은 이동 가능, 0은 이동 불가 칸을 의미 더보기 문제 N×M크기의 배열로 표현되는 미로가 있다. 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, $(1, 1)$에서 출발하여 $(N, M)$의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다. 위의 예에서는 15칸을 지나야 $(N, M)$의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도..
[백준] 2667번 단지번호붙이기 [Python] - DFS, BFS NxN 지도에 1은 집이 있는 곳, 0은 집이 없는 곳을 나타냄 상하좌우로 연결된 집의 모임을 단지라고 함 단지의 개수와 각 단지별 집의 수를 오름차순으로 정렬해 출력하는 문제 더보기 문제 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오. 입력 첫 번째 줄에는 지도의 크기 N$($..
[백준] 1389번 케빈 베이컨의 6단계 법칙 [Python] - 플로이드–워셜 유저 N과 그 사이의 그 사이의 친구 관계 수 M이 주어질 때, 모든 사람과의 연결 관계 수의 합이 가장 작은 사람 출력 더보기 문제 케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다. 예를 들면, 전혀 상관없을 것 같은 인하대학교의 이강호와 서강대학교의 민세희는 몇 단계만에 이어질 수 있을까? 천민호는 이강호와 같은 학교에 다니는 사이이다. 천민호와 최백준은 Baekjoon Online Judge를 통해 알게 되었다. 최백준과 김선영은 같이 Startlink를 창업했다. 김선영과 김도현은 같은 학교 동아리 소속이다. 김도현과 민세희는 같은 ..
[백준] 2606번 바이러스 [Python] - DFS, BFS 1번 컴퓨터가 바이러스에 감염됨 연결된 컴퓨터는 바이러스를 전파함 1번에 의해 감염될 모든 컴퓨터의 개수를 구하는 문제 $($개수에 1번은 제외,,,$)$ 더보기 문제 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다. 어느 날 1..
[백준] 11286번 절댓값 힙 [Python] - 자료구조, 힙 0이 아닌 숫자를 배열에 저장 0일 경우 배열 내 절대값이 가장 작은 값 출력 및 제거 절대값이 같은 숫자가 여러 개일 경우 최소값에 대해서 진 위 연산을 구현하는 문제 더보기 문제 절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다. 배열에 정수 x (x ≠ 0)를 넣는다. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x..
[백준] 1541번 나무 자르기 [Python] - 이진 탐색 최소 M미터의 나무를 얻기 위해 가장 큰 높이 H를 구하는 문제 N개의 나무가 있고, 각 높이가 주어진다. 높이를 고정해서 한 번에 모든 나무를 가로질러 자른다. 이 때의 최대 높이 H를 구하면 된다. 더보기 문제 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다. 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분..
[백준] 11279번 최대 힙 [Python] - 자료구조, 힙 0이 아닌 숫자를 배열에 저장 0일 경우 배열 내 최댓값 출력 및 제거 위 연산을 구현하는 문제 더보기 문제 널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오. 배열에 자연수 x를 넣는다. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 231보다 작다. 출력 입력..
[백준] 1541번 잃어버린 괄호 [Python] - 그리디 양수, +, -, 괄호가 주어진 수식에서 괄호만 지운 문자열이 주어질 때, 괄호를 적절히 쳐서 최소값을 구하는 문제 양수는 0부터 시작하는 문자열로 주어지기도 합니다. 더보기 문제 세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다. 그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다. 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오. 입력 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어..
[백준] 1260번 DFS와 BFS [Python] - DFS, BFS 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 문제 더보기 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. 출력 첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 B..

티스토리툴바