그리디
-
BOJ) 빵집 (3109 번)알고리즘/백준 2021. 2. 23. 01:18
빵집 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 가스관과 빵집을 연결하는 파이프를 설치하려고 한다. 빵집과 가스관 사이에는 건물이 있을 수도 있다. 건물이 있는 경우에는 파이프를 놓을 수 없다. 이 경로는 겹칠 수 없고, 서로 접할 수도 없다. 모든 파이프라인은 첫째 열에서 시작해야 하고, 마지막 열에서 끝나야 한다. 각 칸은 오른쪽, 오른쪽 위 대각선, 오른쪽 아래 대각선으로 연결할 수 있고, 각 칸의 중심끼리 연결하는 것이다. 이 문제에서 필요한 제약 조건들이다. 그리고 가장 중요한 힌트는 문제의 사진 첨부에 나온다..
-
BOJ) 멀티탭 스케줄링알고리즘/백준 2021. 2. 5. 00:02
멀티탭 스케줄링 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net N개의 구멍이 있는 멀티탭이 주어지고, 멀티탭 사용을 해야하는 전자제품의 순서가 K 개 주어진다. 전자제품은 1 ~ K 번의 고유 숫자를 가지고 있다. 코드는 O(k^2*n)의 시간 복잡도를 보이지만, N과 K의 최댓값이 100이기 때문에 크게 적당히 빠른 속도를 보여준다. 우선 멀티탭에 꽂혀있는 전자제품을 파악하기 위해 list를 선언해주었다. k개의 대기 열을 돌면서, 멀티탭에 구멍이 있는지 확인했다.남은 구멍이 없는 경우, 현재 멀티탭에 꽂..
-
프로그래머스 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..