🌱1 Day, 1 Commit Wonseok's Record

https://www.acmicpc.net/problem/1874 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 연산을 수행해야 하는지를 알아내는 ..

https://www.acmicpc.net/problem/1817 1817번: 짐 챙기는 숌 첫째 줄에 책의 개수 N과 박스에 넣을 수 있는 최대 무게 M이 주어진다. N은 0보다 크거나 같고 50보다 작거나 같은 정수이고, M은 1,000보다 작거나 같은 자연수이다. N이 0보다 큰 경우 둘째 줄에 책 www.acmicpc.net 해설 : 쌓여있는 책을 박스에 차곡차곡 넣어서 택배로 미리 보내려고 한다. 책은 탑처럼 차곡차곡 쌓여있기 때문에, 차례대로 박스에 넣을 수밖에 없다. 각각의 책은 무게가 있다. 그리고 박스는 최대 넣을수 있는 무게가 있다. 이 때, 필요한 박스의 최소개수를 구하면 된다. 풀이 : 박스에 담을 수 있는 무게보다 작은동안 쌓여있는 책을 하나씩 넣는다 순서가 있으므로 정렬은 할 수..

https://www.acmicpc.net/problem/1783 1783번: 병든 나이트 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 해설 : 병든 나이트가 N × M 크기 체스판의 가장 왼쪽아래 칸에 위치해 있다. 병든 나이트는 건강한 보통 체스의 나이트와 다르게 4가지로만 움직일 수 있다. 2칸 위로, 1칸 오른쪽 1칸 위로, 2칸 오른쪽 1칸 아래로, 2칸 오른쪽 2칸 아래로, 1칸 오른쪽 병든 나이트는 여행을 시작하려고 하고, 여행을 하면서 방문한 칸의 수를 최대로 하려고 한다. 병든 나이트의 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다. 이동 횟수가 4..

https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 해설 : N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다. (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다. 이와 같이 종이..

https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 해설 : 듣도 못한 사람과 보도 못한 사람이 주어질 때 듣도 보도 못한 사람을 찾는 문제이다. 풀이 : 듣도 못한 사람과 보도 못한 사람의 교집합을 구하면 된다. 소스코드 : 1 2 3 4 5 6 7 8 9 10 11 12 13 if __name__ == "__main__": N,M = map(int,input().split()) D = [] B = [] for _ in range(N): D.a..

https://www.acmicpc.net/problem/1758 1758번: 알바생 강호 첫째 줄에 스타박스 앞에 서 있는 사람의 수 N이 주어진다. N은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 총 N개의 줄에 각 사람이 주려고 하는 팁이 주어진다. 팁은 100,000보다 작거나 같 www.acmicpc.net 해설 : 줄을 서 있는 손님들이 입장하는 순서대로 강호에게 팁을 준다. 원래 주려고 했던 팁이 10원이고 3번째로 들어갔다면 10 - (3 - 1) = 8원의 팁을 주게 된다. 손님들이 주려는 팁의 정보가 주어질 때 어떻게 줄을 세워야 가장 팁을 많이 받을 수 있는지 찾는 문제이다. 풀이 : 그리디하게 풀 수 있는 문제이다. 돈을 많이 주는 사람의 순으로 정렬하고 받을 수 있는 ..

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 해설 : 그래프에서 V와 E의 정보가 주어지고 시작점의 정보가 주어질 때, 시작점에서부터 다른 모든 V까지의 최단거리(가중치 합의 최솟값)을 구하는 문제이다. 쉽게 말하면 다익스트라 기본형 문제이다. 풀이 : 다익스트라 알고리즘을 구현할 수 있는지 없는지를 묻는 문제이다. 다익스트라는 알고리즘중 구현이 쉽지 않기 때문에 단순 구현이지만 골드5의 난이도를 부여받..

https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 해설 : 수열 N이 주어질 때 이 수열의 합을 구하려고 한다. 이 때, 두 수를 위치에 상관없이 묶어 이 두 수는 곱해서 더할 수 있다고 한다. 이 조건에서 수열 합의 최댓값을 구하는 문제이다. 풀이 : 쉬운 문제이다. 주어진 수열을 음수와 양수로 분리한 후 (0은 음수로, 1은 따로 카운팅) 음수는 작은 값에서부터 2개씩 묶고 양수는 큰 값에서부터 2개씩 묶는다. 소스코드 : 1 2 3 4 5..

https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 해설 : 준규의 가전제품 사용 순서와, 멀티탬의 구멍 개수가 주어질 때, 모든 가전제품을 사용하기 위해 플러그를 최소한으로 빼는 횟수를 구하는 문제이다. 풀이 : 그리디하게 해결하였다. 현재 플러그가 꽉 차있을 때부터 replacement가 발생하는데 이 때 남은 프로세스들 중 빈도가 가장 낮은 프로세스를 대체하면 된다. 이 문제에서 사용된 replacement 방법은 프로세스의 replaceme..