전체 글
-
[백준][Kotlin]1976번 여행 가자백준 2023. 4. 12. 15:01
해당 문제는 유니온 파인드을 이용하여 작성 할 수 있는 문제 였습니다. 저의 경우 헷갈리지 않으려고 도시정보를 저장 하는 배열은 N+1의 size를 가진 IntArray를 생성하여 저장 하였습니다. 여기서 제가 실수를 한번 했었는데 N의 값을 +1을 해서 받은 다음 배열 생성 후 N을 -1 을 한 뒤에 코드가 실행 되도록 작성해야 됬었는데 -1을 안해서 문제의 예제는 잘 돌아갔는데 제출을 하면 NullPointer 에러가 발생하였었습니다. -1을 코드 작성 시 바로 했어야 됬는데 하지 않아 해당 문제를 찾는데 있어 조금 당혹 스러웠던 경험을 하였습니다. 하기는 제가 작성한 코드와 제출 결과 입니다. import java.io.BufferedReader import java.io.BufferedWriter..
-
[백준][Kotlin]1717번 집합의 표현백준 2023. 4. 11. 21:40
해당문제는 유니온 파인드를 이용하여 작성하면 통과할 수 있는 문제였습니다. 유니온 파인드(Union-Find)는 서로소 집합(Disjoint-set)을 표현하고 관리하기 위한 알고리즘입니다. 서로소 집합은 공통 원소가 없는 두 집합을 의미합니다. 예를 들어, {1, 2, 3}과 {4, 5}는 서로소 집합입니다. 유니온 파인드 알고리즘은 각 원소를 개별적인 집합으로 만들고, 두 개의 집합을 하나로 합치는(union) 연산과 어떤 원소가 어떤 집합에 포함되어 있는지를 확인하는(find) 연산을 지원합니다. 유니온 파인드 알고리즘은 배열 형태로 구현되며, 배열의 각 인덱스는 각각의 원소를 의미합니다. 각 원소는 자신이 속한 집합의 대표 원소(루트 노드)를 가리키는 포인터를 갖습니다. 두 집합을 합치는 경우, ..
-
[프로그래머스][Kotlin]연속 펄스 부분 수열의 합프로그래머스 2023. 4. 11. 14:55
해당 문제는 연속 펄스 부분 수열의 합 중 가장 큰 값을 return 하는 문제입니다. 저는 처음에는 세크먼트트리를 연습할 겸해서 시간 초과가 발생할 것 같은 제한조건 이였지만, 세그먼트트리를 이용하여 펄스 수열이 1,-1 로 시작되는 케이스에 따라 2개를 만들어 갱신 및 조회 하는 방법으로 사용하였고, 그렇게 시간 초과가 발생하여 실패 하였습니다. 세크먼트트리로 작성 시 제가 연습이 부족하여 그런 것일 수도 있음을 말씀드립니다. 맘같아서는 연습했던 코드도 같이 올리고 싶지만 실수로 날려버려 하기에는 통과한 코드만 있습니다. -----잡설 -----본문 해당 문제는 부분 합이 가장 큰 값을 리턴하는 것인데 생각해보면 가장 큰 값을 예상해보면 음수들을 더하는 것이 아닌 양수들의 합임을 알 수 있습니다. 다..
-
[백준][Kotlin] 2042번 구간 합 구하기백준 2023. 4. 10. 17:00
해당 문제는 세그먼트트리를 이용하면 통과 할 수 있는 문제였습니다. 세그먼트 트리는 구간 질의 (range query) 문제를 효율적으로 해결하기 위한 자료구조입니다. 구간 질의란, 배열이나 리스트와 같은 자료구조에서 주어진 범위에 속하는 값들을 찾는 문제를 의미합니다. 예를 들어, 주어진 배열에서 특정 구간의 합이나 최소값, 최대값 등을 구하는 문제가 구간 질의 문제에 해당됩니다. 세그먼트 트리는 주어진 배열을 트리 형태로 변환하여 구간 질의를 해결합니다. 이를 위해, 배열을 노드로 가지는 이진 트리를 만들고, 각 노드는 해당 구간의 합, 최소값, 최대값 등을 저장합니다. 이진 트리의 루트 노드는 전체 구간에 대한 질의 결과를 저장하며, 자식 노드들은 부모 노드의 구간을 반으로 나눈 구간에 해당하는 값..
-
[백준][Kotlin]2559번 수열백준 2023. 4. 10. 13:00
해당 문제는 투 포인터를 사용하면 풀 수 있는 문제였습니다. 간단하게 K의 길이만큼 합을 구한 후 가장 큰 수를 출력하면 됩니다. 하기는 제가 작성한 코드와 제출 결과 입니다. import java.io.BufferedReader import java.io.BufferedWriter import java.io.InputStreamReader import java.io.OutputStreamWriter import java.util.* import kotlin.collections.ArrayList import kotlin.collections.HashMap fun main() { val br = BufferedReader(InputStreamReader(System.`in`)) //val bw = Buf..
-
[프로그래머스][Kotlin]달리기 경주프로그래머스 2023. 4. 7. 22:37
해당 문제는 LV1 문제인데 처음에는 가볍게 swap 함수를 생성하여 작성하였으나 시간초과가 발생하였습니다. 그래서 단순하게 list를 생성 후 선수의 이름이 불릴 때 마다 sort를 하여 순위를 갱신 하였으나 이것도 시간 초과가 발생하여, 순위 별 선수 이름을 저장하는 map, 선수 별 순위를 저장하는 map 2개를 생성하여 callings에서 선수가 불릴 때 마다 순위 별 선수이름과 선수이름 별 순위를 갱신하는 형식으로 코드를 작성하여 통과하였습니다. 처음에는 단순히 LV1 문제이길래 간단하게 작성하였었으나, 간단하게만 생각하면 통과 할 수 없는 문제였습니다. 제한조건을 봤을 때 시간초과가 나올 것 같긴 하였으나 그래도 LV1이니깐 그냥 넘어 갔어서 작성하는데 시간이 조금 더 걸렸던 문제 였던 것 같..
-
[프로그래머스][Kotlin]연속된 부분 수열의 합프로그래머스 2023. 4. 7. 19:33
해당문제는 이진탐색을 사용하면 쉽게 풀 수 있는 문제였습니다. 저의 경우 이진탐색이 서툴러 처음에는 다른 방법으로 작성하였으나, 해당 문제 통과 후 이진탐색을 다시금 공부하여 다시 작성하여 통과 하였습니다. 두 코드의 실행 결과를보면 단순 연산을 하는 이진탐색을 하는 코드의 실행시간이 deque를 사용한 코드보다 대폭 줄어든 점을 확인 할 수 있었습니다. 하기는 처음에 deque를 사용하여 작성한 코드와 제출결과 입니다. import java.util.ArrayDeque class Solution { fun solution(sequence: IntArray, k: Int): IntArray { var answer = intArrayOf(0,1000000001) var sum = 0 var dq = Arr..
-
[백준][Kotlin]15650번 N과 M (2)백준 2023. 4. 5. 16:51
해당문제는 15649번 N과 M (1) 문제와 비슷하지만 중복된 숫자의 구성을 허용하지 않는다는 차이점이 있습니다. ex) (1,2) , (2,1) 이 두개는 동일한 것으로 처리함. 그렇기에 15649번 N과 M (1) 문제와 비슷하게 코드를 작성하지만 dfs 함수 호출 시 같이 인자로 보낸 num보다 큰 숫자만을 추가 할 수 있도록 next 라는 인자를 추가하였으며, dfs내 반복문 실행 시 next+1부터 실행 될 수 있도록 하였습니다. 왜냐하면 N과 M이 각각 4 와 2 일때, 처음에는 i가 1 일때 1,2 1,3 1,4가 되며, i가 2일 때는 2,3 2,4 가 됩니다. 이때 i보다 큰 수부터 시작을 해야 오름차순 및 1,2 와 2,1 처럼 중복되는 경우를 방지 할 수 있기 때문입니다. 하기는 제..