본문 바로가기

💯 | 백준/😐 | Gold9

[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, G5] 백준 10827번 a^b a^b(10827번)Gold 5#임의 정밀도 / 큰 수 연산https://www.acmicpc.net/problem/10827 문제 내용 문제 접근a에 소수가 들어오고, b에 지수가 들어올 때, a의 b제곱을 구하기.소수(a)의 b제곱이라, 소수를 정확히 계산할 BigDecimal을 사용한다. 문제 해결 코드더보기import java.io.BufferedReaderimport java.io.InputStreamReaderimport java.math.BigDecimalfun main() = with(BufferedReader(InputStreamReader(System.`in`))) { val input = readLine().split(" ") val a = BigDecimal(input.. 2024. 9. 19.

[Kotlin, G1] 백준 1300번 K번째 수 K번째 수(1300번)Gold 1#이분 탐색 #매개 변수 탐색https://www.acmicpc.net/problem/1300 문제 내용 문제 접근문제 자체는 이해하는 데 어렵지 않다.배열의 index는 1부터 시작한다. 각 배열에 들어 있는 수들은 각 index의 곱이다.그러므로 표로 나타내 보면 아래와 같다.위 표에는 5 * 5 크기의 2차원 배열에 들어갈 수들을 나열해 놨다.각 index의 곱으로 이루어져 있다.모든 값들은 각 줄에 해당하는 배수들로 이루어져 있는 것을 볼 수 있다.1번째 줄은 1의 배수, 2번째 줄은 2의 배수 ... 5번째 줄은 5의 배수로 이루어져 있다. 입력 예제에서는 3 * 3의 2차원 배열의 값들을 정렬했을 때, 7번째 값을 불러와야 한다.우선 배열 데이터를 정렬해 보면.. 2024. 9. 9.

[Kotlin, G5] 백준 16928번 뱀과 사다리 게임 뱀과 사다리 게임(16928번)Gold 5#그래프 이론 #그래프 탐색 #너비 우선 탐색https://www.acmicpc.net/problem/16928 문제 내용 문제 접근1부터 100번째 칸까지 존재하는 뱀과 사다리 게임판이 존재할 때, n개의 사다리와 m개의 뱀이 있다.사다리를 밟으면 위로 이동하고 뱀을 밟으면 아래로 내려간다.입력 예제 1을 예로 들면3 732 6242 6812 9895 1397 2593 3779 2775 1949 4767 17사다리가 3개, 뱀이 7개 있고 2번째 줄부터 순서대로 사다리, 뱀을 입력받는다.숫자 2개가 있는데, 사다리 32 62를 예로 들면 32를 밟게 되면 62로 이동하고, 4번째 줄인 뱀 95 13의 경우는 95를 밟으면 13으로 내려간다. 주사위를 적게 돌리.. 2024. 8. 12.

[Kotlin, G5] 백준 1013번 Contact Contact(1013번)Gold 5#문자열 #정규 표현식https://www.acmicpc.net/problem/1013 문제 내용 문제 접근입력받은 숫자 코드가 (100+1+ | 01)+ 을 만족하는지 확인해야 한다.위의 예시에서 봤다시피, +기호는 특정 문자가 반복해서 나오는 것을 뜻한다.100+의 경우에는 100, 10000, 1000000... 와 같은 숫자들이 100+ 를 만족한다.(01)+의 경우에는 괄호 안의 숫자들이 반복돼서 나오는 것을 뜻한다.01, 0101, 010101... 와 같은 숫자들이 (01)+ 을 만족한다. 우리가 확인해야 할 패턴은 (100+1+ | 01)+은1. 10 다음에 0이 반복된다. 그리고 반복이 끝나면 1이 반복된다.2. 01로 끝난다.패턴 1 또는 2가 반복.. 2024. 8. 7.

[Kotlin, G5] 백준 1011번 Fly me to the Alpha Centauri Fly me to the Alpha Centauri(1011번)Gold 5#수학 문제 내용 문제 접근수학적으로 접근하면 반복문을 사용하지 않고도 문제를 해결할 수 있다.먼저 장치가 작동하는 횟수를 기준으로 거리와 최댓값을 확인하면 다음과 같다.이 표를 보면 3가지의 규칙을 확인할 수 있다.1. 최댓값이 증가하면서 2번씩 반복된다.2. 거리는 이전의 거리에서 현재의 최댓값을 더한 값과 같다.3. 최댓값이 변하는 지점은 항상 최댓값의 제곱 값이다. 사진 1-1의 표를 이용해 거리의 사이에 존재하는 데이터들의 값들도 표로 나타내 보자.분량 문제상 거리가 8부터 16까지의 데이터들에서 최댓값과 장치 작동 횟수를 구해 보겠다.녹색이 최댓값이 변하는 구간, 노란색이 작동 횟수가 변하는 구간이다.녹색의 경우는 위에서.. 2024. 7. 30.

[Kotlin, G3] 백준 2812번 크게 만들기 크게 만들기(2812번)Gold 3#자료 구조 #그리디 알고리즘 #스택 문제 내용 문제 접근n자리의 숫자가 주어지고, 숫자에서 k개의 숫자를 뺀 숫자의 경우들 중, 가장 큰 값을 출력해야 한다.가장 큰 값을 얻기 위해서는 맨 앞자리의 수가 제일 크고, 마지막 자릿수가 제일 작은 내림차순의 숫자에 가까워져야 제일 커진다.stack에 값을 넣으면서 들어간 값보다 더 큰 수가 들어오면 stack에 들어간 숫자를 빼는 방식으로 stack을 사용해야 한다.k번 숫자를 지우고 나면 나머지 숫자들은 그대로 stack에 넣어서 출력해 주면 된다. 문제 해결 코드더보기import java.io.BufferedReaderimport java.io.InputStreamReaderimport java.util.Stackpr.. 2024. 7. 29.

[Kotlin, G5] 백준 7569번 토마토 토마토(7569번)Gold 5#그래프 이론 #그래프 탐색 #너비 우선 탐색 문제 내용 문제 접근비슷한 문제인 토마토(7576)와는 상자를 여러 개를 받아 3차원으로 작업해야 하는 것이 다르다.입력을 받을 때, 미리 생성한 ArrayDeque에 1(익은 토마토)이 들어 있으면 x, y, z, 0을 리스트로 받아서 넣어 준다.x, y, z는 익은 토마토의 좌표이고, 0은 경과한 날짜를 뜻한다. 나중에 0을 하나씩 더해 가면서 경과 날짜를 체크할 것이다.3차원 리스트에 입력값을 모두 넣어 주고 나서, 토마토를 bfs를 이용해 현재 토마토의 위치를 담은 ArrayDeque에 있는 값을 하나씩 빼면서 뺀 값의 x, y, z에서 앞, 뒤, 오른쪽, 왼쪽, 위, 아래에 해당하는 토마토들을 확인해서 덜 익은 토마토(0.. 2024. 7. 29.

이전 1 다음

728x90

티스토리툴바