1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 자연수 N이 주어졌을 때, N보다 작은 연속하는 소수들의 합이 N과 같을 경우의 수를 구하는 문제이다. N의 최댓값이 4,000,000이므로, 소수 판별에 있어서는 에라토스테네스의 체를, 연속합은 투 포인터 알고리즘을 통해 시간복잡도 O(n)으로 구현하였다. N = int(input()) # 예외 처리 if N == 1: print(0) exit(0) # 소수 판별 by 에라토스테네스의 체 sosu = [True for _ in range(N + 1)] number = list() for i in range(2, N + 1): if sosu[i]: for j in range(i, ..

9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 퇴각 검색 알고리즘을 다룰 때 대표적으로 등장하는 문제다. 2차원 배열이 아닌 인덱스를 행, 요소를 열로 사용하는 1차원 배열을 활용하고, PyPy3로 제출해야만 시간초과 없이 AC를 받을 수 있다. n = int(input()) # 체스판, 0은 아직 놓이지 않음을 의미 map = [0] * n ans = 0 # 퀸을 놓을 수 있는지 판단하는 함수 def is_satisfy(x): for i in range(x): # 같은 열에 놓였는지, 대각선에 놓였는지(-> 절댓값으로 판..

10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 좀 더 클린한 코드로 리팩토링이 필요해보이나, List와 DFS 개념을 활용하여 해결하였다. 방문 배열을 만들어주고, 정상인의 경우와 적녹색약인 경우 각각의 함수를 정의하지 않고, 정상인일 경우를 해결한 후에 적색을 녹색으로 변경하여 다시 한번 깊이 우선 탐색을 돌려주었다. import sys sys.setrecursionlimit(10 ** 9) n = int(input()) arr = list() for _ in range(n): arr.append(l..

1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 추가하는 건 맨 뒤에서, 빼는 건 양쪽 방향에서 해줄 수 있는 큐가 필요하다. 덱(double ended queue)을 구현해주면 되는데, 해당 문제에서는 양방향으로 추가해줄 필요가 없어서 기존에 구현했던 큐를 일부 수정, 변형하였다. 회전하는 큐 구현 struct Queue { var left = [Int]() var right = [Int]() var count: Int { left.count + right.count } var isEmpty: Bool ..

1. 기본 PS를 할 때 기본적으로 사용되는 입출력이다. # 입력 # str, 문자열이 그대로 출력 a = input() # int, 문자열을 정수형으로 변경 a = int(input()) # list, 문자열을 문자(char) 리스트로 변경 a = list(input()) # list, 문자열을 공백으로 구분하여 문자열(str) 리스트로 변경 a = input().split() # list, 문자열을 공백을 구분하여 정수형 리스트로 변경 a = list(map(int, input().split)) # 복수 할당(공백을 구분하여 각각의 정수를 할당) a, b, c = map(int, input().split()) # 출력 # 기본 출력 print(a) # 배열을 "주어진 문자열"로 구분하여 합친 문자열로..