Algorithm10 프로그래머스 - 봉인된 주문 참가 신청을 할까말까 하다 결국 안 했던 2025 프로그래머스 코드챌린지...의 2차 예선 문제입니다.문제를 보고 26진수를 떠올릴 수 있고 진수 변환 방법만 알고있다면 쉽게 해결할 수 있습니다.lv3 난이도에 비해 비교적 쉽게 나온 편에 속하는 것 같습니다. 크게 복잡하지 않아서 풀이를 간단하게 적어보면금지된 주문을 이용해 적절한 n의 위치를 설정할 때 26진수 -> 10진수 변환이재설정된 n을 다시 주문으로 변환할 때 10진수 -> 26진수 변환이 한 번씩 사용됩니다. 아래는 제출 코드입니다.import java.util.*;class Solution { char[] alp = new char[26]; Map indexes = new HashMap(); PriorityQueue.. 2025. 2. 19. BOJ 3653 - 영화 수집 푸는데 3일 걸렸고요. 진짜 너무너무 괴로웠고요...맨날 실버 풀다가 오랜만에 플레 함 해볼까 했다가 대가리 시원하게 박살났음니다.다시는 플레를 조심성 없이 고르지 않으리... 푸념은 여기까지 하고, 아래는 문제입니다.영화로 10만 개로 젠가 하는 미친놈이 너 말고 또 있을까 상근아?죄송합니다. 문제 볼게요. 사실 문제 유형 파악부터 굉장히 애먹었습니다. 이분 탐색인가? 하니 정렬 데이터가 아니고, 그리디인가? 하니 모든 비용이 1입니다. 최단 거리, 최소 비용 알고리즘인가? 하면 사실 적용법이 떠오르지 않았고요... 설마 트리겠어? 했는데 아니나 다를까 트리였습니다. 그것도 딱 한 번 해봤던 세그먼트 트리요... 세그먼트 트리는 구간 정보를 다룰 때 유리한 자료구조입니다. 일반적으로 구간 합, 구간 최.. 2024. 7. 30. BOJ 11726 - 2 x n 타일링 DP란 무엇인가... 답을 알고 보는데도 한참 걸렸던 문제다. 패턴을 손으로 하나하나 그려가면서 경우의 수가 피보나치 수열과 동일하게 증가한다는 걸 알게 됐는데, 항상 그렇게 된다는 걸 증명하지 못해서 3시간은 시간을 더 쓴 것 같다. 결국 답에 도달하고 보니 이렇게 간단했나... 싶어서 허망했다만, 결국 대부분의 DP문제가 그런 것 같기도 하다. 여하튼 문제를 보면 \( 2 \times n \) 타일을 채워야하기 때문에 \( 2 \times 1 \) 타일은 하나로도 칸을 채워갈 수 있지만, \( 1 \times 2 \) 타일은 위 아래로 두개를 붙여야만 칸을 채울 수 있다. 결국 타일을 채울 수 있는 도형은 위의 세 도형 뿐이다. 필자는 이걸 넓이 1과 2로 순열을 만들어서 풀려고 했었는데 대차게 실.. 2024. 6. 17. Counting Sort 좁은 범용성주어진 엘리먼트의 크기를 비교해서 정렬하는 일반적인 정렬 알고리즘과는 달리 각 엘리먼트의 개수를 세어 그 위치를 결정하는 정렬 알고리즘이다. 특히 엘리먼트의 값 범위가 좁을 때 매우 높은 퍼포먼스를 보여준다. 하지만 엘리먼트의 개수가 적더라도 값의 범위가 넓은 경우에는 메모리 사용성과 성능이 급격히 떨어지기 때문에, 좁은 범위의 정수 정렬에 적합하며 범용적으로 사용하기는 어렵다. 시간 복잡도\( O(n + k) \) 로 작동한다. 여기서 n은 엘리먼트의 개수이고, k는 범위를 의미한다. 엘리먼트의 범위가 좁은 경우 빠른 속도를 보여준다. 안정 정렬(Stable Sort)같은 값이라면 정렬 전의 순서가 유지되는 안정 정렬이다. 엘리먼트의 수를 세면서 해당 값의 가장 마지막 위치를 저장한 후, 해.. 2024. 6. 14. Merge Sort 분할 정복(Divide and Conquer)배열을 좌/우로 반씩 나눠가면서 최소 단위까지 내려간다. 이후 올라오면서 각 단위를 병합(merge)하면서 정렬하는 방식이다. 재귀로 구현하는 게 일반적이며, 각 단위를 절반씩 나누며 내려가기 때문에 재귀 깊이는 \( \log n \)이 되고, 각 깊이마다 전체 엘리먼트를 순회하며 병합하므로 \( O(n) \)의 시간복잡도가 발생한다. 모든 정렬을 수행했을 때 항상 \( O(n \log n) \) 의 시간복잡도를 보장받는다. 안정 정렬(Stable Sort)정렬 과정에서 같은 우선순위를 가진 데이터가 정렬 후에도 순서가 유지되는 것을 안정적(Stable)이라고 표현한다. 분할 과정에서 데이터는 정렬되지 않은 상태이므로 원래 위치를 유지하고, 병합 과정에서도 .. 2024. 6. 14. BOJ 11834 - 홀짝 이분 탐색 카테고리 문제만 연달아 풀다가 마주쳐서인지 쉽게 접근이 가능했지만 평소에 봤다면 꽤 힘들만했을 것 같다. 입력 값이 10^100인 걸 보면 어쨌건 시간복잡도가 log n이어야겠다 하는 게 이분 탐색과 연결 지을 힌트라면 힌트겠다. 그 외 숫자에 대한 접근은 간단하다. 짝수는 2의 배수이므로 홀수 -> 짝수 / 짝수 -> 홀수로 넘어가는 경우 모두 1만 더해주면 홀/짝이 바뀌게 된다. 반대로 짝수/홀수 상태가 유지돼야 할 때는 2씩 증가하면 된다. 값이 변하는 양은 정해져있고, 우리는 규칙만 찾으면 된다. 앞부분부터 하나씩 살펴보자.먼저 초항에서 다음 항으로 넘어가는 부분이다. 홀 / 짝 / 홀 / 짝 순으로 나오는 수열이고, 초항이 홀수 1이므로 n = 2일때 올 숫자는 n = 1에서 1증가한.. 2024. 6. 9. 이전 1 2 다음
