1. 2606 바이러스 1.1. 문제유형 그래프, BFS, DFS 1.2. 자료구조 Q (deque): BFS 구현을 위한 큐 자료구조 node (int): Q에서 꺼낸 현재 노드(Vertex) next (int): node와 연결되어 있으며 다음에 방문할 노드(Vertex) graph (2d-list): 인접 리스트(Adjacency list)로 노드에 연결된 간선(edge) 정보 저장 visited (1d-list): 방문 여부를 확인하는 리스트 1.3. 해결과정 ⭐1번 노드부터 BFS를 순회하며 방문한 장소는 True로 표시한다. 방문이 끝난 후 True의 개수를 출력한다. 이 때, 1번은 포함하지 않으므로 -1한 값을 출력한다. 1.4. 소스코드 from collections import dequ..

1072 게임 1. 문제유형 Binary Search 2. 자료구조 중요한 점은 y/x * 100과 같이 실수형으로 계산 후 int로 바꿔줄 시 정확하지 않을 수 있다. 따라서 실수형 계산이 아닌, y * 100//x처럼 정수형 계산으로 바꿔 승률을 계산해야 한다. z (int): 초기 승리한 게임 수 y/전체 게임 수 x * 100 target (int): 승리한 경기수를 이분탐색하며 계산한 승률 left (int): 더해나갈 승리한 횟수의 최소값 right (int): 더해나갈 승리한 횟수의 최대값 mid (int): (left+right)//2 == 중간값으로 실제 더할 승리한 횟수 3. 해결과정 승리한 게임 수를 찾는 게 핵심이며, 범위는 0부터 x(10 ** 9)까지이다. 따라서 1부터 적용할 ..

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은 마일리지를 최소로 사용하므..

🔸 문제 접근 방식 ❗ 풀이 성공, 시간 초과 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. 가장 무거운 사람을 먼저 태..