본문 바로가기
728x90

이분탐색4

[PG/Python] 징검다리 건너기 📌 문제 https://programmers.co.kr/learn/courses/30/lessons/64062# 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr 📌 문제 접근 방법 처음엔 당연히 효율성에서 0점을 맞을 줄 알면서도 한 명씩 징검다리를 건너는 상황을 구현했다. 역시 효율성을 통과 못하고 찾아봤더니 결국 이분탐색..! 징검다리에 적힌 숫자의 최소와 최대를 시작과 끝으로 정하고 이분탐색으로 풀었다. 근데 사실 아직 answer를 갱신하는 부분이 이해가 잘 안간다... if-else문에서 else문에 answer를 갱신하도록 했더니 테케 2개가 자꾸 틀려서 if문쪽으로 올려줬더니 성공했다.. 나중에 이분탐색을 다시.. 2022. 2. 6.
[PG/Python] 입국심사 📌 문제 https://programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 📌 문제 접근 방법 최소 시간을 구해야하므로 처음에는 최소힙을 이용해서 풀이하였다. i를 현재 심사를 기다리는 사람의 번호라고 하면, 힙에 (i번째 사람의 심사가 끝날 시간, 심사관의 심사 시간)을 push해줬다. 그 후 i를 계속 늘려가며 n이 될 때까지 힙에서 최소 시간을 pop하고 다시 걸린 시간만큼 더해서 push하는 작업을 반복한다. -> 이런 .. 2022. 1. 25.
[PG/Python] 보석 쇼핑 📌 문제 https://programmers.co.kr/learn/courses/30/lessons/67258 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 📌 문제 접근 방법 맨 처음에 짠 코드는 각 보석들의 인덱스를 딕셔너리에 저장한 후, 보석마다 가장 뒤에 있는 인덱스를 start에 담아주고 가장 앞에 있는 인덱스를 end에 담아줬다. 그 후, start에서 가장 작은 값과 end에서 가장 큰 값을 범위로 설정하면 최소의 길이로 모든 보석을 포함하는 구간을 찾을 수 있다. -> 하지만 짧은 구간이 여러 개일 경우 시작 진열대 번호가 가장 작아야 한다는.. 2022. 1. 8.
[BOJ/Python] 1208. 부분수열의 합2 📌 문제 https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 📌 문제 접근 방법 시간 초과를 피하기 위해 리스트를 2개로 나누어 준다. (N의 최대값은 40으로, 나누지 않고 부분집합을 구할 경우 2^40번의 연산이 필요하다. 둘로 나눌 경우, 2^20 + 2^20번의 연산으로 줄일 수 있다.) left, right로 나눈 두 개의 부분집합에 대해서 나올 수 있는 합의 경우의 수를 구한다. 투 포인터를 활용하.. 2021. 10. 8.
728x90

티스토리툴바