본문 바로가기

Algorithm

 (252)
[백준] 1389 : 케빈 베이컨의 6단계 법칙 python n개의 정점에 대해 bfs를 수행할 때마다 num이라는 배열에 연관된 정점사이의 거리를 기록하고, num의 총합을 result라는 리스트에 append해준다. 1-3, 3-2, 2-4, 4-5이렇게 연결되어있을 때 1번을 시작 정점으로 bfs를 수행하면서 1번의 인접정점인 3,4의 거리가 1이라는 것을 num[3], num[4]에 기록해준다. 그리고 3번을 시작 정점으로 다시 bfs를 수행할 때 3번의 인접 정점인 2번자리 num[2]에는 num[3]+1을 저장하는 방식으로 하면 1번과 연관이 있는 각 정점간의 거리를 알 수 있다. import sys from collections import deque input = sys.stdin.readline n,m = map(int,input().split()..
[백준] 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..

티스토리툴바