기록

문제 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 파이썬으로 작성한 코드는 시간초과로 테스트를 통과하지 못했다. N의 범위가 작다보니 정답 값을 리스트에 저장해서 통과하는 방법이 가능하다. 그 이외의 다른 방법을 찾지 못해 자바로 코드를 작성하였다. queen의 위치가 다음과 같을 때 [2, 4, 1, 3]처럼 저장할 수 있다. 1 1 queen 1 queen 2 2 2 3 3 3 queen 4 queen 4 4 후보자 n(1~N)은 arr의 각각의 원소에 대해 조건을 만족해야 한다. 1) 같은 행에 위치하지 않는다..

문제 18119번: 단어 암기 준석이는 영어 단어를 외우려고 한다. 사전에는 N가지 단어가 적혀 있다. 모든 단어는 소문자이다. 단어 안에 있는 모든 알파벳을 알 때, 그 단어를 완전히 안다고 한다. 다음과 같은 쿼리들이 주 www.acmicpc.net 풀이 파이썬을 이용한 풀이는 같은 방식으로 코드를 작성해도 시간초과로 테스트를 통과하지 못했다. 시간을 줄일 수 있는 해결방법을 찾지 못해서 자바로 풀이를 진행하였다. table에는 알파벳의 포함 여부를 기록한다. 단어별로 a부터 z까지 문자의 포함 여부를 기록하여, 단어 하나당 0부터 2**26(67108864)까지의 수를 저장한다. 쿼리의 내용은 비트 연산자를 이용하여 bitmask에 저장한다. table을 순회 하면서 (원래값&bitmask)==원래..

문제 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 풀이 1. 미세먼지의 확산 : 함수 diffusion "확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다."라고 명시하고 있기 때문에, 확산되는 먼지의 양은 '변화가 있기 전의 먼지/5'로 계산하여야 한다. BOARD NEW_BOARD 10 9 10 9 0 0 0 0 [초기값] BOARD NEW_BOARD 10-10/5-10/5 = 6 9+10/5 = 11 10 9 0+10/5 = 2 0 0 0 [(0, 0) 미세먼지 10의 확산] BOARD NEW_BO..

문제 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m번 문자가 차례로 � www.acmicpc.net 풀이 1) 실패 함수 PI PI는 패턴에서 건너뛸 수 있는 문자의 개수를 의미하며 다음과 같이 구할 수 있다. ABAA의 PI = 1 접두사 접미사 접두사==접미사 1(문자의 개수) A A True 2(문자의 개수) AB AA False 3(문자의 개수) ABA BAA False A, AB, ABA, ABAA에 대해 위와 같은 방법으로 PI값을 구하면, [0, 0, 1, 1]이라는 배열을 얻을 수 있다. (인덱스 0은 0으로 연산) 위처럼 하나씩 ..

문제1016번: 제곱 ㄴㄴ 수첫째 줄에 min과 max가 주어진다. min은 1보다 크거나 같고, 1,000,000,000,000보다 작거나 같은 자연수이고, max는 min보다 크거나 같고, min+1,000,000보다 작거나 같은 자연수이다.www.acmicpc.net풀이에라토스테네스의 체를 이용한 문제로, 위 코드에서는 1) 소수 구하기와 2) a, b사이의 값이 제곱수로 나누어지는지 확인하는 두 가지 기능이 한 번에 작성되어 있다. ans에 탐색해야하는 자연수의 개수를 담고, '제곱수의 배수'를 만날 때마다 1씩 값을 줄여나간다.코드def solution(a, b) : ans = b-a+1 prime = [i for i in range(floor(b**0.5)+1)] # 소수를 저장할 공간 num..