2110 공유기 설치 1. 문제유형 Binary Search 2. 자료구조 cnt (int): 공유기 개수 left (int): 최소 거리 == 1 right (int): 최대 거리 == (마지막 집 좌표 - 첫 번째 집 좌표) mid (int): 공유기 간 거리 == (left + right) // 2 wifi (int): 공유기가 설치된 집 좌표 3. 해결과정 집 좌표 최대 크기가 10억이므로, 순차탐색이 아닌 이분탐색을 떠올려볼 것 공유기 간 최대거리를 찾는 것이 목적이므로 이분탐색 활용할 것 left

1. 2343 기타 레슨 1.1. 문제유형 Binary Search1.2. 자료구조 cnt (int) : 블루레이 개수 file (int) : 레슨을 저장한 파일 크기 mid (int) : 블루레이 크기 left (int) : 가장 작은 블루레이 크기 right (int) : 가장 큰 블루레이 크기1.3. 해결과정 가장 작은 블루레이 크기는 max(lesson), 최대 크기는 sum(lesson)이다. 주어진 m개의 블루레이에 강의를 저장하되, 블루레이 크기는 작을수록 좋다. 따라서 블루레이의 크기를 찾는 이분탐색 문제로 해결할 수 있다. left는 max(lesson), right는 sum(lesson)로 설정한다. left m: left = mid+1 else: answer = mid right = ..

1. 12018 Yonsei TOTO 12018번: Yonsei TOTO 연세대학교 수강신청이 얼마 전부터 바뀌어, 마일리지 제도로 바뀌었다. 이 제도는 각각의 학생들에게 마일리지를 주어 듣고 싶은 과목에 마일리지를 과목당 1~36을 분배한다. 그리고 모두 분배 www.acmicpc.net 1.1 자료구조 mylect (max heap) : 내 강의를 담을 힙 자료구조 milege (min heap) : 수강 신청한 마일리지 점수를 저장한 힙 자료구조 → mylect가 max heap인 경우 : 마일리지를 초과할 경우 큰 마일리지가 소모되는 강의를 우선적으로 제거하기 위함 1.2 해결과정 신청인원(P)과 수강인원(L) 차이를 구해 마일리지와 함께 heap에 저장한다. heap은 마일리지를 최소로 사용하므..

12906 새로운 하노이 탑 12906번: 새로운 하노이 탑 첫째 줄에 막대 A에 놓여져 있는 원판의 개수와 막대 A의 상태, 둘째 줄에 막대 B에 놓여져 있는 원판의 개수와 막대 B의 상태, 셋째 줄에 막대 C에 놓여져 있는 원판의 개수와 막대 C의 상태가 주 www.acmicpc.net 📌문제유형 set, map bfs queue 📌자료구조 q (queue) : 방문할 하노이 탑을 담는 Queue 자료구조 visited (set) : 이미 방문한 하노이 탑을 담는 Set 자료구조 count (int) : 이동횟수를 저장하는 변수 📌해결과정 queue에 각 막대별 처음 원판 상태와 이동횟수를 tuple로 저장한다. q가 존재할 동안 다음 loop를 반복한다. q를 꺼낸 후 A,B,C 막대 상태를 조합해..

def solution(numbers, hand): ''' Notes: 1. 왼손, 오른손 현재 위치를 저장하는 자료구조 생성 2. 1,4,7이면 왼손을 3,6,9면 오른손으로 입력 3. 2,5,8,0이면 왼손, 오른손과의 거리 계산 후 작은 손 선택 4. 왼손, 오른손 거리가 같을 경우 hand의 선택에 따라 선택 Args: numbers (list): 입력할 키패드 숫자(int)를 담은 리스트 hand (str): 왼, 오른손 잡이를 나타내는 문자열 Returns: answer (str): 사용한 손 순서를 담은 리스트 ''' answer = '' pad = [ [1,2,3], [4,5,6], [7,8,9], ['*',0,'#'] ] l = [3, 0] r = [3, 2] for n in number..

🔸 문제 접근 방식 ❗ 풀이 성공, 시간 초과 participant, completion을 Queue에 넣는다. completion을 꺼내 participant에 있으면 participant에서 제거한다. completion 요소가 없어질때까지 반복하고 남아있는 participant를 반환한다. → 이 문제의 경우 답을 구할 수는 있지만, 효율성 문제가 있었다. 시간복잡도가 O(N^2)일 경우 통과할 수 없다. ⭕ 시간 초과 해결 best_solution1, 2로 풀이 시 효율성 문제를 통과할 수 있었다. best_solution1의 경우, 정렬 후 최대 $10^5$번 비교를 수행하기 때문에 O(N)만 수행하면 된다. best_solution2의 경우 해시를 사용한 풀이방식으로 시간 단축에 효과적이었다...

🔸 문제 접근 방식 truck_weights를 큐에 넣는다. bridge_length보다 작고, weight를 넘지 않으면 trcuk을 Queue에 넣는다. truck은 bridge_length + 1이 되면 Queue에서 빠져나온다. truck_weights가 비어있고, Queue에 남아 있을 경우 seconds를 증가시킨다. truck이 bridge_length +1이 되면 Queue에서 빠져나온다. 💧 Source Code from collections import deque def solution(bridge_length, weight, truck_weights): ''' Notes: https://programmers.co.kr/learn/courses/30/lessons/..

🔸 문제접근방식 progresses, speeds를 큐에 넣는다. progresses의 0번째 값이 100이상이면 꺼낸다. speeds도 progress 꺼낼 때 0번째부터 함께 꺼낸다. 1일마다 speeds만큼 progresses를 더한다. progresses 원소를 모두 꺼낼 때까지 2-3을 반복한다. 💧 Source Code from collections import deque def solution(progresses, speeds): ''' https://programmers.co.kr/learn/courses/30/lessons/42586 Notes: 1. progresses를 큐에 넣고 100이상이면 꺼낸다. 2. 1일마다 speeds만큼 progresses를 더한다. 3. 하루마다 1,2번..

🔸 문제접근방식 priorities를 위치를 저장하는 값과 함께 큐에 넣는다. 더 큰 값이 있다면 0번째 값을 맨 뒤로 보낸다. 더 큰 값이 없다면 해당 값을 출력하고 answer를 1증가시킨다. 해당 위치의 값이 location이라면 answer를 반환한다. 💧 Source Code from collections import deque def solution(priorities, location): '''https://programmers.co.kr/learn/courses/30/lessons/42587 Notes: 1. priorities의 0번째보다 더 큰 값이 있는지 확인한다. 2. 더 큰 값이 있다면 0번째값을 맨 뒤로 보낸다. 3. 더 큰 값이 없다면 해당 값을 출력한다. Args: prior..

🔸 문제 접근 방식 가장 무거운 사람을 먼저 태운다. 가장 가벼운 사람부터 보트에 태워나간다. 보트 무게가 limit를 초과하면, 가벼운 사람을 한 명 내리고 1번으로 돌아간다. ❗ 주의 사항 처음에 리스트의 원소가 남아있을 때까지 While문을 반복하였다. 하지만 리스트 삭제 연산 수행 시 시간초과가 발생했다. 리스트 원소 최대값이 50,000임에도 비효율적인 알고리즘으로 판명되었다. 따라서 리스트를 삭제하는 대신, left, index 포인터를 두고 indexing하였다. 💧 Source Code def solution(people, limit): ''' https://programmers.co.kr/learn/courses/30/lessons/42885 Notes: 1. 가장 무거운 사람을 먼저 태..