백준
-
[백준][Kotlin]4883번 삼각 그래프백준 2023. 6. 10. 03:51
해당 문제는 DP 문제입니다. 저의 경우 처음에는 혹시나 싶어 다익스트라 방식으로 작성해 봤었지만 메모리 초과라는 문제가 발생하여 이중 for문을 돌리면서 해당 위치값을 저장하고 있는 map 과 값을 갱신 및 누적할 map 을 생성하여 해당 문제를 작성하였습니다. 누적되는 map의 값을 구하는 방식을 구하는 것은 쉬웠으나 통과를 하지 못하여 식을 잘못 구한 듯 싶어 수정을 몇번 하였었지만 통과하지 못하였었습니다. 그래서 코드가 진행되는 과정에서 중간중간 출력문을 이용하여 값의 변경에 대해서 추적을 하여 문제를 찾았습니다. 제가 처음에 고려하지 못했던 문제는 값을 갱신하는 map에 있어 row값이 1 일 때 해당 row에 해당하는 col을 갱신할 때 올바른 값이 들어가지 않는다는 것을 알게되어 수정을 하여..
-
[백준][Kotlin] 2302번 극장 좌석백준 2023. 6. 6. 02:31
해당 문제는 DP 문제였습니다. 해당 문제에서 빈자리 별 경우의 수를 구하는 점화식은 arr[i] = arr[i-2] + arr[i-1] 입니다. 사람마다 다를 수 있겠지만 저의 경우는 빈자리의 갯수만큼 나올 수 있는 경우의 수를 저장한 배열을 생성하고, 고정석의 자리를 확인하면서 빈자리의 개수를 확인하여 발생 할 수 있는 경우의 수를 구하는 방식으로 코드를 작성하였습니다. 하기는 제가 작성한 코드와 제출 결과 입니다. import java.io.BufferedReader import java.io.BufferedWriter import java.io.InputStreamReader import java.io.OutputStreamWriter import java.util.StringTokenizer f..
-
[백준][Kotlin]9461번 파도반 수열백준 2023. 6. 6. 02:24
해당 문제는 DP 문제 였습니다. 개인적으로 알고리즘 공부를 하면서 정말 어려웠고 어려운 알고리즘 입니다. 수식이 잘 떠오르지 않아 수식을 찾는 시간이 오래 걸리기 때문입니다. 분명 고등학생때는... 잘 찾았던거 같은데....???ㅋㅋㅋㅋ 해당 문제의 점화식을 먼저 말씀드리면 a[ i ] = a[ i -2 ] + a[ i - 3 ] 입니다. 그리고 제가 작성하면서 생각을 미처 하지못햇던 부분이 있는데 N이 최대 100이면 자료형을 Int로 하면 78번째에서 오버플로우가 발생한다는 점이였습니다. 처음에는 점화식을 잘못 구한줄 알고 검산을 해봤으나 문제가 없음을 확인한 뒤 문제를 다시 한번 보니 2^31-1 이라는 조건이 없는 것을 보고 작성한 코드에서 최대값을 100을 입력하면 오버플로우가 발생하는 것을 ..
-
[백준][Kotlin]5427번 불백준 2023. 5. 28. 22:01
해당문제는 BFS를 이용하면 작성 할 수 있는 문제였습니다. 저의 경우에는 이해하기 쉽도록 방문처리 배열을 2개를 생성하여 불을 번지게 한 후 위치 별로 불이 번지는 시간을 구하는 BFS와 사람이 위치 별로 도착하는 시간을 구하는 BFS를 이용하여 문제를 작성하였습니다. 하기는 제가 작성한 코드와 제출 결과 입니다. import java.io.BufferedReader import java.io.BufferedWriter import java.io.InputStreamReader import java.io.OutputStreamWriter import java.util.* lateinit var fireMap : Array lateinit var visit : Array lateinit var visit..
-
[백준][Kotlin] 1854번 K번째 최단경로 찾기백준 2023. 4. 23. 21:07
해당 문제는 다익스트라 알고리즘을 응용하여 작성할 수 있었습니다. 다익스트라 알고리즘은 가중치가 있는 그래프에서 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 너비 우선 탐색(BFS)을 응용한 알고리즘으로, 시작 정점에서부터 거리가 가장 가까운 정점부터 탐색하면서 최단 경로를 구합니다. 알고리즘의 구체적인 동작은 다음과 같습니다. 1. 시작 정점을 선택하고, 시작 정점에서 직접 이어져 있는 모든 정점들의 거리를 계산합니다. 2. 시작 정점으로부터 거리가 가장 가까운 정점을 선택합니다. 3. 이전에 선택된 정점을 통해 직접 이어져 있는 정점들의 거리를 갱신합니다. 4. 위 과정을 모든 정점이 선택될 때까지 반복합니다. 이 알고리즘의 시간 복잡도는 우선순위 큐를 사용..
-
[백준][Kotlin] 1916번 최소비용 구하기백준 2023. 4. 20. 15:58
해당문제는 다익스트라 알고리즘을 사용하여 작성 할 수 있었습니다. 다익스트라 알고리즘은 거리배열과 우선순위큐를 이용하여 가중치가 적은 자료부터 확인하는 로직,그리고 방문했던 노드 재방문 방지 등에 대한 로직에 대한 이해를 하고 있다면 쉽게 작성할 수 있는 알고리즘이라고 개인적으로 생각이 듭니다. 해당 문제는 코드 내에 주석을 이용하여 설명을 적어 쉽게 이해 할 수 있도록 하였습니다. 하기는 제가 작성한 코드와 제출 결과 입니다. import java.io.BufferedReader import java.io.BufferedWriter import java.io.InputStreamReader import java.io.OutputStreamWriter import java.util.* import kot..
-
[백준][Kotlin]1753 최단경로백준 2023. 4. 20. 15:26
해당 문제는 다익스트라 알고리즘을 이용하여 작성 할 수 있습니다. 다익스트라 알고리즘은 노드별로 가중치가 있고 가중치가 0 이상의 양수 일 때 사용가능 하며, 출발 노드로 부터 특정 노드까지의 최단 거리를 구할 때 사용합니다. 작성 포인트로는 첫번째. 인접 리스트로 그래프 구현하기 두번째. 최단 거리 배열 초기화 하기 세번째. 값이 가장 작은 노드 고르기 네번째. 최간 거리 배열 업데이트 하기 두번째 포인트에 맞춰 최단 거리 배열을 초기화 할 때 추 후 값이 작은 값을 선택해야 하므로 그나마 무한대에 가까운 값을 넣어 초기화 합니다. 만약 입력값의 최대 범위가 Int 일 경우에는 Int.MAX_VALUE 로 초기화 하여도 됩니다. 세번째 포인트의 경우 우선순위큐를 이용하여 가중치가 적은 순 부터 비교하면..
-
[백준][Kotlin]1948번 임계경로백준 2023. 4. 19. 16:57
해당 문제는 위상정렬의 개념을 이해하고 위상정렬을 이용하여 걸리는 시간을 구한 뒤 해당 로직을 반대로 돌리면서 1분도 쉬지 않고 달려야 하는 도로의 수를 구해야 하는 문제였습니다. 단순히 도시에 도착하기까지 걸리는 시간은 단순히 위상정렬을 이용하여 구할 수 있지만, 해당 로직을 어떻게 반대로 돌려야 하는지 헷갈릴 수 있습니다. 해당 문제 작성 시 포인트로는 해당 도시에서 갈 수 있는 경로를 구할 때 배열을 2개를 생성하여 첫번째 배열에는 정방향 일때 두번째는 역방향 일때의 경로를 저장하여 추후 로직을 반대로 돌릴 때 이용합니다. 하기는 제가 작성한 코드와 제출 결과 입니다. import java.io.BufferedReader import java.io.BufferedWriter import java.i..