Map5 [Kotlin] 백준 6523 : 요세푸스 한 번 더! 문제 링크 : https://www.acmicpc.net/problem/6523문제 해설일종의 구현 문제. 따로 특별한 알고리즘이 필요하진 않다. 문제에서 각 사람들은 두번째에 걸렸을 때 술을 마시게 되고, 누구든 세 번 걸린다면 모두 집에 간다는 내용이 있다. 술을 마시지 않고 집으로 가는 사람의 수를 출력해야 하기 때문에 누군가 두번째 걸렸을 때 술을 마신 사람의 수를 더하고, 세번째 걸린다면 해당 테스트 케이스를 종료하면 된다. 각 사람들이 걸린 횟수를 기록하기 위해 HashMap을 사용한다. 정수배열을 사용해서 기록할 수도 있겠으나, 크기가 최대 10억인 정수배열을 선언하게 되어 어마어마한 메모리를 차지하게 되는 문제가 있어서 사용할 수 없다. 현재 사람의 번호가 \(x\)일 때 다음 사람의 번호.. 2024. 6. 10. [Kotlin] 백준 25240 : 가희와 파일 탐색기 2 문제 링크 25240번: 가희와 파일 탐색기 2 Q개의 질문에 대해, 연산이 성공하면 1을 실패하면 0을 출력해 주세요. 각 질문에 대한 답은 한 줄에 하나씩 출력해 주세요. www.acmicpc.net 문제 해설 리눅스의 파일 권한과 관련된 문제. 관련 지식이 있다면 어렵지 않게 풀 수 있다. 우선 각 권한을 2진수로 바꿔보자. \begin{align*} 000 &\to 권한 없음\\ 001 &\to 실행 가능\\ 010 &\to 수정 가능\\ 011 &\to 실행 및 수정 가능\\ 100 &\to 읽기 가능\\ 101 &\to 읽기 및 실행 가능\\ 110 &\to 읽기 및 수정 가능\\ 111 &\to 읽기, 수정, 실행 모두 가능 \end{align*} 여기서 \(2^2\)에 해당하는 비트는 읽기.. 2023. 12. 30. [Kotlin] 백준 20551 : Sort 마스터 배지훈의 후계자 문제 링크 20551번: Sort 마스터 배지훈의 후계자 지훈이는 Sort 마스터다. 오랫동안 Sort 마스터 자리를 지켜온 지훈이는 이제 마스터 자리를 후계자에게 물려주려고 한다. 수많은 제자들 중에 후계자를 고르기 위해서 지훈이는 제자들에게 문제 www.acmicpc.net 문제 해설 사용 알고리즘 : 이진탐색 문제 자체는 단순히 배열을 정렬한 후 M번에 걸쳐서 해당 요소의 첫 위치를 찾아내면 되는 문제이다. N과 M이 작다면 그냥 \(O(N\times M)\)인 indexOf()로 해결할 수 있지만 N과 M이 각각 최대 20만이기 때문에 이 방법은 시간초과가 발생한다. 코틀린에서는 이진탐색을 수행하는 binarySearch() 메소드가 존재하지만 이 메소드는 찾고자 하는 값을 발견하면 가장 첫 위치.. 2023. 8. 23. [Kotlin] 불변 컬렉션과 가변 컬렉션 목차 서론 코틀린의 컬렉션은 기본적으로 자바의 그것을 그대로 사용하지만 불변 컬렉션과 가변 컬렉션으로 구분된다는 차이가 있다. 물론 자바에서도 불변 컬렉션을 만드는 것이 불가능하진 않지만 불변이라는 것을 컴파일 타임에 검증할 수 없고, 만드는 것도 조금 번거롭기 때문에 완전하다고 보기는 어렵다. 이 글에서는 코틀린의 불변 컬렉션과 가변 컬렉션에 대해 다룬다. 컬렉션(Collection)? 컬렉션은 수집이라는 단어 의미 그대로 다수의 객체를 수집해놓은 객체라고 볼 수 있다. 컬렉션은 크게 리스트(List), 집합(Set), 맵(Map)으로 나눌 수 있다. List : 인덱스를 통해 요소에 접근할 수 있는, 순서가 보장된 컬렉션. 중복 요소가 허용된다. 스택과 큐, 덱 등의 자료구조도 큰 의미에서 리스트에 .. 2023. 4. 18. [Kotlin] 백준 7662 : 이중 우선순위 큐 문제 링크 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 문제 해설 처음에는 최대힙과 최소힙을 하나씩 만들어서 구현하려고 했는데 시간 초과가 났다. 제거 연산을 수행할 때 'D 1'이면 최대힙에서 제거한 값을 최소힙에서 remove()로 제거하고, 'D -1'이면 최소힙에서 제거한 값을 최대힙에서 같은 방법으로 제거하는 방식으로 구현했는데 저 remove() 과정에서 힙을 탐색해야 하다보니 시간을 초과한 것 같아서 다른 방법을 찾아보기로 했다. 그런 이유로 TreeMap을 이용하여 문제를 풀어보았는데 성.. 2022. 12. 4. 이전 1 다음
