본문 바로가기

알고리즘/백준

(22)
17299. 오등큰수 우선, n이 백만이여서 O(n2)으로 풀면 시간초과에 걸린다. 아래는 시간초과 풀이이다. import sys;input=sys.stdin.readline n = int(input()) a = list(map(int,input().split())) from collections import Counter c = Counter(a) most_common = c.most_common()[0][0] for i in range(n): if a[i] == most_common: print(-1, end=' ') continue for j in range(i+1, n): if c[a[j]] > c[a[i]]: print(a[j], end= ' ') break 리스트를 순회하면 안될 것 같다. 어떻게 하면 순회를 안하..
15681. 트리와 쿼리 트리에서의 동적계획법. 재귀 호출을 통해서 노드의 개수를 세줄 수 있다. import sys;input=sys.stdin.readline sys.setrecursionlimit(10**9) n,r,q=map(int,input().split()) tree = [[] for _ in range(n+1)] cnt = [0] * (n+1) def NodeCount(x): cnt[x] = 1 for i in tree[x]: if not cnt[i]: NodeCount(i) cnt[x] += cnt[i] for _ in range(n-1): u, v = map(int,input().split()) tree[u].append(v) tree[v].append(u) NodeCount(r) for i in range(q)..
2629. 양팔저울 구슬의 무게를 구하기 위해서는 두 양팔 저울무게의 차이를 구하면 된다. 쉽게 접근하면 추1번을 왼쪽에 올릴 수도, 오른쪽에 올릴 수도, 올리지 않을 수도 있다. 근데 추가 30개 까지 가능하다. 즉 3의 30승 = 205,891,132,094,649 에 해당하는 경우의 수를 가질 수 있다. 이러면 약간 불안하다. 따라서 경우의 수를 적게 만들거나 이미 계산한 것은 계산하지 않는 방식을 취해야한다. 왼쪽 오른쪽에 놓을수 있고 놓지 않을 수도 있다. -> 탐색. dfs를 생각하게 되었다. dfs의 리턴 조건에서 추의 개수가 다 차면 리턴하면 좋을 것 같았다. import sys;input=sys.stdin.readline n = int(input()) weights = list(map(int,input()...
1189. 컴백홈 우선 이 문제는 뜻깊은 문제이다. 백준에서 문제를 푼 개수가 600개가 되었다. 이문제는 그 600번째이다. 600개를 풀면서 드는 생각들은 회고로 적어 놓아야 겠다. 이문제는 dfs를 떠올릴 수 있는 구조이다. k의 거리로 이동한 것을 찾으니까 리턴조건은 당연히 거리가 k인것 + '그 위치에 도착했는가' 이다. 자스 풀이 const input = require("fs") .readFileSync("./dev/stdin") .toString() .trim() .split("\n") const [r, c, k] = input[0].split(" ") const dy = [-1, 0, 1, 0], dx = [0, 1, 0, -1] const visited = Array.from({ length: r }, (..
2468. 안전 영역 탐색만 하면 되니까 dfs bfs 모두 가능하다. 높이 보다 높으면 탐색 시작 점이 될 수 있고 그 시작점에서 그래프 탐색을 시작한다. JavaScript bfs const fs = require("fs") const input = fs.readFileSync("./dev/stdin").toString().trim().split("\n") const n = +input[0] const board = input.slice(1).map((e) => e.split(" ").map((e) => +e)) const max = Math.max(...board.flat()) let dx = [0, 0, 1, -1], dy = [1, -1, 0, 0] function bfs(x, y, h, visited) { cons..
1826. 연료 채우기 현재 연료로 갈 수 있는 거리에 포함되는 아이들을 heap에 넣는다. 그리고 연료가 가장 큰 아이를 택해서 p에 더해주고 cnt를 증가시킨다 -> 방문 import heapq n = int(input()) oil = [] for _ in range(n): oil.append(tuple(map(int, input().split()))) l, p = map(int, input().split()) oil.sort() hq,i,cnt = [],0,0 while p < l: while i < n and oil[i][0]
14500. 테트로미노 최근 코딩테스트에서 이 테트로미노와 비슷한 문제를 접했다. 백준에서 문제를 찾아보니 비슷한 문제들이 몇개 있어서 풀어보자! 탐색을 한다고 했을 때 처음 블록을 깊이 1 두번째 블록을 깊이 2라고해보자. 깊이 2에서는 탐색 방법 살짝 다르다. ㅗ 모양 같은 경우는 탐색하려면 아래와 같이 해야한다. 그냥 무작정 전진해버리면 ㅗ 모양은 탐색할 수 없다. N,M = map(int,input().split()) board = [list(map(int,input().split())) for _ in range(N)] ans = 0 dx,dy = [0,1,0,-1],[1,0,-1,0] visited = [[0]*M for _ in range(N)] max_value = max(map(max,board)) def df..
10159. 저울 문제에서 그래프를 한쪽 방향으로 그리게끔 유도. 모든 점에서 모든 점을 방문해야 비교결과를 알 수없는 물건 도출 가능 -> 플로이드 와샬을 유추 가능 자기 자신과 비교 안함 -> 마지막에 -1 const fs = require("fs") let input = fs.readFileSync("./dev/stdin").toString().trim().split("\n") let [n, m] = input const graph = Array.from({ length: +n + 1 }, () => Array.from({ length: +n + 1 }, () => 0) ) const edges = input.slice(2).map((x) => x.split(" ").map((x) => +x)) for ([a, b]..