안녕하세요. 모각코 6일차입니다. 오늘도 저번 주와 같이 그리디 알고리즘 문제를 풀었습니다. 난이도는 골드 문제로 풀었습니다. 골드 문제 골드 문제에서는 heapq를 쓰는 문제가 많았습니다. sort를 계속 진행하면 시간초과가 나기 때문에 우선순위 큐를 사용하여 문제를 해결해야했습니다. 11000 https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 강의실 배정의 경우 시작 시간을 기준으로 정렬한 뒤, 새로운 강의실을 배정해야하는지 배정하지 않아도 되는지를 종료 시간과 다음 시작 시간으로 비교하면..
안녕하세요. 모각코 5일차입니다. 오늘은 그리디 알고리즘을 복습하고 풀어보는 시간을 가졌습니다. 그리디 알고리즘이란 근사 알고리즘으로 현 상황에서 할 수 있는 최선의 선택에만 집중하는 일입니다. 그러므로 현 상황에서 최적의 해가 전체의 최적의 해라는 보장이 없습니다. 전체의 해의 보장이 되기 위한 조건은 현재 선택이 미래의 선택에 영향을 주지 않아야 합니다. 브론즈 문제 2720 https://www.acmicpc.net/problem/2720 2720번: 세탁소 사장 동혁 각 테스트케이스에 대해 필요한 쿼터의 개수, 다임의 개수, 니켈의 개수, 페니의 개수를 공백으로 구분하여 출력한다. www.acmicpc.net import sys n = int(sys.stdin.readline()) li = [in..
백준 7562번 나이트의 이동 문제입니다. https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 입력 예제입니다. 첫째 줄은 테스트 케이스의 개수 그 다음 줄은 하나의 테스트 케이스로 체스판의 크기, 현재 있는 칸, 목적지 이렇게 주어집니다. 3 8 0 0 7 0 100 0 0 30 50 10 1 1 1 1 출력 예제입니다. 5 28 0 나이트의 8번의 이동을 bfs로 구현해서 풀었습니다. 나이트는 (2, 1), (1, 2), (-2, 1), (-1,..
백준 1303 번 전투 문제입니다. https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net 아군은 W, 적군은 B이고 n명이 뭉쳐있을 때 n^2의 위력을 나타내니 bfs 탐색을 사용하면 되겠습니다. 입력의 첫째 줄은 전쟁터의 가로 길이, 세로 길이이며 전쟁터의 모습이 출력됩니다. 5 5 WBWWW WWWWW BBBBB BBBWW WWWWW 출력입니다 130 65 저는 입력 받는 것 때문에 인덱스 에러를 겪어서 다른 예제도 적어..
