본문 바로가기

전체 글

알고리즘 Algorithm/BOJ 백준 (초급~중급) 2021. 7. 30. [BOJ 백준] 두 번째로 작은 스패닝 트리(1626) Java 링크 : https://www.acmicpc.net/problem/1626 문제 설명 : 더보기 방향성이 없는 그래프 G가 주어진다. 문제는 G의 최소 스패닝 트리보다는 크면서 가장 작은 스패닝 트리인 'The second minimum spanning tree'를 구하는 것이다. MST와 second MST의 모습 입력 : 더보기 첫째 줄에 그래프의 정점의 수 V(1 ≤ V ≤ 50,000)와 간선의 수 E(1 ≤ E ≤ 200,000)가 들어온다. 둘째 줄부터 E+1번째 줄까지 한 간선으로 연결된 두 정점과 그 간선의 가중치가 주어진다. 가중치는 100,000보다 작거나 같은 자연수 또는 0이고, 답은 231-1을 넘지 않는다. 정점 번호는 1보다 크거나 같고, V보다 작거나 같은 자연수이다. 출력 ..
알고리즘 Algorithm/BOJ 백준 (초급~중급) 2021. 7. 30. [BOJ 백준] 공장 (7578) Java 링크 : https://www.acmicpc.net/problem/7578 문제 설명 : 더보기 어떤 공장에는 2N개의 기계가 2열에 걸쳐 N개씩 배치되어 있다. 이 2개의 열을 각각 A열과 B 열이라고 부른다. A열에 있는 N개의 기계는 각각이 B열에 있는 N개의 기계와 하나씩 짝을 이루어 케이블로 연결되어 있다. 즉, A열의 임의의 기계는 B열의 유일한 기계와 케이블로 연결되어 있고, B열의 임의의 기계는 A열의 유일한 기계와 케이블로 연결되어 있다 또한, 각 기계에는 식별번호가 붙어있으며, 짝이 맺어진 기계끼리는 같은 식별번호가 붙어있다. 즉, 각 열에 있는 N개의 기계끼리는 서로 다른 식별번호를 가지고 있으며, 반대쪽 열에 있는 같은 식별번호를 가진 기계와 케이블로 이어져 있다. 공장 작업의 효율..
알고리즘 Algorithm/BOJ 백준 (초급~중급) 2021. 7. 30. [BOJ 백준] 경찰차 (2618) Java 링크 : https://www.acmicpc.net/problem/2618 문제 설명 : 더보기 어떤 도시의 중심가는 N개의 동서방향 도로와 N개의 남북방향 도로로 구성되어 있다. 모든 도로에는 도로 번호가 있으며 남북방향 도로는 왼쪽부터 1에서 시작하여 N까지 번호가 할당되어 있고 동서방향 도로는 위부터 1에서 시작하여 N까지 번호가 할당되어 있다. 또한 동서방향 도로 사이의 거리와 남 북방향 도로 사이의 거리는 모두 1이다. 동서방향 도로와 남북방향 도로가 교차하는 교차로의 위치는 두 도로의 번호의 쌍인 (동서방향 도로 번호, 남북방향 도로 번호)로 나타낸다. N이 6인 경우의 예를 들면 다음과 같다. 이 도시에는 두 대의 경찰차가 있으며 두 차를 경찰차1과 경찰차2로 부른다. 처음에는 항상 경찰차1..
알고리즘 Algorithm/BOJ 백준 (초급~중급) 2021. 7. 30. [BOJ 백준] 케이크 자르기2 (10714) Java 링크 : https://www.acmicpc.net/problem/10714 문제 설명 : 더보기 JOI 군과 IOI 양은 쌍둥이 남매이다. JOI 군은 최근 과자 만들기에 푹 빠졌기 때문에, JOI 군은 오늘도 케이크를 만들어서 먹으려고 했지만, 막 구워진 참에 냄새를 맡고 온 IOI 양이 왔기 때문에 두 명이 케이크를 나누어 먹기로 했다. 케이크는 둥그런 모양을 하고 있다. 어느 점에서부터 직선으로 칼집을 넣어 케이크를 N 개의 조각으로 나눈 뒤, 각 조각마다 1부터 N 까지 반시계방향으로 번호를 매긴다. 즉, 1 ≦ i ≦ N에 대해, i 번째 조각은 i - 1 번째와 i + 1 번째 조각과 인접해있다. (단, 0번째는 N 번째, N + 1 번째는 1번째로 간주한다). i 번째 조각의 크기는 Ai ..
알고리즘 Algorithm/BOJ 백준 (초급~중급) 2021. 7. 30. [BOJ 백준] 발전소 (1102) Java 링크 : https://www.acmicpc.net/problem/1102 문제 설명 : 더보기 은진이는 발전소에서 근무한다. 은진이가 회사에서 잠깐 잘 때마다, 몇몇 발전소가 고장이난다. 게다가, 지금 은진이의 보스 형택이가 은진이의 사무실로 걸어오고 있다. 만약 은진이가 형택이가 들어오기 전까지 발전소를 고쳐놓지 못한다면, 은진이는 해고당할 것이다. 발전소를 고치는 방법은 간단하다. 고장나지 않은 발전소를 이용해서 고장난 발전소를 재시작하면 된다. 하지만, 이때 비용이 발생한다. 이 비용은 어떤 발전소에서 어떤 발전소를 재시작하느냐에 따라 다르다. 적어도 P개의 발전소가 고장나 있지 않도록, 발전소를 고치는 비용의 최솟값을 구하는 프로그램을 작성하시오. 입력 : 더보기 첫째 줄에 발전소의 개수 N이 ..
알고리즘 Algorithm/BOJ 백준 (초급~중급) 2021. 7. 30. [BOJ 백준] 외판원 순회 (2098) Java, C 링크 : https://www.acmicpc.net/problem/2098 문제 설명 : 더보기 외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자. 1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이..
알고리즘 Algorithm/BOJ 백준 (초급~중급) 2021. 7. 30. [BOJ 백준] Dance Dance Revolution (2342) Java 링크 : https://www.acmicpc.net/problem/2342 문제 설명 : 더보기 승환이는 요즘 "Dance Dance Revolution"이라는 게임에 빠져 살고 있다. 하지만 그의 춤 솜씨를 보면 알 수 있듯이, 그는 DDR을 잘 하지 못한다. 그럼에도 불구하고 그는 살을 뺄 수 있다는 일념으로 DDR을 즐긴다. DDR은 아래의 그림과 같은 모양의 발판이 있고, 주어진 스텝에 맞춰 나가는 게임이다. 발판은 하나의 중점을 기준으로 위, 아래, 왼쪽, 오른쪽으로 연결되어 있다. 편의상 중점을 0, 위를 1, 왼쪽을 2, 아래를 3, 오른쪽을 4라고 정하자. 처음에 게이머는 두 발을 중앙에 모으고 있다.(그림에서 0의 위치) 그리고 게임이 시작하면, 지시에 따라 왼쪽 또는 오른쪽 발을 움직인..
알고리즘 Algorithm/BOJ 백준 (초급~중급) 2021. 7. 29. [BOJ 백준] 카드 게임 (11062) Java 링크 : https://www.acmicpc.net/problem/11062 문제 설명 : 더보기 근우와 명우는 재미있는 카드 게임을 하고 있다. N개의 카드가 일렬로 놓여 있다. 각 카드에는 점수가 적혀있다. 근우부터 시작하여 번갈아가면서 턴이 진행되는데 한 턴에는 가장 왼쪽에 있는 카드나 가장 오른쪽에 있는 카드를 가져갈 수 있다. 카드가 더 이상 남아있지 않을 때까지 턴은 반복된다. 게임의 점수는 자신이 가져간 카드에 적힌 수의 합이다. 근우와 명우는 서로 자신의 점수를 가장 높이기 위해 최선의 전략으로 게임에 임한다. 놓여있는 카드의 개수 N과 카드가 놓여있는 상태가 주어졌을 때 근우가 얻는 점수를 구하는 프로그램을 작성하시오. 예를 들어 카드가 [4, 3, 1, 2]로 놓여있다고 하자. 근우는 ..

티스토리툴바