문제 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 설계 - 보통 이분탐색은 최소한의 횟수로 목표를 찾는 것이다. - 이번 문제는 공유기를 설치할 거리를 이분 탐색으로 결정하여 공유기 사이의 거리가 mid값 이상인 경우 공유기를 설치할 수 있다. - mid값 이상의 간격으로 공유기를 설치했을 때 공유기의 개수가 모자라다면 mid 값을 줄여주고, 설치해야하는 공유기의 개수가 너무 적다면 mid..
리엑트 components를 생성하고 Route를 사용하여 링크를 연결하려고 했는데 오류가 발생했다. import './App.css'; import Home from "./components/Home"; import Parking from "./components/Parking"; import Search from "./components/Search"; import {BrowserRouter, Switch, Route} from "react-router-dom"; function App() { return ( ); } export default App; 처음에는 구글링을 하여 Switch로 route를 구현했는데 react-router-dom에는 없는 기능이라는 오류가 발생했다. 다시 검색을 해보니 ..
문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 설계 - flood fill - 토마토가 모두 익는 최소 날짜를 구하여야 하기에 DFS도 생각해봤으나 N, M의 수가 너무 커서 불가능 - flood fill을 이용하여 아직 익지 않은 곳에 이전보다 1 큰 숫자를 누적하며 넣어주고 마지막에 max 값을 찾아 소요일을 확인한다. - 생각보다 코드가 길게 나왔다. 다음에는 더 줄이도록 해봐야겠다. from collections ..
문제 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 설계 - 이분탐색 - 처음에는 2중 while문을 이용하여 전선의 개수를 카운트, 시간초과 - cnt += line // mid 를 이용하여 while문 대신 한번에 cnt 계산 - start = 1로 해야 cnt += line // mid 에서 mid가 0이 되지 않는다. # 랜선 자르기 K, N = map(int, input().split()) arr = [i..
문제 https://www.acmicpc.net/problem/6236 6236번: 용돈 관리 현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 www.acmicpc.net 설계 - 이분탐색 - 처음 주머니에 금액을 충전하고 카운트 + 1 - 모자라면 남은 금액을 통장에 집어넣고 K원 인출하는 조건 - answer는 K 가 end에서만 최신화 N, M = map(int, input().split()) arr = [int(input()) for _ in range(N)] start, end = 1, sum(arr) # end : 한번의 충전으로 모두 사용할 수 있는 최..
문제 https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 설계 - 이분탐색 - 백준 문제 설명에 띄어쓰기가 헷갈리게 되어있어 문제를 이해하는데 오래 걸렸다. - SumV에 남아있는 것을 하나의 묶음으로 처리하는 것이 Point N, M = map(int, input().split()) arr = list(map(int, input().split())) # start : 블루레이 중 가장 큰값이 최소값이어야 모두 담을 수 있다. start, end = ma..
문제 https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 설계 - 이분탐색 - 백준 [2805. 나무자르기] 문제와 연결하니 좀 더 쉽게 접근할 수 있었다. N = int(input()) arr = list(map(int, input().split())) M = int(input()) start, end = 1, max(arr) switch = 1 while switch: mid = (start + end) // 2 sumV = 0 for i..
문제 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 설계 - 처음에는 내음대로 풀었으나 시간초과 - 투포인터 학습 후 접근 - start와 end 설정이 중요하다. N, M = map(int, input().split()) arr = list(map(int, input().split())) arr.sort() start = 1 end = max(arr) while start mid: # 높이보다 큰 나무..
문제 https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 설계 - 처음에는 2중 for문을 이용하여 확인했으나 시간초과로 실패 - sort를 활용하여 접두어를 i와 i+1만 검사하면 된다. T = int(input()) for tc in range(T): result = 'YES' n = int(input()) arr = [input() for _ in range(n)] arr.sort() for i in range(n-1)..
문제 https://www.acmicpc.net/problem/14606 14606번: 피자 (Small) 예제1의 입력이 1이므로, 게임 시작부터 갑이 분리할 수 있는 피자탑이 없습니다. 따라서 갑이 얻는 즐거움은 0입니다. 예제2의 정답 3은 다음과 같은 과정을 통해 얻어집니다. 먼저 놀이를 시작 www.acmicpc.net 설계 - 재귀, 피보나치 응용 n = int(input()) result = 0 def cal(level): global result if level == n: return result += level cal(level+1) cal(0) print(result)
