Algorithm Problem

[python] 백준 - 21608. 상어 초등학교

🤔문제 해결 시뮬레이션 학생: *친구들 딕셔너리를 만든다. 문제의 크기가 크지 않기 때문에 이중 포문으로 교실 전체를 탐색 좋아하는 사람 옆자리와 빈자리 개수를 각각 체크해준다. 좋아하는 사람 옆자리 수 빈자리 수 순서로 체크해가며 큰 값을 업데이트 해준다. 인덱스가 작은 값부터 탐색하기 때문에 같다면 행번호, 열번호가 작은 자리가 선택되게 된다. 다 찾았으면 교실 전체를 돌며 만족도 조사 끝 💻소스 코드 import sys input = sys.stdin.readline def is_in(ix, iy, n): if 0 max_blank): # 1. 좋아하는 사람 옆자리, 2. 같으면 빈자리 max_blank = blank max_like = like loc = i, j x, y = loc classro..

[python] 백준 - 1347. 미로 만들기

🤔문제 해결 구현 좌표를 먼저 구하자. (0, 0) 에서 시작해서 제시된 행동대로 좌표로 담아준다. x좌표, y좌표 각각의 최소와 최대를 구한다. 모든 좌표들에 대해서 최소값을 더해준다. ( 음수가 나올 수 있기 때문에 양수로 바꿔주기 위해서 ) 최대 최소로 2차원 배열을 만들고, 구한 좌표로 길을 만들어준다. 💻소스 코드 import sys input = sys.stdin.readline N = int(input()) action = input().strip() # 0,0 부터 좌표 구하기 loc_list = [(0, 0)] dx, dy = [-1, 0, 1, 0], [0, 1, 0, -1] # 상 우 하 좌/ 북 동 남 서 status = 2 for a in action: if a == 'R': # ..

[python] 백준 - 12764. 싸지방에 간 준하

🤔문제 해결 우선순위 큐 대기중인 사람과 먼저 사용중인 사람 중 가장 빨리 끝나는 곳과 비교 대기중인 사람보다 늦게 끝나면 새로운 자리로 배정 기존의 사람이 끝나는 곳이 있으면 그게 여러 곳이 있으면 끝나는 곳을 다 뽑아서 남는 자리 우선순위 큐에 넣는다. 더 이상 없을 때 남는 자리 우선순위 큐에서 자리르 하나 뽑아서 배정한다. 사용중인 컴퓨터 끝나는 시간과 자리번호가 담긴 우선순위 큐 남아있는 자리가 담긴 우선순위 큐 이렇게 해서 두개를 사용했다. 우선순위 큐를 두개 써야해서 헷갈렸던 문제 💻소스 코드 import sys import heapq input = sys.stdin.readline N = int(input()) logs = [list(map(int, input().split())) for ..

[python] 백준 - 11085. 군사 이동

🤔문제 해결 크루스칼 C에서 출발! 갈 수 있는 곳을 찾아서 우선순위 큐에 넣는다. 우선순위 큐에서 넓이가 가장 넓은 녀석을 뽑는다. 거기서 또 갈 수 있는 곳을 찾아서 큐에 넣는다. (단, 재방문 X) V를 만나면 끝! 노드를 이동하는 동안 최소값을 계속 갱신해준다. (답을 찾아야하므로) 💻소스 코드 import sys from collections import defaultdict import heapq input = sys.stdin.readline P, W = map(int, input().split()) # P개의 지점, W개의 길 C, V = map(int, input().split()) # C 백준수도, V 큐브수도 # 인접노드 만들기 nodes = [input() for _ in range..

[python] 백준 - 19598. 최소 회의실 개수

🤔문제 해결 우선순위큐 회의를 오름차순으로 정렬한다. 사용한 회의실의 끝나는 시각을 배열로 만든다. 우선순위큐로 사용할 것 회의를 하나씩 꺼내서 가장 빨리 끝나는 회의실과 회의 시작 시간을 비교 회의 시작 시간이 더 빠르면 회의실 추가 회의 시작 시간이 더 늦으면 해당 회의실의 끝나는 시각 업데이트 🍞 heapreplace는 가장 작은 요소를 빼고, 추가할 요소를 집어 넣는다. ( pop 후 push 를 합친것 - 더 빠르다고 한다.) 💻소스 코드 import sys import heapq input = sys.stdin.readline N = int(input()) meetings = [list(map(int, input().split())) for _ in range(N)] meetings.sort(..

[python] 백준 - 1013. Contact

🤔문제 해결 정규표현식 정규표현식 문제인줄 모르고 열심히 풀었는데.... 하🤣 💥 match 를 쓰면 포함되어있는걸 찾기 때문에 fullmatch 를 써서 전체가 맞는 지 확인해줘야한다. match로도 맞는 구간이 나오기 때문에 답을 찾을 순 있지만 fullmatch가 있기 때문에 저걸로 찾으면 된다. 💻소스 코드 import re import sys input = sys.stdin.readline for tc in range(int(input())): p = re.compile('(100+1+|01)+') # 정규표현식 준비 m = p.fullmatch(input().strip()) # 매칭 print('YES') if m else print('NO') 📕문제 확인 출처: BACKJOON ONLINE ..