시간 제한 메모리 제한 1 초 256 MB 문제 (링크) https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 나의 풀이 from collections import deque # 나이트의 8가지 이동 dx = [1, 1, -1, -1, 2, 2, -2, -2] dy = [2, -2, 2, -2, 1, -1, 1, -1] def bfs(start_x, start_y, target_x, target_y): q = deque() q.append((start..
알고리즘
시간 제한 메모리 제한 1 초 128 MB 문제 (링크) https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 나의 풀이 import sys from collections import deque n = int(sys.stdin.readline()) graph = [] # 각 집으로의 이동을 표현할 좌표리스트 dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] for _ in range(n): graph.append(list(map(in..
시간 제한 메모리 제한 0.3 초 512 MB 문제 https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 나의 풀이 string_list = list(input()) cursor = len(string_list) for _ in range(int(input())): command = list(input().split()) if command[0] == 'P': string_list.insert(cursor, command[1]) cursor += 1 ..
문제 (링크) https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 나의 풀이 import sys n = int(sys.stdin.readline()) stack = [] ans = [] count = 1 possible = True for _ in range(n): input_num = int(sys.stdin.readline()) while input_num >= ..
문제 설명선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다. 예를 들어 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더일때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다. 위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더와 같은 스킬트리는 불가능합니다. 선행 스킬 순서 skill과 유저들이 만든 스킬트리1를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 return 하는 solution 함수를 작성해주세요. 제한 조건 스..
시간 제한 메모리 제한 2 초 128 MB 문제 (링크) https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 나의 풀이 import sys import math n = int(sys.stdin.readline()) # n이하의 수 중 소수를 찾아줄 배열 (에라토스테네스의 체) prime_checker = [True for _ in range(n+1)] # 소수가 아닌 0과 1에 대해 별도의 False처리 prime_checker[0:2] = False for i in range(2, int(math.sqrt(n)) + 1): if prime_checker[i]: j ..
시간 제한 메모리 제한 0.5 초 128 MB 문제 (링크) https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 나의 풀이 import sys n, m = map(int, sys.stdin.readline().split()) arr = list(map(int, sys.stdin.readline().split())) end = 0 intervalSum = arr[0] ans = float('inf') for start in range(..
문제 (링크) https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 나의 풀이 import sys n, m = map(int, sys.stdin.readline().split()) arr = list(map(int, sys.stdin.readline().split())) intervalSum = arr[0] # m과 비교할 start ~ end까지 더한 값들 cnt = 0 # start ~ end == m 일..
