Algorithm
-
[일간임무] - 전깃줄일간임무 2021. 11. 1. 23:27
https://www.acmicpc.net/problem/2565 Elapsed time = 45min LIS을 구현하는 건 어렵지 않지만, 이걸 떠올리는 것이 거의 불가능에 가깝다는 생각이 듭니다. 그냥 운이 좋아서 정렬을 해볼 생각이 떠오른 것이지 딱히 실력으로 풀었다는 생각은 전혀 들지 않습니다. 순전히 운으로 풀었습니다. 두 개의 전깃줄을 상상하고 한 쪽을 오름차순으로 정렬하여 다른 전깃줄에 매겨진 번호를 LIS을 활용하면 되는데 원리가 대체 뭔지는 모르겠습니다. 분류가 LIS이니 LIS이겠거니 해서 풀었지만 원리가 뭘까요?
-
-
[일간임무] - 소수찾기일간임무 2021. 10. 27. 21:43
https://programmers.co.kr/learn/courses/30/lessons/42839#qna 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr Elapsed time = 21min 소수를 판별하는 문제 + Permutation + 간단한 Hash문제라고 생각합니다. 소수를 판별하는 기법은 다양하지만 수가 크지 않기 때문에 제곱을 이용해서 풀어도 될 것입니다. Permutation역시 같은 이유로 재귀 함수를 사용해도 될 것입니다. 다만, 제곱을 이용하여 소수를 판별할 땐 제곱하는 ..
-
[일간임무] - 프린터일간임무 2021. 10. 26. 11:55
Elapsed time = 5min 프린터 대기열에 격납된 어떤 작업들은 서로 다른 우선 순위를 갖습니다. 입력으로 주어진 우선순위를 내림차순으로 정렬하면 가장 먼저 처리되어야 할 작업의 우선순위를 알 수 있습니다. 따라서, priorities을 그대로 Queue에 복사하는 작업과 정렬을 위해 vector 컨테이너를 마련합니다. Queue에 저장된 작업들은 (index, priority)로 쌍을 이루고 있습니다. Queue에서 하나씩 빼면서 현재 검사 중인 작업의 우선순위가 가장 높은 우선순위보다 낮다면 다시 Queue에 Push합니다. 반대로 Queue에서 빼서 검사 중인 현재 작업의 우선순위가 가장 높은 우선 순위보다 같거나 높다면 나가도 무방합니다. 이때 확인해야 할 것은 내가 검증하길 원했던 작업..
-
[일간임무] - 튜플일간임무 2021. 10. 25. 20:43
Elapsed time = 45min 풀고 나서 찾아보니 상당히 쉬운 문제라고 해서 절망했습니다. 개인적으로 Tuple이라는 구조 자체가 익숙하지도 않고 문자열을 나누는 알고리즘을 구현하거나 직접 적합한 정렬 알고리즘을 작성하는 것도 쉬운 일이 아니었기 때문입니다. 보니까 1. String Parsing 2. Custom sorting algorithm 3. Acquaintance of the tuple 이렇게 세 가지가 핵심인 것 같습니다. 다른 사람들의 풀이를 보면 훨씬 쉽게 풉니다. 특히, Tuple을 구하기 위해서 입력된 문자열을 {} 단위로 나누고 정렬하는 부분을 획기적인 방법으로 구현하여 훨씬 간결하고 쉽게 풉니다. 단순히 String이 담긴 컨테이너를 STL sort함수로 돌려버리면 원하는 ..
-
[일간임무] - 수식 최대화일간임무 2021. 10. 24. 22:54
Elapsed time = 60min 아이디어는 빠르게 떠올렸지만 한 가지를 구현하는데 애를 먹었습니다. 계산을 하고 나면 두 개의 값이 하나로 합쳐지면서 컨테이너의 한 공간을 제거하고 다음 공간을 당겨와야 하는데 어쩌면 좋을지 잘 몰라서 고민했습니다. Erase method는 자동으로 그것을 해결해주며 for loop의 j의 값을 1만큼 후퇴시키는 것으로 해결할 수 있었습니다. Permutation, 문자열 Splicing, for loop application 등등 낮은 난이도라고 하는데 알차게 구성된 것 같습니다.