B_log

문제 www.acmicpc.net/problem/11728 11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거�� www.acmicpc.net 문제 상황 - 정렬된 두 배열을 하나로 합쳐 정렬된 결과물을 출력한다. 해결 전략 1. 인덱스를 하나씩 탐색하며 더 작은 쪽을 결과물에 담으면 된다.(Merge)의 개념 2. Python의 내장 sort(O(NlogN))을 이용한다. 코드 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 ..

장고 템플릿에서 요소 슬라이싱하기 - Django의 models나 views에서 객체 자체를 슬라이싱하는 것이 아니라 이미 존재하는 객체를 슬라이싱해서 django template을 표현할 때에는 아래와 같은 표현으로 사용한다. {{ element|slice:"start:end+1" }} 주의할 점 - 파이썬과 다르게 template에서는 띄어쓰기가 문제가 될 수 있다. element | slice : "" 처럼 표현 할 경우 에러가 발생했다. - slicing 뿐만 아니라 element|문법 표현을 통해 다양한 기능을 사용할 수 있다. model 자체에서 slicing하기 - model에서 model 객체의 필드 값을 슬라이싱해서 새로운 필드로 정의해주는 것이 아니라 함수를 정의해 슬라이싱 값을 ret..

문제 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분탐색으로 경우가 무수히 많이 나뉠 수 있다. 이분탐색을 반복하는 구조는 공유기의 개수가 짝수 일 때 문제가 발생한다. 그래서 역으로 최대 거리를 ..

문제 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..

문제 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번의 방법이 유리하다. 길이의 경우 단순히 완전탐색하는 ..

문제 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()...

문제 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 ..

문제 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..