Han's Tech LAB

https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 📕 설명 📕 구간을 Indexing한 뒤, sum 함수를 이용해 풀이하였다. 그냥 indexing으로 sum을 하면 시간초과가 발생하므로, prefix_sum 알고리즘을 사용해야한다. 새로운 배열에 값을 쌓는 형식으로 계속 더해서 넣은 후 indexing으로 값을 계산한다. pypy로 실행하여 시간초과를 피하였다. 🧑🏻‍💻 나의 풀이 🧑🏻‍💻 N, M = map(int, i..

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 📕 설명 📕 2차원 배열을 1차원 배열의 인덱스로 표현하였다. (x, y) => row[x] = y와 같이 말이다. 1. row 배열 내에 같은 값의 유무 확인. 2. 대각선의 값들을 고려하여 대각선의 위치한 Queen의 자리를 확인한다. 🧑🏻‍💻 나의 풀이 🧑🏻‍💻 N = int(input()) result = 0 r = [0] * N def is_OK(num): for i in range(num): if r[..

https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 📕 설명 📕 backtracking 문제로, DFS에서 조건을 걸어 문제의 요구 사항에 맞게 출력한다. 중복 되는 수열을 여러 번 출력하지 않는다. 🧑🏻‍💻 나의 풀이 🧑🏻‍💻 N, M = map(int ,input().split()) result = [] visited = [False]*(N+1) def DFS(): if len(result) == M: print(' '.join(map(str..

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 📕 설명 📕 토마토 문제로, bfs로 matrix를 순회하는 문제이다. bfs로 토마토 농장을 순회하여 대각선이 아닌 상하좌우 좌표를 활용해서 1 주변의 것들을 1로 만든다. -1인 것은 비어있는 것, 0은 토마토가 익지 않은 것, 1은 토마토가 익은 것이다. 🧑🏻‍💻 나의 풀이 🧑🏻‍💻 from collections import deque M, N = map(int, input(..

https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 📕 설명 📕 N과 M (1)의 변형으로 풀이하였다. DFS에서 자신을 제외하는 것을 하지 않으면 풀린다. 🧑🏻‍💻 나의 풀이 🧑🏻‍💻 N, M = map(int ,input().split()) result = [] visited = [False]*(N+1) def DFS(): if len(result) == M: print(' '.join(map(str, result))) return for i..

https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 📕 설명 📕 itertools의 combinations를 사용하여 조합을 만들었다. 1. tmp라는 list에 값을 1 ~ N 만큼 반복하여 넣는다. 2. tmp list를 combinations에 넣어 M개 만큼의 부분 조합을 만든다. 3. *로 감싸서 출력한다. 🧑🏻‍💻 나의 풀이 🧑🏻‍💻 from itertools import combinations N, M = map(int ,input(..

https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 📕 설명 📕 본 풀이는 DFS를 활용하여 재귀함수를 통해 구현하였다. 하나씩 넣고 True, False를 활용한다. 🧑🏻‍💻 나의 풀이 🧑🏻‍💻 N, M = map(int ,input().split()) result = [] visited = [False]*(N+1) def DFS(): if len(result) == M: print(' '.join(map(str, result))) return..

https://www.acmicpc.net/problem/2004 2004번: 조합 0의 개수 첫째 줄에 정수 $n$, $m$ ($0 \le m \le n \le 2,000,000,000$, $n \ne 0$)이 들어온다. www.acmicpc.net 📕 설명 📕 직접 구하면 시간초과가 발생한다. 2와 5의 개수를 구하여 더 작은 쪽의 개수가 10의 개수이다. 🧑🏻‍💻 나의 풀이 🧑🏻‍💻 N, M = map(int, input().split()) def cnt(N, divide): count = 0 while N: N //= divide count += N return count N_5_cnt = cnt(N,5) M_5_cnt = cnt(M,5) NM_5_cnt = cnt(N-M,5) N_2_cnt = ..

https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 📕 설명 📕 factorial과 reversed를 이용한 풀이이다. 🧑🏻‍💻 나의 풀이 🧑🏻‍💻 N = int(input()) def factorial(N): if N == 1: return 1 if N == 0: return 1 return N * factorial(N - 1) cnt = 0 for i in reversed(str(factorial(N))): if i != '0': break cnt += 1 print(cnt)

https://www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 📕 설명 📕 경우의 수를 활용하여, (종류의 수 + 1) * (종류의 수 + 1) * ... - 1 로 계산한다. 한 가지 빼는 경우는 알몸인 경우이다. 🧑🏻‍💻 나의 풀이 🧑🏻‍💻 from collections import Counter T = int(input()) for _ in range(T): N..