항해993 [python]2470_두 용액 사용한 자료구조 및 개념 : 투 포인터 (Two-Pointer), 정렬 💡 문제풀이 아이디어 및 어려웠던 점⚠️ 어려웠던 점: 모든 용액의 조합을 확인하여 합의 절댓값이 0에 가까운 숫자들을 찾을려고 했습니다. 그러나 가능한 조합 수는 n x (n - 1) / 2 로 n이 크면 시간 초과가 발생하였습니다.N 최대 100,000일 때 조합의 수는 약 5×10¹⁰개로 O(N²) 복잡도를 가지며 시간 내에 계산이 불가능한 것이었죠..!그래서 다른 아이디어를 생각했습니다. 💫 아이디어1️⃣ 리스트 정렬: 음수와 양수가 섞여 있는 리스트를 정렬해 두 용액의 합에 대해 접근합니다.2️⃣ 양 끝에서 시작: 리스트의 가장 왼쪽(left)과 가장 오른쪽(right)에서 출발하여 두 용액의 합을 계산3️⃣ 합에 따른 .. 2025. 1. 17. [python]1654_랜선 자르기 사용한 자료구조 및 개념 : 이분 탐색 (Binary Search) 💡 문제풀이 아이디어 및 어려웠던 점💫 아이디어가능한 최대 길이를 효율적으로 찾기 위해 이분 탐색(Binary Search) 을 사용하였습니다. 🤓 문제 풀이 단계1️⃣ 입력 받기 및 초기 설정랜선의 개수 k와 필요한 랜선의 수 n을 입력받습니다.이어서 각 랜선의 길이를 입력 받아 cables 리스트에 저장합니다.이분 탐색을 위한 시작점 start를 1로, 종료점 end를 주어진 랜선들 중 최대 길이로 초기화합니다.2️⃣ 이분 탐색을 통한 최대 길이 탐색while start 중간 길이 mid를 계산하고 이 길이로 자를 수 있는 랜선의 개수 cnt를 구합니다.만약 cnt가 목표치 n 이상이면 해당 길이 mid는 조건을 만족하므로 정답.. 2025. 1. 14. [python]2776_암기왕 사용한 자료구조 및 개념 : set 💡 문제풀이 아이디어 및 어려웠던 점💫 아이디어이 문제에서는 두 개의 수열이 주어졌을 때, 두 번째 수열의 각 수가 첫 번째 수열에 존재하는지 여부를 빠르게 확인해야 합니다. 기본적으로 브루트 포스로 모든 요소를 비교할 수도 있겠지만, 그렇게 하면 시간복잡도가 높아져서 효율적이지 못합니다.효율적으로 해결하기 위해 set 자료구조를 활용했습니다. 파이썬의 set은 내부적으로 해시 테이블을 사용하여, 멤버십 테스트(어떤 요소가 집합에 있는지 확인)를 평균 O(1)의 시간복잡도로 수행합니다. 이를 통해 각 숫자가 첫 번째 수열에 존재하는지를 빠르게 확인할 수 있습니다.🤓 문제 풀이 단계1️⃣ 입력 받기 및 자료구조 초기화먼저 테스트 케이스(tc)의 수를 입력받습니다.각.. 2025. 1. 13. 이전 1 다음