알고리즘
-
BOJ) 종이의 개수 (1780 번)알고리즘/백준 2021. 2. 12. 16:11
종이의 개수 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. www.acmicpc.net N by N 크기의 종이가 있고, 각 칸에는 -1, 0, 1 세 숫자 중 하나가 저장되어있다. 이 종이는 아래의 규칙에 따라 사용한다. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다. (1)이 아닌 경우에는 종이를 같은 크기의 9개의 종이로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다. 위의 규칙에 따라 종이를 잘랐을 때, 각각 -1, 0, 1로만 채워진 종이의 개수를 구하는 문제다. 일단 규칙에 따라..
-
BOJ) 플로이드 (11404 번)알고리즘/백준 2021. 2. 12. 16:00
플로이드 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 모든 도시의 쌍 (A, B)에 대해서 도시 A -> 도시 B로 가는데 필요한 비용의 최솟값을 구하는 문제다. 사실, 최단거리를 보면 다익스트라를 가장 먼저 떠올렸을 것이다. 플로이드-워셜에 분류되어 있어서 플로이드-워셜 방법으로 접근을 했다. 근데, 다시 생각해보면, 모든 경로를 구해야하기 때문에, 모든 도시의 쌍 (A,B)의 거리를 다익스트라로 구한다고하면, 시간이 더욱 오래 걸릴 것 같다. 모든 도시의 쌍의 최단 거리 정보를 저장해두는 플로이드 워셜이..
-
BOJ) 극장 좌석알고리즘/백준 2021. 2. 12. 15:52
극장 좌석 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 1 ~ N 까지 극장에 좌석이 존재한다. VIP 티켓을 가진 사람은 티켓에 적힌 번호에 딱 앉는다. 나머지 일반 티켓의 경우 좌우로 1씩 증감한 번호에 앉을 수 있다. 이 때, 좌석에 배치할 수 있는 좌석표의 경우의 수를 구하는 문제다. 문제 자체는 크게 어렵지 않았다. N =1 일 때, 1가지 경우가 존재하고, N =2 일 때, 2가지 경우 (1, 2) 와 (2,1)이 존재한다. N =3 일 때, (1,2,3), (1,3,2), (2,1,3)이 존재한다. 같은 ..
-
BOJ) ABCDE (13023 번)알고리즘/백준 2021. 2. 12. 15:44
ABCDE 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 문제 설명 N 명이 0 ~ N-1의 번호가 매겨져 있고, 친구 관계가 주어진다. 이 때, 아래와 같이 A, B, C, D, E의 친구 관계가 존재하는지 알아보는 문제다. A는 B와 친구다. B는 C와 친구다. C는 D와 친구다. D는 E와 친구다. 친구 관계기 때문에, 단방향 그래프가 아닌 양방향 그래프로 생각해야한다. 또한, 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000) 으로 주어지기 때문에, 최악의 상황이 아닌 경우의 불필요한 loop를 줄이기 위해 List를 선택해서 친구 관계를 저장해주었다. 문제를 처음 봤을..
-
BOJ) 키 순서 (2458 번)알고리즘/백준 2021. 2. 10. 16:39
키 순서 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net Floyd Warshall 아래는 위키에 설명된 내용을 가져왔다. 플로이드-워셜 알고리즘은 동적 계획법의 한 예로, 로버트 플로이드가 1962년에 현재 알려진 형태로 발표했다.[3] 하지만, 이 알고리즘은 본질적으로 버나드 로이가 1959년에 발표한 알고리즘[4]과, 스티븐 워셜이 1962년에 발표한 알고리즘[5]과 그래프의 추이적 폐포를 찾는다는 점,[6]그리고 결정적 유한 오토마타를 정규 표현식으로 변환할 때, 클레이니 알고리즘(1956년에 발표됨)과..
-
BOJ) 치즈알고리즘/백준 2021. 2. 5. 18:24
치즈 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 처음에는, 4면을 검사하면서 공기와 접촉하지 않은 치즈들의 지워지는 시간을 1시간씩 증가 시켰었다. 하지만, 문제의 조건에서 모든 공기가 치즈를 녹이는 것이 아니라, 가장 외부에 있는 공기들만 치즈를 녹인다는 조건이 있었다. 또한, 맵의 테두리는 공기로만 주어진다는 조건이 있어서 BFS를 이용했다. 외부 공기의 위치와 가장 외부에 노출된 치즈의 위치를 저장할 큐 두 개를 선언해주었다. 0,0을 시작으로 외부 공기를 큐에 저장하면서, 가장 외부에 닿은 치즈들의 좌표 또한 다른 ..
-
BOJ) 보석알고리즘/백준 2021. 2. 5. 00:16
보석 2492번: 보석 첫째 줄에 4개의 정수 N, M, T, K가 빈칸을 사이에 두고 주어진다. N은 지도의 너비를 나타내고, M은 지도의 높이를 나타낸다(1 ≤ N, M ≤ 1,000,000). T는 금강석의 개수를 나타내고, K는 정사각형의 크 www.acmicpc.net 정말 어려운 문제였다. M by N 크기의 map이 주어지는데, 이 맵에 금강석이 묻혀있는 정보가 주어진다. n과 m은 1 ~ 1,000,000의 숫자로 주어지고, 금강석은 최대 100개 까지 주어진다. 또한, 정사각형의 한 변의 길이가 되는 k가 주어지는데, 이 정사각형을 임의로 맵에 그렸을 때, 가장 많은 금강석을 갖게되는 정사각형의 왼쪽 위 꼭짓점의 위치와 금강석의 개수를 출력하는 문제다. 우선, 이 문제가 슬라이딩 윈도우로..
-
BOJ) 멀티탭 스케줄링알고리즘/백준 2021. 2. 5. 00:02
멀티탭 스케줄링 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net N개의 구멍이 있는 멀티탭이 주어지고, 멀티탭 사용을 해야하는 전자제품의 순서가 K 개 주어진다. 전자제품은 1 ~ K 번의 고유 숫자를 가지고 있다. 코드는 O(k^2*n)의 시간 복잡도를 보이지만, N과 K의 최댓값이 100이기 때문에 크게 적당히 빠른 속도를 보여준다. 우선 멀티탭에 꽂혀있는 전자제품을 파악하기 위해 list를 선언해주었다. k개의 대기 열을 돌면서, 멀티탭에 구멍이 있는지 확인했다.남은 구멍이 없는 경우, 현재 멀티탭에 꽂..