https://programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr BFS문제이다. from collections import deque def solution(n, computers): cnt = 0 visited = [False] * (n+1) graph = [[] for _ in range(n)] q = deque() # 연결되어 있는 컴퓨터 graph에 저장 for i in range(n): for j in rang..
https://programmers.co.kr/learn/courses/30/lessons/43165?language=python3 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 무난한 DFS/BFS 문제이다. def solution(numbers, target): global answer answer = 0 cnt = 0 dir = [-1, 1] # 숫자를 더하거나 빼거나 둘 중 하나이므로 [-1, 1] 선언 def dfs(cnt, k): global ..
programmers.co.kr/learn/courses/30/lessons/42885 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr # 문제분류가 Greedy로 되있긴 한데.. greedy가 솔직히 제일 어려운 것 같다. 쉬운 문제랑 개념자체는 쉬운데 그냥 분류없이 문제를 봤을 때 '아, 이건 그리디로 풀어야겠다.'라고 떠올리기도 힘들고 그걸 증명해야하기 때문에 더 어려운 것 같다. # 풀고보니 이분탐색 느낌도 나고 '투 포인터'인 것 같기도 하다. def solution(peo..
programmers.co.kr/learn/courses/30/lessons/42628 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr 기본 heapq문제이다. 파이썬에서 '우선순위큐'를 사용하려면 priorityQueue가 아닌 heapq를 사용해야한다. import heapq def solution(operations): # 힙 정렬 def heap_sort(nums): heap = [] for num in nums: heapq.heappush(heap, num) sorted_nums = [] while heap: sorted_nums.append(heapq.heappop(heap)) return sorted_nums h = [] for o in operations: op = o.s..
programmers.co.kr/learn/courses/30/lessons/42583 코딩테스트 연습 - 다리를 지나는 트럭 트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이 programmers.co.kr * 시뮬레이션 문제는 확실히 디버깅을 할 때, 노트에 직접 시뮬레이션 돌려가며 하거나 컴퓨터에 1초마다 결과값을 출력해가며 비교해야해서 오래걸리는 것 같다. # bridge_length: 다리길이, weight: 다리가 최대 견딜 수 있는 무게, truck_weights: 대기트럭, bridge: 현재 다리에 있는 트럭 상태이다. # 원래 10~16번째 줄을 ..
programmers.co.kr/learn/courses/30/lessons/42586 코딩테스트 연습 - 기능개발 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 programmers.co.kr 다른사람들 풀이를 보니 O(N^2)풀이가 많아 '이러면 스택을 쓰는 의미가 없지않나' 생각이 들었다. deque를 사용해 popleft()와 appendleft()를 통해 O(1)에 풀이를 해보았다. import math from collections import deque def solution(progresses, speeds): stack, answer = deq..
programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 무난한 DP문제이다. 오른쪽과 아래로만 갈 수 있으므로 dp연산을 할 때 윗 좌표값, 왼쪽 좌표값만 고려해주면 된다. def solution(m, n, puddles): dp = [[0] * m for _ in range(n)] dp[0][0] = 1 # 물에 잠긴 곳은 -1 넣어줌 if puddles: for i in puddles: dp[i[1] - 1][i[0..
programmers.co.kr/learn/courses/30/lessons/42579 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 programmers.co.kr Python의 dictionary는 '해쉬테이블'형식으로 구현되어 있어서 속도가 빠르다. 코테나 알고리즘을 공부하면서 '해시'가 나온다면 파이썬은 대부분 dictionary로 풀면 될 것이다. def solution(genres, plays): answer = [] dic = {} for i in range(len(genres)): if genres[i] in dic: # ..
모르는 사이에 조금씩 조금씩..
