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. 가장 무거운 사람을 먼저 태..

🔸 문제 접근 방식 stack에 값이 없거나, 더 작은 경우 넣는다. top에 위치한 값이 더 작으면 해당 값을 배내고, k를 감소시킨다. k가 0이되면 남은 값들을 스택에 넣는다. 스택이 꽉 찼는데, k가 남아있다면 맨 위에서 k개를 꺼낸다. 💧 Source Code def solution(number, k): ''' Notes: 1. stack에 값이 없거나, 더 작은 경우 넣는다. 2. top에 위치한 값이 더 작으면 해당 값을 빼내고, k를 감소시킨다. 3. k가 0이되면 남은 값들을 스택에 넣는다. 4. 스택이 꽉 찼는데, k가 남아있다면 맨 위에서 k개를 꺼낸다. Args: number (str) : 주어진 숫자 (문자열로 주어짐) k (int) : 삭제할 숫자 개수 Returns: answe..

🔸 문제접근방식 'A' 문자가 아닌 곳으로 이동하기까지 왼쪽, 오른쪽 이동 횟수를 계산 후 최소값을 더한다. 왼쪽 or 오른쪽 이동 후, 문자 완성을 위해 'A'에서부터 문자까지, 'Z'에서부터 문자까지 횟수를 계산 후 최솟값을 더한다. 모든 위치를 다 방문하여 문자열을 완성 시 종료한다. 파이썬에서 리스트는 음수로도 indexing이 가능하다. 가운데 중간 지점에서부터 계산하는 것이 아닌 주어진 조건 'A'부터 혹은 뒤에서 'Z'부터 계산할 것 💧 Source Code def solution(name): ''' Programmers 조이스틱 문제풀이 - Greedy Notes: 1. 'A' 문자가 아닌 곳으로 이동하기까지 왼쪽, 오른쪽 이동 횟수를 계산 후 최소값을 더한다. 2. 왼쪽 or 오른쪽 이동..