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: # ..
programmers.co.kr/learn/courses/30/lessons/77485 코딩테스트 연습 - 행렬 테두리 회전하기 6 6 [[2,2,5,4],[3,3,6,6],[5,1,6,3]] [8, 10, 25] 3 3 [[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]] [1, 1, 5, 3] programmers.co.kr "2021 Dev-Matching: 웹 백엔드 개발자(상반기)" 문제이다. 문제에서 지시한대로 따라가며 노가다로 푸는 구현, 시뮬레이션문제이다. 1. rows, columns를 입력받고 행렬을 만든 뒤 1부터 순차적으로 행렬에 넣어준다. 2. queries를 돌며 각각 회전을 실행한다. 주석에 설명했듯이 우측방향(맨 윗줄)을 회전시켜주고 하(맨 오른쪽), 좌..
programmers.co.kr/learn/courses/30/lessons/77484?language=python3 코딩테스트 연습 - 로또의 최고 순위와 최저 순위 로또 6/45(이하 '로또'로 표기)는 1부터 45까지의 숫자 중 6개를 찍어서 맞히는 대표적인 복권입니다. 아래는 로또의 순위를 정하는 방식입니다. 1 순위 당첨 내용 1 6개 번호가 모두 일치 2 5개 번호 programmers.co.kr 최근에 진행된 "2021 Dev-Matching: 웹 백엔드 개발자" 코딩테스트에 출제된 문제이다. def solution(lottos, win_nums): rank = {6: 1, 5: 2, 4: 3, 3: 4, 2: 5, 1: 6, 0: 6} cnt = 0 super = lottos.count(0..
모르는 사이에 조금씩 조금씩..
