백준 알고리즘 - 공유기 설치 (2110) [Python]

문제 www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (1 ≤ xi ≤ 1,000,000,000)가 � www.acmicpc.net 문제 상황 - 수직선 위에 존재하는 집들에 공유기를 설치할 때, 최대한 먼 거리에 공유기를 설치하여 그 거리중 가장 가까운 거리를 출력한다. 해결 전략 - 집을 기준으로 잡아서 설치를 시작하면 2분탐색, 3분탐색으로 경우가 무수히 많이 나뉠 수 있다. 이분탐색을 반복하는 구조는 공유기의 개수가 짝수 일 때 문제가 발생한다. 그래서 역으로 최대 거리를 ..
알고리즘 학습/백준 알고리즘 2020. 10. 15. 11:23
백준 알고리즘 - 나무 자르기 (번호) [Python]

문제 www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M을 www.acmicpc.net 문제 상황 - 주어진 나무 리스트를 기준 길이로 자를 때, 주어진 길이 M 이상 만큼의 길이를 얻을 수 있는 경우 가능한 최대 높이를 구한다. 해결 전략 - 이분탐색을 이용하여 기준 길이를 움직이며 구한다. 기준 길이를 구할 때 linear하게 검색할 경우 너무 많은 탐색이 있으므로 logN의 이분 탐색이 필요하다. 코드 1 2 3 4 5 6 7 8 9 10 11 1..
알고리즘 학습/백준 알고리즘 2020. 10. 15. 10:36
백준 알고리즘 - 랜선 자르기 (1654) [Python]

문제 www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제 상황 - 입력받은 개수 N만큼 자른 랜선을 만들어야 할 때, 최대의 길이로 랜선을 자를 때 그 최대 길이를 계산한다. 해결 전략 - 방법은 두가지로 나눌 수 있다. 1) 길이를 정해 개수를 계산 2) 개수를 정해 길이를 계산 2번의 경우 개수가 정확히 N개일 때면 가능하지만 N보다 크거나 같다는 상황이므로 2번보단 1번의 방법이 유리하다. 길이의 경우 단순히 완전탐색하는 ..
알고리즘 학습/백준 알고리즘 2020. 10. 13. 16:06
백준 알고리즘 - 미로 탐색 (2178) [Python]

문제 www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제 상황 - 시작점에서 끝점까지의 길이 항상 존재할 때 가장 최단으로 갈 수 있는 거리의 길이를 찾는다. 해결 전략 - 최단거리이므로 BFS를 활용하여 deque를 이용한다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 from sys import stdin from collections import deque input = stdin.readline N, M = map(int, input()...
알고리즘 학습/백준 알고리즘 2020. 10. 8. 10:10
백준 알고리즘 - 토마토 (7576) [Python]

문제 www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토� www.acmicpc.net 문제 상황 - 토마토가 다 익는데 걸리는 최소 시간을 출력하고, 불가능하다면 -1을 출력한다. 해결 전략 - 우선 0의 개수를 계산하여 전부 익었는지 확인하는데 사용한다. 그리고 같은 시간에 익는 토마토의 위치들을 새로운 큐에 넣어 작업을 반복한다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 ..
알고리즘 학습/백준 알고리즘 2020. 10. 8. 09:32
백준 알고리즘 - 섬의 개수 (4963) [Python]

문제 www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도� www.acmicpc.net 문제 상황 - 이동할 수 있는 블록의 집합을 하나의 섬으로 보고, 섬의 총 개수를 구한다. 해결 전략 - 간단한 dfs 문제이다. 순회하며 visited를 갱신하며 개수를 찾는다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 from sys import stdin,setrecursionlimit setrecur..
알고리즘 학습/백준 알고리즘 2020. 10. 7. 13:50
백준 알고리즘 - 텀 프로젝트 (9466) [Python]

문제 www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 문제 상황 - 주어진 리스트의 부분 사이클을 구해 팀을 구성하고, 팀이 없는 학생 수를 구한다. 해결 전략 - 재귀보다는 반복을 통해 구한다. 내 방법으로는 조건을 통해 사이클이 되는지 안되는지를 확인하는 알고리즘을 사용하여 만약 부분적으로 사이클을 이룬다면 그 부분만 사이클이 된다고 표시하고 넘어가는 방식을 택한 후 사이클에 포함 안되는 요소의 개수를 찾았다. 하지만 이 방식으로는 속도 이슈가 발생하였다. -..
알고리즘 학습/백준 알고리즘 2020. 10. 7. 12:07
백준 알고리즘 - 반복수열 (2331) [Python]

문제 www.acmicpc.net/problem/2331 2331번: 반복수열 첫째 줄에 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 출력한다. www.acmicpc.net 문제 상황 - 반복적인 연산을 통해 수열을 만들고 겹치는 부분이 발생했을 때 겹치지 않는 부분의 길이를 구하는 문제 해결 전략 - 연산을 반복하면서 조건을 설정해 해당 조건이 아니면 수열에 추가하고, 맞으면 반복을 탈출하며 그 반복 요소의 위치를 찾는다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 from sys import stdin input = stdin.readline A, P = input().split() D = [A] while True: A = D[-1] total = 0 for ..
알고리즘 학습/백준 알고리즘 2020. 10. 7. 09:48
1 ··· 7 8 9 10 11 12 13 ··· 22