본문 바로가기

알고리즘/백준

 (22)
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])..

티스토리툴바