본문 바로가기

전체 글

(35)
[Python] BOJ 2630 - 색종이 만들기(분할 정복) https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 하얀색으로 칠해진 칸은 0, 파란색으로 칠해진 칸은 1로 주어지며, 각 숫자 사이에는 빈칸이 하나씩 있다. www.acmicpc.net * 분할 정복이란? - 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법 분할 정복에도 여러가지 종류가 있지만, 이 문제는 쿼드트리(quad-tree)를 통해 풀어 보았다. (https://www.acmicpc.net/problem/1992 ..
[Python] BOJ 10816 - 숫자 카드 2 (lower bound, upper bound) https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,00 www.acmicpc.net 주어진 배열에 대해 입력받은 숫자의 갯수를 세야 하는 문제이다. 단순한 이분 탐색으로는 그 숫자의 위치는 찾을 수 있을지 몰라도..
[Python] BOJ 2108 - 통계학 https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 어렵진 않지만 소문제 4개로 나누어져 있고 정리할게 많아서 정리해본다. import sys, collections input = sys.stdin.readline numList = [] T = int(input()) for _ in range(T): n = int(input()) numList.append(n) numList.sort() print(round(sum(numList)/T)) print(numList[int(T/2)])..
[Python] BOJ 1316 - 그룹 단어 체커 https://www.acmicpc.net/problem/1316 1316번: 그룹 단어 체커 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때문에 그룹 단어이지만, aabbbccb는 b가 떨어져서 나타나기 때문에 그룹 단어가 아니다. 단어 N개를 입력으로 받아 그룹 단어의 개수를 출력하는 프로그램을 작성하시오. www.acmicpc.net 딱히 어려운 문제는 아니지만, 잡기술(?)하나를 설명하기 위해 정리를 해본다. import sys input = sys.stdin.readline n = int(input()) cnt = 0 def..
[Python] BOJ 1654 - 랜선 자르기(Binary Search) https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 231-1보다 작거나 같은 자연수이다. www.acmicpc.net 이분 탐색문제이다(함정이 있는) import sys input = sys.stdin.readline N,M = map(int,input().split()) L = [] for _ in range(N): L.append(int(inp..
[Python] BOJ 2609 - 최대공약수와 최소공배수(유클리드 호제법) https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를,둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net * 유클리드 호제법이란? - 즉, a,b의 최대공약수는 b,r의 최대공약수와 같다는 것이다. n,m = map(int,input().split()) def Eucliden(a, b): while(b != 0): r = a % b a = b b = r return a print(Eucliden(n,m)) print(n*m // (Eucliden(n,m))) - 따라서 b가 0이 아닌 동안 b를 a에 넣고 a를 b로 나눈 나머지를 b에 넣는 과정을 반복했다. - 9번째..
[Python] collections.deque 맨날 무엇이든지 대충대충 하는 습관이 들어서 그걸 고치기 위해 영어문서를 해석해보고 정리해본다. 문제풀이 할 때 가끔씩(?) 쓰는 collections 모듈이다. Source code는 https://github.com/python/cpython/blob/3.8/Lib/collections/__init__.py python/cpython The Python programming language. Contribute to python/cpython development by creating an account on GitHub. github.com 에서 확인할 수 있다. 여러 Object들이 존재하지만, 아직 사용해본 2개만 정리해보겠다. (나머지는 나중에 쓰는 날이 오면 그때 마다 정리하는 걸로..) *..
Python 시간복잡도, 코드시간측정 파이썬으로 여러문제를 풀다보면 시간초과가 나는 일이 많이 발생한다. (파이썬은 편리함과 효율성을 맞바꾼 언어라고 누가 그러더라..) 그래서 백준에서는 파이썬으로 채점할 때 (제한시간*3+2)초 이런식으로 시간을 늘려주기는 한다. 그렇지만 항상 코드를 짜면서 내장함수를 사용할때마다 이 함수는 O(n)인가? O(1)인가? 이런 고민들을 하게 된다. TimeComplexity - Python Wiki This page documents the time-complexity (aka "Big O" or "Big Oh") of various operations in current CPython. Other Python implementations (or older or still-under development v..