분류 전체보기 검색 결과
281 개의 검색 결과가 있습니다.
코딩/백준 (Python)

백준 1005번: ACM Craft (Python)

접근 위상정렬에 DP를 더한 문제였는데 둘다 기본적인 수준으로만 섞여있어서 간단한 문제였다. 위상 정렬 기본 문제: 2021.06.20 - [코딩/백준 (Python)] - 백준 2252번: 줄 세우기 (Python) 백준 2252번: 줄 세우기 (Python) 접근 위상 정렬에 대한 공부를 하고 나서 풀었다. 위상 정렬은 사이클이 없고, 방향만 존재하는 그래프에서 정점들을 나열하는 방법이다. 학생들의 순서를 앞 학생에서 뒤 학생으로 연결된 한개 ca.ramel.be 기본적인 위상 정렬 알고리즘에 DP를 새로 작성해주되, DP[i] 는 i 를 완성하기까지 필요한 시간을 갱신하면서 저장해주면 된다. 코드 import sys from collections import deque t = int(sys.stdi..

2021. 6. 23. 22:23
코딩/백준 (Python)

백준 3665번: 최종 순위 (Python)

접근 위상 정렬 문제였고, 처음에 많이 헤메었지만 바뀐 순위들만 생각하는 것이 아니라 처음에 주어진 순위를 모두 어떤 처리를 해서 같이 계산해주어야 된다고 생각의 방향을 바꾸고 나서는 쉽게 해결이 되었다. 위상 정렬 기본 문제: 2021.06.20 - [코딩/백준 (Python)] - 백준 2252번: 줄 세우기 (Python) 백준 2252번: 줄 세우기 (Python) 접근 위상 정렬에 대한 공부를 하고 나서 풀었다. 위상 정렬은 사이클이 없고, 방향만 존재하는 그래프에서 정점들을 나열하는 방법이다. 학생들의 순서를 앞 학생에서 뒤 학생으로 연결된 한개 ca.ramel.be 1 2 3 4 5 다섯개의 팀이 각각 1 2 3 4 5 의 순위를 가지고 있을 때, 1 -> 2 2 -> 3 3 -> 4 4 -..

2021. 6. 22. 22:58
코딩/백준 (Python)

백준 2252번: 줄 세우기 (Python)

접근 위상 정렬에 대한 공부를 하고 나서 풀었다. 위상 정렬은 사이클이 없고, 방향만 존재하는 그래프에서 정점들을 나열하는 방법이다. 학생들의 순서를 앞 학생에서 뒤 학생으로 연결된 한개의 방향 화살표라고 할 때, 뒤 학생에는 진입루트가 한개 증가한 것이다. 주어진 비교 측정들을 모두 확인하여 뒤에 있는 학생들의 진입루트를 한개씩 더해주고 나서 보았을 때, 진입루트가 없는 학생은 가장 앞에 서게 될 것이다. 따라서 진입 루트가 0인 학생들을 모두 queue에 넣고 해당 학생들과 연결된 학생들의 진입루트를 한개씩 없애준다. 이 과정에서 진입 루트가 0이 된 학생은 추가로 queue에 넣어주게 된다. 진입 루트가 0이 되었다는 말은 앞선 학생들이 빠지고 난 상황에서 가장 앞에 있다는 의미이기 때문이다. 코드..

2021. 6. 20. 18:18
코딩/백준 (Python)

백준 5670번: 휴대폰 자판 (Python, PyPy3)

접근 트라이를 이용하여 풀었다. 트라이를 생성하여 입력받는 문자열들을 트라이에 저장해주고, 나중에 평균을 구해주기 위해 문자열을 저장할 때, 해당 string 이 몇번 사용되었는지 각 노드에 저장하는 식을 추가해주었다. 평균을 구할 때에는 해당 노드의 자식 수에 따라서 자식이 한개일 경우 카운트하지 않고, 자식이 있을 경우 각 자식이 몇번 쓰이는지를 체크하여 모두 더해주었다. 더해진 모든 수를 총 단어 수로 나누면 평균 입력 수를 구할 수 있었다. Python 으로는 50% 시간 초과 발생하여 PyPy3으로 문제 해결하였다. 트라이 기본 문제: 2021.06.19 - [코딩/백준 (Python)] - 백준 14725번: 개미굴 (Python) 코드 import sys from collections imp..

2021. 6. 20. 15:51
코딩/백준 (Python)

백준 14425번: 문자열 집합 (Python, PyPy3)

접근 트라이에 insert, search 함수를 구성하여 문제를 풀 수 있었다. 코드 import sys class Node: def __init__(self, key): self.key = key self.children = dict() class Trie: def __init__(self): self.head = Node(None) def insert(self, string): curr_node = self.head for char in string: if char not in curr_node.children: curr_node.children[char] = Node(char) curr_node = curr_node.children[char] def search(self, string): curr_..

2021. 6. 19. 23:58
코딩/백준 (Python)

백준 14725번: 개미굴 (Python)

접근 처음에는 트라이가 무엇인지 모르고 풀었고, 이후에 트라이에 대해 공부하고 다른 분의 코드도 참고하여 트라이를 이용하여 풀었다. 첫번째 풀이는 모든 리스트를 저장 및 sort 한 후, 이전 문자열과 동일한 문자가 몇번 나오는지 체크하여 중복되지 않는 부분부터 결과를 출력하도록 코딩하였다. 트라이를 이용한 방법은 Node 에 자식 노드들을 저장하여 점점 내려가면서 자식들을 순서대로 표시하는 방법이다. 코드1 트라이를 사용하지 않은 코드 import sys n = int(sys.stdin.readline()) array = [] for _ in range(n): tmp = list(sys.stdin.readline().split()) array.append(tmp[1:]) array.sort() for ..

2021. 6. 19. 23:09
반응형