문제https://www.acmicpc.net/problem/10469문제 설명8x8 체스판 위에 여덟개의 퀸을 배치하여 서로 공격할 수 없게 만들어야 한다.여왕은 네 대각선과 상,하,좌,우 네 방향, 총 여덟 방향으로 이동이 가능하다.8x8의 체스판이 주어지며, 올바른 배치인지 판단해야 한다. 풀이단순한 8 Queen 문제이다. 하지만 문제를 제대로 읽지 않으면 발생하는 문제가 있다.사이나쁜 여왕 퀴즈는 "여덟" 여왕을 8x8 체스판 위에 배치하는 문제이다. 따라서 보드판에 8개의 여왕이 존재하지 않으면 해당 배치는 올바르지 않은 해법이다.여왕은 8 방향으로 이동할 수 있기에 8 방향을 모두 탐색해서 해당  방향에 퀸이 존재하는지 판별해야하는 문제이다.나는 퀸을 찾기 위해 인덱스 순으로 완전 탐색을 했..

문제https://www.acmicpc.net/problem/29155문제 설명구름 LEVEL에는 난이도1 ~ 난이도5까지 문제들을 제공한다.난이도를 같거나 증가하는 순으로 문제를 풀어야 한다.각 문제와 문제 사이에는 휴식 시간이 필요하다.두 문제가 같은 난이도 일 경우 : 두 문제를 푸는 데 걸리는 시간의 차이만큼 필요난이도를 증가시키는 경우 : 60분의 시간이 필요계획한 문제를 푸는데 걸리는 최소시간을 구해라 풀이입력받은 문제들을 정렬한다.각각의 난이도 별로 문제를 다 풀 때까지 while문을 통해 반복한다.현재 푸는 문제가 첫 문제일 경우 휴식시간을 설정할 필요가 없으므로 Flag를 통해 첫 문제인지 확인한다.이전 문제와 현재 문제를 차를 계산하여 문제 푸는데 걸리는 시간 + 휴식시간을 더한다.문제..

문제https://www.acmicpc.net/problem/24523문제 설명  수열 A가 주어진다.$1\le i \le N$인 정수 $i$마다 $i 이고 $A_i \ne A_j$인 정수 $j$중 최솟값을 출력하라. 만약 이러한 j$j$가 없다면 −1$-1$을 출력하라.풀이수열을 순회하면서 현재 인덱스와 이전 인덱스가 다른 위치를 찾아 배열에 저장한다.값이 전환되는 포인트를 기점으로 반복문을 통해 해당 위치의 인덱스를 사이의 범위만큼 출력한다.마지막 포인트일 경우 -1을 출력한다.코드import sysinput = sys.stdin.readlineN = int(input())arr = list(map(int,input().split()))prev = arr[0]lst = []for i in range(..

문제https://www.acmicpc.net/problem/15966문제 설명군계일학 수열은 각 항이 연속적인 수열을 의미한다.군계일학 수열은 어떤 임의의 $i$에대해서 $a_i = a_1 +(i-1)$을 만족해야한다.  길이가 N이고 정수로 이루어진 수열이 주어진다.뽑은 항의 순서를 유지하며 만들 수 있는 가장 긴 군계일학 수열의 크기를 출력한다.풀이길이가 $N$인 수열이 주어지는데 $N$의 범위는 $1$  $\leq$ $N$  $\leq$ $10^5$이다.군계일학 수열의 정의 조건인 $a_i = a_1 +(i-1)$를 만족시키는 항을 모두 찾기 위해서는 약 $N^2$만큼의 연산이 필요하지만 문제의 시간 제한인 2초의 시간 복잡도는 약$O(2 *10^8)$이므로 $O(N^2)$은 $O(10^{10})..

문제https://www.acmicpc.net/problem/24460문제 설명$N*N$크기만큼 의자가 존재하며, 각 의자에는 번호가 적혀있다.전체 크기를 정사각형 4개로 나누어 각 구역에서 한명씩 뽑는다. 해당 과정을 재귀적으로 반복한다.각 구역에서 뽑힌 네 명 중 추첨 번호가 두 번째로 작은 사람이 뽑힌다.경품을 받기 위해 앉아야 하는 의자 번호를 출력한다.풀이단순 분할정복을 통한 재귀 문제이다. 구역을 네 등분으로 나누어 재귀한다.구역의 크기가 1이되면 해당 위치의 추첨 번호를 반환한다.각 구역의 추첨 번호를 받아 두번째로 작은 추첨번호를 반환한다.코드import sysinput = sys.stdin.readlineN = int(input())arr = [list(map(int,input().spl..

문제https://www.acmicpc.net/problem/21317문제 설명N개의 돌이 일렬로 나열되어있는 강가가 있다.세 종류의 점프를 해서 앞의 돌로 이동할 수 있다.작은 점프 : 다음 돌로 이동한다. (정해진 만큼의 에너지 소비)큰 점프 : 1개의 돌을 건너뛰어 이동한다. (정해진 만큼의 에너지 소비)매우 큰 점프 : 2개의 돌을 건너뛰어 이동한다. (K 만큼의 에너지 소비 N 번째 돌에 도달하기 위한 에너지의 최솟값을 구한다.풀이탐색을 통해서 N번째 돌에 도착했을 때 에너지의 최솟값을 구해야한다.각 돌에서 다음 돌로 이동하기 위한 에너지의 양 즉 가중치의 크기가 각각 다르므로 BFS로는 탐색이 불가능하다고 판단했다. 또한 앞으로만 이동하기 때문에 사이클이 존재하지 않는다. 따라서 DAG(Dir..

문제https://www.acmicpc.net/problem/1005문제 설명ACM 크래프트에서는 매 게임마다 건물을 짓는 순서가 주어진다.모든 건물은 각각 건설을 시작하여 완성될 때까지 Delay가 존재한다.W번 건물을 짓게되면 게임에서 승리한다.W번 건물을 건설완료하는 데 걸리는 최소 시간을 구해야한다.  건설 조건2번, 3번 건물은 1번 건물이 건설되기 전까지 지을 수 없다.1번 건물이 건설완료되면 2번, 3번 건물은 동시에 건설할 수 있다.4번 건물을 짓기 위해서는 2번, 3번 건물이 전부 건설이 완료되어야 한다.1번 건물을 건설하는 데 10초가 소요된다. 2번, 3번 건물을 동시에 건설하므로 4번 건물을 건설하기 위해 걸리는 시간은 총 100초이다.마지막 4번 건물을 건설하는데 필요한 건물은 1..

문제https://www.acmicpc.net/problem/2785문제 설명N개의 체인이 존재한다.각각의 체인은 여러 개의 고리로 이루어져 있다.길이가 3인 체인 -> 고리가 3개인 체인체인을 분리하거나 연결하여 두 개의 체인을 하나의 긴 체인으로 변경할 수 있다.모든 체인을 하나의 체인으로 묶기 위해 필요한 최소한의 고리를 찾아라.  1. 길이가 1인 체인(고리가 1개로 이루어진)이 3개가 존재한다. 2. 가운데 체인을 연다. 3. 양 끝 체인을 연결한다. 4. 가운데 체인을 닫는다.풀이하나의 체인을 전부 다 사용해서 체인들을 연결한다면 최종적으로 사용하는 고리의 수가 줄어들게 된다. 따라서 고리의 개수가 낮은 것부터 길이가 긴 체인끼리 묶는다면 최소한의 고리를 사용하여 모든 체인을 하나로 묶을 수 ..

문제https://www.acmicpc.net/problem/14627문제 설명길이가 일정하지 않은 파가 S개 존재한다.파닭을 만드는데 들어가는 파의 양은 일정하다.최대한 많은 양의 파를 넣어야 한다.모든 파닭을 만들고 남은 파를 구한다.풀이파의 길이 L은 $(1 ≤ L ≤ 10^9)$이다. 따라서 완전 탐색으로 전체를 탐색하기에는 시간이 부족하다. 따라서 이분 탐색을 통해 하나당 넣을 수 있는 최대 파의 길이를 탐색했다. start, end의 값을 초기화한다.각각의 파를 mid값으로 나눈다. -> mid 길이의 파로 현재 가지고 있는 파로 몇개의 파닭을 만들 수 있는지 구한다.mid의 길이로 주문받은 파닭을 충분히 만들 수 있으면 start = mid, 그럴 수 없다면 end = mid로 변경한다.이분..

문제https://www.acmicpc.net/problem/17129문제 설명0이면 빈 복도여서 지나갈 수 있고, 1이면 장애물로 막혀 지나갈 수 없다.윌리암슨수액빨이딱따구리 식구는 2, 청국장은 3, 스시는 4, 맥앤치즈는 5이다.윌리암슨수액빨이딱따구리는 단위 시간마다 한 칸, 상하좌우로 움직일 수 있다.시작점은 현재 위치 2이며, 어떤 음식에 가장 빠르게 도착하는지 구한다."TAK"을 출력 후 음식까지의 최단 거리를 출력한다. 이 때 음식을 먹을 수 없다면 "NIE"를 출력한다. 풀이너비 우선 탐색을 이용했다. 범위 내에서 해당 위치를 방문하지 않았고, 이동한 위치가 2보다 클 때(해당 위치가 장애물이 아닌 음식이라면)"TAK"을 출력하고 최단 거리를 출력한다.해당 위치가 빈 복도라면 queue에 ..