백준 알고리즘 - 병든 나이트 (1783) [Python]

문제 www.acmicpc.net/problem/1783 1783번: 병든 나이트 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 상황 - 나이트가 이동하며 최대한 많은 지점을 방문할 방법을 고려한다. dfs를 통해 개수를 카운트할 수 있지만 문제의 분류가 탐욕법이고 가로와 세로의 범위가 2,000,000,000 이하이므로 다른 방법을 생각해보아야한다. 해결 전략 - 문제의 상황을 일일이 가정하고 범위를 정의해 상황에 맞춰 시뮬레이션한다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 from sys import stdin..
알고리즘 학습/백준 알고리즘 2020. 10. 20. 11:41
백준 알고리즘 - 암호코드 (2011) [Python]

문제 www.acmicpc.net/problem/2011 2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net 문제 상황 - 숫자가 주어지고 대응되는 암호코드를 만들 때, 가능한 암호 코드의 수를 출력한다. 숫자가 커질 경우를 대비해 1,000,000으로 나눈 수를 출력한다. 암호로 변경이 불가능한 경우 0을 출력한다. 해결 전략 - 우선 암호로 변경 불가능한 경우는 크게 두가지이다. 숫자가 아닌 값이 입력되거나, 0이 들어가는데 10, 20처럼 처리 가능한 숫자가 아닌 00, 40 처럼 알파벳에 대응될 수 없는 경우가 존재하는 상..
알고리즘 학습/백준 알고리즘 2020. 10. 19. 18:04
백준 알고리즘 - 쿼드트리 (1992) [Python]

문제 www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1≤N ≤64의 범위를 가진다. 두 번째 줄부터는 길이 N 의 문자열이 N 개 들어온다. 각 문자열은 0 또는 www.acmicpc.net 문제 상황 - 0과 1로 이루어진 2차원 배열을 압축하며 압축이 불가능할 경우 4분할하여 작업을 반복한다. 해결 전략 - 재귀를 이용하여 주어진 조건을 분할정복한다. 요소가 전부 한가지로 되어있으면 괄호가 없이 해당 숫자를 출력하고 0과 1이 모두 존재하면 다시 4분할하며 작업을 반복한다. 이 때, 괄호를 넣어주어야 한다. 1. 모든 요소를 검사하며 0행 0열의 값을 기준으로 다른 값이 하나라..
알고리즘 학습/백준 알고리즘 2020. 10. 19. 11:01
백준 알고리즘 - 종이의 개수 (1780) [Python]

문제 www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. www.acmicpc.net 문제 상황 - 종이를 확인하여 종이가 하나의 숫자로만 되어있으면 그 종이는 더이상 자르지 않고, 다르다면 9분할해서 카운팅을 반복한다. 해결 전략 - BOJ의 Z 문제와 유사한 풀이로, 함수를 설정해 재귀하도록 한다. 주어진 조건을 만족하면 글로벌을 통해 카운트를 증가시켜주고, 아니면 스플릿을 반복한다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ..
알고리즘 학습/백준 알고리즘 2020. 10. 16. 11:39
백준 알고리즘 - 배열 합치기 (11728) [Python]

문제 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 ..
알고리즘 학습/백준 알고리즘 2020. 10. 16. 10:50
{{ Django }} - Slicing in django templates

장고 템플릿에서 요소 슬라이싱하기 - Django의 models나 views에서 객체 자체를 슬라이싱하는 것이 아니라 이미 존재하는 객체를 슬라이싱해서 django template을 표현할 때에는 아래와 같은 표현으로 사용한다. {{ element|slice:"start:end+1" }} 주의할 점 - 파이썬과 다르게 template에서는 띄어쓰기가 문제가 될 수 있다. element | slice : "" 처럼 표현 할 경우 에러가 발생했다. - slicing 뿐만 아니라 element|문법 표현을 통해 다양한 기능을 사용할 수 있다. model 자체에서 slicing하기 - model에서 model 객체의 필드 값을 슬라이싱해서 새로운 필드로 정의해주는 것이 아니라 함수를 정의해 슬라이싱 값을 ret..
Web/Python | Django 2020. 10. 15. 12:39
백준 알고리즘 - 공유기 설치 (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
1 ··· 21 22 23 24 25 26 27 ··· 39