본문 바로가기

Algorithms & Languages

 (78)
[Python/DailyAlgo, 백준] 92. 우선순위 큐, 11279. 최대 힙, 11286. 절댓값 힙 문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.문제 유형 보기더보기힙https://dailyalgo.kr/ko/problems/92https://www.acmicpc.net/problem/11279https://www.acmicpc.net/problem/11286풀이92. 우선순위 큐더보기from heapq import heappop, heappushdef solution(queries): heap = [] answer = [] for query in queries: # pop if query == 0: # answer.append(heappop(heap) if heap else 0) ..
[Python/백준] 1068. 트리 문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.문제 유형 보기더보기더보기트리 + dfs or 트리 + 순회https://www.acmicpc.net/problem/1068풀이1차 시도) 실패테케는 다 맞았는데… 더 고민해보자.import sysinput = sys.stdin.readline# 노드 하나 지운 이후의 트리의 리프 노드 개수를 구하라.# 노드를 지우면 그 노드에 딸린 서브트리가 통째로 지워짐.# 입력 : 노드 개수, 0~n-1번 노드까지의 각 노드의 부모, 지울 노드의 번호# 출력 : 처리 이후 리프 노드의 개수# 흠... 이거 오름차순으로 주나?# 일단, 결국 그 노드를 기준으로 후위 순회 돌리면 되겠는데?# 후위 순회의 action은, 자신의..
[Python/백준] 20364. 부동산 다툼 문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.문제 유형 보기더보기이진 트리https://www.acmicpc.net/problem/20364풀이1차 풀이, 실패import sysinput = sys.stdin.readline# 이진 트리# 루트 땅은 1번# 방 번호는 그냥 완전 이진 트리 인덱스대로임.# 오리들이 1번 땅에서 출발할건데,# 입력 : 땅 개수 n, 오리 수 Q# N 100만# 2번째 줄부터 Q개의 줄 동안 i줄에 i번째 오리가 원하는 땅 번호 xi# 출력 : Q개의 줄을 출력할건데, 갈 수 있으면 0, 못 가면 처음 마주치는 점유된 땅 번호.# 이거 dfs + 백트래킹 쓰면 될 것 같은데? => 안됨. q*O(V + E) 시간 터짐.# 원하는..
[Python/백준] 1991. 트리 순회 문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.문제 유형 보기더보기이진 트리의 순회https://www.acmicpc.net/problem/1991풀이유니코드 풀이import sysinput = sys.stdin.readline# 입력 : 첫째 줄) 노드 개수# 둘째 줄부터) N개 줄에 걸쳐 노드 이름, 레프트 자식 노드, 라이트 자식 노드 이름# 각 노트 이름은 'A', 'B', ..., 'Z' 까지.# 자식 노드가 없는 경우는 .으로 표기함.def ord_minus_ord(x): return ord(x) - ord('A')def chr_plus_ord(x): return chr(x + ord('A'))def preorder(node): #..
[Python/DailyAlgo] 94, 95, 96. 트리 전위, 중위, 후위 순회 문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.문제 유형 보기더보기이진 트리의 순회https://dailyalgo.kr/ko/problems/94https://dailyalgo.kr/ko/problems/95https://dailyalgo.kr/ko/problems/96풀이트리 전위 순회def solution(childNodes): def preorder(node): # 종료 조건 if node == -1: return # 점화식 answer.append(node) preorder(childNodes[node-1][0]) preorder(childNodes[n..
[알고리즘 코딩캠프 7일차] 트리, 이진 트리, 이진 트리의 순회, 힙, 우선순위 큐 제가 재학 중인 대학교에서 열린 파이썬 알고리즘 코딩캠프(25.02.03 ~ 25.02.14) 수업을 듣고 정리한 글입니다.목차 :트리, 이진 트리이진 트리의 순회힙, 우선순위 큐트리, 이진 트리더보기트리는 ‘사이클이 없는 무방향 그래프’를 의미하며, 계층형 자료구조를 가짐.이진 트리 : 노드의 차수가 최대 2인 트리 트리 및 이진 트리에 대한 자세한 건 자료구조 때 공부했던 거 참고.트리는 다양한 표현 방식이 있으나, 이진 트리의 경우는 차수 최대 제한이 있으니,각 노드에 대해 left, right 두 가지를 가지고 표현하는 게 가장 효율적. 백준 등에서 트리에 대한 입력은 보통 아래처럼 들어옴.0번은 보통 안 씀.L R이 둘다 -1면 리프 노드 ← 문풀에 많이 쓰는 정보. 1번부터 13번까지 총 13..
[Python/DailyAlgo] 112. N-Rook Problem 2 문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.문제 유형 보기더보기순열과 조합https://dailyalgo.kr/ko/problems/112풀이def solution(board): # 입력 : 각각의 칸에 숫자가 배정되어있는 행렬 board # 출력 : 룩을 여러가지 경우의 수로 놓을 수 있잖음? # 이 때의 룩들이 놓인 칸의 숫자 합이 최대인 경우를 반환 # 이거, max_score 변수 하나 둔 다음에, max(max_score, cur_score) 하면 되겠는데? # 그러면, 순열의 매개변수로 max_score 변수를 넣어주면 될듯? 직접 써먹을 거니까! # 그리고, max_score 초기값 0으로 하면 될듯 # ..
[Python/DailyAlgo] 97. N-Rook Problem 문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.문제 유형 보기더보기순열과 조합https://dailyalgo.kr/ko/problems/97풀이def solution(n):# 입력 : 체스판의 크기 n x n이자 룩의 개수인 n# 출력 : 조건에 맞게 n개의 룩을 배치 가능한 경우의 수# 조건 : n개의 룩은 체스판 위에서 공격 불가,# 행 번호와 열 번호가 같은 곳(i == j)에는 룩을 둘 수 없음.# 엥... 이거 사실상 순열조합 문젠데?# 01234 란 놈을 높이로 정해놓고,# 이걸 가로로 가지고 순열을 돌리면 될거같은데?# '높이'가 저 놈들을 unique하게 만들어주고, 따라서 중복 없이 순서를 고려해야 함.# 근데, numbers[index] ..

티스토리툴바