9. 16236 아기상어 9.1. 문제유형 시뮬레이션 9.2. 해결과정 고려할 조건이 많은 까다로운 문제였다. 상어 위치를 찾고, BFS 탐색을 수행한다. 먹을 물고기가 있는지 없는지를 확인한다. 같은 거리라면 가장 위 물고기를, 그런 물고기가 여러마리라면 왼쪽 물고기를 먼저 먹는다. 상어의 크기 변화 조건 (먹은 물고기 수)을 체크한다. 먹이를 먹은 후, 새로운 위치 탐색을 위해 큐와 방문장소를 초기화한다. 먹이를 먹은 후, 현재까지의 시간을 저장한다. 9.3. 소스코드 from collections import deque dxs=[-1,1,0,0] dys=[0,0,-1,1] def BFS(x, y): Q, visited=deque([(x,y)]), set([(x,y)]) time=0 shark=2 e..

7. 14503 로봇 청소기 7.1. 문제유형 시뮬레이션 7.2. 풀이과정 3가지를 정확히 구현해야 해결할 수 있었다. 좌표 이동을 기존 좌표계와 반대로 구현해야한다. 좌표 이동 시 방향 d가 현재 기준 왼쪽부터 탐색하도록 구현해야 한다. 방향 d에 대해 후진 위치를 정확히 지정해주어야 한다. 1,2번까지는 제대로 구현했으나, 3번 제대로 지정하지 못해 오랜 시간이 소요되었다. 7.3. 소스코드 n, m = map(int, input().split()) r,c,d = map(int, input().split()) graph = [list(map(int, input().split())) for _ in range(n)] visited = [[0]*m for _ in range(n)] dx=[-1,0,1,0..

5. 13335 트럭 5.1. 문제유형 시뮬레이션 5.2. 풀이과정 주어진 로직을 따라가며 그대로 구현하였다. 두 가지 조건을 체크하며, 트럭을 통과시켰다. 다리가 꽉 차 있는가? 다리의 무게가 버틸 수 있는가? 다리가 꽉 차 있지 않고, 트럭 무게를 감당할 수 있으면 트럭을 통과시킨다. 다리 위의 트럭 초를 증가시키며 1칸씩 전진시킨다. ⭐ 주의할 점은 다리를 완전히 통과할 때, 동시에 다음 트럭이 들어와야 하는 경우를 고려해야한다. 따라서 미리 트럭을 제거해주었으므로, 마지막 소스코드에 1초를 추가해주었다. 5.3. 소스코드 from collections import deque n, w, l = map(int, input().split()) trucks = deque(list(map(int, inpu..

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..

8983 사냥꾼 1. 문제유형 이분탐색, 정렬 2. 자료구조 m (int): 사대의 수 n (int): 동물의 수 l (int): 사대 사정거리 gun (list): 사대 좌표를 담은 리스트 animal (list): 동물 좌표를 담은 리스트 cnt (int): 잡은 동물의 수 s (int): 해당 동물을 잡을 수 있는 최소 사대 좌표 e (int): 해당 동물을 잡을 수 있는 최대 사대 좌표 left, right(int): 사대 좌표의 최소값(0), 최대값(m-1) 인덱스 mid (int): 동물을 잡을 수 있는 사대 좌표값 (left+right)//2 3. 해결과정 ⭐ 사대 거리를 고정하고 가능한 동물 수를 구하려고 하면 시간 복잡도가 높아진다. (n^2) ⭐ 따라서 동물을 고정하고, 잡을 수 있는 ..

11977 Angry Cows 1. 문제유형 이분탐색, 정렬, 브루트포스 2. 자료구조 n (int): 건초의 수 bay (list): 건초의 위치를 담은 리스트 cur (int): 현재 건초의 위치 인덱스 rad (int): 폭발 사정거리 l (int): 옮겨 붙을 왼쪽 건초 좌표 인덱스 r (int): 옮겨 붙을 오른쪽 건초 좌표 인덱스 cnt (int): 폭발시켜 태운 건초의 최대값 3. 해결과정 ⭐왼쪽으로 옮겨 붙는 경우와 오른쪽으로 옮겨 붙은 경우를 나누어 구했다. ⭐왼쪽으로 옮겨 붙을 때는 터뜨린 가장 왼쪽 건초 index까지 count한 후 rad를 증가시킨다. ⭐오른쪽으로 옮겨 붙을 때 역시, 터뜨린 가장 오른쪽 건초 index까지 count한 후 rad를 증가시킨다. 0번째 건초부터 n-..

1654 랜선 자르기 1. 문제유형 이분탐색, Binary Search 2. 자료구조 lans (list): 보유한 랜선의 길이를 저장하는 리스트 left, right (int): 랜선 최소길이, 최대길이 mid (int): 지정한 랜선 길이. left, right의 중간값 cnt (int): 잘라서 얻어낸 랜선 개수 3. 해결과정 최대 랜선 길이가 2^31-1이므로 이분탐색을 떠올렸다. 항상 n개의 랜선 개수를 만들 수 있으므로, 랜선 길이를 지정 후 n개가 되는지 테스트한다. 최대 범위가 2^31-1인 것을 깜빡해서 1차시도 때 오답으로 책정되었다. left, right를 지정하되 right의 범위는 2^31-1을 포함하도록 설정한다. mid 계산 후 cnt가 n을 만족하는 지 확인한다. cnt가 n..

17393 다이나믹 롤러 1. 문제유형 Binary Search 2. 자료구조 ink (list): 잉크를 저장하는 리스트 vis (list): 점도를 저장하는 리스트 answer (list): 각 자리에서 최대 칠할 수 있는 타일 수를 저장하는 리스트 pos (int): 현재 타일 위치의 잉크값 l (int): 현재 위치의 바로 앞 타일 위치를 저장 r (int): 타일의 가장 끝 위치를 저장 mid (int): l,r의 중간값 res (int): 현재 위치에서 칠할 수 있는 최대 타일 위치 3. 해결과정 아이디어는 현재 위치 ink값보다 작은값들 중 최대값의 위치를 찾는다. 현재 위치 + 1 부터 ink값보다 작은 최대값 위치까지의 값을 카운트한다. 이 거리가 현재 위치에서부터 칠할 수 있는 타일 수..

12015 가장 긴 증가하는 부분 수열2 1. 문제유형 Binary Search, DP 2. 자료구조 lis (list): 최장 부분 순열을 저장하는 리스트 a (int): n개의 입력값을 저장하는 리스트 3. 해결과정 입력받은 값을 a에서 하나씩 꺼낸다. lis가 비어 있으면 꺼낸 값을 추가한다. 비어있지 않고, lis[-1] < num이면 꺼낸 값을 추가한다. 꺼낸 값이 lis의 마지막 값보다 작으면 이분탐색으로 들어갈 index를 찾고 덮어씌운다. 반복이 끝나면 lis의 길이를 출력한다. import sys from bisect import bisect_left input = sys.stdin.readline n = int(input()) a = list(map(int, input().split()..

2470 두 용액 1. 문제유형 Binary Search Two Pointer 2. 자료구조 l (int): 첫 번째 원소 인덱스 r (int): 마지막 원소 인덱스 flag (boolean): 탐색 여부를 결정하는 변수 3. 해결과정 시작하기 전, 정렬을 수행한다. 만약 첫 번째 값과 마지막 값이 모두 양수라면, 가장 작은 두 값을 출력한다. 만약 첫 번째 값과 마지막 값이 모두 음수라면, 가장 큰 두 값을 출력한다. 만약 첫 번째 값과 마지막 값의 부호가 다르다면, 탐색을 수행한다. 탐색과정은 flag and l < r동안 반복한다. sum의 절대값이 answer 값보다 작다면 answer에 sum을 저장하고, a,b = l,r를 저장한다. sum이 0보다 작다면 용해값을 키우기 위해 왼쪽값을 증가시..