python

문제https://www.acmicpc.net/problem/2630백준 단계별 풀이 - 분할 정복풀이전체 코드# 분할 정복# 메모리: 31120KB / 시간: 52ms# 1from sys import stdininput = stdin.readlineN = int(input())paper = [list(map(int, input().split())) for _ in range(N)]ret = [0, 0]# 2def quadtree(row: int, col: int, size: int) -> None: color: int = paper[row][col] for i in range(row, row+size): for j in range(col, col+size): ..

공통점복잡한 문제를 더 작은 부분 문제로 나누어 해결하는 방식대게 최적화 문제나 조합 문제를 해결하는데에 사용한다.차이점재귀특징함수가 자기 자신을 호출하여 문제를 해결종료조건(base case)이 필수적예시: 팩토리얼 계산, 하노이 탑, 피보나치 수열# 피보나치 수열def factorial(n): if n == 0 or n == 1: return 1 return n * factorial(n-1)# 하노이 탑def hanoi_tower(n, start, end, middle): if n == 1: print(f"원반 1을 {start}에서 {end}으로 옮깁니다.") return hanoi_tower(n-1, start, middle, en..

문제https://www.acmicpc.net/problem/9663백준 단계별 풀이 - 백트래킹풀이기준이 바뀐것인지 일반적인 코드로는 통과되지 않았다.결국 비트마스킹을 이용한 풀이로 성공...# 1def dfs(row, ld, rd, n): if row == all_bits: return 1 count = 0 poss = all_bits & ~(row | ld | rd) while poss: bit = poss & -poss poss -= bit count += dfs(row | bit, (ld | bit) > 1, n) return count# 2N = int(open(0).readline())all_bits = (1 row..

문제https://www.acmicpc.net/problem/11050백준 단계별로 풀어보기 - 조합론풀이자연수 N과 K가 주어졌을때, 이항계수 (n/k)를 구하는 문제. 이항계수 (n/k)는 nCk 와 같다.nCk = n!/(k!(n-k)!) 단순 반복문 사용# 메모리: 31120KB / 시간: 36ms# 1N, K = map(int, input().split())ret = 1# 2for i in range(K): ret *= (N - i)# 3for i in range(1, K+1): ret //= iprint(ret)n! = (n * (n-1) * ... * (n-k+1)) * (n-k)!이걸 다시 공식에 적용해서,nCk = (n * (n-1) * ... * (n-k+1)) * (n-k)..

문제백준 단계별 풀이 - 스택, 큐, 덱https://www.acmicpc.net/step/11(모든 문제는 파이썬으로 풀이)[18258]큐 2문제링크: https://www.acmicpc.net/problem/18258 큐 구현 후 주어진 명령대로 처리하는 문제다. 단계별 풀이먼저 나는 deque모듈을 사용했다.deque는 O(1)의 속도, list는 O(n)의 속도를 지원한다.그리고 Queue모듈은 멀티쓰레드 환경을 지원하기 때문에 deque보다 느리다.=> 결론: 알고리즘 문제 풀 때는 deque!from sys import stdinfrom collections import dequeinput = stdin.readlineN = int(input())dq = deque()input 함수 제정의.명..

문제백준 단계별 풀이 - 스택, 큐, 덱https://www.acmicpc.net/step/11[28278]스택 2문제링크: https://www.acmicpc.net/problem/28278 조건을 순서대로 수행하기만 하면 되는 문제다.물 흐르듯이 따라가면 되는 문제...지만 잘못 이해한 부분이 있었다.조건 2번을 보면, "맨 위의 정수를 빼고 출력한다."로 되어있다.빼고(except)로 이해했건만 알고보니 빼고(pop)였다.단계별 풀이from sys import stdininput = stdin.readlineN = int(input())stack = []우선 input을 stdin.readline함수로 선언해준다.명령의 수 N의 값을 받아 정수형으로 변환.스택으로 사용할 리스트 stack 생성.fo..