전체 글224 [Kotlin] 백준 6523 : 요세푸스 한 번 더! 문제 링크 : https://www.acmicpc.net/problem/6523문제 해설일종의 구현 문제. 따로 특별한 알고리즘이 필요하진 않다. 문제에서 각 사람들은 두번째에 걸렸을 때 술을 마시게 되고, 누구든 세 번 걸린다면 모두 집에 간다는 내용이 있다. 술을 마시지 않고 집으로 가는 사람의 수를 출력해야 하기 때문에 누군가 두번째 걸렸을 때 술을 마신 사람의 수를 더하고, 세번째 걸린다면 해당 테스트 케이스를 종료하면 된다. 각 사람들이 걸린 횟수를 기록하기 위해 HashMap을 사용한다. 정수배열을 사용해서 기록할 수도 있겠으나, 크기가 최대 10억인 정수배열을 선언하게 되어 어마어마한 메모리를 차지하게 되는 문제가 있어서 사용할 수 없다. 현재 사람의 번호가 x일 때 다음 사람의 번호.. 2024. 6. 10. [Kotlin] 백준 14715 : 전생했더니 슬라임 연구자였던 건에 대하여 (Easy) 문제 링크 : https://www.acmicpc.net/problem/14715문제 해설나름 간단한(?) 수학 문제. 별다른 알고리즘이 필요하진 않다. 슬라임은 2 이상의 에너지를 갖는 슬라임으로 계속 분할할 수 있다. 분할할 수 있는 슬라임이 존재하지 않을 때까지 슬라임을 분할한다는 것은 모든 슬라임의 에너지가 소수가 된다는 것이고, 모든 슬라임의 에너지가 소수가 되도록 분할한다는 것은 다시 말해 최초의 슬라임을 소인수분해하면 된다는 뜻이 된다. 문제에서 구해야 하는 값은 슬라임의 흠집 개수 = 슬라임을 분할한 횟수가 된다. K=7200인 경우를 생각해보자. K를 소인수분해하면 \(7200=2\times 2 \times 2 \times 2 \times 2 \times 3 \times 3.. 2024. 5. 31. [Kotlin] 백준 17612 : 쇼핑몰 문제 링크 : https://www.acmicpc.net/problem/17612문제 해설일종의 정렬 문제. 계산대를 우선순위 큐로, 빠져나온 고객을 리스트로 생각해볼 수 있다. 고객을 정렬해야 하니 고객 정보를 어떻게 할지 생각해보자. 각각의 고객은 회원번호와 계산해야 할 물건의 개수를 갖고 있다. 그리고 계산해야 할 물건의 개수는 계산에 걸리는 시간과 같다. 우선 계산대에 들어가는 순서부터 생각해보면 가장 시간이 적게 걸리는 계산대에 먼저 들어가고, 같은 시간이 걸리는 계산대는 번호가 빠른곳부터 들어가게 된다. 모든 고객은 계산대에 들어가게 되니 각 고객 번호와 계산에 걸리는 시간에 더불어 들어간 계산대 번호를 속성으로 넣어주고, 시간과 계산대 번호를 정렬 기준으로 정해준다.private class .. 2024. 5. 22. [Kotlin] 백준 28078 : 중력 큐 문제 링크 : https://www.acmicpc.net/problem/28078문제 해설조금 변형된 큐 문제. 큐의 방향에 따라 내용을 처리해야 한다. 큐의 방향에 따라서 공이 앞부분으로 나올 수도 있고 뒤부분으로 나올 수도 있기 때문에 덱(Deque)을 사용한다. 편의 상 본문에서는 큐라고 언급한다. 큐의 방향에 대해 생각해보자. 큐의 방향은 90도씩 회전하는 4가지 방향만 존재하기 때문에 큐의 앞부분이 바라보는 방향을 오른쪽부터 시계방향으로 0, 1, 2, 3으로 지정할 수 있다.var direction = 0 // 0: right, 1: down, 2: left, 3: up각 쿼리에 대한 동작을 구현하기 전에 큐에서 공의 개수와 가림막의 개수를 구하는 방법을 생각해보자. 단순히 count() 메소.. 2024. 5. 17. [Kotlin] 백준 1322 : X와 K 문제 링크 : https://www.acmicpc.net/problem/1322문제 해설X+Y=X|Y가 되는 Y 중 K번째 수를 구해야 한다. X+Y=X|Y가 성립하는 것이 어떤 의미인지 생각해보기 위해 2진수의 경우를 생각해보자. X|Y는 2개의 2진수 중 하나라도 1인 모든 비트를 1로 만들어주는 연산이다. X+Y는 아래 그림의 101001+1110의 경우를 보자.2개의 2진수 중 하나만 1인 비트만 1이 되고, 둘 다 1인 비트는 받아올림 비트가 발생하면서 0이 된다. 여기까지 보면 Y가 X에서 0인 비트만 1로 채워나가서 받아올림 비트가 발생하지 않는 수일 때 X+Y=X|Y가 성립한다는 것을 알 수 있다. 그러면 이제 \(K\.. 2024. 5. 13. [Kotlin] 백준 23031 : 으어어… 에이쁠 주세요.. 문제 링크 : https://www.acmicpc.net/problem/23031문제 해설특별한 알고리즘이 필요하진 않은 단순 구현 문제. 한 번의 이동이 발생했을 때 아리와 좀비가 마주치더라도 해당 칸에 스위치가 있거나 불이 켜져있기만 하면 아리는 기절하지 않는다. 이로 인해 아리의 행동할 때 마다 진행되는 내용을 과정을 3가지 단계로 나누어 생각해볼 수 있다.아리가 현재 순서에 맞는 행동을 수행한다.아리의 현재 위치에 스위치가 있다면 스위치를 킨다.모든 좀비들이 바라보는 방향으로 1칸 이동한다.이제 각 순서에 맞게 구현을 해보자.1. 아리가 현재 순서에 맞는 행동을 수행한다. 아리의 행동 중 방향을 바꾸는 L과 R을 생각해보자. 방향은 한 번 전환할 때 90도씩 전환하고 4번 전환하면 원래 방향을 보.. 2024. 5. 2. [Kotlin] 백준 25418 : 정수 a를 k로 만들기 문제 링크 : https://www.acmicpc.net/problem/25418문제 해설정수 A에 1을 더하거나 2를 곱하는 연산을 반복하여 정수 K를 만들 때 필요한 가장 적은 연산 횟수를 구해야 한다. 역으로 생각해보면 이 횟수는 K를 2로 나누거나 1을 빼는 연산을 반복하여 A를 만드는 횟수와 동일하다. 2로 나누는 연산이 1을 빼는 연산보다 훨씬 효율적이기 때문에 K를 A로 만들 때 까지 현재 수가 짝수라면 2로 나누고, 홀수라면 1을 빼주면 된다.while (current != a) { if (current and 1 == 0) { current /= 2 } else { current-- } count++.. 2024. 4. 29. [OOP] 일급 컬렉션(First Class Collection)으로 컬렉션을 다뤄보자 목차들어가기 전에컬렉션은 굉장히 유용하고 그만큼 많이 사용되는 자료구조 인터페이스지만 그 자체로도 많은 기능을 구현할 수 있다. 이렇게 유용한 컬렉션을 일급 컬렉션(First Class Collection)으로 사용한다면 이미 강력한 기능을 갖고 있.. 2024. 4. 15. 이전 1 2 3 4 5 6 ··· 28 다음
