백준
-
BOJ) 순열 사이클 (10451번)알고리즘/백준 2021. 2. 15. 14:58
순열 사이클 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 1 ~ N 으로 이루어진 순열을 방향 그래프로 나타냈을 때, 몇 개의 사이클이 존재하는지 구하는 문제다.각 Node에서 다음 Node의 vertex를 가지고 있고, 이 정보가 주어지기 때문에 배열을 활용했다.또한, find-union에서 착안하여 연결되는 지점을 DFS로 찾아가며 문제를 해결했다. 사이클을 형성하는지 확인하는 isCycle 메소드를 만들어 주었다.return 값은..
-
BOJ) 앱 (7579 번)알고리즘/백준 2021. 2. 15. 14:45
앱 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 스마트폰 앱을 이용하는데, 사용자에게 더욱 빠른 반응을 위해 백그라운드에서 앱이 돌아간다. 하지만, 메모리는 한계가 존재하기 때문에 새로운 앱을 실행시키기 위해서 백그라운드에서 돌아가는 앱 중 일부를 종료시켜야 한다. 종료된 앱을 다음에 이용할 때 드는 비용을 최소화하는 문제다. 설명이 조금 복잡해서 여러번 틀렸지만, 문제를 제대로 이해한 뒤의 풀이 자체는 어렵지 않았다. 우선, 실행중인 앱의 정보를 저장해주었다. 현재 메모리를 얼마나 차지하는지, 종료한 뒤에 나중..
-
BOJ) 다리 만들기알고리즘/백준 2021. 2. 14. 23:20
다리 만들기 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 여러 섬으로 이루어진 나라에서 가장 가까운 두 섬을 잇는 최단 거리 비용을 구하는 문제다. 최단 거리라고해서 해당 알고리즘들을 사용할 수 있을까 고민했는데, 떠오르지 않았다. 그래서 평소에 즐겨하던 grouping을 하면서, 모든 섬마다 전체 좌표를 List에 저장했다. 또한, 각 섬마다 위치를 식별할 수 있어야해서 위의 섬의 좌표를 저장하는 List를 List에 저장해주었다. List 으로 섬의 모든 좌표를 저장해주었다. 좌표를 모두 저장한 이후에는 각..
-
BOJ) 스도쿠 (2580 번)알고리즘/백준 2021. 2. 14. 23:13
스도쿠 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 스도쿠의 조건에 따라 로직을 짜주었고, 백트래킹을 이용했다. (백트래킹을 사용하지 않으면 시간초과가 난다) 우선, 재귀 함수를 사용할 예정이어서 모든 스도쿠 맵을 돌면서 빈칸인 곳을 찾는 것이 비효율적이라고 생각했다. 그래서, 스도쿠 맵을 저장할 때, 비어있는 칸의 위치를 List에 저장해서 빈 칸들만 순회하도록 만들었다. 그리고, 빈 칸들에 들어갈 수 있는 모든 수를 넣어보면서, 적합한 수를 넣어주었다. 모든 수를 검사할 때는 빈칸의 가로와 세로에 어떤..
-
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를 선택해서 친구 관계를 저장해주었다. 문제를 처음 봤을..