본문 바로가기

알고리즘74

프로그래머스 - 고득점 킷 : 기능개발 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.
[알고리즘 개념] 최단경로 알고리즘 - 다익스트라, 플로이드 워셜, 벨만 포드 다익스트라 알고리즘 특정 노드에서 다른 노드(One To Any)로 가는 각각의 최단 경로 구하기 모든 vertex 사이의 edge의 cost는 음수가 아니어야 한다 -> 그렇기 때문에 실제 길 찾기 알고리즘으로 쓰인다 "가장 비용이 적은 vertex를 선택하여 경로 삼는 방식 -> 가장 작은 비용이 적은거를 기반으로 다음 노드를 선택하면 그 다음 노드도 결국 비용이 작은 것이다!!! " 따라서 알고리즘 분류를 한다면 greedy 알고리즘 에 속한다 준비 사항 최단 거리 배열 - 각 idx는 vertex를 가리키고 출발점에서 해당 vertex까지의 최단 거리 / 각 vertex에 대한 현재까지의 최단 거리 visited 배열 - 방문했는지 체크 과정 최단 거리 배열을 1e9 로 초기화 최단 거리 배열의 .. 2022. 3. 14.

티스토리툴바