코딩테스트

[python] 프로그래머스 - 디스크 컨트롤러

🤔문제 해결 Lv3 | 우선순위 큐 파이썬에서는 heapq 를 사용합니다. 먼저 현재 시간을 항상 계산해 줍니다. 현재 시간보다 투입시간이 작은 작업들을 힙큐에 넣어줍니다. 힙큐에 값이 여러개 들어있더라도, heappop() 을 하게 되면 작업시간이 가장 짧은 작업이 나오게 됩니다. ( 힙큐에서는 최솟값이 나오게 됩니다 ) 작업시간만큼 현재시간 을 늘려주고, 해당 작업의 대기시간+작업시간 을 따로 저장해 둡니다. 한 작업이 끝나고 나면 시간이 흘렀기 때문에 다시 현재 시간보다 투입시간이 작은 작업들을 힙큐에 넣어줍니다.(아까 넣은 작업 제외) 똑같이 heappop() 으로 현재시간과 작업시간을 저장합니다. 💨 업무투입시간이 오름차순 정렬이 안되어있어서 먼저 정렬을 해줘야 합니다. 💻소스 코드 import..

[python] 백준 - 2343. 기타 레슨

🤔문제 해결 S1 | 이분 탐색 이분 탐색 문제는 무엇을 탐색 할 것인지가 가장 중요합니다. 이 문제에서는 블루레이의 최소 크기 를 찾아야 합니다. 처음에 각각의 블루레이에 레슨들을 순서대로 담아야 합니다. 블루레이의 크기가 11라고 가정해 보겠습니다. 그렇게 되면 레슨들의 합이 11을 넘어서는 안됩니다. 그럼 아래와 같은 결과를 얻을 수 있습니다. 총 5개의 블루레이에 담아야 합니다. 테스트 케이스에서는 3개에 담으라고 했으니 답이 될 수 없습니다. 그렇다면 블루레이 크기를 늘려서 한 블루레이에 좀 더 많이 담아야 겠다는 생각을 할 수 있습니다. 15라고 가정해 보겠습니다. 총 4개의 블루레이에 담았습니다. 하지만 여전히 블루레이 개수가 많습니다. 블루레이의 크기를 더 늘려야 합니다. 만약 30으로 크..

[python] 백준 - 1926. 그림

🤔문제 해결 S1 | BFS, 그래프 그림을 하나 선택 한다. 그 그림의 상하좌우를 탐색한다. 만약 상하좌우에 그림이 있다면 그 그림을 선택 후 다시 상하좌우 선택한다. 더 이상 처음 선택한 그림과 연결된 그림이 없을 때 까지 탐색. 위의 과정을 반복한다. 처음 그림을 선택하면 그림의 갯수 +1 그림선택후 상하좌우 탐색하면서 그림을 찾으면 그림의 크기 +1 💨 기본적인 BFS 문제 💻소스 코드 from collections import deque def bfs(x, y): q = deque() q.append((x, y)) images[i][j] = 0 size = 1 # 최초 들어갈 때 그림 크기 1로 시작 while q: x, y = q.popleft() for k in range(4): # 상하좌우..

[python] 백준 - 1743. 음식물 피하기

🤔문제 해결 S1 | BFS 이번에는 2차원리스트를 활용하지 않고 set()을 활용하여 문제를 해결했다. 각각의 좌표가 주어져 있으므로 쓰레기를 하나 선택해 상하좌우 BFS탐색을 한다. 주변의 쓰레기를 선택할 때마다 visited 에 add 해준다. 또 count + 1 을 해줘서 쓰레기 더미의 크기를 answer 에 담는다. 💨 set() 을 쓰는 이유 if tmp in set() : 이렇게 tmp가 set()에 있는지 없는지 확인할 때 시간복잡도가 O(1) 이다. 하지만 if tmp in list : list의 경우 O(n) 이다. 💻소스 코드 import sys from collections import deque def bfs(x, y): q = deque() q.append((x, y)) cnt..

[python] 프로그래머스 - 외벽 점검(2020 KAKAO BLIND RECRUITMENT)

🤔문제 해결 Lv 3 | 정답률: 0.6% 주어진 값의 크기가 크지 않기 때문에 완전탐색으로 해결이 가능하다. 먼저 친구를 순열로 만든다. ex) [1,2,3] 이면 [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] 외벽이 원형이므로 앞과 뒤가 이어져 있다고 생각해야 한다. 취약점도 첫번째 취약점을 먼저 갈것인가 두번째 취약점을 먼저 갈것인가... 순서를 정해서 가야한다. - 첫번 째 테스트케이스의 취약점([1, 5, 6, 10])을 배열(n=12)로 나타내면 [0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0] 위의 경우는 첫번째 취약점(1)이 가장 먼저 나오는 경우 - 다음 취약점 2가 가장 먼저 나오는 경우는 0,1을 맨뒤로 옮겨주면 된다. ..

[python] 프로그래머스 - 블록 이동하기(2020 KAKAO BLIND RECRUITMENT)

🤔문제 해결 1. Lv3 | BFS 심화 2. BFS를 돌릴 q와 방문체크할 visited리스트를 준비한다. (1) q는 deque를 이용. 로봇의 좌표 4가지 (x1,y1,x2,y2)와 현재의 거리 d 를 넣는다. (2) visited에는 로봇의 좌표만 넣는다. 3. BFS를 돌린다. (1) 먼저 끝점에 도달했다면 바로 멈춰주고 거리를 출력한다. (2) 그렇지 않다면 로봇이 세로인경우와 가로인경우를 나누고, 상하좌우 움직일 수 있는 지 체크한다. (3) 로봇이 세로인 경우 오른쪽 이동이 가능하면 오른쪽 회전도 가능하다. 마찬가지로 왼쪽이동이 가능하면 왼쪽으로 회전도 가능하다. (4) 가로도 마찬가지 (5) 이동이나 회전이 가능하면 visited리스트를 확인해 방문한적이 없으면 q와 visited에 넣어..