본문 바로가기

💯 | 백준69

[Kotlin, S1] 백준 2468번 안전 영역 안전 영역(2468번)Silver 1#그래프 이론 #브루트포스 알고리즘 #그래프 탐색 #너비 우선 탐색 #깊이 우선 탐색 문제 내용 문제 접근n * n의 영역에서 내리는 비의 양에 따라서 잠기는 영역이 생기게 된다.영역이 3일 때, 비의 양이 3 이상이면 모든 영역 3이 잠기게 된다. 영역의 개수는 상하좌우에 붙어있는 모든 안전 영역들은 하나로 간주한다.대각선의 안전 영역은 모두 별개의 안전 영역이 된다. 내리는 비의 양에 따라 잠기는 영역의 수가 달라지게 될 것이다.물에 잠기지 않은 영역의 수의 최대 개수를 구한다. 비의 양은 영역에서 가장 작은 값에서부터 가장 큰 값까지 정의하고 탐색해 보면 될 거라고 생각하기 쉽다.하지만 영역에서 가장 큰 값으로 구해봤자 모든 영역이 잠기게 되기 때문에 굳이 구할 .. 2025. 1. 19.

[Kotlin, G5] 백준 11000번 강의실 배정 강의실 배정(11000번)Gold 5#자료 구조 #그리디 알고리즘 #정렬 #우선순위 큐https://www.acmicpc.net/problem/11000 문제 내용 문제 접근강의실을 최대한 적게 사용해 n개의 수업을 모두 진행해야 한다.강의의 시작 시간과 종료 시간을 참고해 모든 강의를 진행하는 데 필요한 최소 강의실의 개수를 구해야 한다. 각각의 강의들 중 강의 시작 시간이 강의 종료 시간보다 작거나 같을 때는 한 강의실에서 같이 들을 수 있다.예를 들어 시작 시간이 1이고 종료 시간이 3인 강의와 시작 시간이 3이고 종료 시간이 5인 강의는 한 강의실에서 같이 들을 수 있다. 강의들 중 제일 먼저 시작하는 강의부터 시작해 한 강의실에서 쓸 수 있는 강의들을 모두 제거하면서 문제를 해결하면 된다.예.. 2025. 1. 18.

[Kotlin, S2] 백준 14247번 나무 자르기 나무 자르기(14247번)Silver 2#그리디 알고리즘 #정렬 문제 내용 문제 접근n일 동안 나무를 잘라서 얻을 수 있는 나무의 최대 양을 구한다.첫날의 나무는 n개의 나무가 각각 h의 높이를 이루고 있고 날이 지날 때마다 hⁱ 에 해당하는 aⁱ 만큼 나무가 자라게 된다. 문제를 보면 날마다 자라는 나무의 높이가 다르기 때문에 매일 제일 높이가 높은 나무를 고르는 것으로 문제를 해결할 수 있다고 생각하기 쉽다.하지만 그 방법은 최적해가 아니다. 우리는 제일 덜 자라는 나무부터 시작해서 제일 잘 자라는 나무 순서대로 나무를 골라야 한다.나무가 잘 자랄수록 나중 갈수록 나무의 높이가 매우 커지기 때문에 매일 제일 높이가 높은 나무를 고르는 것보다 더 많이 나무를 고를 수 있데 된다. 이제 이 아이디어를 .. 2025. 1. 14.

[Kotlin, S1] 백준 2205번 저울 추 만들기 저울 추 만들기(2205번)Silver 1#수학 #그리디 알고리즘https://www.acmicpc.net/problem/2205 문제 내용 문제 접근1부터 n까지의 무게를 가진 납과 주석을 합쳐서 2의 제곱수의 무게를 가지는 저울추를 만들어야 한다.각 무게를 가지는 덩어리는 중복해서 사용이 불가능하다. n이 1부터 5까지 이루어져 있을 때, n이 5일 때는 3을 대입해서 8을 만들 수 있다. 4일 때는 주석의 무게를 추가해서 (4, 4) 조합으로 8을 만들 수 있고 주석이 3일 때는 (3, 5)의 조합으로 저울추를 만들 수 있다.정의된 무게를 만들기 위해 주석이 커지면 납이 작아지고, 납이 커지면 주석이 작아지는 특징을 이용해 중복을 허용하지 않고 주석의 무게를 구성할 수 있게 된다. 저울추의 무게는.. 2025. 1. 7.

[Kotlin, S2] 백준 1780번 종이의 개수 종이의 개수(1780번)Silver 2#분할 정복 #재귀https://www.acmicpc.net/problem/1780 문제 내용 문제 접근종이가 -1 또는 0 또는 1로 모두 채워지지 않았을 때, 정확히 9등분을 해 다시 종이가 -1 또는 0 또는 1인지 확인해서-1, 0, 1로 채워진 종이의 개수를 세서 출력하면 된다. 시작 좌표와 확인할 size를 정한 다음, 시작 좌표에서 size만큼의 범위를 확인해 숫자의 개수를 세주는 방식의 재귀 호출을 통해 해결할 수 있다. 문제 해결 코드더보기import java.io.BufferedReaderimport java.io.InputStreamReaderprivate var paper = arrayOf(arrayOf())private var cntMinu.. 2024. 12. 18.

[Kotlin, S3] 백준 32186번 역시 내 이세계 수열은 잘못됐다 역시 내 이세계 수열은 잘못됐다(32186번)Silver 3#수학 #그리디 알고리즘https://www.acmicpc.net/problem/32186 문제 내용 문제 접근각 위치에 맞는 index의 값 2개를 +k 연산과 +1 연산을 이용해 같은 값으로 만들어야 하는 최소 연산 횟수를 출력한다. 값 2개 중 작은 값을 큰 값에 딱 맞게 만드는 방법과작은 값에 +k 연산을 반복해 큰 값보다 커지도록 만들고 큰 값에 +1 연산을 해서 값을 맞추는 방법이 있다. 예를 들어 k가 7이고 5와 28이 매칭되는 값일 때5를 28로 만들기 위해서는 5에 7을 3번 더하고 1을 2번 더하면 28이 된다(연산 횟수 5번).그리고 5에 7을 4번 더하면 33이 되는데, 28에 1을 5번 더하면 두 값이 모두 33이 된다.. 2024. 12. 18.

[Kotlin, B1] 백준 10275번 골드 러시 골드 러시(10275번)Bronze 1#수학 #구현https://www.acmicpc.net/problem/10275 문제 내용 문제 접근a, b 중에 하나를 2의 제곱수만을 이용해 만들어야 한다.예를 들어 24는 16 + 8로 만들 수 있는데, 이때 차수가 가장 적은 수를 만들기 위해 2의 n제곱한 수에서 몇 번을 반으로 잘라야 만들 수 있는지 구하면 된다.a, b에 정확히 요구된 수만큼만 들어가야 한다는 것과 a + b가 2의 n제곱과 같기 때문에 a와 b 중 하나만 구해도 나머지를 구할 수 있게 되기 때문에 이를 생각하게 되면 하나만 구해도 된다는 것을 알게 될 것이다. 문제 해결 코드더보기import java.io.BufferedReaderimport java.io.InputStreamRead.. 2024. 12. 14.

[Kotlin, S2] 백준 26007번 Codepowers Codepowers(26007번)Silver 2# 누적 합 문제 내용 문제 접근각 쿼리는 시작 라운드(포함), 종료 라운드(미포함)의 사이에 진행된 라운드마다의 현재 레이팅을 구해서 k보다 낮은 레이팅의 개수를 구해서 출력하면 된다. 문제 내용은 단순하지만 왜 silver 2씩이나 받았는지 생각해봐야 한다. 문제 해결 코드더보기import java.io.BufferedReaderimport java.io.InputStreamReaderimport java.util.StringTokenizerfun main() { val bf = BufferedReader(InputStreamReader(System.`in`)) // n: round, x: 초기 레이팅, m: 쿼리의 개수, k: 낮은 레이팅.. 2024. 12. 3.

[Kotlin, S4] 백준 2090번 조화평균 조화평균(2090번)Silver 4#수학 #구현 #정수론 #유클리드 호제법 문제 내용 문제 접근입력받는 수들을 모두 역수로 바꾼 값들의 합을 분수 형태로 변환 후 그 값의 역수를 출력하는 문제이다.1, 2, 4가 들어왔으면 1 + 1/2 + 1/4 = 7/4를 역수로 출력해서 정답이 4/7이 되는 방식이다. 입력값들의 역수를 더하려면 통분이 필요한데, 통분은 입력값들의 최소공배수를 이용해 통분을 진행하면 된다.주의해야 하는 점은 출력을 가장 적은 수의 문자를 사용하는 답을 출력하라고 돼 있는데, 이를 쉽게 풀면 약분해서 출력하라는 뜻이기 때문에 약분까지 진행해서 출력해야 한다. 문제 해결 코드더보기import java.io.BufferedReaderimport java.io.InputStreamRea.. 2024. 11. 25.

[Kotlin, S4] 백준 16471번 작은 수 내기 작은 수 내기(16471번)Silver 4#그리디 알고리즘 #정렬https://www.acmicpc.net/problem/16471 문제 내용 문제 접근사장님이 뽑은 카드에서 이기기 위해 낼 수 있는 가장 큰 카드를 계속 냈을 때, 더 이상 이기는 수가 없을 경우, 이긴 횟수에 2를 곱해서 카드의 개수보다 크다면 YES를 출력하고, 아니면 NO를 출력하면 된다. 입력 예제를 예로 들면,2 1 3 5 61 1 3 2 5 아래가 사장님의 카드고, 위가 주언의 카드일 때, 사장님이 카드를 큰 순서대로 뽑게 되면 5, 3, 2, 1, 1의 순서대로 뽑게 된다.주언이 카드를 뽑아 사장님을 이기려면,사장님이 5를 뽑았을 때, 5보다 작은 카드인 1, 2, 3 중에서 제일 큰 3을 고르고,사장님이 3을 뽑으면 주언이.. 2024. 11. 17.

[Kotlin, S5] 백준 11116번 교통량 교통량(11116번)Silver 5#구현 #브루트포스 알고리즘https://www.acmicpc.net/problem/11116 문제 내용 문제 접근다리의 왼쪽에서 오는 차들(들어오는 차)의 시간과 오른쪽으로 나가는 차들의 시간이 주어졌을 때, 문제에 언급된 규칙을 이용해 다리를 지난 차들이 몇 대인지 구하면 된다. 왼쪽에서 오는 차의 시간이 t, t + 500이고, 오른쪽으로 나간 시간이 t + 1000, t + 1500이 있는 경우가 다리를 지난 차가 된다. 문제 해결 코드더보기import java.io.BufferedReaderimport java.io.InputStreamReaderfun main() { val bf = BufferedReader(InputStreamReader(Syste.. 2024. 11. 15.

[Kotlin, S2] 백준 2232번 지뢰 지뢰(2232번)Silver 2#그리디 알고리즘 #정렬https://www.acmicpc.net/problem/2232 문제 내용 문제 접근지뢰를 모두 터트리는 최소 개수를 구해야 한다.직접 터트리는 지뢰의 개수를 최소로 하려면 연쇄적으로 터지는 지뢰의 개수가 많은 곳을 위주로 터트리면 된다. 직접 터트리는 지뢰의 위치에서 왼쪽 방향은 오름차순으로 수가 정렬되어 있어야 하고, 오른쪽 방향은 내림차순으로 정렬되어 있어야 한다.예를 들어 다음과 같이 지뢰가 있을 때,1 2 5 4 3 3 6 6 2 3, 7, 8번의 지뢰를 직접 터트리면 모든 지뢰를 제거할 수 있다. 지뢰가 연쇄적으로 터지려면 왼쪽은 오름차순으로 중복 없이 정렬되어 있어야 하고, 오른쪽은 내림차순으로 중복 없이 정렬되어 있어야 한다. 오름.. 2024. 10. 21.

[Kotlin, B1] 백준 31432번 소수가 아닌 수 3 소수가 아닌 수 3(31432번)Bronze 1#수학 #애드 혹 #정수론 문제 내용 문제 접근n개의 숫자를 사용해서 소수가 아닌 수가 있으면 yes를 출력하고 소수가 아닌 수 하나를 아무거나 출력하고, 소수가 아닌 수가 없을 때는 no를 출력하는 문제이다.각 숫자는 중복해서 사용할 수 있다. 약간의 수학적 고민이 필요한 문제이다. 같은 숫자를 중복해서 쓸 수 있다는 경우 때문에 no가 나오는 경우는 하나도 없다.n개의 숫자가 2, 3, 5, 7인 경우에는 n의 숫자들이 모두 소수이지만, 같은 숫자를 여러 번 쓸 수 있으면 22, 33, 55, 77처럼 소수가 아닌 수를 언제든지 만들 수 있다는 뜻이 되기 때문에 n에 어떤 수가 나와도 no가 나오는 경우가 없어지는 것이다. 그러면 정답을 같은 수를 사용.. 2024. 10. 17.

[Kotlin, P4] 백준 10000번 원 영역 원 영역(10000번)Platinum 4#자료 구조 #정렬 #기하학 #스택https://www.acmicpc.net/problem/10000 문제 내용 문제 접근우선 문제 이해부터 해보자.간단하다.원을 x축에 구성하고 난 후, 영역을 세면 된다. 영역의 개수는 다음과 같이 세면 된다. 원의 영역과 원끼리 접하면서 나뉜 영역도 생각해야 하고, 원 바깥의 영역도 처리해야 한다.원끼리 접하면서 나뉘게 되는 영역을 나누는 방법을 생각해야 하기 때문에 어렵다. 초기 구현 아이디어를 떠올리기 위해 아래의 블로그를 참고해서 구현했다.https://wonyoung2257.tistory.com/79 [백준 python] 10000번 원 영역[백준 python] 10000번 원 영역 레벨: 플레티넘5 언어: 파이썬 htt.. 2024. 10. 14.

[Kotlin, G5] 백준 1711번 직각삼각형 직각삼각형(1711번)Gold 5#브루트포스 알고리즘 #기하학 #피타고라스 정리 문제 내용 문제 접근각 주어지는 점에서 무작위로 중복되지 않게 3개를 골라 만들 수 있는 직각삼각형의 개수를 구해야 한다.점의 개수가 1500개까지 있고, 시간제한이 5초이다.결정적으로 브루트포스 알고리즘으로 분류되어 있다.이는 최대 1500개의 점에서 3개를 골라야 할 때, 무지성 탐색이 가능하다는 뜻이다. 무지성 탐색에서 나온 3개의 점에서 각 점 사이의 길이를 구하고 그 길이를 피타고라스 정리 공식을 이용해 직각삼각형인지 파악하면 된다.두 점 (x1, y1), (x2, y2)가 있을 때, 두 점사이의 거리는(x2 - x1) * (x2 - x1)의 제곱 + (y2 - y1) * (y2 - y1)의 제곱에 루트를 씌운 값.. 2024. 10. 1.

[Kotlin, G4] 백준 9935번 문자열 폭발 문자열 폭발(9935번)Gold 4#자료 구조 #문자열 #스택https://www.acmicpc.net/problem/9935 문제 내용 문제 접근첫 번째 줄의 문자열에서 두 번째 문자열이 존재하지 않을 때까지 문자열을 제거한 결과를 출력하는 문제.문자열이 제거되고 남은 문자열들은 서로 붙어서 새 문자열이 된다. 단순히 문자열을 확인해 보면서 문자열을 제거해 나가면 되는 간단한 문제이다.그래서 일단은 replace를 반복시켜서 진행해 보았다.while (true) { val replaceRes = string.replace(removeStr, "") if (replaceRes != string) string = replaceRes else break}결과는 메모리 초과, 애초에 repl.. 2024. 10. 1.

[Kotlin, S2] 백준 14430번 자원 캐기 자원 캐기(14430번)Silver 2#다이나믹 프로그래밍https://www.acmicpc.net/problem/14430 문제 내용 문제 접근wook이 0, 0에서 n, m까지 이동할 때, 오른쪽, 아래쪽으로만 이동하면서 자원을 캘 수 있을 때, n, m까지 도달했을 때, 얻을 수 있는 자원의 최대 개수를 구해야 한다. 얻을 수 있는 최대 자원 개수를 구하는 방법은 입력 예제 1을 예로 설명해 주겠다.5 40 1 0 00 0 1 01 1 0 01 0 1 01 1 0 0// init dp array0 0 0 00 0 0 00 0 0 00 0 0 00 0 0 0 처음의 0, 0 부분은 입력값을 그대로 사용한다.그러면 2차원 array를 모두 0으로 초기화했을 때 0, 0에는 0 또는 1이 오게 될 것이.. 2024. 9. 30.

[Kotlin, S4] 백준 2358번 평행선 평행선(2358번)Silver 4#자료 구조 #정렬 #해시를 사용한 집합과 맵https://www.acmicpc.net/problem/2358 문제 내용 문제 접근2개 이상의 점을 지나는 선분에서 x축 또는 y축에 평행한 선분의 개수를 세는 문제.선분의 구성이 2개 이상의 점을 지날 수도 있고, 한 좌표에 점이 여러 개가 있을 수도 있다.// 선분의 구성에 2개 이상의 점이 쓰이는 경우41 02 03 04 0정답: 1// 한 좌표에 여러 점이 있는 경우21 11 1정답: 2첫 번째 case가 이해하기 어려웠다.문제를 처음 읽었을 때는 2개 이상의 점을 지나는 선분이라는 것을 못 보고 2개의 점을 지나는 선분이라고 생각해서 왜 1개가 나오는지 헷갈렸다.case 1의 경우에는 점 4개를 연결한 y축과 평행.. 2024. 9. 26.

[Kotlin, S5] 백준 32344번 유물 발굴 유물 발굴(32344번)Silver 5#구현 #기하학https://www.acmicpc.net/problem/32344 문제 내용 문제 접근운동장에 a번 유물이 w, h 위치에 묻혀 있다.a번 유물 조각들의 위치 정보를 이용해 a번 유물의 예상 크기를 직사각형으로 정의한다.직사각형의 넓이가 가장 큰 유물의 번호와 그 넓이를 출력한다.만약 넓이가 동일하다면 유물 번호가 더 작은 게 더 우선이다. 유물의 예상 크기 직사각형을 구하는 방법은 아래와 같다.예를 들어 4개의 위치에 유물이 있을 때점 a, b, c, d가 유물의 위치라고 하면 유물의 예상 크기는 사각형 efgh와 같다.위 사진으로 가장 큰 x축(d)과 가장 작은 x축(a), 그리고 가장 큰 y축(c)과 가장 작은 y축(b)의 값을 이용해 위 도형.. 2024. 9. 23.

[Kotlin, B1] 백준 32343번 드랍 더 비트 드랍 더 비트(32343번)Bronze 1#그리디 알고리즘 #브루트포스 알고리즘 #비트마스킹2024 HICON 홍익대학교 프로그래밍 경진대회 B번https://www.acmicpc.net/problem/32343 문제 내용 문제 접근n자리의 2진수에서 각각 1의 개수가 a, b개인 2진수 2개가 주어질 때, 두 2진수의 xor 연산 결과가 제일 큰 경우를 구해야 한다.n자리의 2진수에서 나올 수 있는 수는 2의 n승에 - 1만큼 나온다.예를 들어 3자리의 2진수에서 나올 수 있는 최댓값은 2의 3승에 -1이므로 7이다. 1부터 7까지 나올 수 있다는 뜻이다. 그래서 1부터 n자리의 2진수에서 나올 수 있는 최댓값만큼 반복해서 반복되는 수를 2진수로 변환 후, 1의 개수를 확인해서 1의 개수가 a, b개.. 2024. 9. 23.

[Kotlin, S4] 백준 9242번 폭탄 해체 폭탄 해체(9242번)Silver 4#구현 #문자열 #파싱https://www.acmicpc.net/problem/9242 문제 내용 문제 접근별 기호(*)와 공백으로 이루어진 숫자가 입력된다.숫자는 7 segment 숫자 표기법으로 이루어져 있다.그냥 숫자를 파싱 해서 6으로 나누어 떨어지면 beer를 출력하고 그렇지 않으면 boom을 출력하면 되는 간단한 문제이다. 또한 암호가 무조건 7 segment의 숫자들만 나오는 것도 아니다.암호는 3 * 5의 형태로 1칸씩 공백을 띄고 주어지게 되는데, 3 * 5의 암호 형식을 지키지 않은 코드가 올 수 도 있다.그래서 위 2가지 상황에 맞는 처리(boom)를 해주어야 한다. 문제 해결 코드더보기import java.io.BufferedReaderimpor.. 2024. 9. 20.

이전 1 2 3 4 다음

728x90

티스토리툴바