💡Algorithm31 [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. [python]1012_유기농 배추 사용한 자료구조 및 개념 : bfs, dictionary, set 💡 문제풀이 아이디어 및 어려웠던 점 💫 아이디어 1️⃣ 2차원 배열판을 만들 필요없이 배추 위치 입력값들로 바로 확인한다! 2️⃣ 배추 좌표를 키로하고 인덱스를 값으로 저장하는 딕셔너리를 만든다. ⇒ 지금 현재 배추 위치에서 상,하,좌,우에 해당 하는 값들의 인덱스를 빠르게 조회를 하기 위함이다. ✅ 딕셔너리는 해시 테이블을 기반으로 하므로 키를 사용한 값의 조회가 평균 O(1)의 시간 복잡도로 매우 빠르다. 이를 활용하면 특정 (x, y) 좌표가 존재하는지와 그에 해당하는 인덱스를 매우 빠르게 찾을 수 있다. 3️⃣ 배추 딕셔너리의 모든 키(배추 좌표)들을 가지고와 set으로 만든다. ⇒ 지금 현재 배추 위치에서 상,하,좌,우에 해당 .. 2023. 10. 8. [python]13023_ABCDE 사용한 자료구조 및 개념 : DFS, 백트래킹 💡 문제풀이 아이디어 및 어려웠던 점 💫 아이디어 1️⃣ 5개의 노드가 연속적으로 이루어진 경우가 있으면 1을 출력하는 문제이다. 2️⃣ dfs 재귀를 활용하여 깊이가 4인 경우를 찾는다. dfs에 현재 노드와 깊이를 인자로 넘겨준다! 3️⃣ 깊이가 4인 경우 result값을 1로 바꾸고 return하여 함수를 탈출! 반복문도 break한다! 4️⃣ 끝까지 탐색했는데도 깊이가 4가 되지 않는다면 재탐색을 해야하므로 현재 노드(v)를 False로 바꿔준다. ⇒ 백트래킹! ✅ 백트래킹이란? Promising : 트리 구조를 기반으로 DFS로 깊이 탐색을 진행하면서 각 루트에 대해 조건에 부합하는지 체크한다. Pruning : 해당 트리에서 조건에 맞지않는 노드는.. 2023. 9. 29. [python]2668_숫자고르기 사용한 자료구조 및 개념 : DFS 💡 문제풀이 아이디어 및 어려웠던 점 💫 아이디어 ❣️ 이 문제는 사이클이 생기는 노드를 찾아내면 되는 문제이다. 1️⃣ arr리스트의 입력값을 받을 때 인덱스와 연결을 맞추기 위해 -1을 해준다. 2️⃣ arr의 각 인덱스는 노드를 나타내며, 그 인덱스에 해당하는 값은 해당 노드에서 다음으로 연결된 노드를 나타내게 된다. 3️⃣ dfs의 인자로 시작노드 2개를 넣는다. (출발점으로 다시 돌아오는지 확인을 위해!) 4️⃣ 현재 순회하는 노드가 시작점으로 다시 되돌아 온다면 사이클이 생기는 것이므로 결과 리스트에 추가한다. 👻 어려웠던 점 🚨 조합을 사용해서 중복제거 값이 0이면 결과 리스트에 추가하는 방법으로 풀었는데 시간 초과가 났다..! 사이클을 만드는 것을 찾으면.. 2023. 9. 27. 이전 1 2 3 4 ··· 6 다음
