본문 바로가기

알고리즘

 (54)
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]..
2638. 치즈 치즈가 먹고싶다. bfs문제이다. 그래프 탐색문제는 뭔가 코테에서 만나면 아직 어렵게 느껴진다. 다 연습이 부족해서겠지. 이 문제는 바깥 공간과 접촉한 치즈만 녹는다. 이게 힌트이다. 그냥 무지성 bfs (0,0)에서 해주고, 그에 따라서 외부와 접촉한 치즈 (1 ) 을 1씩 증가시킨다. (접촉할 때마다) 즉 3이상이면 2번이상 접촉한거고 다음 반복에서 삭제하면 된다. import sys from collections import deque input = sys.stdin.readline n,m=map(int,input().split()) board = [list(map(int,input().split())) for _ in range(n)] dx,dy=[0,0,1,-1],[1,-1,0,0] ans = ..
13164. 행복 유치원 인접한 아이끼리만 같은 조가 될 수 있다는 조건을 꼭 읽어야한다. n명을 k개의 조로 나눌때 그 구간의 길이들 중에서 길이 간격이 가장 긴 k-1개를 제거한다. k-1개를 제거하면 k조가 나오니까! import sys input = sys.stdin.readline n,k = map(int,input().split()) heights = list(map(int,input().split())) costs = [] for i in range(n-1): costs.append(heights[i+1]-heights[i]) costs.sort() print(sum(costs[:n-k])) 아래는 javascript 풀이입니다. const inputs = require("fs").readFileSync("./dev..
9576. 책 나눠주기 오늘 코테를 봤는데 짧은 시간안에 문제를 더많이 풀려면 구현실력을 더 길러야 겠다는 생각을 했다..!! 째튼.. 이 책나눠주기 문제는 그리디 문제이다. 문제에서 주어진 a와 b의 범위중 b를 기준으로 정렬해야한다. -> 끝에가 가장 작은거 부터. 왜냐? 어짜피 a
9205. 맥주 마시면서 걸어가기 ⭐️ 맥주 마시면서 걸어가기 제목이 맘에 들어서 풀기 시작했다. bfs로 거리를 모두 탐색하는데 거리가1000이하면 큐에 넣는 방식으로 진행했다. -> 거리가 1000이하인곳 갈수만 있으면 맥주병 교체하는건 신경안써도된다. import sys from collections import deque input = sys.stdin.readline def bfs(): q = deque() q.append((home[0], home[1])) while q: y, x = q.popleft() if abs(y - fest[0]) + abs(x - fest[1])
2250. 트리의 높이와 너비 ⭐️ 트리의 높이와 너비 밑에 표시된 열을 방문 순서라고 생각하면 좋습니다. 그러면 중위순회라는 것을 알아낼 수 있습니다. import sys input = sys.stdin.readline n = int(input()) graph= [[] for _ in range(n+1)] isRoot = [0] * (n + 1) # 루트노드를 찾을 때 쓸 리스트 distance = [[] for _ in range(n+1)] # 각 레벨별 거리 저장 root = 0 for _ in range(n): parent, left, right = map(int, input().split()) graph[parent].append(left) graph[parent].append(right) isRoot[parent] += 1..
3584. 가장 가까운 공통 조상 문제의 중요한 점은 마지막에 주어지는 두 노드가 서로 부모가 될 수 있다는 점입니다. 그러니까 둘다 거슬러 올라갈 때 자기 자신도 포함해서 거슬러 올라가 줘야합니다. import sys T = int(sys.stdin.readline()) for _ in range(T): N=int(sys.stdin.readline()) p_list=[0 for _ in range(N+1)] for _ in range(N-1): p,c=map(int,sys.stdin.readline().split()) p_list[c]=p a,b=map(int,sys.stdin.readline().split()) a_parent=[a] b_parent=[b] while p_list[a]: a_parent.append(p_list[a])..
[Summer/Winter Coding(~2018)] 지형 편집 ⭐️ 지형 편집 문제를 처음 접했을 때 백준에서 풀어본 문제랑 거의 동일하다는 것을 느꼈습니다. 문제는 높이는 최소 1, 최대 300으로 제한하고 있습니다. 당연히 높이마다 탐색해서 최소값을 구하는 것 보다 최소 높이와 최대 높이를 정해서 이분탐색하는게 더 빠를 것 같습니다. def solution(land, P, Q): answer = 1e9 min_height = 1e9 max_height = 0 for i in range(len(land)): for j in range(len(land[0])): max_height = max(max_height, land[i][j]) min_height = min(min_height, land[i][j]) def find_value ( h, land): cnt =0..

티스토리툴바