[Java] 백준 15683 (감시) Gold 5

Problem : https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net Approach BruteForce(완전탐색) + 구현 문제이다. 1 ~ 5번 연산을 구현해야 하고, 연산에 필요한 CCTV가 감시하고 있는 영역을 구현해야 한다. 먼저 1 ~ 5번 연산에 필요한 공통적인 부분을 구현해야 한다. (fiilLeft(), fillRight(), fillUp(), fillDown()) 위 4개 메소드는 현재 위치 (x, y)에서 XXX 방향..

→2021.06.11

Algorithm/Baekjoon Online Judge

[Java] 백준 16936 (나3곱2) Gold 5

Problem : https://www.acmicpc.net/problem/16936 16936번: 나3곱2 나3곱2 게임은 정수 하나를 이용한다. 가장 먼저, 정수 x로 시작하고, 연산을 N-1번 적용한다. 적용할 수 있는 연산은 두 가지 있고, 아래와 같다. 나3: x를 3으로 나눈다. x는 3으로 나누어 떨어져야 www.acmicpc.net Approach Backtracking으로 BruteForce(완전탐색)를 수행하는 문제이다. 만들 수 있는 모든 경우의 수를 탐색하기 위해 백트랙킹 기법을 사용하였다. 모든 숫자를 시작 숫자로 시도해 보아야 한다. 3으로 나누어 떨어지면, 3으로 나눈 수가 배열에서 아직 사용이 되지 않았는지 검사하고 재귀 호출한다. 2를 곱한 수가 배열에서 아직 사용이 되지 ..

→2021.06.10

Algorithm/Baekjoon Online Judge

[Java] 백준 17089 (세 친구) Gold 5

Problem : https://www.acmicpc.net/problem/17089 17089번: 세 친구 첫째 줄에 사람의 수 N(3 ≤ N ≤ 4,000), 친구 관계의 수 M(0 ≤ M ≤ 4,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계를 의미하는 두 정수 A, B가 주어진다. 친구 관계는 A와 B, 그리고 B와 A가 친 www.acmicpc.net Approach BruteForce(완전탐색) 문제이다. 먼저 입력을 받으면서 관계 배열 relations 을 구성한다. 또한, 특정 사람의 친구의 수를 기록한다. 세 친구 A, B, C 를 A = 0, B = 1, C = 2부터 시작하여 세 친구 ABC가 모두 친구인 경우를 찾고, 그 때의 최대 친구 수를 찾으면 된다. ABC의 친구를..

→2021.06.10

Algorithm/Baekjoon Online Judge

[Java] 백준 1981 (배열에서 이동) Gold 1

Problem : https://www.acmicpc.net/problem/1981 1981번: 배열에서 이동 n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다. 이와 같이 이동하다 보면, 배열에서 몇 개의 수를 www.acmicpc.net Approach 이분탐색 + BFS 문제이다. 꽤 어렵게 문제를 풀었다. 문제 풀이에 앞서, 입력을 받으면서 구해놔야 할 것이 있다. 배열의 값중 최솟값 minNum과 최댓값 maxNum을 이분탐색의 left와 right에 이용하기 때문이다. left는 0이다. (배열의 값이 모두 같은 경우 최대 - 최소 = 0이다.) right는 maxNum - minN..

→2021.06.09

Algorithm/Baekjoon Online Judge

[Java] 백준 1561 (놀이 공원) Gold 2

Problem : https://www.acmicpc.net/problem/1561 1561번: 놀이 공원 첫째 줄에 N(1 ≤ N ≤ 2,000,000,000)과 M(1 ≤ M ≤ 10,000)이 빈칸을 사이에 두고 주어진다. 둘째 줄에는 각 놀이기구의 운행 시간을 나타내는 M개의 자연수가 순서대로 주어진다. 운행 시간은 1 이상 30 www.acmicpc.net Approach 이분탐색을 이용하여 풀이가 가능한 문제이다. 먼저 n이 m이하일 경우, 0초에 모든 사람들이 놀이기구에 탑승할 수 있으므로 n번째 놀이기구가 마지막 사람이 타는 놀이기구가 될 것이다. 위 경우가 아니라면, 문제를 푸는 주요 로직은 다음과 같다. 먼저 n -= m 을 수행한다. (0초에 m명이 놀이기구를 탈 수 있기 때문이다.)..

→2021.06.06

Algorithm/Baekjoon Online Judge

[Java] 백준 13397 (구간 나누기 2) Gold 4

Problem : https://www.acmicpc.net/problem/13397 13397번: 구간 나누기 2 첫째 줄에 배열의 크기 N과 M이 주어진다. (1 ≤ N ≤ 5,000, 1 ≤ M ≤ N) 둘째 줄에 배열에 들어있는 수가 순서대로 주어진다. 배열에 들어있는 수는 1보다 크거나 같고, 10,000보다 작거나 같은 자연수 www.acmicpc.net Approach 이분탐색을 이용한 문제이다. 문제에서 말한 점수의 최솟값은 구간의 크기가 1일 때, 0이다. 점수의 최댓값은 최대 요소값 - 최소 요소값이지만, 편의상 최대 요소값 - 1로 이분탐색의 left와 right를 정해도 상관없다. 이분탐색을 진행하면서 해당 값을 만족시키는 구간의 개수가 m개 초과인지 아닌지 판단한다. 초과라면, 해..

→2021.06.05

Algorithm/Baekjoon Online Judge

[Java] 백준 1939 (중량제한) Gold 4

Problem : https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리 www.acmicpc.net Approach 이분탐색과 DFS/BFS를 사용하는 문제이다. 먼저 입력을 받으면서 그래프를 구성한다. 와중에 중량제한의 최솟값과 최댓값 또한 같이 구한다. 이 두 값이 이분탐색에 쓰일 left와 right가 될 것이다. 이 중량제한 값을 이용하여 BFS를 수행한다. 시작 섬을 출발하여 도착 섬에 도달할 수 있다면, ans를 갱신하..

→2021.06.04

Algorithm/Baekjoon Online Judge

[Java] 백준 1377 (버블 소트) Gold 3

Problem : https://www.acmicpc.net/problem/1377 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net Approach 정렬을 활용한 문제이다. 문제에서 소개한 버블정렬 알고리즘은 해당 리스트를 맨 뒤부터 채우는 정렬 방법이다. 문제에서 물어보는 것은 완전히 정렬될 때까지, 외부 for문이 몇번 돌아가는지를 물어보는 것이다. 한 번의 외부 for문을 돌릴 때, 리스트의 한 요소 a는 오른쪽으로는 최대 리스트의 끝까지 움직일 수 있고, 왼쪽으로는 1칸 움직일 ..

→2021.06.03

Algorithm/Baekjoon Online Judge

[Java] 백준 1933 (스카이라인) Gold 2

Problem : https://www.acmicpc.net/problem/1933 1933번: 스카이라인 첫째 줄에 건물의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 N개의 건물에 대한 정보가 주어진다. 건물에 대한 정보는 세 정수 L, H, R로 나타나는데, 각각 건물의 왼쪽 x좌표, 높이, 오 www.acmicpc.net Approach 우선순위 큐(PriorityQueue)와 TreeMap 자료구조를 활용하는 문제이다. 문제에서 원하는 것은 높이가 변하는 부분의 x좌표와 그 때의 최대높이이다. 이를 위해 우선순위 큐와 TreeMap을 사용한다. 우선순위 큐는 x좌표 기준 오름차순(같을 경우, 높이 기준 내림차순)으로, 트리맵은 높이 기준 내림차순의 정렬 기준을 규정한다..

→2021.06.03

Algorithm/Baekjoon Online Judge

[Java] 백준 21776 (가희와 읽기 쓰기 놀이) Gold 4

Problem : https://www.acmicpc.net/problem/21776 21776번: 가희와 읽기 쓰기 놀이 1번째 줄에 N, C가 공백으로 구분되어 주어집니다. 2번째 줄 부터 N+1번째 줄까지 1번 사람부터 N번 사람까지 낸 카드의 갯수와 카드를 낸 순서가 주어집니다. 예를 들어 3번째 줄에 3 2 4 5 가 있다면 www.acmicpc.net Approach 중복된 요소로 만드는 순열 알고리즘과 문자열 처리가 필요한 문제이다. 주어진 카드 개수로 순열을 만들되, 특정 카드 집합의 순서가 유지되어야 한다. 만약 1번 사람이 3,2,1 순으로 카드를 사용하고 2번 사람이 4,5 순으로 카드를 사용한다면 (1번, 1번, 1번, 2번, 2번)으로 만드는 수열과 같은 개수가 된다. (1번,2번..

→2021.06.02

티스토리툴바