우선순위 큐
-
BOJ) 스택 수열 (1874 번)알고리즘/백준 2021. 2. 3. 17:26
스택 수열 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 1 ~ n의 수를 스택에 넣었다가 뽑아 늘어놓아서 하나의 수열을 만든다. 이때, 스택에 push하는 순서가 반드시 오름차순을 지켜야한다. 조건에 맞으면 push와 pop하는 행위에 대한 문자열을, 충족하지 못하면 NO를 출력하는 문제다. 문제는 간단했다. 배열을 돌면서 현재 스택의 top과 같은지, 혹은 대소인지 비교해주어 문제를 풀었다. 스택의 top보다 순회중인 배열..
-
프로그래머스 Lv.3) 섬 연결하기알고리즘/프로그래머스 고득점 Kit 2020. 6. 5. 18:41
고득점 Kit - Greedy(탐욕법) 섬 연결하기 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 풀이 find - union가 부족하다고 판단되서, 다시 감을 잡고자 다시 풀었다. 풀이 방법은 처음 풀었을 때와 크게 차이점이 없었고, find 메소드와 union메소드만 잘 짜준다면 find - union문제는 무리 없이 풀 수 있을 것 같다. 로직 1. parents 배열을 선언 및 초기화한다. 2. 두 섬의 번호와 비용을 담을 class Island 를 선언한다. 3. 주어진 연결 정보를 담은 배열을 순회하면서, Island 변수를 만들어 우선순위 큐에 담아준다. ( 비용 오름차순 정렬) 4. Queu..
-
프로그래머스 Lv.3) 디스크 컨트롤러 (HEAP)알고리즘/프로그래머스 고득점 Kit 2020. 6. 5. 18:34
프로그래머스 고득점 Kit - HEAP 디스크 컨트롤러 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를�� programmers.co.kr 풀이 저번에 풀었을 때보다 더 빨리 풀기는 했지만, 이놈의 고질병인 문제를 대충 읽는다는게 발목을 계속 잡는다. 정말 중요한 부분인데, 사소한거 하나에 꼬이게 되면 정말 골치가 아프다... 문제 제발 꼼꼼하게 읽자... 문제에서 막혔던 부분을 떠올려보자면, 대기시간을 구하는 방법, 작업 간 공백이 있을 때 시간을 구하는 방법 정도가 되겠다. 대기시간은 몇 번 삽질끝에 쉽게 구했는데, 공백기도 대기시..
-
프로그래머스 Lv.3) [1차] 셔틀버스알고리즘/프로그래머스 카카오 2020. 6. 2. 21:33
2018 KAKAO BLIND RECRUITMENT 셔틀버스 코딩테스트 연습 - [1차] 셔틀버스 10 60 45 [23:59,23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59] 18:00 programmers.co.kr 풀이 카카오 문제 중, 추석 트래픽을 풀 때 시간 문자열을 int형으로 변환하여 푼 경험 덕분인지 쉽게 풀었다. 우선, timetable에 저장된 시간 문자열을 시간과 분에 따라 int형으로 값을 저장해주었다. (시간 * 60 + 분) 이후, 문제 예제를 보면 앞서 줄 서있는 사람이 있더라도 시간이 버스 출발 시간마다 꽉 채워 타는 것이 아닌 경우가 있..
-
프로그래머스 Lv.3) 야근 지수알고리즘/프로그래머스 2020. 5. 30. 17:26
야근 지수 코딩테스트 연습 - 야근 지수 회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도 programmers.co.kr 풀이 N : 야근을 해야하는 총 시간 ~> 1시간 마다 한 작업에 대해 -1을 해줄 수 있음 works[] : 각 작업마다 해야하는 총 일의 양 야근 피로도 = 각 work를 시작하는 시점 + (work의 남은 작업량)^2 이 문제는 위의 세 가지로 정리할 수 있다. 즉 각 작업마다 작업량이 많을 수록 야근 피로도가 쌓이기 때문에, 제곱이 되어 커지는 수를 최대한 줄여주어야하는 문제이다. 그렇다면 여기서 생각해야하는 것은, 최대한 고르게..