분류 전체보기

from collections import deque def bfs(x,y): q.append((x, y)) # 큐에 현재 좌표 추가 dx = [-1, 0, 1, 0] # 움직일 방향 dy = [0, 1, 0, -1] visited[x][y] = 1 # 현재 위치 기준. while q: # 큐가 비지 않았다면 x, y = q.popleft() # 첫번째값을 가져옴. for d in range(4): # 4방향으로 이동 nx = x + dx[d] ny = y + dy[d] # x, y가 범위를 벗어나지 않고, 같은 색이고, 아직 방문하지 않은 경우 if 0

# 뿅망치에 맞은 경우 키가 반으로 줄어듬. 1인 경우 제외. # 매번 가장 큰 수를 줄인다. => 최대값을 찾아야 함. 최대 힙 사용. # t번 망치를 사용했을때 모든 값이 센티의 키보다 작다면 yes, 뿅망치 최소 사용 횟수 작성 # 모든 횟수를 다 써도 안되면 no, 최대값 출력 from heapq import * import sys n, h, t = map(int, input().split()) titan_h = [-int(sys.stdin.readline()) for _ in range(n)] # 최대힙 사용을 위해 음수로 바꿔줌 heapify(titan_h) cnt = 0 for i in range(t): if -titan_h[0] == 1 or -titan_h[0] < h: # 만약 거인들의..

# 스택 구현 # 가장 높은 기둥을 찾아 일차원 리스트에 추가하는데 인덱스는 가로점으로, 인덱스의 값은 높이로 저장함 # 0부터 최대 가로길이까지 반복문을 나눠서 돈다. 왼쪽 ~ 최대높이 / 오른쪽 ~ 최대높이 높이를 계속 더해준다. n = int(input()) info = [0] * 1001 # 좌표마다 높이를 넣어줄 배열을 생성. n이 1이상 1000이하이므로 거기에 맞게 만들어줌 max_height = 0 # 기둥의 최대 높이 max_height_idx = 0 # 제일 높은 기둥의 인덱스 end_idx = 0 # 끝 인덱스 # 제일 높은 기둥 찾기 for i in range(n): w, h = map(int, input().split()) # 좌표값, 높이 info[w] = h # 가로를 인덱스로..

# 평균, 중앙값, 최빈값, 범위 리턴 # 평균 - n개수의 합 // n import sys n = int(input()) nums = sorted(int(sys.stdin.readline()) for _ in range(n)) avg = round(sum(nums) / n) # 평균 mid = nums[len(nums) // 2] # 중앙값 range = nums[-1] - nums[0] # 범위 mode_dict = {} # 최빈값 담을 딕셔너리 for i in nums: # 요소별 빈도수 저장 if i in mode_dict: mode_dict[i] += 1 else: mode_dict[i] = 1 # 최빈값에 해당하는 요소들만 필터링 mode = list(filter(lambda x: mode_d..

import math def get_winning_rate(x, y): return (y * 100) // x x, y = map(int, input().split()) z = get_winning_rate(x, y) # 승률. 구할때는 소수점 버림 start, end = 1, x result = 0 if z >= 99: print(-1) else: while start z: # 승률이 변했을경우. 변하는 경우중에 최소값을 찾아야하기때문에 왼쪽범위 탐색 end = mid - 1 result = mid else: # 승률이 계속 같다면 게임을 더 해야함. 오른쪽 범위 탐색 start = mid + 1 print(result) 게임 플레이 횟수와 게임을 이긴 수가 주어졌을때, 최소 몇게임을 더 해야 승률이 ..

그래프 탐색 - DFS / BFS 1. 깊이 우선 탐색 (DFS) 시작 정점에서 탐색 가능한 최대 깊이의 정점까지 탐색하는 방법. 최대 깊이까지 도달했다면 방문한 정점들을 역순으로 재방문하며 탐색 가능한 정점이 있는지 확인한다. 탐색 가능한 정점이 있다면 해당 정점부터 다시 최대 깊이 정점까지 탐색을 진행한다. 스택 또는 재귀로 구현할 수 있다. 아래 그림의 그래프를 DFS로 탐색하는 과정은 다음과 같다. 1번 노드에서 탐색을 시작한다. 스택에 1번 노드를 삽입한다. ([1]) 1번에서 탐색 가능한 노드는 2번과 4번이 있다. 2번을 스택에 삽입한다. ([1, 2]) 2번에서 탐색 가능한 노드는 3번과 4번이 있다. 3번을 스택에 삽입한다.([1, 2, 3]) 3번에서 탐색 가능한 노드는 2번과 4번이 ..

1. 그래프(Graph) 1) 그래프의 구성 요소 정점(Node / Vertex) 특별한 하나의 객체 간선(Edge) 정점을 연결하는 선. 두 노드 간의 관계를 나타냄. 방향이나 비중을 나타낼수있음. 그래프(Graph) 정점과 간선의 집합으로 이루어진 구조. 2) 그래프 관련 용어 인접(adjacent) : 두 정점이 간선으로 연결되어 있는 경우 차수(degree) : 정점에 연결된 간선의 수 진입 차수(in-degree) : 해당 정점으로 향하는 간선의 수 진출 차수(out-degree) : 해당 정점에서 나가는 간선의 수 경로(path) : 한 정점에서 다른 정점으로 이어지는 정점들의 리스트 경로 길이(path length) : 경로를 구성하는 간선의 수 단순 경로(simple path) : 모두 다..

# 이진탐색 # 가장 인접한 두 공유기 사이의 거리를 최대로 하는 # 공유기의 거리를 이진탐색으로 찾는다. # 설정한 공유기의 거리를 통해 공유기를 몇대 설치할 수 있는지 확인 import sys n, c = map(int, input().split()) x = sorted(int(sys.stdin.readline()) for _ in range(n)) # 이진탐색을 위해 오름차순 정렬 start = 1 # 시작지점 end = x[-1] - x[0] # 최대 거리 result = 0 # 결과값 while start = current + mid: # 다음 좌표가 현재 좌표 + 중간값과 같거나 크다면 = 공유기 거리의 최대값 + 위치보다 크다면 count += 1 # 공유기 설치 current = x[i] ..

# 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액 찾기 # x + y가 0에 가장 가까운 수가 되는 두개의 수 찾기. 오름차순 정렬. # 0에 가장 가까운 수를 만들어내는 방법? => 절대값이 비슷한 음수와 양수를 합치기 # 투포인터 문제. 배열을 정렬한 후 양쪽 끝에서부터 비교 n = int(input()) liquid = list(map(int, input().split())) # 용액들의 리스트 liquid.sort() # 오름차순 정렬 left = 0 # 포인터. 왼쪽 끝에 위치 right = n-1 # 포인터. 오른쪽 끝에 위치. result = abs(liquid[left] + liquid[right]) # 초기값은 첫값과 마지막 값의 합의 절댓값 final ..

# 이분탐색 # 심사대 n개 사람수 m명 시간 t # 탐색 범위는 심사에 걸리는 시간. t의 최소값 / 최대값 * 인원수 import sys n, m = map(int, input().split()) t = [int(sys.stdin.readline()) for _ in range(n)] start, end = min(t), max(t) * m result = end # 탐색을 진행하며 더 작은 값을 찾아가기때문에 현재 최대값으로 초기화해줌 while start = m: # 만약 심사할수있는 사람이 m보다 크다면 = 탐색할 범위의 값을 줄여야함 end = mid - 1 result = mid # 중간값을 결과에 갱신 else: # 심사할 수 있는 사람이 m보다 작다면 = 탐색 범위의 값을 늘려야함 sta..