코테 준비
-
[백준] 9663. N-QUEEN (N-QUEEN 알고리즘) -백트래킹코테 준비/완전탐색 2023. 2. 3. 00:42
퀸(Queen)은 상하좌우, 대각선으로 칸수에 관계없이 움직일 수 있다. 크기가 N x N 인 체스판 위에 퀸 N 개가 서로를 공격 할 수 없게 놓는 경우의 수를 구하는 문제 확인해봐야할 것 1. 상하좌우 대각선에 이미 위치한 퀸(Queen)이 있는가? 2-1. 있으면 퀸을 놓을 수 없음 2-2. 없으면 퀸을 놓을 수 있음 count+1 python으로는 도저히 통과가 안되서 pypy3로 제출했다... # 1. 상하좌우 대각선에 이미 위치한 퀸(Queen)이 있는가? # 2-1. 있으면 퀸을 놓을 수 없음 # 2-2. 없으면 퀸을 놓을 수 있음 count+1 퀸이 n개가 되면 break # 브루투포스, 백트래킹: DFS 보다 효율적 # col[1]=2: 1행 2열에 퀸이 있음이라는 뜻 import sys..
-
[백준] 11403. 경로찾기 (bfs)코테 준비/DFS, BFS 2023. 2. 2. 04:23
풀이1. BFS (시간 가장 빠름) from collections import deque def bfs(graph,start,visited): #bfs queue=deque([start]) queue.append(start) while queue: v=queue.popleft() for i in range(n): if graph[v][i]==1 and not visited[i]: queue.append(i) visited[i]=True result[start][i]=1 #result[0][i]=1, result[1][i]=1... n=int(input()) graph=[[0]*n for _ in range(n)] result=[[0]*n for _ in range(n)] #정답 인접행렬 for i in ..
-
[백준] 7576. 토마토 (DFS)코테 준비/DFS, BFS 2023. 1. 31. 03:13
from collections import deque dx=[-1,1,0,0] dy=[0,0,-1,1] def dfs(graph): queue=deque() for i in range(n): for j in range(m): if graph[i][j]==1: #그래프를 모두 탐색하여 1인 좌표들을 모두 queue에 넣는다 queue.append((i,j)) while queue: x,y=queue.popleft() for i in range(4): nx=x+dx[i] ny=y+dy[i] if nx=m: continue if graph[nx][ny]==0: #주변 좌표가 0이면 graph[nx][ny]=graph[x][y]+1 #이전 좌표에+1 queue.append((nx,ny)) m,n=map(int,..
-
[백준] 1931. 회의실 배정코테 준비/Greedy 2023. 1. 30. 04:03
회의종료시간이 빠른 순서대로 / 그다음 회의 시작 시간이 빠른 순서대로 sort해준다. (처음에는 key=lambda(x[0],x[1]-x[0])으로 했었는데 종료시간을 먼저 기준으로 해줘야한다.) 그 다음 종료 시간이 그 다음 시작 시간보다 작으면 count하면 된다! n=int(input()) meeting=[] for i in range(n): start,end=map(int,input().split()) meeting.append((start,end)) meeting.sort(key=lambda x:(x[1],x[0])) connect=0 count=0 for a,b in meeting: if a>=connect: connect=b count+=1 print(count)
-
[백준] 11497. 통나무 건너뛰기코테 준비/Greedy 2023. 1. 27. 22:55
가장 큰 숫자를 중간에 두고 왼쪽 오른쪽 번갈아가면서 다음 큰수를 배치하게 되면 결국 두 수의 차는 인덱스가 2씩 차이나게 됨 t=int(input()) for i in range(t): n=int(input()) L=list(map(int,input().split())) L.sort() #10 11 11 12 12 13 / 2 4 5 7 9 result=0 for j in range(2,n): l=L[j]-L[j-2] #1 1 1 1 / 3 3 4 result=max(l,result) print(result)