Algorithm/문제 풀이8 프로그래머스 - 봉인된 주문 참가 신청을 할까말까 하다 결국 안 했던 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. BOJ 11834 - 홀짝 이분 탐색 카테고리 문제만 연달아 풀다가 마주쳐서인지 쉽게 접근이 가능했지만 평소에 봤다면 꽤 힘들만했을 것 같다. 입력 값이 10^100인 걸 보면 어쨌건 시간복잡도가 log n이어야겠다 하는 게 이분 탐색과 연결 지을 힌트라면 힌트겠다. 그 외 숫자에 대한 접근은 간단하다. 짝수는 2의 배수이므로 홀수 -> 짝수 / 짝수 -> 홀수로 넘어가는 경우 모두 1만 더해주면 홀/짝이 바뀌게 된다. 반대로 짝수/홀수 상태가 유지돼야 할 때는 2씩 증가하면 된다. 값이 변하는 양은 정해져있고, 우리는 규칙만 찾으면 된다. 앞부분부터 하나씩 살펴보자.먼저 초항에서 다음 항으로 넘어가는 부분이다. 홀 / 짝 / 홀 / 짝 순으로 나오는 수열이고, 초항이 홀수 1이므로 n = 2일때 올 숫자는 n = 1에서 1증가한.. 2024. 6. 9. BOJ 10868 - 최솟값 가장 먼저 떠오른 건 우선순위 큐였지만 당연하게 시간 초과가 났습니다. 사실 제출할 때도 그렇게 큰 기대 없이 냈기 때문에 다른 로직을 생각해야 했고... 그러다가 합병 정렬 진행 과정이 불현듯 스쳐갔습니다. 시간 복잡도를 줄이려면 반드시 트리 구조여야 할 텐데, 합병정렬에서 분할 정복을 통해 모든 엘리먼트를 최소 단위까지 쪼갠 기억이 난 것이죠. 합병 정렬을 그림으로 그리고, 위 과정에서 정렬 대신 최솟값만 취하면 훨씬 빠르지 않을까? 하는 생각이었습니다. 쪼갠 후, 정렬 과정을 생략하고 최소 값만 모아봤습니다. 이렇게 보니 시간 초과를 극복할 수 있다는 예감이 강하게 듭니다. 이제 트리를 만들고, 범위 값을 찾는 과정을 생각해 보겠습니다. 배열이 있고, 트리의 노드는 포함한 범위 정보와 그 범위 안.. 2024. 6. 4. BOJ 3080 - 아름다운 이름 [Java / Python] 상근이가 뭐 하고 살든 알 바 아니지만 이런 이상한 짓은 좀 안 했으면 좋겠다. 사람이름은 타고나길 이쁜 거지 뭘 위치를 정해가며 아름답네 마네 한단 말인가... 여하튼 참여 중인 캠프에서 문제는 던져줬고, 나는 풀어야 하는 입장이었다. 문제만 보면 어떤 규칙인지는 알겠는데, 그냥 사전순 정렬하면 끝나는 거 아닌가 하는 생각이 든다. 필자는 예제 데이터를 보고나서야 문제가 요구하는 조건을 이해할 수 있었다. 예제를 먼저 살펴보자. 예제 1번은 비교적 쉽다. I로 시작하는 문자 하나와 J로 시작하는 문자가 2개 있으므로, J문자들을 정렬하는 2가지 경우에 앞뒤로 IVO를 붙여주는 걸 생각할 수 있다. 그렇게하면 2 * 2로 4가 나온다. 이 추측이 맞는지 아래 예제로 확인해 보자 문자의 한 열씩 비교하.. 2024. 6. 2. 이전 1 2 다음
