본문 바로가기

알고리즘 고득점 kit10

티켓으로 여행 경로 만들기: BFS 모든 공항은 알파벳 대문자 3글자로 이루어집니다. 주어진 공항 수는 3개 이상 10,000개 이하입니다. tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다. 주어진 항공권은 모두 사용해야 합니다. 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다. 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다. from collections import deque def solution(tickets): answer = [] graph = dict() # 출발 공항: 도착 가능한 공항 # 방문 가능한 공항 그래프 생성 for d, a in tickets: graph[d] = graph.get(d, []) + [a] # key=d에 아.. 2024. 2. 16.
단어 변환 최소 스텝: BFS 1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다. from collections import deque def bfs(begin, target, words): queue = deque() queue.append([begin, 0]) #시작 단어와 단계 0으로 초기화 while queue: now, step = queue.popleft() # 현재 단어, 단계 if now == target: return step # 단어를 모두 체크하면서, 해당 단어가 변경될 수 있는지 체크 for word in words: count = 0 for i, w in enumerate(now): # 현재 단어의 알파벳 하나씩 # 리스트 내 단어와 겹치지 않는 알파벳이 있.. 2024. 2. 16.
네트워크 덩어리 세기: DFS visited = [] def dfs(v, n, computers): global visited visited[v] = True for nei in range(n): # 인접노드 탐색 # unvisited & 인접 또는 노드 자신(1) if not visited[nei] and computers[v][nei]: dfs(nei, n, computers) def solution(n, computers): # computers = n*n # 네트워크 개수 global visited # 덩어리 세기 -> DFS # 외딴 노드도 count count = 0 visited = [False] * (n) for node_idx in range(n): if not visited[node_idx]: dfs(node_idx.. 2024. 2. 16.
target으로 계산되는 경우의 수 구하기: DFS 모든 경우의 수에서 target의 개수를 구하는 문제 사용하는 경우: 모든 노드를 방문 하고자 하는 경우이므로 DFS 계산 # 타겟 넘버를 만드는 방법의 수 -> DFS (모든 경우 탐색) answer = 0 def DFS(numbers, target, idx=0, value=0): global answer N = len(numbers) # idx가 마지막이고 value가 target과 같을 때는 answer if(idx == N and target == value): answer += 1 return elif(idx == N): # idx가 마지막이기만 하면 non answer return DFS(numbers,target,idx+1,value+numbers[idx])# idx번째 수를 더해준 경우로 .. 2024. 2. 16.
BFS: 게임 맵 최단거리 구하기 from collections import deque # 최단거리: BFS def solution(maps): answer = 0 n = len(maps) m = len(maps[0]) visited = [[False]*m for _ in range(n)] q = deque() q.append((0, 0)) # e,w,s,n dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] visited[0][0] = True # me while q: y, x = q.popleft() for i in range(4): nx=x+dx[i] ny=y+dy[i] # e/w/s/n 이동이 n*m 내부이고 maps에서 1인 경우(이동 가능) if 0 2024. 2. 16.
비트연산자: XOR 연산 직사각형 나머지 한 변 찾기 def solution(v): x = v[0][0] ^ v[0][1] ^ v[0][2] y = v[1][0] ^ v[1][1] ^ v[1][2] answer = [x,y] return answer 비트연산자 a = 60, b = 13 이라 가정했을 때, a = 0011 1100 b = 0000 1101 & AND 연산. 모두 참일때만 만족 (a & b) = 12 → 0000 1100 | OR 연산. 하나만 참이여도 만족 (a | b) = 61 → 0011 1101 ^ XOR 연산. 하나만 참일 때 만족 (a ^ b) = 49 → 0011 0001 ~ 보수 연산. (~a) = -61 → 1100 0011 > 2 = 15 → 0000 1111 (a ^ b ^ b) = 60 → 0.. 2024. 2. 15.
스택/큐 1. 기능개발 lv.2 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다. 먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요. 제한 사항 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다. 작업 진도는 100 미만의 자연수입니다. 작업 속도는 10.. 2024. 1. 8.
힙 1. 더 맵게 lv.2 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해, Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다. 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2) Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다. Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return. [제한 사항] scoville의 길이는 2 이상 1,000,000 이하입니다. K는 0 이상 1,000,000,000 이하입니다. sco.. 2023. 12. 22.
정렬 1. K번째 수 lv.1 배열 array의 i번째부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수 구하기 [매개변수] 배열 array [i, j, k]를 원소로 가진 2차원 배열 commands [제한사항] array의 길이는 1 이상 100 이하입니다. array의 각 원소는 1 이상 100 이하입니다. commands의 길이는 1 이상 50 이하입니다. commands의 각 원소는 길이가 3입니다. def solution(array, commands): answer = [] for i,j,k in commands: answer.append(sorted(array[i-1:j])[k-1]) return answer 한 줄로 표현한 코드는 아래와 같다. def solution(array, com.. 2023. 12. 21.
해시 1. 완주하지 못한 선수 lv.1 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion에서 완주하지 못한 선수 return하는 문제 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. completion의 길이는 participant의 길이보다 1 작습니다. 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다. 참가자 중에는 동명이인이 있을 수 있습니다. def solution(participant, completion): # len(completion) = len(participant)-1 # person=participant.. 2023. 12. 18.

티스토리툴바