Search for a command to run...
![[코테] 그리디 문제 - 무지의 먹방 라이브](https://cdn.hashnode.com/res/hashnode/image/upload/v1712215455263/1ac1f35a-8862-4e42-8d0c-e2bea01e04c0.png)
https://school.programmers.co.kr/learn/courses/30/lessons/42891 효율성 테스트에 신경써야 하는 문제 우선순위 큐를 활용해서 먹는 시간이 짧은 음식부터 큐에서 빼기 import heapq # 우선순위큐 활용: food_time이 짧은 음식부터 삭제 def solution(food_times, k): if sum(food_times) <= k: return -1 ...
![[코테] Bfs 토마토](https://cdn.hashnode.com/res/hashnode/image/upload/v1709032619170/70056896-c857-444b-9c99-45bfcb466806.png)
💡 첫 시도 시간초과! https://www.acmicpc.net/problem/7576 시간초과 코드 from collections import deque import sys input = sys.stdin.readline def bfs(x, y, visited): dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] while queue: x, y = queue.popleft() ...
![[코테] Dfs 문제 유형 - 그래프 내에서 구분하여 카운트 하기](https://cdn.hashnode.com/res/hashnode/image/upload/v1709019361383/b0585d72-c808-4169-83a9-2724f312e927.png)
메인 함수에서 for문을 통해 여러번 dfs를 돌리며, dfs 함수 내에서 그래프 정보를 변경해주는 경우
![[코테] DFS vs BFS](https://cdn.hashnode.com/res/hashnode/image/upload/v1708971211123/71f9386c-6a62-43b2-a602-4d084c24d6cf.png)
언제 뭘 선택해야 할까?
![[코테] 여행경로](https://cdn.hashnode.com/res/hashnode/image/upload/v1708971251412/27ce72ed-8ee7-4d13-a02f-ff4bbe50c4be.png)
💡 [출발지, 도착지] 형태로 주어진 비행기 티켓을 통해 모든 티켓을 사용할 수 있는 경우의 공항을 방문 순서 구하기 (단, 여러 공항을 방문할 수 있는 경우 알파벳이 빠른 공항부터 방문한다.) 틀렸던 코드 from collections import defaultdict def dfs(graph, route, depart): if graph[depart]: connected = graph[depart][0] ...
![[코테] Lis & Lcs](https://cdn.hashnode.com/res/hashnode/image/upload/v1707116316008/69933178-9014-48e1-856a-d9e5a336ba79.png)
LIS (Longest Increasing Subsequence) 어떤 수열에서 순서를 유지하며 부분 수열로서 증가하는 원소들의 최대 길이를 찾는 문제 [10, 22, 9, 33, 21, 50, 41, 60, 80]일 때, LIS는 [10, 22, 33, 50, 60, 80] 각 위치에서 현재 원소까지의 LIS를 구할 때, 이전 위치의 원소들과 비교하면서 더 큰 값의 LIS를 업데이트 n = int(input()) arr = list(...
![[코테 - Softeer] 출퇴근길](https://cdn.hashnode.com/res/hashnode/image/upload/v1706853194244/1511591b-2929-4047-a900-b681ca71faf8.png)
https://softeer.ai/practice/6248 💡 고려해야할 부분 => 단, 출퇴근길에서 목적지 정점을 방문하고 나면 동환이는 더 이상 움직이지 않는다. 즉, 출근길 경로에 T는 마지막에 정확히 한 번만 등장하며, 퇴근길 경로도 마찬가지로 S는 마지막에 한 번만 등장해야 한다. (출근길 경로에 S는 여러 번 등장해도 되고, 퇴근길 경로에 T는 여러 번 등장해도 된다.) 1. S->T 이동시 방문 노드2. T->S 이동시 방문...
![[코테] 경우의 수 고려하기 - Dynamic Programming](https://cdn.hashnode.com/res/hashnode/image/upload/v1706770941472/17ada507-6dba-47b2-9cc8-0419bcdecf24.png)
Top-down knapsack 문제를 탑다운 DP (재귀)로 풀어보자 import sys input = sys.stdin.readline sys.setrecursionlimit(10 ** 6) # item의 위치와 무게를 index로 하는 2차원 list dp 테이블에 누적 value 값을 저장해서 기억한다 def recur(cur, w): global ans if w > weight_limit: return ...
![[코테] 경우의 수 고려하기 - 순열과 조합](https://cdn.hashnode.com/res/hashnode/image/upload/v1706770883960/858cb05f-5459-4134-a873-9ca23c75bea4.png)
경우의 수 문제 다른 접근법: 순열과 조합 permutation : 순열 nPr 순서를 고려하여 r개 줄 세우기 from itertools import permutations arr = ['A', 'B', 'C'] nPr = permutations(arr, 2) print(list(nPr)) # [('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')] combina...