백준
-
[백준][Kotlin]1715번 카드 정렬하기백준 2023. 3. 21. 15:06
해당 문제는 카드 묶음이 적은 것 부터 비교를 해야 비교 횟수가 적게 나옴을 알 수있습니다. 그렇기에 현재 입력받은 자료 중 가장 작은 카드의 개수를 가진 2개를 뽑아 합친 후 현재 입력받은 자료에서 넣은 후 다시 정렬하여 비교하여 합니다. 저의 경우 처음에 2개의 카드 뭉치를 합친 후 자료에 다시 넣을 때 정렬을 해야되는 사실을 잊고 넣었다가 실패를 몇번 반복했었습니다. 하기는 제가 작성한 코드와 제출 결과 입니다. import java.io.BufferedReader import java.io.BufferedWriter import java.io.InputStreamReader import java.io.OutputStreamWriter import java.util.* fun main() { val..
-
[백준][Kotlin]11047번 문제 동전 0백준 2023. 3. 20. 19:28
해당 문제는 동전의 가치가 큰것부터 k원과 비교하여 같거나 클 경우 answer(정답) 에 k/동전의 가치 를 더한 후 k는 동전의 가치로 나눈 후 남은 나머지로 변경하며, 최종적으로 k가 0원이 되었을때 answer를 반환하면 되는 문제였습니다. 하기는 제가 작성한 코드와 제출 결과 입니다. import java.io.BufferedReader import java.io.BufferedWriter import java.io.InputStreamReader import java.io.OutputStreamWriter import java.lang.Math.max import java.util.* import kotlin.collections.ArrayList import kotlin.collections..
-
[백준][Kotlin]1300번 K번째 수백준 2023. 3. 20. 18:48
해당 문제는 문제를 봤을 때 어떤 알고리즘으로 풀어야하는지 떠오르기부터가 어려운 문제였습니다. 하나 확실했던 것은 문제의 설명 중 "첫째 줄에 배열의 크기 N이 주어진다. N은 10^5보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(10^9, N^2)보다 작거나 같은 자연수이다." 문구가 있어 N^2의 시간복잡도를 가지는 코드는 딱히 확인해 보지 않더라도 시간초과가 나온다는 것을 알 수 있었습니다. 그렇다면 해당 문제는 어떻게 풀어야하는지 생각해 보니 K번째 수는 K보다 클 수 없음을 알 수 있습니다. 1 2 3 2 4 6 3 6 9 값 1 2 2 3 3 4 6 6 9 순서 1 2 3 4 5 6 7 8 9 이진 탐색을 이용하여 배열에서 mid 값보다 작은 수의 개수를 계산하고, k와..
-
[백준][Kotlin]2343번 기타 레슨백준 2023. 3. 20. 16:03
해당 문제는 이진 탐색을 사용하여 풀 수 있는 문제였습니다. 주어진 자료 중 가장 큰 값이 정답이 될 수 있는 최소값이 되며, 자료의 합이 정답이 될 수 있는 최대 값이 됩니다. 최소값과 최대값의 중간값으로 비교하며, 최대값과 최소값의 증감을 정하여 다시 중간값으로 비교하면서 최적의 해를 찾으면 되는 문제입니다. 하기는 제가 작성한 해당 문제의 제출 코드와 제출 결과입니다. import java.io.BufferedReader import java.io.BufferedWriter import java.io.InputStreamReader import java.io.OutputStreamWriter import java.lang.Math.max import java.util.* import kotlin.c..
-
[백준][Kotlin]1920번 수 찾기백준 2023. 3. 20. 13:51
해당 문제는 이진탐색을 사용하면 풀 수 있는 문제였습니다. 이진탐색은 간단히 설명하자면 최소값과 최대값을 중간값과 원하는 결과값의 대소비교를 하여 최소값과 최대값을 변경하면서 최적의 해를 찾는 방법입니다. 그리고 이진탐색으로 해당 문제를 작성하였습니다. 하기는 이진탐색으로 작성한 코드와 제출 결과 입니다. import java.io.BufferedReader import java.io.BufferedWriter import java.io.InputStreamReader import java.io.OutputStreamWriter import java.lang.Math.max import java.util.* import kotlin.collections.ArrayList fun main() { val b..
-
[백준][Kotlin]1167번 트리의 지름백준 2023. 3. 20. 13:12
해당 문제는 bfs와 하나의 아이디어를 생각한다면 쉽게 풀 수 있습니다. 아이디어는 바로 임의의 점에서 가장 먼 노드는 트리의 한쪽 끝이다라는 사실을 기반으로 트리의 한쪽 끝 지점을 알아내는 것입니다. 그 후 알아낸 끝 지점부터 가장 먼지점의 거리를 구하게 되면 해당 트리의 지름을 알 수 있습니다. 하기는 제가 작성한 코드와 제출 결과 입니다. import java.io.BufferedReader import java.io.BufferedWriter import java.io.InputStreamReader import java.io.OutputStreamWriter import java.lang.Math.max import java.util.* import kotlin.collections.ArrayL..
-
[백준][Kotlin] 1520번 내리막 길백준 2023. 3. 13. 15:18
https://www.acmicpc.net/problem/1520 해당 문제는 DFS의 특징 중 경로를 지나갔는지 기록할 수 있다는 특성을 알고 사용해야 풀 수 있는 문제였습니다. 저의 경우 처음에 문제를 읽고 일반적인 DFS를 이용하여 코드를 작성하였었으나 메모리초과가 발생하여 통과 하지 못하였었습니다. 그리고 원인이 무엇인지 잘 몰라 수정을 계속 하면서 작성하고 있었습니다. 그러던 중 알고리즘 스터디 강의 에서 해당 문제는 DFS의 특성 을 사용해야 한다는 것과 제가 처음에 작성한 코드가 메모리 초과가 되는 원인을 알았습니다. 제가 처음에 작성하였었던 코드는 DFS를 실행하면서 결과값을 +1 하는 코드였는데 문제의 설명 중 "첫째 줄에 이동 가능한 경로의 수 H를 출력한다. 모든 입력에 대하여 H는 ..
-
[백준][Kotlin] 2178번 미로 탐색백준 2023. 3. 11. 23:45
해당문제는 BFS를 알고 있다면 간단하게 풀 수 있는 문제였습니다. 저의 경우 입력을 CharArray로 받은 후 map라는Array에 저장하였고, 또한 지나온 칸을 세기 위하여 visit 를 Array(N,{IntArray(M){1}) 로 만들어 저장 하였습니다. 추후 BFS를 실행하며, 해당 위치의 상하좌우를 확인 하면서 상하좌우 위치가 '1'인지와 그리고 visit에서 상하좌우 위치가 1인지 아닌지 를 확인하여 Deque에 넣어 주면서 탐색하는 코드를 작성 하였습니다. 하기는 제가 작성한 코드와 제출 결과 입니다. import java.io.BufferedReader import java.io.BufferedWriter import java.io.InputStreamReader import java..