본문 바로가기

분류 전체보기

 (261)
[백준] 2606 : 바이러스 python 1번 컴퓨터와 자기 사이에 아무리 많은 컴퓨터가 있더라도 연결되어있다면 무조건 바이러스에 걸린다. 따라서 1번 노드에서 BFS를 수행하면서 1번과 연결된 컴퓨터의 개수를 세주면 된다. 1. 컴퓨터의 수 n을 입력받는다. 2. 간선의 수 m을 입력받는다. 3. m줄에 걸쳐 그래프의 연결 정보를 입력받고 graph라는 2차원 리스트에 저장한다. 4. 해당 정점을 방문했는지 확인하는 visited 리스트를 만들고 0으로 초기화한다. 방문할 때마다 1로 바꿔주면, BFS를 수행한 뒤에 visited 리스트의 총합-1을 했을 때 1번과 연결된 컴퓨터의 개수를 알 수 있다. 5. dfs 함수를 작성한다. 6. 1번 컴퓨터에서 dfs함수를 수행하고 연결된 컴퓨터의 개수를 출력한다. import sys input = ..
[백준] 2178 : 미로 탐색 python BFS를 수행하면서 각 위치마다 거리를 적어두는 식으로 해결하면 되는 문제다. from collections import deque n,m = map(int,input().split()) graph = [[]for i in range(n)] for i in range(n): data = input() for c in data[:]: graph[i].append(int(c)) dx = [-1,1,0,0] dy = [0,0,-1,1] def bfs(x,y): queue = deque() queue.append((x,y)) while queue: x,y = queue.popleft() for i in range(4): nx = x+dx[i] ny = y+dy[i] if nx=m: continue if grap..
[백준] 1260 : DFS와 BFS python 제목 그대로 DFS와 BFS를 수행한 결과를 출력하면 되는 문제인데, 인접정점이 오름차순으로 입력되지 않기 때문에 입력을 받은 후에 정렬을 한 번 해줘야 한다. from collections import deque n,m,v = map(int,input().split()) graph = [[]for i in range(n+1)] visited = [False]*(n+1) for i in range(m): s,e = map(int,input().split()) graph[s].append(e) graph[e].append(s) for i in range(n+1): graph[i].sort() def dfs(graph, v, visited): visited[v] = True print(v,end=' ') f..
[백준] 2798 : 블랙잭 python n,m = map(int,input().split()) data = list(map(int,input().split())) res = 0 tmp = 0 for i in range(n-2): for j in range(i+1,n-1): for k in range(j+1,n): tmp = data[i]+data[j]+data[k] if tmp>=res and tmp
[백준] 11286 : 절댓값 힙 python 이전에 풀었던 최댓값 힙 문제에서 최대 힙을 만들기 위해 아래와 같은 방식으로 힙에 숫자를 추가했었다. heapq.heappush(h,(-item,item)) 이렇게 튜플 형식으로 값을 추가하면 튜플의 첫 번째 원소인 -item의 오름차순으로 정렬되기 때문인데, 이 문제에서는 절댓값의 오름차순으로 정렬을 해야 하니 heapq.heappush(h,(절댓값,원래값))의 형식으로 값을 추가하면 되겠다는 생각이 들었다. 1. n을 입력받는다. 2. 우선순위 큐가 될 리스트 h를 생성한다. 3. n번에 걸쳐 x를 입력받는다. 3-1. x가 0일 때 3-1-1. h에 아무것도 없으면 0을 출력한다. 3-1-2. 절댓값이 가장 작은 값을 출력하고 제거한다. 3-2. x가 0이 아니면 우선순위 큐에 (abs(x),x)..
[백준] 13305 : 주유소 python 저렴한 기름값으로 최대한 멀리 가야 하는 문제이다. 일단 현재 도시의 기름값으로 다음 도시까지 가는 데에 필요한 기름을 사고, 다음 도시의 기름값이 더 저렴할 때에만 기름값을 업데이트하면 된다. 1. n을 입력받는다. 2. 다음 도시까지의 거리를 순서대로 dist라는 list에 저장한다. 3. 각 도시의 기름값을 oil이라는 list에 저장한다. 4. 현재 기름가격인 price에 첫 번째 도시의 기름값(oil[0])을 저장한다. 5. 총 금액인 total을 0으로 초기화한다. 6. 1번 인덱스부터 총 금액에 기름값과 다음 도시까지의 거리를 곱한 값을 더한다. 7. 만약 다음 기름값이 더 싸다면 price를 업데이트 한다. n=int(input()) dist = list(map(int,input().spl..
[백준] 11399 : ATM python 1. n을 입력받는다 2. 인출하는 데에 걸리는 시간을 list에 저장한다. 3. list를 정렬한다. 4. 한 사람이 ATM을 사용할 때마다 앞 사람들이 인출하는 데에 걸린 시간을 더해 tmp를 계산하고, 총합인 sum에 더해준다. 5. sum을 출력한다. n = int(input()) time = list(map(int,input().split())) time.sort() tmp = 0 sum = 0 for i in range(n): for j in range(i+1): tmp += time[j] sum += tmp print(tmp) 이중반복문을 쓰는 것이 그다지 효율적인 방법은 아닌 것 같아 다른 사람들의 풀이도 찾아보았다. 아래는 enumerate()를 사용한 코드이다. N = int(input..
[백준] 1931 : 회의실 배정 python 1. N을 입력받는다. 2. 시작시간과 종료시간을 저장할 list인 data를 생성한다. 3. data에 (시작시간, 종료시간)의 형태로 회의시간을 저장한다. 4. data를 회의의 종료시간을 기준으로 오름차순 정렬한다. 5. 회의의 개수를 저장할 cnt를 0으로 초기화한다. 6. 회의의 종료시간을 저장하는 변수 end에 data[0][1]을 저장한다.(가장 빨리 끝나는 회의의 종료시간) 7. 가능한 회의의 개수를 센다. 7-1. 현재 회의의 종료시간

티스토리툴바