알고리즘 문제/Programmerse42 [Programmers] 디스크 컨트롤러 문제 : https://programmers.co.kr/learn/courses/30/lessons/42627 먼저 시작시간이 가장 빠르고, 시작시간이 같다면 소요시간이 적은 순으로 jobs를 정렬한다. 마지막 작업이 종료된 시간(let, 종료시간)을 저장하는 변수를 하나 만들고 0으로 초기화시킨다. 가장 먼저 시작되는건 jobs의 첫번째 요소일 것이다. 작업 소요시간이 적은 순으로 정렬되는 최소힙을 하나만들어서 가장 먼저 시작되는 jobs의첫번째 요소를 큐에 넣는다. 이제 최소힙 빌때까지 잡들의 최소 소요시간을 구해서 sum 변수에 더해나간다. 최소힙의 첫번째 요소를 꺼내서 job의 실제 시작시간을 구한다. 만일 이전 잡의 종료시간이 현재 job의 시작시간보다 작거나 같으면 현재 job의 시작시간이 실.. 2021. 6. 11. [Programmers] 순위 문제 : https://programmers.co.kr/learn/courses/30/lessons/49191 A가 B를 이겼는데 B가 C를 이겼다면 A가 C를 이긴것과 같다. 어디선가 많이 본 것 같은.. A에서 B로 가는 최단거리가 x1이고, B에서 C로 가는 최단거리가 x2라면 A에서 C로 가는 거리의 최단거리 중 하나가 x1 + x2 일 수 있다. 플로이드 워셜 알고리즘의 기본 이론이다. 알고리즘이론 글을 안쓴지 오래되었는데 다익스트라랑 벨만포드는 포스팅했는데 플로이드는 없네. 그렇지만 최단거리 알고리즘 중에 제일 좋아하는 알고리즘이다. (구현이 간단해서 ㅎㅎ) 플로이드 워셜을 돌려서 승부결과를 nxn 크기의 matches 배열에 채운다. matches[A][B] = A가 B를 이겼으면 true... 2021. 6. 11. [Programmers] 입국심사 문제 : https://programmers.co.kr/learn/courses/30/lessons/43238 문제 풀기전에 문제 분류를 봐버렸다.. 이분탐색 문제를 풀고싶었다기 보다는 레벨3 문제를 풀고싶었던건데 문제분류가 너무 잘보여버림. 이분탐색이란걸 알았으니 어떻게 이분탐색으로 해야하는지 분석해보자. 입국심사를 기다리는 사람은 최대 10억명. 한 명의 심사관이 걸리는 시간은 최대 10억분. 심사관의 수는 최대 10만. 이분탐색은 내부 조건이 정답이 가능한지 안한지를 판단할 수 있어야한다. 그럼 주어진 조건을 어떻게 정답이 되는지 안되는지 알 수 있을까. m분안에 모든 심사원이 최소 n명을 처리할 수 있다면 m분이 정답이 될 수 있다. 모든 심사원이 처리할 수 있는 시간 = 각 심사원들이 m분안에 .. 2021. 6. 10. [Programmers] 가장 먼 노드 문제 : https://programmers.co.kr/learn/courses/30/lessons/49189 bfs로 풀 수 있다. bfs를 돌면서 현재 노드, 1번 노드와의 거리를 저장한다. 만약 노드와의 거리가 갱신되면 정답 변수를 0으로 갱신한다. 노드를 탐색할때 정답변수에 1을 더한다. 시간복잡도는 O(V + E). V = 정점개수, E = 간선개수 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/programmers/Graph/%EA%B0%80%EC%9E%A5%20%EB%A8%BC%20%EB%85%B8%EB%93%9C.cpp 2021. 6. 9. [Programmers] N으로 표현 문제 : https://programmers.co.kr/learn/courses/30/lessons/42895 DP 관련 문제이니 DP로 풀어야겠는데 number를 인덱스로 dp 배열을 만드려고하니 막막하다. 막힐때는 제한사항을 보면서 문제 제작자의 의도를 파악해보자. 제한사항 1. 1 2021. 6. 8. [Programmers] 다단계 칫솔 판매 문제 : https://programmers.co.kr/learn/courses/30/lessons/77486 추천인을 저장하는 parentMap(key = 판매원, value = 추천인)과 총 이익을 저장하는 priceMap(key = 판매원, value = 이익)을 만든다. enroll, referral 을 탐색하며 parentMap을 세팅한다. seller, amount 배열을 탐색하며 priceMap 을 세팅해보자. 얻은 이익은 칫솔가격이 100이므로 amount[i] * 100이다. 이익의 10프로를 제외한 가격을 자신한테 더하고 10프로는 추천인한테 배분한다. 만약 parentMap[탐색중인 판매원] value가 "-"가 아닌 경우 이익의 분배를 다시 해야하므로 parentMap[탐색중인 판매.. 2021. 6. 1. 이전 1 2 3 4 5 ··· 7 다음
