본문 바로가기

알고리즘31

프로그래머스 - 고득점 킷 : 기능개발 https://programmers.co.kr/learn/courses/30/lessons/42586 코딩테스트 연습 - 기능개발 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 programmers.co.kr 생각하기 처음에는 각 진도 상황을 deque에 넣고 계속 시간별로 for문을 돌면서 popleft 할 것들을 찾아보려했다 하지만 시간별로 가면 최대 100의 시간을 돌것이고 100개의 기능이 있다면 100개의 기능들의 진도상황을 업데이트 해주어야 할것이다 -> O(100 * 100) = O(10000) 가장 앞에 있는 기능과 뒤에 기능들의 진도상태를 비교.. 2022. 3. 25.
[Hash] 프로그래머스 : 베스트 앨범 - 파이썬 Python https://programmers.co.kr/learn/courses/30/lessons/42579?language=python3 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 programmers.co.kr 생각하기 먼저 장르에 따라 dictionary에 해당 장르에 속하는 노래 idx를 분류 각 장르 딕셔너리를 돌면서 장르별 play 횟수를 counting 가장 높은 play 횟수를 가진 장르부터 각 노래 plays와 idx 기준으로 정렬 정렬된 list를 answer에 추가 구현하기 dictionary : {장르 : [idx의 리.. 2022. 3. 23.
[DP] 백준 11058 : 크리보드 - 파이썬 Python https://www.acmicpc.net/problem/11058 11058번: 크리보드 N = 3인 경우에 A, A, A를 눌러 A 3개를 출력할 수 있다. N = 7인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V를 눌러 9개를 출력할 수 있다. N = 11인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V, Ctrl-A, Ctrl-C, Ctrl www.acmicpc.net 생각하기 dp[N]을 N번 키보드를 눌렀을 때, 화면에 출력할 수 있는 A의 최대 개수라고 한다 먼저 각 버튼의 종류를 살펴보자면 A를 추가 출력하기 위해 한번 누르면 된다 ctrl + A, ctrl + C는 출력을 위한 것이 아니라 ctrl + V의 선행 조건이.. 2022. 3. 16.
[BFS] 백준 1600번 : 말이 되고픈 원숭이 - 파이썬 Python https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 생각하기 처음에는 말의 움직임과 원숭이 본래 움직임을 통합하여 BFS로 풀고자 하였다. 하지만 간과한 사안이 있었다. 말의 움직임과 원숭이 본래 움직임이 전혀 다른 패턴이기 때문에 원숭이의 본래 움직임으로 방문한 칸을 나중에 말의 움직임으로 더 짧은 시간에 방문할 수 있다는 점이었다. 만약 움직임의 패턴이 다른 경우, 칸까지 움직인 최소 거리를 하나의 visited 배열에 넣는 방.. 2022. 3. 10.

티스토리툴바